Check whether set of strings is prefix-free via lexicographic sort?

Question

I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So {a, b} is prefix-free (has the prefix property) while {a, b, ba} is not prefix-free (lacks the prefix property) because the entire string b is a prefix of ba.

One can of course implement this with a double-loop for quadratic performance. In JavaScript (so you can pop open your browser’s JS Console and try it, if so inclined):

function isPrefixCode(strings) {
  for (const i of strings) {
    for (const j of strings) {
      if (j === i) {
        continue;
      }
      if (i.startsWith(j)) {
        return false;
      }
    }
  }
  return true;
}
isPrefixCode(new Set('a b c'.split(' '))) // true
isPrefixCode(new Set('ba b c'.split(' '))) // false

I think one can do better by sorting the set of strings lexicographically ($N \log N$), then comparing each element to its previous one (linear). So:

function isPrefixCodeLinear(strings) {
  strings = Array.from(strings).sort();
  for (const [i, s] of strings.entries()) {
    if (i === 0) {
      continue;
    }
    const prev = strings[i - 1];
    if (s.startsWith(prev)) {
      return false;
    };
  }
  return true;
}
isPrefixCodeLinear(new Set('a b c'.split(' '))) // true
isPrefixCodeLinear(new Set('ba b c'.split(' '))) // false

This linearithmic algorithm seems to work for the tests I’ve come up with (and ~100x speedup over the quadratic double-loop algorithm on a 1000-string example), but I’d like to ask

1. if this approach based on lexicographic sorting is guaranteed to work,
2. if this approach has a name, and
3. if the prefix property has a more common term in computer science, or
4. if there are other algorithms that can solve it.

(I found this question on StackOverflow, about finding whether any entry in a set of strings is prefixed by a specific given string, How to search whether a string is a prefix of strings stored in a set?, which is a related problem to mine, but here I want to consider not just any one string but all the strings in the set.)

Answer 1

