The index that is the text

Every search in this field so far has been handed the text cold. Horspool reads a seventh of it, KMP reads all of it, and both start again from nothing on the next query.

A text that is going to be searched many times deserves better, and the structure that gives it is unusual enough to be worth building slowly: an index whose entries are positions in the text and whose keys are never stored at all.

The object #

The suffix array of a text is the list of its starting positions, sorted by the suffix beginning at each one.

For banana with a terminator, the suffixes are banana$, anana$, nana$, ana$, na$, a$, $, and sorting them gives the positions 6, 5, 3, 1, 0, 4, 2. That array of seven integers is the whole structure. The suffixes themselves are not stored anywhere — each is just an offset into the text that is already in memory.

The consequence is a space claim that can be stated exactly rather than asymptotically. A suffix array of an $n$-character text is $n$ integers: four bytes each for texts under four gigabytes, so 4n bytes on top of the text. A suffix tree, which supports a superset of the same queries with better asymptotics, is universally quoted at 10 to 20 bytes per character in a real implementation, because it stores a node with children and edge labels for every branching position.

That factor of four is why every large text index built since about 1995 is an array and not a tree, and it is a case where the other axis decides which structure exists rather than merely characterising it.

The build makes no character comparisons #

Sorting $n$ suffixes looks, from the first essay in this field, like the most expensive sort imaginable. The suffixes of a 4,096-character text have a total length of about 8.4 million characters. They share enormous prefixes with one another by construction — the suffix at position $i$ and the one at $i+1$ differ only by having one more character at the front. A comparison sort on them should cost $\Theta(n \log n)$ comparisons of $\Theta(L)$ characters each, and $L$ here is large.

Measured on a 4,097-character text: 85,248 element comparisons and zero character comparisons.

Not few. Zero.

How #

Prefix doubling sorts the suffixes by their first character, then by their first two, then four, then eight, until every suffix has a distinct rank.

The first round is the only one that looks at characters, and it does not compare them — it uses each suffix’s first character directly as a rank. After that round, every suffix has an integer rank reflecting its first character.

The second round needs to sort by the first two characters. But the rank of the suffix starting at $i+1$ already encodes the character at $i+1$. So the key for suffix $i$ is the pair of integers $(\text{rank}[i], \text{rank}[i+1])$, and sorting by that pair sorts by the first two characters — with no character touched, because the ranks are integers.

The third round uses $(\text{rank}[i], \text{rank}[i+2])$ from the second round’s ranks, which encode two characters each, so the pair encodes four. And so on, doubling every round.

The characters are consulted once, at the start, and the algorithm compares integers from then on. That is the trick, and it is the exact answer to the cost the first essay of this field measured: the way to avoid re-reading shared prefixes is to arrange never to read a prefix at all after the first pass.

The rounds, and why there are four #

The doubling stops when every suffix has a distinct rank, which happens as soon as $2^k$ exceeds the longest prefix any two suffixes share.

On the 4,097-character text over four symbols the ranks go 18 distinct, then 260, then 3,973, then 4,097 — four rounds, and the longest common prefix in the whole text is 11 characters. $2^4 = 16 > 11$, so four rounds is what the structure of the text demanded rather than a parameter anyone chose.

Change the alphabet and the round count changes with it. Over two symbols the longest shared prefix is 22 and the build takes five rounds and 99,123 comparisons; over 26 symbols it is 5, and the build takes three rounds and 65,318. The cost is $O(n \log^2 n)$ in the worst case and $O(n \log L)$ in practice, and $L$ is the property of the text that the whole field keeps coming back to.

The query #

Searching the index is a binary search over the sorted suffixes. Each probe compares the pattern against a suffix, which costs at most $m$ characters, and there are $\log_2 n$ probes — so $O(m \log n)$ characters against a scan’s $O(n)$.

Measured on the 4,097-character text with eight-character patterns: 91, 82 and 96 characters for three different patterns, at 23, 21 and 24 element comparisons each. The element counts are $2\log_2 4097 \approx 24$, because the implementation runs two binary searches to find both ends of the matching range and thereby report all occurrences rather than one.

Horspool on the same text and the same patterns: 1,472, 1,232 and 1,668 characters.

The ratio is about 16, and it is $n / (m \log n)$ with the constants in. It grows with the text, which is the point of an index: the scan’s cost is linear in $n$ and the query’s is logarithmic.

