The character that costs a chain

An index that stores no text has to produce one. A transform-based index does it by walking backwards through the transform, one LF step per character, and the walk’s length is the number of characters wanted.

A parse-based index does it differently, and the difference is the subject of this essay. To produce the character at position $i$, find the phrase containing $i$; if the phrase is a literal, the character is written down there; otherwise the character is at the phrase’s source plus the offset, and the question repeats.

The chain is the structure’s read cost #

Every character this structure produces is charged at its copy depth — the number of phrases followed before a literal is reached. It is a property of the position rather than of the query, and it is decided when the parse is computed rather than when the query is asked.

That makes it unlike almost every cost this collection measures. A comparison count depends on the algorithm and the input; a cache miss depends on the access order; a copy depth depends on nothing but where in the text the character sits.

It is also unlike them in being unbounded by construction. A phrase’s source is strictly earlier than the phrase, so the chain terminates, and nothing in the parse limits how long it is. A greedy parse over a collection of copies produces a chain as long as the number of copies, because each copy is parsed as a copy of the one before it.

Half the number of copies, measured #

The mean depth across the sweep runs 2.38, 2.89, 3.89, 5.89, 9.89, 17.89 at one, two, four, eight, sixteen and thirty-two copies.

Those numbers have an obvious shape and it is the right one: the mean is about half the number of copies plus a constant. The $k$-th copy’s characters sit at depth about $k$, because the $k$-th copy is a copy of the $(k-1)$-th; averaging over a collection where each copy contributes equally many positions gives $k/2$.

The worst depth is the number of copies plus a small constant — 7, 8, 10, 14, 22, 38 — and it is reached by the positions in the last copy that were literals in the first.

Neither number is in the structure’s size, which is 7,285 bits at one copy and 8,892 at thirty-two. The size stopped growing at the second copy and the read cost grew linearly with every copy after it.

Why the mean is the wrong summary #

The distribution is reported here rather than a rate, and the reason is that the queries do not sample positions uniformly.

A search over this structure performs binary searches over the boundary orderings, and each comparison produces characters at whatever position the binary search landed on. Those positions are boundaries and their neighbourhoods, not uniform draws — and a boundary in the thirty-second copy is at depth thirty-one whatever the mean says.

So the plate reports the median, the ninetieth percentile and the worst beside the mean: at thirty-two copies they are 18, 31 and 38. A cost model using the mean would underestimate a search landing in the tail by a factor of two, and the tail is a fifth of the positions.

This is the same argument on average is not a number makes about running times and the height is a distribution makes about a randomised structure’s shape. Here the distribution is not random at all — it is a deterministic function of the parse — and it is still not summarised by its mean.

What bounds it, and what does not #

Three things might be expected to bound the depth and none of them does.

The phrase count does not. $z$ is 156 at every point of the sweep past the first, and the worst depth goes from 8 to 38 over the same range. A structure with a fixed number of phrases can have chains of any length, because a chain is a path through the phrases rather than a subset of them.

The alphabet does not. Four-symbol text gives means of 3.19, 4.70 and 10.70 at one, four and sixteen copies — the same shape at a different constant.

The text’s length does not, except through the copies. A longer base text with the same number of copies has the same depths; a shorter base with more copies has deeper ones at the same $n$.

What does bound it is a construction nobody here has built: a parse restricted so that a phrase’s source may not itself be deeply copied, or a structure of “bookmarks” that stores explicit characters at intervals along a chain. Both cost bits proportional to the bound, and both are named in the literature this strand is drawn from.

The depth is not the phrase length #

Two quantities about a parse are easy to confuse and they behave oppositely, which is worth one section because the confusion makes the trade look smaller than it is.

A phrase’s length is how much text it covers. Long phrases are what a repetitive collection produces and what makes $z$ small: one copy of a 512-character text is one phrase of length 512.

A position’s depth is how many phrases were followed to produce it. Long phrases do not make it small — they make it large, because a long phrase is a copy of a long region that was itself copied.

So the two quantities that describe a parse move in opposite directions as a collection repeats, and the one that appears in the structure’s size is the one that improves. A reader looking at the phrase-length distribution would conclude that a repetitive collection is easy for this structure in every respect; the depth is where the other half of the story is, and it is not visible in the parse’s summary statistics at all.

