Every substring, in fewer states than substrings

Write down every distinct substring of a text of $n$ characters. There are up to $n(n+1)/2$ of them, and on ordinary text there are nearly that many — a random sequence of 512 characters over a four-letter alphabet has 129,416.

Now build a machine that accepts exactly the suffixes of that text, and note that reading any substring from the start state lands somewhere: the machine recognises every substring on the way. It needs 831 states.

The ratio is 156, it grows with the length, and the reason is not compression in any ordinary sense. Nothing has been thrown away and no query has become approximate. Many substrings simply behave identically as far as the future is concerned, and a deterministic machine that distinguishes only what it must has one state for each class of them.

Two bounds, both exact, both reached #

The suffix automaton of a string of $n \ge 3$ characters has at most $2n - 1$ states and at most $3n - 4$ transitions.

Those are not asymptotic statements with hidden constants. They are exact small integers, they are what makes the structure usable, and both halves of the claim can be put to the test: nothing may exceed them, and something must reach them.

Nothing exceeds them, on every text this site’s gate builds — three lengths crossed with three alphabet sizes, and the closest approach is 98.2%.

Something reaches them, and the something is a string that can be written in one line. The text $ab^{n-1}$ — one a followed by $n-1$ copies of b — has exactly $2n-1$ states. The text $ab^{n-2}c$ has exactly $3n-4$ transitions.

Both halves are needed and this site has recorded why more than once. A bound nothing approaches is not evidence that the bound is the right one, and a check that fires on everything is not a check. Asserting only that the automaton stays under $2n-1$ would pass on an implementation that built something twice too small and wrong.

How big it actually gets, and what the alphabet does #

On ordinary text the automaton is well under its bound and how far under depends on the alphabet, which is the second measurement worth having:

A binary text nearly saturates the bound. That is not an accident: with two symbols a text of three hundred characters contains almost every short binary string, so the machine has to distinguish a great many contexts and the clone step fires constantly. With twenty-six symbols most short strings do not occur, the automaton is closer to a plain trie of the few that do, and it needs fewer states.

The direction is worth noticing because it is the opposite of the usual intuition about alphabets. In the matching field a wider alphabet made things cheaper — the shift the pattern already knows showed Horspool’s shift saturating at the alphabet size, so a wide alphabet buys long jumps. Here a wider alphabet makes the index smaller. Both are consequences of the same fact — a wide alphabet makes coincidences rare — and they land on opposite sides of the ledger.

What a state stands for #

The states are not substrings and are not positions, and getting this right makes the rest of the structure obvious rather than mysterious.

A state stands for a set of end positions. Reading a substring from the start lands in the state whose end-position set is the set of places that substring finishes. Two substrings land in the same state exactly when they finish in the same places — which is why bcbc and cbc can share a state in the automaton above, and why b and bc cannot.

Three consequences follow immediately and each of them is a use of the structure:

The substrings in one state form a contiguous run of lengths. They are the suffixes of the longest one, from $\mathrm{len}(\mathrm{link})+1$ up to $\mathrm{len}$ — which is what the counting formula below rests on.

The suffix link points to the state of the next shorter class. Removing characters from the front of a string can only ever grow its end-position set, and the link goes to the first state where it grows. So the links form a tree, and that tree is the suffix tree of the reversed text.

The number of occurrences of a substring is the size of its state’s end-position set, computable in one pass over the link tree. One structure, and it answers “does this occur”, “how often” and “how many distinct substrings are there” with three different readings of the same states.

The substring count, computed three ways #

The automaton knows how many distinct substrings the text has, and it can say so without holding any of them.

Each state stands for a set of substrings that all end at the same set of positions, and those substrings are exactly the suffixes of one string whose lengths run from $\mathrm{len}(\mathrm{link}(v)) + 1$ up to $\mathrm{len}(v)$. So the count is $\sum_v \bigl(\mathrm{len}(v) - \mathrm{len}(\mathrm{link}(v))\bigr)$ over every state but the first — a sum of small integers over a linear-sized structure.