1. Yes. The common prefix is maximal with the closest predecessor (if you're treating the empty string as less than any other, which you are). Edit: in general if a prefix key exists it will be the immediate predecessor or there will be another key in between which shares the same prefix, and your test will fail on that. eg ABC, ABCD, ABCE will fail on the first pair even though the last key also contains ABC and is non-consecutive. The LCP is indeed maximal with the closest predecessor neighbor, but that predecessor neighbor may not be a prefix; I just wanted to clarify that.

2. There are situations where the longest common prefix is useful; in particular to augment a suffix array, which is a sorted list of suffixes. Look up LCP Array. The LCP+1 (roughly) is called the distinguishing prefix; string sorting algos express their complexity in terms of O(n log n + D), where D is the sum of all the distinguishing prefixes of all the keys. So it's a familiar idea.

3. "Prefix free" is the term that I remember.

4. You can put them in a trie and look for strings that end on an intermediate node. It's a variant of sorting.

Answer 2

I had to solve this problem recently. Here's the Python implementation I came up with, which includes a (rough) proof using a mixture of Python and mathematical notation:

def is_prefix_free(values: Iterable[str]) -> bool:
    '''determine if a list of strings is prefix-free
       (i.e., no element of 'values' is a prefix of any other)

    Args:
        values: any iterable of strings
    Returns:
        True iff there is no solution (i, j) to the following
        statements:

            values[i].startswith(values[j])
            i >= 0
            j >= 0
            i != j


    Approach:

        We sort 'values' and examine adjacent pairs: once sorted, iff
        'svalues[i]' is a prefix of 'svalues[j]' (i != j), then there
        must exist an adjecent pair of 'svalues[k], svalues[k+1]' s.t.
        'svalues[k]' is a prefix of 'svalues[k+1]'.

    Rough proof of validity for this approach:

        Let s := svalues (as defined in 'Approach'; for brevity).

        The approach assumes that the list is prefix-free IFF the sorted
        list is pairwise prefix-free. We can validate this by showing
        that each condition implies the other.

        It's trivial to demonstrate that presence of an adjecent prefix
        pair in the sorted list implies the presence of an
        (unrestricted) prefix pair in the unsorted list, as these lists
        contain the same elements.

        The rest of this proof focuses on proving the converse: that
        the presence of an (unrestricted) prefix pair in the unsorted
        list implies presence of an adjecent prefix pair in the sorted
        list.

        Per the problem, we assume:

            i != j                                                  [0]

        Suppose the assumptions given in 'Approach' are untrue,
                i.e.,:
            s[j].startswith(s[i]), but                              [1]
            ∄k | s[k+1].startswith(s[k])                            [2]
        We show that this leads to contradictions in all cases.

        ∀ a,b: s[a] < s[b] => a < b                                 [3]

        If s[i] = s[j]: contradiction!                              [4]

            i != j  (per [0])

            i < j                                                   [5]
                We may assume this is without loss of generality:
                we may swap i and j if necessary to ensure this
                condition without violating any earlier
                assumption.

            j != i+1                                                [6]
                Suppose j = i+1
                    s[i] = s[j]  (per [4])
                =>  s[i] = s[i+1]
                =>  contradiction! (k=i, per[2])

            i < i+1 < j                                             [7]
                    i < i+1  (trivial algebraic proof)
                    i < j  (per [5])
                    j != i+1  (per[6])
                    (no value exists between i, i+1)

            s[i] = s[i+1] = s[j]  (per [3], [4], [7])               [8]

            contradiction! (k=i, per[2])
                s[i+1].startswith(s[i])
                    s[i] = s[i+1]  (per [8])
                    ∀ v: v.startswith(v)  (trivial proof)

        Otherwise: contradiction!                                   [9]

            i < i+1 < j, and                                        [10]
            s[i] < s[i+1] < s[j]                                    [11]

                i < j                                               [12]
                    i != j  (per [0])
                    Suppose: j < i                                  [13]
                            s[j] ≤ s[i]  (per [3])                  [14]
                            s[i] ≤ s[j]  (per [1], [A1])            [15]
                            s[i] = s[j]  (per [14], [15])
                         => contradiction!  (per [9])

                s[i] != s[i+1]                                      [16]
                    otherwise: contradiction! (with k=i, per[2])

                i+1 != j                                            [17]
                s[i+1] != s[j]                                      [18]
                        s[j].startswith(s[i])  (per [1])            [19]
                        not s[i+1].startswith(s[i])  (per [2])      [20]
                     => s[i+1], s[j] are distinct values            [21]
                                (per [19], [20])
                     => i+1 != j  (per [21], [A2])

                i < i+1                                             [22]
                    (simple algebraic proof)

                i+1 < j                                             [23]
                    i+1 != j  (per [17])
                    i < j  (per [12])
                    (no value exists between i, i+1)

                s[i] < s[i+1]  (per [3], [16], [22])                [24]

                s[i+1] < s[j]                                       [25]
                    i+1 < j  (per [23])
                    s[i+1] != s[j]  (per [18])
                    (per [3])

            ∃ p ≥ 0 s.t. s[i][:p] = s[i+1][:p], and                 [26]
            s[i][p] != s[i+1][p]                                    [27]
                otherwise, one of the following would be true:
                    s[i+1].startswith(s[i])  (contradicts [2])
                    s[i].startswith(s[i+1])
                            (contradicts [3] given [A1])

            p < len(s[i])                                           [28]
                (otherwise s[i][p] would be undefined in [26])

            s[i][p] < s[i+1][p]                                     [29]
                s[i][:p] = s[i+1][:p]  (per [26])
                s[i][p] != s[i+1][p]  (per [27])
                (per [3])

            s[i][:p] = s[j][:p], and                                [30]
            s[i][p] = s[j][p]                                       [31]
                p < len(s[i])  (per [28])
                s[i] = s[j][:len(s[i])]
                    s[j].startswith(s[i])  (per [1])

            s[i][:p] = s[i+1][:p] = s[j][:p]                        [32]
                s[i][:p] ≤ s[i+1][:p] ≤ s[j][:p]  (per [3], [A3])
                s[i][:p] = s[j][:p]  (per [30])


            s[i+1][p] < s[j][p]  (per [32], [36], [A4])             [33]
                s[i][p] != s[i+1][p]  (per [27])                    [34]
                s[i][p] = s[j][p]  (per [31])                       [35]
                s[i+1][p] != s[j][p]  (per [34], [35])              [36]

            s[i][p] < s[i+1][p] < s[j][p]                           [37]
                s[i][p] < s[i+1][p]  (per [29])
                s[i+1][p] < s[j][p]  (per [33])

            Contradiction!
                    s[i][p] < s[i+1][p] < s[j][p]  (per [37])
                =>  s[i][p] < s[j][p]
                =>  s[i][p] != s[j][p]                              [38]
                    s[i][p] = s[j][p]  (per [31])
                    ([38] conflicts with [31])

        Annex (proofs left as an exercise):

            s[b].startswith(s[a])  =>  a ≤ b  (assuming [3])        [A1]

            s[a] != s[b]  =>  a != b                                [A2]

            ∀ q: s[a] ≤ s[b]  =>  s[a][:q] ≤ s[b][:q]               [A3]

            Given:                                                  [A4]
                0 ≤ a < b
                q ≥ 0
                s[a][:q] = s[b][:q]
                s[a][q] != s[b][q]
            =>  s[a][q] < s[b][q]  (per above, [3])
    '''
    values = sorted(values)
    for left, right in zip(values[:-1], values[1:]):
        if right.startswith(left):
            return False
    return True

For those who aren't Pythonistas: in Python, sequences and strings are zero-indexed. The slice notation for a string "some_str[:p]" means "the first p characters of some_str", while "some_str[p]" means "the p-th character, where p=0 is the first character".

There are probably errors and omissions in the proof, so take it with a grain of salt.

There must be a much more elegant proof, but it's not obvious to me what approach one would take.

Answer 3

Here's another proof that doesn't use contradiction:

        Given:

            values[q].startswith(values[p])                         [1]

        Assumptions:

            Let s := sorted(values)                                 [2]
            Let i := s.index(values[p])                             [3]
            Let j := s.index*(values[q]), j != i                    [4]
                    i.e., choose the first index matching
                    'values[q]' that isn't also the index 'i';
                     in Python, one might write:
                         j = s[i+1:].index(values[q]) + i+1

        We want to show:

            s[k+1].startswith(s[k]) for at least one k ≥ 0

        Proof:

            s[i] = values[p]  (per [3])                             [5]
            s[j] = values[q]  (per [4])                             [6]

            s[j].startswith(s[i])  (per [1], [5], [6])              [7]

            0 ≤ i < j  (per [2], [4], [7], [A2])                    [8]

            if j == i+1:
                solution: k = i
            otherwise:                                              [9]

            i < i+1 < j  (per [8], [9])                             [10]

            if s[i] == s[j]:                                        [11]
                s[i] == s[i+1] == s[j]                              [12]
                        (per [1], [10], [11], [A3])
                s[i+1].startswith(s[i])  (per [12], [A1])
                solution: k = i
            otherwise...                                            [13]

            s[i] < s[j]  (per [7], [13], [A2])                      [14]

            if s[i] == s[i+1]:                                      [15]
                solution: k = i
            otherwise...                                            [16]

            s[i] < s[i+1]  (per [2], [16])                          [17]

            if s[i+1] = s[j]:                                       [18]
                if j = i+2:                                         [19]
                    s[i+1] = s[i+2]  (per [18], [19])
                    solution: k = i+1
                otherwise:                                          [20]
                    i+1 < i+2 < j (per [10], [20])                  [21]
                    s[i+1] = s[j]  (per [18])                       [22]
                    s[i+1] = s[i+2] = s[j]
                            (per [2], [21], [22], [A3])
                    solution: k = i+1
            otherwise...                                            [23]

            s[i+1] < s[j]  (per [2], [23])                          [24]

            s[i] < s[i+1] < s[j]  (per [17], [24])                  [25]

            let I := len(s[i])                                      [26]

            s[j][:I] = s[i]  (per [7], [26], definition of prefix)  [27]

            s[i][:I] = s[i]  (per [26], trivial proof)              [28]

            s[i][:I] = s[j][:I]  (per [27], [28])                   [29]

            s[i][:I] = s[i+1][:I] = s[j][:I]                        [30]
                    (per [2], [10], [26], [29], [A4])

            s[i][:I] = s[i+1][:I]  (per [30])                       [31]
            s[i] < s[i+1]  (per [17])                               [32]
            s[i+1].startswith(s[i])  (per [31], [32], [A5])
            solution: k = i

    Annex (proofs left as an exercise):

        Given 's', a sorted list of strings:

            s[a] = s[b]                                             [A1]
        =>  s[b].startswith(s[a])

            s[b].startswith(s[a])                                   [A2]
        =>  s[a] ≤ s[b]
        =>  a ≤ b

            a < b < c, and                                          [A3]
            s[a] = s[c]
        =>  s[a] = s[b] = s[b]

            a < b < c, and                                          [A4]
            s[a][:q] = s[c][:q]
        =>  s[a][:q] = s[b][:q] = s[c][:q]

            a < b, and                                              [A5]
            s[a] < s[b], and
            s[a][:len(s[a])] = s[b][:len(s[a])]
        =>  s[b].startswith(s[a])