The parse in one pass of the text

Every measurement about a depth cap in this collection was taken on a text of a few thousand characters. The reason was never the structure. It was that finding the longest previous occurrence of every position by comparing characters is quadratic, so eight thousand characters is a minute and eighty thousand is two hours.

The structure that removes it has been in this collection since the tables field opened, doing something else.

The parse, and what makes it expensive #

The phrases a text copies from itself defines it. Walk the text; at each position take the longest string starting there that has occurred starting earlier; emit it as a phrase and jump past it. Where nothing has occurred before, emit one character as a literal.

The number of phrases is z, and it is one of the two measures of repetition this collection weighs texts by.

Computing it as written means, at each position, comparing against every earlier position — which is quadratic in the text and quadratic again in the phrase lengths. Measured: 7,906 character comparisons at 512 characters and 1,324,336 at 8,192, which is 167 times as many for 16 times the text.

That is what set every sweep size in the ladder about depth caps, and it is what this essay removes.

The structure that already knew #

Every substring, in fewer states than substrings built a suffix automaton: the smallest deterministic machine accepting exactly the substrings of a text. Its size is bounded by exact small integers — at most 2n − 1 states and 3n − 4 transitions — and it is built one character at a time in amortised constant time.

Three properties make it the right instrument for a parse.

It accepts exactly the substrings. Walking it from the start with the characters of the text at position i gives, in one transition each, how far the string starting at i has occurred before — provided the automaton was built over what came before.

It is extendable. A parse reads left to right, so the automaton it consults must be the automaton of a growing prefix, which is what the online construction gives.

And a state knows where its strings end. Each state carries the smallest position at which any of its strings ends, so a match of length L in a state ending at e is an occurrence at e − L. That is one field, set when a state is created and never changed, and it is the difference between “this substring has occurred” and “this substring occurred here”.

The parse as a walk #

At position i, with the automaton holding the text up to i, walk from the start state following the characters at i, i + 1, and so on. Each transition that exists is one more character of a match; the first that does not exist ends it. The state reached after k + 1 characters gives an occurrence, and if it starts before i the match is legal.

Take the longest such match, emit it as a phrase, feed those characters to the automaton, and continue.

That is the whole algorithm, and the total work is one transition per character examined plus the automaton’s own construction, which is amortised constant. Measured: 25,420 operations at 8,192 characters against 1,324,336 comparisons — and per character, 3.10 against 161.7.

What the walk looks like at one position #

It is worth following one position through, because the algorithm is short enough to be opaque.

Say the text so far is abracadabr and the parse is at position 10, which holds a. The automaton holds abracadabr. Walk from the start state: a exists, so the match is at least one; the state reached says its strings end earliest at position 1, so the occurrence is at 0. Feed a to the automaton — it now holds abracadabra — and ask for c. It exists; the match is two; the state’s earliest end is 4, so the occurrence is at 2. Continue until a transition is missing.

Every step is a lookup and an arithmetic check, and the automaton grows by exactly the characters the match has consumed. Nothing is backtracked and nothing is re-read.

The two units, and what the ratio is not #

A transition is a map lookup. A character comparison is an equality test. They are not the same act, and the ratio between the two columns is not a speed-up.

What the plate shows is a shape: one column grows with the text and the other with its square. That claim survives any reasonable exchange rate between the units, and it is the claim the structure is built to support.

This collection’s convention since the operations a candidate count leaves out is that a comparison must state what one act is on each side, and the reason it applies here with force is that the temptation is large: 161.7 against 3.10 is a factor of fifty-two, and quoting it as a speed-up would be quoting an exchange rate nobody set.

The ordering that decides whether it is the same parse #

Here is the subtlety, and it is one line of code.

The greedy parse allows a phrase to overlap its own source. A run of a thousand identical characters is two phrases — one literal and one copy of length 999 starting at position 0 — because the copy reads characters it is itself producing. That is what makes z a measure of repetition rather than a compressor’s phrase count, and the phrases a text copies from itself is explicit about it.

