Suffix trees, suffix arrays, etc.

From MIT 6.851:

• Video: https://www.youtube.com/watch?v=NinWEPPrkDQ

• https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf

• https://courses.csail.mit.edu/6.851/spring12/lectures/L16.pdf

Given text upfront, preprocess text T and query pattern P. Goal - query in O(P). O(T) space.

Trie - rooted tree with child branches labeled with letters in Σ.

Task: find predecessor. Solved with tries, but the problem is how to represent the node in the trie. Array: too much memory. BST - too slow. Hash - doesn't preserve order, so doesn't solve the predecessor. There are tricks how to do it in O(P + logΣ).

Can use to sort strings: O(T + klgΣ).

Compressed trie - contract non-branching path into single edge. O(k) nodes.

Suffix trees (or suffix tries) - compressed trie of all |T| suffixes. T[i:] of T with $ appended.

Applications of suffix trees:

• Search for P gives subtree whose leaves correspond to all occurrences of P in T.

  • Which node representation to use?

    • Hashing => O(P) time. But not in order.

    • Trays => O(P + lgΣ) time.

• LCP (T[i:], T[j:]) = LCA

• All occurrences of T[i:j] = weighted level ancestor j-i of T[i:] leaf. O(lglgT).

• Document retrieval: O(p + #docs) - all documents matching the pattern. With RMQ.

Suffix array - sort suffixes of T (just store their indexes) in O(T) space.

LCP - largest common prefix or neighbour prefixes.

You can build suffix tree using suffix array and LCPs.

O(T + sort(Σ)) construction:

1. Sort Σ.

2. Replace each letter by its rank in Σ.

3. Form T0=<(T[3i], T[3i+1], T[3i+2])> for i =0,1,... T1=<(T[3i+1], T[3i+2], T[3i+3])>. T2=...

4. Recurse on <T0, T1>

5. Radix sort of T2's suffixes. T2[i:] = T[3i+2] = <T[3i+2],T[3i+3:]>

6. Merge suffixes of T0 and T1 with suffixes of T2.

Exercises:

• Build suffix tree.

• Find substring.

• Find longest repeated substring. Try wikipedia!