The LCP array, and the linear-time result that deserves its own paragraph #

The suffix array alone answers “where does this pattern occur”. A great deal else — the longest repeated substring, the number of distinct substrings, the longest common substring of two texts — needs one more array: the length of the longest common prefix of each adjacent pair in the sorted order.

Computing it naively costs $\Theta(n)$ comparisons of up to $L$ characters each. Kasai’s algorithm computes it in $O(n)$ character comparisons total, and the argument is one invariant worth stating in full.

Process the positions of the text in text order rather than in sorted order. Suppose the suffix at position $i$ has a common prefix of length $h$ with the suffix preceding it in sorted order. Then the suffix at position $i+1$ — which is the same suffix with its first character removed — has a common prefix of at least $h-1$ with its sorted predecessor.

So a counter that starts at $h$, is decremented by one at each step, and is incremented once per character comparison can increase at most $n$ times in total, because it decreases at most $n$ times and never goes below zero. At most $2n$ character comparisons for the whole array.

The measurements: 2,044 comparisons for a 1,025-character text (bound 2,050), 8,188 for 4,097 (bound 8,194), 32,764 for 16,385 (bound 32,770).

Each of those is within seven of its own bound — 99.7%, 99.9% and 99.98% of it. A guarantee approached that closely is a guarantee about the case being run rather than about a case nobody constructed, and it is the same shape as KMP at 99.6% of its 2n. The two bounds are the same bound, in fact: both are potential-function arguments over a counter that rises by one and falls by at least one, which is the argument what amortised means sets out for a dynamic array.

What the LCP array answers that the suffix array cannot #

The two arrays together answer a set of questions that have nothing obviously to do with searching, and each falls out in one line once both are built.

The longest repeated substring is the largest entry in the LCP array. If two suffixes share a prefix of length $\ell$, that prefix occurs at least twice; and any repeated substring is a shared prefix of two suffixes, so the largest LCP entry is the longest repeat. On the 4,097-character text over four symbols it is 11, and the substring is abccccdaabc, occurring at positions 1,445 and 1,524. Over 26 symbols and four times the length it is 5 — fftnn — because a wider alphabet makes long accidental repeats vastly rarer.

The number of distinct substrings is $n(n+1)/2$ minus the sum of the LCP array. Every suffix contributes its own prefixes as substrings, and the LCP entry is exactly how many of them were already contributed by the suffix before it. For the four-symbol text: 8,373,468 distinct substrings out of 8,394,753 possible, or 99.75%. For the 26-symbol one: 99.97%.

Both of those numbers are computed from two arrays in one pass, and both would be hopeless to compute directly — enumerating and deduplicating eight million substrings is minutes of work and hundreds of megabytes, against a linear scan of an array of integers that is already in hand.

That is the shape worth carrying out of this essay. The index is not a faster search; it is a different set of questions becoming answerable at all. A text with a suffix array attached supports queries that a text alone does not support at any price, and the search speed is the least interesting of them.

What structured text does to the numbers #

Every measurement above is on random text, which is the clean case and the pessimistic one. Real text is not random and its longest repeats are much longer.

A 626-character text built from a vocabulary of stems and suffixes — the same generator the first essay sorts word lists from — has a longest repeated substring of 19 characters: -transferors-measur, a whole word plus its neighbours’ edges, occurring twice by chance in a 626-character text. A random text of that length over the same alphabet would have a longest repeat of three or four.

That has a direct consequence for the build. The doubling stops when $2^k$ exceeds the longest shared prefix, so a text with a 19-character repeat needs five rounds where the random one needs three. Structured text is more expensive to index and more rewarding to have indexed, and both halves come from the same property.

It is also the property the compression half of this field is about. A text whose suffixes share long prefixes is a text that repeats itself, and repetition is the only thing any compressor has ever exploited.

Where the break-even actually is #

The hero figure’s crossing is at six queries, and that number is worth reading carefully because it is much lower than the usual intuition about index-building suggests.

The arithmetic: the build costs 8,188 character comparisons, a query against the index costs 90, and a scan costs 1,540. Each query saves 1,450, so the build is repaid after $8188 / 1450 = 5.6$ of them.

Two things make that number small. The scan is expensive because the text is long, and the build is cheap because it barely touches characters at all — 8,188 of the build’s comparisons are Kasai’s, and the suffix array’s own 85,248 comparisons are of integers, which this counter does not charge for.