An automaton built over the prefix before the phrase cannot find those matches: everything it accepts ends before position i, so no match can extend past i. Build it that way and the parse is correct, is a legal Lempel-Ziv parse, and is not the same parse — a run of five hundred characters comes out as nine phrases rather than two.

The fix is to extend the automaton during the match. Before asking for the transition on the character at i + k, feed it the character at i + k − 1, so the automaton always holds exactly T[0 … i + k). Then a match of length k + 1 can end at position i + k, its source can start before i and run past it, and the overlap is found.

The automaton must be one character behind the character being asked about. One ahead and every position matches itself.

What one character ahead does #

It is worth measuring the wrong version rather than describing it, because the symptom is not what one would guess.

Feed the automaton the character before asking for its transition, and the state reached stands for an occurrence ending at the position just fed — which is the phrase itself. Every position then matches itself, at every length, and the parse becomes one phrase covering the whole text with a source pointing at its own start.

On a four-hundred-character text: one phrase, against the correct seventy-four, with four hundred self-copies recorded. The check that catches it is the one the parse already has to satisfy — every phrase must copy from strictly earlier — and it is worth having as an assertion rather than as a comment, because the failure is total and silent.

Why the wrong version looks plausible #

The one-ahead version is not obviously wrong from the code. It builds an automaton, walks it, finds matches, and produces phrases that point backwards — every phrase’s source is less than or equal to its own start, which is nearly the condition.

What it violates is strictly earlier. A source equal to the phrase’s own start is a phrase copying from itself with no earlier occurrence to copy from, which produces a parse that cannot be decoded: reconstructing it would need the characters it is producing before it has produced any of them.

The check is therefore not “does the parse look right” but “does the text come back out”. That check is in the strand already — a parse is required to reproduce its own text character for character — and it fails immediately on the one-ahead version, which is what makes it the right check to have.

The check that matters #

The parse is required to be phrase for phrase identical to the quadratic one, on four texts of different character: a repetitive collection, English-like text, four-symbol text, and a periodic string. Not the same phrase count — the same phrases, at the same positions, with the same lengths.

Measured at twelve hundred characters: 81, 254, 289 and 466 phrases, matching exactly in all four.

And a run of five hundred identical characters is required to be two phrases, with the second copying from position zero at length 499. That is the overlap check, and it is the one the ordering above exists for.

It is worth saying why identity rather than agreement is the requirement. This collection has published z for dozens of texts across five strands: repetition measures, index sizes, phrase-index costs, cap sweeps. If the new construction produced a parse with the same number of phrases but different ones, every one of those numbers would still be right and every plate comparing a phrase’s source to a depth would be about a different object.

So the check compares phrases: position and length, in order, for every phrase of every text. Four texts, 1,090 phrases between them, all matching.

Where the work actually goes #

The automaton’s total is two components and it is worth separating them, because only one is the parse.

At 8,192 characters: 8,518 transitions followed by the matching walk, and 16,902 suffix-link steps taken during construction. So two thirds of the work is building the automaton and one third is using it.

The construction’s share is the amortised part — a single character can walk a long suffix-link chain, and the total over all characters is linear because each step shortens a potential that grows by one per character. This collection measures that rather than quoting it: 2.45 steps a character at 64 characters, 2.85 at 4,096, a spread of 1.16 across a sixty-fourfold growth.

That the matching walk is the smaller half is worth noticing. The parse is nearly free once the automaton exists, which is what makes the automaton worth building for a single parse rather than only for repeated queries.

What the linear construction unlocks #

Three things, and they are the next three essays.

The cap sweep at scale. Every measurement in the ladder about depth caps was taken at 2,048 characters; the same sweep now runs at 65,536 in three seconds. What a quadratic construction was setting is which of those conclusions hold at thirty-two times the size.

The depth histogram, which is the measurement that would choose a cap and which nobody prints: one linear pass over the parse, 3.16 operations a character over thirty-two thousand characters.

And a limit. The cap is a condition on the region a phrase copies from, and an automaton state stands for a set of occurrences while handing back one of them. The cap an automaton cannot see is what that costs, and the answer is up to ten per cent of the phrases at the caps that bind.

