Compressed suffix trees: locate patterns across a frozen text

Last updated: 4 Oct 20269 min read

tutorial

A suffix tree is a compressed trie of every suffix of one text followed by a unique sentinel. Each edge stores start and end offsets into the same retained text, not a copied substring. When a new suffix disagrees partway through an edge, insertion splits that edge and hangs both old and new continuations below the branch. A pattern follows edges character by character; it may finish inside an edge, in which case every terminal below that edge is a match. Leaf terminals retain original start positions. This page uses repeated suffix insertion to expose edge splits. It does not implement a linear-time suffix-tree builder.

Operational case

The frozen incident string cabacaba contains aba at offsets one and five. The pattern bac appears at offset two; zzz has no matching edge. A query ending in the middle of a compressed edge is still valid, so stopping only at explicit branch nodes would miss occurrences. The sentinel cannot occur inside user text or search patterns; otherwise suffix termination is ambiguous. Positions are Python code-point offsets, not byte or grapheme positions. If incident text changes, its suffix leaves and edge offsets refer to the old snapshot and the tree needs rebuilding.

Working Python program

class SuffixNode:
    def __init__(self):
        self.edges = {}
        self.terminal = None


class SuffixEdge:
    def __init__(self, start, end, child):
        self.start, self.end, self.child = start, end, child


class StaticSuffixTree:
    def __init__(self, incident_text, sentinel="$"):
        if sentinel in incident_text or len(sentinel) != 1:
            raise ValueError("sentinel must be unique and one character")
        self.text = incident_text + sentinel
        self.sentinel = sentinel
        self.root = SuffixNode()
        for offset in range(len(self.text)):
            self._insert(offset)

    def _insert(self, offset):
        node, position = self.root, offset
        while position < len(self.text):
            initial = self.text[position]
            edge = node.edges.get(initial)
            if edge is None:
                leaf = SuffixNode()
                leaf.terminal = offset
                node.edges[initial] = SuffixEdge(position, len(self.text), leaf)
                return
            matched = 0
            while (edge.start + matched < edge.end and position + matched < len(self.text)
                   and self.text[edge.start + matched] == self.text[position + matched]):
                matched += 1
            if edge.start + matched == edge.end:
                node, position = edge.child, position + matched
                continue
            branch = SuffixNode()
            node.edges[initial] = SuffixEdge(edge.start, edge.start + matched, branch)
            edge.start += matched
            branch.edges[self.text[edge.start]] = edge
            leaf = SuffixNode()
            leaf.terminal = offset
            branch.edges[self.text[position + matched]] = SuffixEdge(position + matched, len(self.text), leaf)
            return

    def locate(self, pattern):
        if not pattern or self.sentinel in pattern:
            raise ValueError("pattern must be nonempty and omit sentinel")
        node, position = self.root, 0
        while position < len(pattern):
            edge = node.edges.get(pattern[position])
            if edge is None:
                return []
            matched = 0
            while (position + matched < len(pattern) and edge.start + matched < edge.end
                   and pattern[position + matched] == self.text[edge.start + matched]):
                matched += 1
            if position + matched == len(pattern):
                node = edge.child
                break
            if edge.start + matched < edge.end:
                return []
            position += matched
            node = edge.child
        result, pending = [], [node]
        while pending:
            current = pending.pop()
            if current.terminal is not None:
                result.append(current.terminal)
            pending.extend(edge.child for edge in current.edges.values())
        return sorted(result)


if __name__ == "__main__":
    index = StaticSuffixTree("cabacaba")
    print(index.locate("aba"))
    print(index.locate("bac"))
    print(index.locate("zzz"))

Output

[1, 5]
[2]
[]

Time, space, and tradeoff

There are O(N) explicit nodes and edges for a terminated text of length N, while the text is stored once and edges use index pairs. This direct construction can compare O(N squared) characters across suffix insertions in the worst case. Pattern traversal costs O(M) character comparisons for pattern length M; reporting K locations costs O(K log K) here because returned offsets are sorted. Output itself needs O(K) memory. Python dictionaries and nodes add substantial overhead. A suffix array provides a compact ordered alternative, and an FM-index changes the count-versus-locate tradeoff for frozen text.

Common Mistakes

Do not require a pattern to end exactly at an explicit node.
Do not copy every edge label into a separate string and claim shared-text storage.
Do not accept the sentinel as ordinary incident input.
Do not call this repeated-insertion builder linear-time.

Connected lessons

Compare its input and update contract with X-fast trie: predecessor and successor in a fixed integer universe, Persistent radix vectors: copy one indexed path per revision, Disjoint interval unions: maintain covered maintenance time, then complete the structure audit and decision quiz.

De Bruijn graphs: compact non-branching k-mer routes into unitigs examines a related structure with a different operation boundary.

data structures

range-query-structures