That last clause is the honest qualification and it should not be buried. The figure compares character comparisons against character comparisons, and by that measure the build is nearly free. By any measure that charged for integer comparisons the build would be 85,248 units rather than 8,188, the break-even would be nearer sixty queries, and the conclusion would change in degree without changing in kind.

Which measure is right depends on what the machine is doing, and this site’s answer to that question is always the same: it depends on where the data is. An integer comparison on two array entries that are already resident costs a fraction of a character comparison that walks two pointers into a large text — which is the count is not the time in its usual form, and the reason the counters here are labelled with their unit on every plate rather than added together.

Why the crossing barely moves, written out #

The second figure notes that the break-even shifts very little when the text quadruples, and offers the reason in a clause — both sides scale with $n$. The arithmetic is worth doing properly, because it turns out that $n$ does not merely scale out; it cancels.

Write the scan’s cost as $cn$, where $c$ is the fraction of the text the matcher reads: 1,540 characters of a 4,097-character text is $c = 0.376$. The build in this unit is Kasai’s $2n$, since the suffix array’s own comparisons are of integers. A query against the index is $m\log_2 n$. The build repays itself after $q$ queries when

$$2n = q\,(cn - m\log_2 n)$$

and dividing through by $n$ leaves

$$q^* = \frac{2}{c - (m\log_2 n)/n}.$$

The second term in the denominator is $96/4097$, about six per cent of $c$, and it shrinks as $n$ grows. So to a good approximation the break-even is $2/c$ and contains no $n$ at all — $2/0.376 = 5.3$, against a measured crossing at six.

That is a sharper statement than the figure makes and it inverts a common intuition. A larger text does not make an index pay sooner. It makes both sides of the trade larger in the same proportion, and the query count at which indexing wins is set by how much of the text the scan being replaced actually reads. Replace a naive scan or KMP, both of which read everything, and $c = 1$ and the index pays at two queries. Replace a skipping matcher reading a seventh, and it pays at fourteen. The matcher is the variable; the text size is not, which is why where a crossing moved to is a question about the thing being compared against rather than about the scale.

The alphabet enters the same way, through $c$ alone. A wider alphabet gives a skipping matcher longer shifts, so $c$ falls, so $q^*$ rises — an index is worth building sooner over two symbols than over ninety-five, exactly as the last figure says, and now with a mechanism rather than an observation.

The other unit behaves differently, and the contrast is the useful part. Charged for integer comparisons the build is 85,248 on this text, about $21n$, so $q^* \approx 21/c \approx 56$ — the “nearer sixty” the previous section estimated. But $21$ is not a constant: prefix doubling performs $\log_2 L$ rounds of an $n\log n$ sort, so its per-element cost grows like $\log n\log L$. In characters the break-even is flat in $n$; in integer comparisons it grows slowly with it. Two units, two different shapes of answer, from one pair of algorithms — which is a cost that is not one’s whole subject, arriving here as a disagreement about whether a decision depends on the size of the input.

Where the crossing moves, and where it does not #

The crossing is the whole of the decision, so it is worth turning the two dials that could move it: the pattern’s length and the text’s.

What the index does not do #

Three limits, and the first is the one that decides whether to use it at all.

It is static. A suffix array is built for a text and is invalidated by editing it. Insert one character at the front and every position shifts, and there is no incremental repair — the structure has to be rebuilt. Dynamic text indexing is a real subject and none of it is as simple or as small as this.

It supports one kind of query well. Exact substring search is what the binary search does. Approximate matching — a pattern with one character wrong — is not a range in the sorted order and the index does not answer it directly.

And the build’s constant is not what this page measured. The doubling algorithm here is $O(n \log^2 n)$ and it was chosen because every round of it is a picture. The algorithms that ship are linear-time — DC3, SA-IS — and they are linear by a recursion that this site has not measured and will not claim on the strength of a citation.

What it makes possible #

The reason this structure closes the string half of the field rather than sitting in the middle of it is the last essay in the phase.

A suffix array is a sorted list of every rotation of a text, near enough, and taking the last character of each sorted rotation produces a permutation of the text that a compressor can do things with that it cannot do with the text itself. The index and the compressor turn out to be the same object read two ways, which is the kind of connection that makes a field worth building rather than a list of algorithms worth reciting.