The two halves are linear in two different senses #

The split of the 25,420 into 8,518 transitions and 16,902 suffix-link steps is worth pushing on, because the two numbers are linear for different reasons and only one of them is linear in the sense a reader is likely to assume.

The walk’s count is exact and can be written down without any amortisation argument at all. Greedy consumes each character of the text into exactly one phrase, so each contributes one successful transition; each phrase then ends with exactly one lookup that fails, which is what stops it. So

$$\text{transitions} \;=\; n + z$$

and 8,518 against a text of 8,192 leaves 326, which is the parse’s own phrase count. Nothing is re-read, nothing is backtracked, and the identity is worth having as a check rather than as an observation: a walk that ever revisited a character would break it in the direction of being larger, and the phrase count is independently known.

The construction’s count is not like that. A single character can walk a long chain of suffix links — the chain is bounded only by the length of the text — and the total stays linear because each step shortens a potential that grows by one per character. That is an amortised bound in the strict sense, and the 2.06 steps a character measured here is an average over a distribution whose maximum is nothing of the kind.

The distinction has a consequence beyond bookkeeping. The walk gives a per-character bound and the construction gives only a total. Anything wanting a guarantee on the work done between two consecutive characters — a parse consumed incrementally, a structure built while a text arrives, a budget per input event — has that guarantee from one half and not the other, and the half that lacks it is the two thirds. That is invisible in the per-character figure, which is where an amortised quantity always hides.

It also settles which half is worth optimising, and the answer is not the larger one in any useful sense. The walk is $n + z$ lookups and $z$ is small on a repetitive text, so it is within a few per cent of one lookup per character — the minimum for any construction that must at least read the text through the automaton. There is nothing to take. The construction’s two suffix-link steps a character is the only reducible part, and reducing it means a different automaton rather than a better loop.

So the honest summary of the cost is not “3.10 operations a character” but two statements: an exact $n + z$ in one unit, and an amortised $\approx 2n$ in another, with no exchange rate between them. Adding them into a single number is convenient for a plate and it does what a cost that is not one warns against — a total whose components are incommensurable behaves like a measurement and answers no question the components would not answer better. The plate’s flat line is the right claim; the height of that line is the one to read carefully.

What it does not do #

It does not make the parse optimal. Greedy is greedy: taking the longest match at each position is a rule, not a claim about the result, and a shorter phrase now can leave a longer one available later. Nothing here changes that, and the essay after next records a case where it goes the other way by three phrases.

It does not compute anything the quadratic construction did not. Every number this collection has published about z is reproduced exactly, which is the point — a faster construction that produced slightly different phrases would invalidate five strands of measurement rather than extending them.

And it does not remove the quadratic construction. That stays as the default in the checks, because a construction is checked against a definition and the definition is the slow one.

What a linear construction changes about a measurement #

There is a general point worth extracting, because this collection will meet it again.

A quadratic construction does not merely make a measurement slow. It changes which measurements are taken, and it does so invisibly. The cap ladder swept ten caps on a 2,048-character collection because that was what fitted in a figure; nobody decided that 2,048 was the right size at which to study a depth cap, and nothing in those essays claims it was.

The risk that creates is not error — every number there is correct about its own collection — but unexamined scope. A conclusion drawn at one size, from a size chosen by the construction’s cost, is a conclusion whose range of validity nobody has looked at.

What a quadratic construction was setting is the essay that looks, and the answer is mostly reassuring and not entirely.

The habit this is an instance of #

The structure was already here. It was built for a different field — every substring, in fewer states than substrings is about a machine whose size is capped by a theorem rather than by a rectangle — and it sat unused by the strand that needed it most for a long time.

What it took was noticing that a state’s endpos set has a minimum, and that one field turns a membership test into a locator. The change to the shared structure is one integer per state, set at creation, never updated; everything the earlier essay measured is unchanged.

A structure built for one question often answers another, and the cost of finding out is usually a field.