Every copy points right

A Lempel–Ziv index finds a pattern’s occurrences in two kinds. The primary ones cross a phrase boundary and are found by searching; the secondary ones lie inside a phrase and are produced from the occurrence they were copied from, by adding the phrase’s displacement.

The occurrences that cross a boundary is that split, and it is the idea the family is built on: only the primaries have to be searched for, and there are at most zm places to look rather than n.

The propagation that produces the secondaries is published as a queue with a visited set: take a known occurrence, find every phrase whose source region contains it, produce the copy, mark it seen, enqueue it, and repeat. The visited set is there because an occurrence might be produced twice.

It cannot be.

The fact #

A greedy self-referential parse builds its phrases left to right. Each phrase’s source is the position of an earlier occurrence of the same string — earlier because the parse has not seen the later text yet, and because a phrase copying from itself or from ahead would not be decodable in one pass.

So source < at for every copying phrase, by construction.

Checked directly on three corpora: two hundred and five copying phrases on English, a hundred and twenty-six on repetitive text, a hundred and ninety on DNA, and every one of them has its source strictly to the left of its own start.

That the check is on every phrase rather than on a sample matters here more than usual, because the property is structural — it should hold by construction, not statistically — and a structural property that holds on 99% of a parse is a property that does not hold.

The three corpora are chosen to span the shapes the parse behaves differently on. English has many short phrases; a repetitive text has fewer, longer ones; DNA has a small alphabet and therefore short phrases everywhere. All three, every phrase.

What follows #

If a phrase’s source is to the left of the phrase, then an occurrence at position p inside that source region is copied to at + (p − source), which is to the right of p by exactly at − source.

Every secondary occurrence lies strictly to the right of the occurrence it was copied from.

So process the known occurrences in text order. Each one is reached once. Each one it produces lies ahead of the cursor, so it is inserted into the sorted list ahead and will be reached later. Nothing can be produced twice, because a second production would have to come from a source further right — which the sweep has not reached, and which is behind the copy anyway.

The queue becomes a sorted frontier that only ever grows to the right, and the visited set becomes nothing at all.

The argument has one step that deserves care, because it is where a similar-looking claim would be false.

It is not enough that phrases point left. What is needed is that an occurrence inside a source region is copied to a position ahead of it, and that follows because the whole source region is to the left of the whole phrase — a phrase’s source region is [source, source + length) and the phrase itself is [at, at + length), and source < at means the two regions are offset by a positive amount.

If a phrase could overlap its own source — which a self-referential parse permits, and which is how a run of identical characters is encoded — then the source region and the phrase overlap, and an occurrence near the end of the source region is copied to a position inside the source region.

Still to the right, by at − source, which is positive. So the overlap case is covered by the same arithmetic and it is worth checking rather than assuming: a run is two phrases is where this collection established that a run is encoded by a self-overlapping phrase, and it is the case a careless version of this argument would miss.

The same substitution, one strand apart #

This is the second time in two strands that a traversal order has made a bookkeeping structure unnecessary, and the two are worth putting side by side because the parallel is exact.

The array the walk never reads is a document listing. Its previous-occurrence chain exists to answer is this the first row of this document in the range, and a walk that visits the left subrange before the right has already reported every document whose first row lies to the left. So the answer-so-far can answer it, and an array of n⌈log₂ n⌉ bits goes.

There it was left-first. Here it is left-to-right. Both times the structure being deleted was recording something the traversal order already knew.

That the same move works twice on unrelated objects is what makes it worth naming as a move rather than as two tricks. The general form: when a structure records what has already been done, ask whether an ordering makes “already” determinable from position.

Why the visited set was there #

It is worth asking what the published queue’s visited set was actually guarding against, because the answer is not “nothing”.

A queue processes occurrences in the order they were produced, which is neither text order nor any other order — it is breadth-first over the copy graph. In that order, an occurrence can be reached along two different paths: if two phrases both contain a given position in their source regions, and both produce copies, and those copies are later contained in further source regions, two chains can converge on one position.