That asymmetry is exactly the one the tuples a summary does not report found in a quantile structure, where the resident size is reported and the peak is not. A structure’s own summary tends to contain the numbers that flatter it, not because anybody chose them but because they are the numbers the structure computes anyway.

The trade this reveals #

The parse-based index is the smallest of the three structures in this field on a repetitive collection, and this is what it pays.

An FM-index produces a character with one LF step, which is a symbol rank on a wavelet tree — a handful of bit-vector ranks and no dependence on the collection’s repetitiveness. An r-index does the same on a run-length representation, at three counted operations per step. Both have a per-character cost that is a property of the structure, which is what the text that does not have to be kept measured when it established that a self-index can hand its text back at all.

The parse-based index’s per-character cost is a property of the position, and it grows with exactly the thing that makes the structure small. A collection so repetitive that the index is half a bit a character is a collection whose characters cost thirty-eight phrase-follows each.

That is a genuine trade rather than an implementation defect, and it is the third distinct shape this collection has found in the same field: a rate to choose, a measure to depend on, and now a depth that grows where the size falls.

The counter, and why it is its own field #

The chain is counted separately from everything else the structure does, in its own field, and never folded into the character comparisons.

A search performs comparisons; each comparison produces a character; each character costs a chain. Reporting “272 character comparisons” for a search over the collection at thirty-two copies would be true and would omit that those comparisons cost 433 phrase-follows between them. Reporting only the chain would omit how many comparisons there were.

Both are reported on every plate in this strand that measures a search. The convention comes from the count somebody chose, which is this collection’s argument that a single number for the cost of an operation is a decision rather than a measurement — and the failure it warns about is exactly the one available here, since the two counts move in opposite directions as the collection grows.

A depth is a stack, and this collection has counted one before #

The chain is followed iteratively here, so it costs no call stack, and the implementation is a loop with a position and a counter.

That is a deliberate difference from the natural recursive version, and it is worth noting because a recursive one would put the depth on the stack — which this collection has a counter for. The stack nobody counts measured a quicksort’s recursion as auxiliary space and established that a call stack is space whether or not anybody allocated it, and a recursive character-producer over a collection of thirty-two copies would carry thirty-eight frames.

Written as a loop it carries none, and the depth is time rather than space. That the same quantity can be either depending on how the traversal is written is a small thing and a real one: the parse decides how many steps there are, and the implementation decides which resource they are charged to.

What a bookmark would cost #

The bound that does not exist here has a known price, and it is worth putting a number on the alternative even though nothing here implements it.

Storing the explicit character at every position whose depth exceeds $d$ turns the worst chain into $d$ steps. On the collection at thirty-two copies, capping at eight would need explicit characters for every position in copies nine through thirty-two — three quarters of the text — which is absurd.

Storing them at intervals along a chain rather than by depth is the construction that actually works: keep a bookmark every $b$ positions of the text, and a chain walk stops at the first bookmark it passes. That costs $n/b$ characters, which is a term proportional to $n$ — the exact term this whole strand exists to remove.

So the trade is not soft. A parse-based index with a bounded read cost is a parse-based index with a term proportional to the text in it, and the choice between the two is the same choice the run-based structure faces between its sampling and its walk. Every occurrence at the same price is that choice made for a different structure, and its resolution — a function with as many pieces as the measure — has no analogue here that this collection has built.

The check that must reject #

A chain that does not terminate is the failure mode, and it is easy to produce: give one phrase a source at or after its own start and the loop runs until a guard stops it.

The gate does exactly that. It takes a real parse, rewrites one phrase’s source to point at the phrase’s own beginning, and requires the structure to refuse — which it does, at the guard, with a message naming the non-termination rather than a stack overflow or a hang.

That check exists because the failure is otherwise invisible in the only place it would be noticed. A parse is produced by a greedy loop whose sources are earlier by construction; a parse read from a file, or transformed, or filtered, has no such guarantee, and the structure accepts whatever it is handed.

What this means for the strand’s headline #

The strand’s opening claim is that an index proportional to $z$ is the smallest of the three structures in this field on a repetitive collection, and this essay is the reason that claim is stated with a cost beside it.

At thirty-two copies the phrase index is 8,892 bits against the r-index’s 17,047, and the r-index answers a locate in one predecessor query per occurrence while producing characters at a fixed price. The phrase index answers a locate in two stages and produces characters at eighteen phrase-follows on average.