Set that against two other routes. The trie’s node count is the substring count plus one, by construction. And for short texts the set can simply be built by exhaustion.

The three agree, and the gate checks them against each other rather than against a remembered value. That agreement is the reason the first number is quotable: a formula read off state lengths, in a structure whose construction involves a clone step subtle enough to get wrong, is worth exactly as much as the thing it has been checked against.

The clone, which is where the linearity is bought #

The construction adds one character at a time. Most of the time this creates one state and rewires a chain of suffix links, which is the easy case.

The hard case is when the character being added already has a transition out of some state on that chain, to a state $q$ whose longest string is longer than it should be for this context. Then $q$ is doing two jobs — it stands for strings that must now be distinguished — and it is split: a clone is made with the shorter length, the transitions are copied, and the links are repointed.

The clone is the whole subtlety of the algorithm and it is where the $2n-1$ comes from. Each character adds at most one ordinary state and at most one clone, so $2n$ is immediate and the exact bound is a small refinement of that. It is also where an implementation goes wrong quietly: an automaton missing a clone still accepts the whole text and still accepts most of its substrings, and finding the failure means asking about a substring that the missing distinction hides.

That is the same kind of defect this site keeps meeting — a structure that is right about the case anybody would test and wrong about the case that made the structure necessary — and the answer is the same. The gate asserts the substring count against exhaustion, and a missing clone changes it.

The construction is linear, and that is an amortised claim #

A single character can walk a very long suffix-link chain. Adding the last b to $ab^{n-1}$ walks a chain proportional to $n$, so there is no per-character bound to be had and the claim has to be about the total.

The total is linear, and this site measures amortised claims rather than quoting them — what amortised means established the discipline on a dynamic array, and the same discipline applies here. Counting the steps taken along suffix links during construction:

Steps per character vary by a factor of 1.16 across a sixty-fourfold change in length, on the alphabet that maximises the work. On a four-letter alphabet the same quantity varies by 1.06 and settles near 2.58.

The argument behind the number is the usual potential argument: the position of the current state on the suffix-link chain is a quantity that grows by at most one per character and falls by one per step of the walk, so the total number of steps is bounded by the number of characters. It is the identical shape as the dynamic array’s — a cheap operation that occasionally does a lot, with a quantity that pays for the expensive case in advance — and it is the reason the clone count in that table is close to the state count minus the length.

What it is for, and what it is not #

The automaton answers is this a substring in time proportional to the length of the query and independent of the length of the text. Walking the query’s characters from the start state either succeeds or gets stuck, and there is no search, no binary search and no comparison of strings.

Set that against the suffix array from this site’s strings field. The index that is the text sorts every suffix in zero character comparisons and answers the same question by binary search over the sorted order, at $O(m \log n)$ character comparisons a query and $O(n)$ machine words of space.

Neither dominates and the choice is the usual one. The array is compact, cache-friendly and supports counting occurrences by a range; the automaton is a graph of small objects with an alphabet-sized branch at each node, and it supports things an array cannot state easily — the number of distinct substrings, the longest common substring of two texts, the number of occurrences of every substring at once.

What neither of them is is a compressor. Both are strictly larger than the text they index, and the whole family of structures that are smaller than the text while still answering these questions — compressed self-indexes, built on the transform this site’s coding field measured — is named here and not taken.

What it costs to build and to hold #

Two numbers close the practical case, and both are worth having beside the elegance.

Space. The automaton holds a state per class and a transition per edge, and the transitions are where the memory actually goes: 1,286 of them at 512 characters against 831 states. A transition is a character and a target, so a compact representation is a sorted list per state or a hash; a fast one is an array of size $\sigma$ per state, which is unusable for a large alphabet and is what most implementations do anyway for small ones.

Construction. Linear in the length, amortised, as measured above — and online, which is the property that separates this structure from a suffix array. Characters can be appended one at a time and the automaton is correct for the text seen so far after each one, with no rebuild. A suffix array built by prefix doubling has no such property: appending a character changes the sorted order of almost every suffix.