Whether that happens depends on the parse. On a collection of d near-identical copies where each copy is one long phrase pointing at the previous one, the copy graph is a path and nothing converges — which is why the visited set is never needed on the collections this strand measures.

On a parse with nested or overlapping repetition it could. So the visited set is a correct guard against a real possibility, and the sweep removes the possibility rather than the guard: in text order, a position is reached exactly once because it is inserted once and the list holds no duplicates.

That distinction matters for anyone porting the argument. The claim is not that convergence cannot happen; it is that a sorted list in text order cannot process a position twice, whatever the copy graph looks like.

What is different about this one #

The parallel is exact in shape and not in what it is worth, and the difference is the honest part of this strand.

The listing’s chain is structure: n⌈log₂ n⌉ bits held at rest, the same width as the suffix array, and removing it made the apparatus 1.93 times smaller.

The propagation’s visited set is working memory: bits held during one query and released after it. Removing it changes no size the index reports.

So this is the first substitution in the strand whose currency is space-during-a-query rather than space-at-rest, and the two are not comparable. A constant factor, not a term measures what it is worth and the answer is smaller than the deferral naming it expected.

Why this is a property and not a coincidence #

There is a version of the ordering claim that would be much weaker and it is worth ruling out: that the parses measured here happen to point left, on the corpora tested.

They do not happen to. The parse’s definition is that a phrase is the longest prefix of the remaining text that occurs earlier, plus one literal character — and “occurs earlier” is the whole of the source’s constraint. A parser that returned a later source would be returning a source it has not read, which in a single-pass construction it does not have.

So the property is a consequence of the algorithm rather than of the data, and the check on three corpora is a check that the implementation has it rather than evidence that texts do.

That distinction decides how much confidence the substitution deserves. A statistical property holding on three corpora is worth a caveat; a structural property confirmed on three corpora is a check that the code matches its definition, and the substitution rests on the definition.

The phrases a text copies from itself is where the parse was built here and where its definition is written down, and this claim is a reading of that definition rather than a new fact about it.

The guard #

The claim rests entirely on the ordering property, so the sweep enforces it rather than assuming it.

Inside the traversal, an occurrence produced at a position at or before the current one raises. Not a check run once at construction; a check on every production, because a parse whose phrases had been modified — or a different parse whose guarantee is weaker — would silently lose occurrences rather than failing.

The rejection test forces exactly that. It takes a long phrase, turns it around so that its source is one position to its right, rebuilds the source ordering so the phrase is still reachable, and runs the sweep. The guard fires: “a phrase produced an occurrence at 756 from one at 757 — a copy must lie to the right.”

Without the guard the production would land behind the cursor, never be processed, and the answer would come back short. Short rather than wrong, which is the failure shape nothing but a comparison against the queue can see.

What the wrong order costs #

The claim is about an order, and an order is only demonstrated by running the other one.

Walk the same occurrences from the right rather than the left, inserting productions into the same list without re-sorting, and every occurrence produced to the right of the cursor lands behind it in a descending order and is never processed.

Measured on a collection of sixteen copies: the correct traversal reports sixteen occurrences and the reversed one reports two. It loses fourteen, which is 87.5%.

Every occurrence it does report is genuinely there. The answer is short rather than wrong, and nothing about it looks incorrect — a pattern search returning two positions, both correct, with no indication that fourteen more exist.

From the right, two of sixteen is that measurement, and it is the same shape as the defect a document already in the answer found one strand ago when the chainless listing’s recursion order was exchanged: nine documents reported against a true seventeen, every one of them real.

Two objects, two orders, two silent shortfalls. The fact that the same failure mode appeared twice in two strands is what turned “check the order” from a note into a rejection test in both.

Which parses have the property #

The guarantee is about greedy self-referential LZ77 and it is worth saying which nearby parses share it.

LZ77 with a window. Yes — a windowed parse’s sources are within a bounded distance to the left, which is a stronger condition.

