1
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ This algorithm is correct, but depending on what $N$ is intended to represent, the running time is not $O(N \lg N)$. Consider a set of $N$ strings, where each string starts with $N$ a's. Then the running time is more like $O(N^2 \lg N)$, because comparing a pair of strings takes $O(N)$ time rather than $O(1)$ time. $\endgroup$ – D.W. Sep 9 '16 at 18:46
  • $\begingroup$ It will be $O(N \log N + N)$ in that case, if you obtain the LCP's during the sort. $\endgroup$ – KWillets Sep 9 '16 at 19:53
  • $\begingroup$ Oops, my brain is elsewhere today. N^2 in the second term. $\endgroup$ – KWillets Sep 9 '16 at 20:28
2
$\begingroup$
  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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.