That makes the choice between them less about size than about the shape of the workload. A text that is fixed and queried many times wants the array, which is compact and cache-friendly. A text that grows wants the automaton, which is the only one of the two that can be extended.

The factor of a hundred and fifty-six is arithmetic, not compression #

The opening ratio is the essay’s most striking number and it is worth defusing, because a reader who takes it as a statement about the text has taken away something false.

A text of $n$ characters has at most $n(n+1)/2$ distinct substrings and its automaton has at most $2n-1$ states. So the ratio between them is at most about $n/4$ whatever the text is, and at $n = 512$ that is 128 against the 156 measured. The factor is a consequence of counting a quadratic quantity with a linear structure, and it grows with the length for that reason alone.

Which means the ratio says nothing about compressibility. A random text over a large alphabet has nearly the maximum number of substrings and nearly the maximum number of states, and its ratio is near $n/4$; a highly repetitive text has few substrings and few states, and its ratio is near $n/4$ as well. The number moves with $n$ and barely with the text.

What does say something about the text is the deviation — the state count as a fraction of $2n-1$, which is the third table in this essay: 98.2% over two symbols, 63.1% over twenty-six. That fraction is a measurement of how many distinct end-position classes the text’s substrings actually fall into, it is bounded above and below, and it moves by a factor of one and a half across the alphabets measured.

A ratio between a quantity bounded by $n^2$ and one bounded by $n$ is not a compression ratio, and this collection has met the same confusion before: an index that contains no information makes the point from the other side, that a structure derived entirely from its input is not storing anything about it. The automaton is smaller than the list of substrings for the same reason a formula is smaller than its table of values.

Two texts, one automaton #

The list of things the structure is for is given above and one of its entries is worth performing, because it is the shortest useful algorithm this collection has and it needs nothing new.

The longest common substring of two texts. Build the automaton of the first. Then feed the second through it one character at a time, keeping a current state and a current match length: on a transition, advance and add one; on a mismatch, follow suffix links until a transition exists, setting the length to the link target’s own $\mathrm{len}$ plus one. The largest length ever reached is the answer.

That is one pass over the second text with an amortised constant per character — the same potential argument as the construction, since the length falls by at least one per link followed and rises by at most one per character. No second structure, no comparison of substrings, and the answer arrives with the position it ended at.

The reason it works is the reading of a state given above. A state is a set of end positions in the first text, so being in a state after reading some characters of the second text is exactly the statement that those characters occur in the first — and the current length is how much of the second text’s recent history that remains true of. Following a suffix link is discarding the front of that history, which is the least one can discard to keep the claim true.

The same walk answers a family of questions with no change to the automaton: the matching statistics of the second text against the first — for every position, the longest suffix ending there that occurs in the first text — fall out as the sequence of current lengths, and the longest common substring is their maximum. One structure, one pass, and a per-position answer that a suffix array would need a separate construction to produce.

What “smallest” means here #

One thing has been asserted throughout and deserves its statement, because it is what separates this structure from a merely clever one.

Two substrings are interchangeable, as far as the machine is concerned, if they occur at exactly the same set of end positions in the text. If they do, then whatever can be read after one can be read after the other, and no automaton accepting the suffixes can distinguish them without wasting a state. If they do not, then some continuation completes one to a suffix and does not complete the other, and any correct automaton must distinguish them.

So the states are forced: one per class of end-position sets, no fewer possible and no more needed. That is the Myhill–Nerode argument, and it makes the automaton the unique smallest deterministic machine for this language rather than a good one somebody found.

It also explains the shape of the whole essay. The bound $2n-1$ is not a property of an algorithm — it is a property of the text, counting how many distinct end-position sets its substrings can have, and the algorithm merely constructs them without ever writing one down. And it explains why the trie is quadratic: a trie insists on a node per substring, which is a node per member of a class rather than per class, and the classes on ordinary text are large.