LZ78 and its dictionary variants. Yes — a phrase extends a previously built dictionary entry, which was built earlier.

A parse with a bounded copy depth. Yes — a parse that will not follow a long chain is that structure, and capping the depth changes which source is chosen but not that it is earlier.

A grammar-based parse. Not necessarily. A straight-line grammar’s rules have no left-to-right order in the same sense, and a rule can be referenced from anywhere. So the substitution does not carry to a grammar index without a separate argument.

That last is worth flagging because grammar indexes are the neighbouring family and a reader might assume the property is about compression rather than about parsing.

What the picture shows #

The plate draws sixty copying phrases of a thousand-character collection, each as a line from source to destination.

Every line points right, which is the claim. What the picture also shows, and the claim does not, is the distribution of displacements: most lines are short and a few span most of the text.

That distribution is the parse’s own structure and it decides how the sweep behaves. A collection of near-identical copies has phrases whose sources are one copy-length to the left, so its lines are all about the same length — and the sweep’s frontier stays small, because each occurrence produces one at a fixed offset ahead.

A collection with nested repetition has a mixture, and its frontier is larger.

Neither changes correctness; both change what the sweep holds, which is a constant factor, not a term’s subject.

The insertion, and where it can go wrong #

The sweep’s implementation is a sorted list and a cursor, and there is exactly one place it can be wrong.

An occurrence is produced and inserted into the list at its sorted position. If that position is ahead of the cursor, the sweep will reach it. If it is behind, it will not.

So the correctness of the whole method reduces to: every insertion is ahead of the cursor. Which is the ordering property, restated as a statement about a data structure rather than about a parse.

That reduction is what the guard checks. It does not check the parse’s phrases directly — it checks, at every production, that the produced position exceeds the position it was produced from, which is the current cursor value.

The alternative implementation is a priority queue, which is the same thing with the ordering enforced by the structure rather than by an argument. It costs a logarithm per operation and it would not need the guard.

The choice here is the sorted list with the guard, and the reason is that it makes the ordering property visible: a reader of the code sees a check saying what the parse guarantees, rather than a heap that silently does the right thing. This collection’s habit is that the claim a structure rests on should be enforced where it is relied on, and a data structure that makes a claim unnecessary also makes it invisible.

What the ordering does not give #

Two things the property does not buy, and both are worth stating because a substitution that removes one structure invites the assumption that it removes the machinery around it.

It does not remove the scan. Finding which phrases’ source regions contain a position is a separate question with its own structure, and the scan the order does not touch is where that is measured. The sweep and the scan are two independent changes to one method, and reporting them together would report one saving as two.

It does not bound the propagation’s depth. An occurrence can be copied, and the copy copied, arbitrarily far. The sweep processes them all in text order, which is a nicer traversal than a queue and is the same amount of work.

So what the ordering buys is exactly one thing: the visited set. Everything else about the propagation is unchanged, and saying so is what keeps the result the size it is.

What a deferral asked for and what arrived #

The sentence that named this work called it the same substitution on the phrase index’s chain, which has the same name for a different object and is the largest part of a different apparatus.

Two of those three clauses hold and the third does not.

The substitution is the same: an ordering makes a bookkeeping structure unnecessary, exactly as it did for the document listing.

The object does share a name and differ: the listing’s chain is an array over rows and the phrase index’s is a queue with a visited set, and calling both “the chain” is how the two came to be expected to behave alike.

But it is not the largest part of a different apparatus. It is not part of the apparatus at all — it is query-time state, and the phrase index’s largest part is something else entirely: half an index is three permutations measures the boundary orders at 45.3% of the structure, which is where a size result in this family would have to come from.

So the deferral asked for a substitution and got one, and was wrong about what it would be worth. That is a smaller retraction than this slate’s others and it is worth recording in the same terms: the sentence naming the work was right about the mechanism and wrong about the magnitude, and only building it separated the two.