Which is better depends on the query mix, and the honest form of the comparison puts all three costs on one page rather than picking the axis that favours a structure. That is what the collection decides which index is small is for.

Where the depth is paid, in a real query #

The measurements above are over every position, and a query does not touch every position, so it is worth closing the loop on what a search actually pays.

A locate on this structure performs $m-1$ pairs of binary searches over the boundary orderings. Each binary search is about $\log_2 z$ comparisons and each comparison produces up to $m$ characters, so a search over a collection of 156 phrases with an eight-character pattern is on the order of a hundred comparisons and a few hundred produced characters.

Measured, on the collection at thirty-two copies: 272 character comparisons and 433 phrase-follows for the whole search. That is 1.6 follows per character produced, well under the mean depth of 17.89 — because the binary searches land on boundaries, and a boundary is where a phrase begins, and a phrase’s first character is often a literal or close to one.

So the tail is real and the query does not sample it uniformly. That is a happier finding than the plate suggests and it is not a general result: a query landing in the middle of a long copied region pays the full depth, and nothing in the search steers away from those.

The relation is exact, and it says where the cheap fix is #

About half the number of copies plus a constant is right and it is exactly right, which is worth establishing because the exactness locates the term a repair would have to remove.

Mean depth against copies: 2.38, 2.89, 3.89, 5.89, 9.89, 17.89. Subtract $k/2$ from each and every one gives 1.89. Six points, two decimal places, no residual.

Worst depth: 7, 8, 10, 14, 22, 38. Subtract $k$ and every one gives 6.

So mean depth is $k/2 + 1.89$ and worst depth is $k + 6$, and the two intercepts are the base text’s own depths — 1.89 is what its parse gives averaged over its positions, 6 is its deepest chain. The whole of the copy collection’s read cost is the base text’s parse plus one step a copy.

The four-symbol sweep confirms it rather than merely rhyming with it. Its means are 3.19, 4.70 and 10.70 at one, four and sixteen copies; subtract $k/2$ and every one gives 2.70. Same slope, different intercept — which is what a decomposition into the base text and the copying predicts, and is not what a fitted curve on one alphabet would have shown.

That changes what the bookmark trade is about. A scheme storing explicit characters every $b$ positions attacks the whole depth, intercept and slope together, and pays $n/b$ characters for it — a term proportional to the text, which is the objection this strand exists to raise. But the intercept is small and does not grow, and the entire unbounded growth is the slope: one step per copy, arising because the greedy parse points each copy at the one before it.

Among matches of equal length the parse is free to choose any earlier source. Taking the earliest rather than the most recent leaves the phrase count identical, leaves every phrase length identical, and changes only the source pointers — so the structure is the same size to the bit. On a collection of exact copies the earliest occurrence of any repeated region is in the base text, so every copy’s phrases point into the base, and the depth becomes $d_0 + 1$ at every copy count.

Worst depth 7 instead of 38, at $z = 156$ either way. Not a term proportional to $n$; not a term at all.

Two honest qualifications. The tie-break is a heuristic rather than a bound: on a general text the earliest longest match may itself sit inside a copying phrase, and nothing forces the chain to stop. And it is a construction change, so it costs whatever finding the earliest match costs, which in the quadratic parse here is nothing and in a linear one is a different question.

What it does establish is that the trade named above is softer than not soft. The cost of a bounded read is not necessarily bits; on the shape this whole strand measures it is a tie-break rule, and the reason nobody noticed is that a parse’s summary reports $z$ and the phrase lengths — the numbers a greedy rule optimises — and never the source depths it decides as a side effect. An index with z in its size is sized by the first and read at the price of the second, and the collection decides which index is small puts the three costs on one page precisely because a structure’s own summary does not.

The honest limit #

The depths are measured over every position of collections of a few thousand to sixteen thousand characters, so the distributions are exact for those collections and are properties of this parse and this generator’s texts.

The relation “mean depth is about half the copies” is a mechanism rather than a fit — it is what a chain of copies must give — and it is not checked against a fitted class, because a quantity with six points and an obvious cause does not need one.

What is not measured is a bounded-depth parse. Restricting a phrase’s source to shallow regions, or storing explicit characters as bookmarks, both bound the chain at a cost in bits, and neither is built here. So this essay establishes that the greedy parse’s depth is unbounded and grows with the repetition; it does not establish what the cheapest bound would cost.