The array the walk never reads

Muthukrishnan’s document listing is one observation and one walk.

The observation: inside the rows of a pattern, the first row belonging to each document is exactly the row whose previous-occurrence entry falls outside the range. So the distinct documents are the positions where C[i] < lo, and finding all of them is a range minimum, a report, and two recursions.

A list of documents is not a list of occurrences is where that is built, and the cost that is the size of the answer is what it buys.

The array in that observation is read once per step and its value is used for exactly one comparison. This page is about what the comparison is asking.

What C[at] < lo means #

C[i] is the previous row, in the index, holding the same document as row i — or −1 if there is none. The chain runs backwards through each document’s rows.

So C[at] < lo says: the previous row of this document is before the range under consideration. Which is to say: this is the first row of this document inside the range.

And “first inside the range” has a second reading, once a walk is under way. If the walk visits the rows in an order that finishes everything to the left before starting on the right, then the first row of a document inside the range is exactly the row at which that document is reported for the first time.

The test is asking whether the document is new. It is phrased as a question about a number.

Answering it from the answer #

The walk keeps a list of the documents it has reported — it has to, that is the output. So the question “is this document new” is answerable by looking at the list, and the array is not needed for it.

That substitution is Sadakane’s, and the arithmetic it produces is the whole of this strand: the chain is not a smaller structure, it is no structure at all. What remains is the range minimum over it, which stores the shape of an array rather than its numbers, plus one bit per document.

The size consequence is the next page but one. This page is about whether the two tests are the same test.

The proof obligation #

They are, and it is not obvious, because the equivalence has to hold in both directions and one of them depends on the order the walk takes.

If C[at] < lo, no row of that document inside the range comes earlier, so nothing already visited could have reported it. New.

If C[at] ≥ lo, the document has an earlier occurrence inside the range, at position C[at]. That position is to the left of the current subrange — because at holds the minimum chain value in the subrange, and any position inside it whose chain entry were smaller would contradict that. So a walk that finishes everything left of its current subrange before entering it has already visited that position, and reported the document. Not new.

The second half is the one that binds, and it binds only for a walk that recurses left first.

What happens when the order is wrong #

The check that makes this a claim rather than a story is the one that gets it wrong on purpose.

Recurse right before left — two lines exchanged, everything else identical — and the walk loses documents. On a collection of 24 documents, over 40 patterns, it lost some on 5% of them, worst case reporting 9 documents where the true answer is 17.

The failure is silent in the worst way. Every document it reports is genuinely there; the answer is simply short. Nothing downstream can tell, because a document listing has no way to know what it did not find.

That is why the walk’s direction is not a tuning parameter here. It is the algorithm, and the version with it reversed is in the gate as a defect that must be caught.

The other piece of per-query state #

The reported set has to be a set, and the natural implementation is a bit per document. That raises a question the chain version never had: clearing it.

A bitmap of d bits, cleared by walking it, costs d per query — on a structure whose entire argument is that a query costs the size of its answer. On a collection of two thousand documents, answering a query about three of them, that would be the dominant cost and it would undo the method.

So it is cleared by the answer: the walk remembers which documents it set, and unsets exactly those. That is |answer| writes, which is inside the cost the method already claims.

Measured on a collection of 512 documents: 166 documents in the answer, 166 clears, and never the 512 a full sweep would cost.

And the mirror check: leave the bitmap dirty between queries, and a later query silently under-reports — reporting 0 documents where the answer is 3, because every one of them was marked by an earlier query. Same failure shape as the wrong walk order, same silence.

What the range minimum still has to do #

Removing the chain does not remove the structure over it, and the reason is worth being precise about.

A range minimum answers where is the smallest value in this range. It is built from the values — the Cartesian tree of the array is what it stores — but once built it holds only the shape: 2n parentheses, plus the machinery to answer excess queries on them. The shape a range question is about is the construction, and its whole argument is that a range minimum does not store numbers.

So the chain is needed at build time and never afterwards. The structure here builds it, hands it to the range minimum, and drops it — and the range minimum is told to forget its reference too, so that asking it for a value raises rather than returning one.

That last part is a check rather than tidiness. A structure that still holds the array and merely promises not to read it is a structure whose size is unchanged, and the number on the next page but one would be a claim about code somebody read.

What the walk costs now #

Identical to what it cost before: the same number of range-minimum queries, at every occurrence count on the sweep, because the two tests take the same decisions at the same subranges.

That is the claim assertTheWorkIsUnchanged makes, and it is stronger than the two methods returning the same answer. Two methods that reached the same set by different routes would return the same answer and would not be the same algorithm — which is the distinction the definition is not the algorithm is about.

Where this goes #

Three pages follow this one.

A document already in the answer is the substitution as an algorithm: the walk written out, the two checks that must reject, and the exhaustive comparison against the chain version.

What the chain cost is the size: n⌈log₂ n⌉ bits, as wide as the suffix array, the largest single part of the listing apparatus and now absent.

The apparatus that is smaller than its index is the accounting all together — from 2.70 times the index it sits on to 0.84.

Why the observation is worth restating #

Muthukrishnan’s observation is usually presented as a fact about the chain, and it is worth putting it the other way round once, because the other way round is what makes the array removable.

The problem is: given a set of rows, report the distinct documents among them, at a cost proportional to the number of distinct documents rather than to the number of rows.

The obstacle is that “distinct” is a global property. A row’s document is one array read; whether that document has appeared elsewhere in the range is a question about the whole range, and answering it by looking is exactly the scan the method is trying to avoid.

The chain turns that global question into a local one. Each row carries a pointer to the previous row of its own document, so whether a row is the first of its document in the range is answerable from the row itself plus the range’s start — one comparison, no search.

And then the second observation, which is the one this page is about: a walk that visits rows in a disciplined order has a second source for the same fact, because it has been recording the documents it reported. The chain localises the question; the walk’s own output answers it.

The range minimum’s part #

It is worth being clear about why a range minimum is the right structure, since the test is a comparison against a threshold rather than a search for an extreme.

The walk needs to find every position in the range whose chain entry is below lo. Those positions are scattered, and there may be one or a thousand. A range minimum finds the smallest, which is the most promising candidate; if even that one fails the test, no position in the subrange can pass, and the whole subrange is pruned.

That is the recursion’s engine. Report the minimum if it passes, then recurse either side of it — and each recursion either finds another qualifying position or terminates immediately. So the number of queries is bounded by twice the answer’s size plus one, which is the output-sensitivity the whole apparatus exists for.

The structure could be anything answering range minimum — and the choice matters here in the way a promise about the rank is about, which is that a structure’s constant decides a crossing its asymptotics cannot see. A segment tree costs 2n numbers and answers in a logarithmic number of visits; the succinct version costs the shape of the array and answers in a constant number of steps. The shape a range question is about prices both, and the difference decides where the crossing against a scan sits.

What the substitution needs from the walk #

Two properties, and both are worth stating because a different walk would break them.

Left-first. Every position to the left of the current subrange has been visited before it. That is what makes “already reported” equivalent to “not the first in the range”.

And no pruning below a qualifying position. The recursion continues into both halves whenever the test passes; it stops only when the test fails. So a document’s first row is never skipped: if it were inside a pruned subrange, that subrange’s minimum would have a chain value at least as small, which contradicts the pruning condition.

The second is what makes the argument airtight, and it is the part that is easy to lose. An implementation that added a cheap extra prune — stop when the answer reaches some limit, or when the subrange is small — would keep the first property and break the second, and would lose documents in exactly the same silent way the wrong recursion order does.

What the test costs in each form #

Both tests are cheap and they are not the same cheap.

The chain version reads C[at] — one array access, into an array of n row numbers — and compares it against a number in a register.

The chainless version reads D[at], which it needs anyway to report the document, and then reads one bit of a bitmap indexed by document. That is one extra access, into a structure of d bits, which on a collection of a few hundred documents fits in a cache line or two.

So the substitution costs one small access per step and saves an array of n⌈log₂ n⌉ bits. On the collections here that is 2.4 million bits against a few hundred extra byte reads per query, which is not a trade anybody has to think about.

What it does cost is the invariant, and invariants are paid for in attention rather than in cycles.

Where the same shape might appear again #

Worth asking, since the move was worth two million bits here.

The pattern is: a structure storing, per element, a fact that an algorithm’s own accumulating output determines. The chain stores “the previous row of my document”; the walk’s output determines whether that document has been seen, and the two are equivalent under the walk’s order.

Two other places in this collection have the same smell and neither has been checked. The document array itself stores, per row, which document it belongs to — a fact the collection’s boundaries determine, and which a rank over a bit vector marking document starts could answer instead, at a cost of one rank rather than one read. That is a real alternative and it trades bits for operations rather than removing them.

And a phrase index’s chain of previous occurrences, which is the largest part of the apparatus in the parse strand and has the same name for a different object, was priced there and not questioned. Whether the same substitution applies is not obvious — the walk there is a different walk — and it is exactly the question this page’s method would ask of it.

The first of those two, priced #

The document array is named above as a real alternative that trades bits for operations, and left there. The trade is one division and it is worth doing, because the answer is larger than the substitution this page is about.

The array holds one document number per row: $n\lceil\log_2 d\rceil$ bits, which on the 131,327-row collection with 256 documents is 8 bits a row and 1,050,616 bits.

The alternative holds a bit per text position, set where a document starts, with rank support over it. The document of row $i$ is then $\mathrm{rank}_1(SA[i])$. The payload is $n$ bits — 131,327 — and rank support is a quarter of that on the usual two-level directory, so about 164,000.

A saving of 886,000 bits, or 84% of the array. Even at a directory overhead of 100% rather than 25% it is 75%, so the conclusion does not depend on the constant.

What it costs is one rank and one suffix-array read per step, where the array cost one read. The walk is output-sensitive, so that is a couple of operations per document reported and it stays inside the cost the method already claims — the same shape of trade as the bitmap cleared by the answer, and about as cheap.

The condition it needs is that $SA[i]$ be available. Here it is: the index this apparatus sits beside is a suffix array and a text, so the value is one array read. In a compressed self-index it is not, and recovering it costs LF steps against a sampling rate — which is where this substitution would stop being nearly free and start being the trade the sentence above describes.

The size consequence is the interesting part, because it does not stop at the array. The apparatus that is smaller than its index reports 2,534,726 bits after the chain is gone, which is 0.84 times the index. Take 886,000 off and it is 1,648,000 bits — 0.55 times the index, and the array stops being 41% of what remains.

And it removes the one place that accounting gets worse. The apparatus climbs back over the index at 2,214 documents entirely because the array costs 12 bits a row there rather than 4. A start-marking bit vector costs one bit a row whatever the document count is — the document numbers live in the ranks rather than in the cells — so the same collection cut into two thousand documents gives 0.54 rather than 1.01.

The apparatus becomes independent of the document count, which is the property the size sweep on that page is entirely about lacking. On the shape where the listing structures are least affordable, this is the change that makes them affordable.

None of which is a measurement, and the distinction matters on a page whose own result is checked against exhaustive search at every step. It is the arithmetic of a structure this collection has built elsewhere applied to a place it has not been put, with its per-step cost stated and its one precondition named. What would settle it is building it and re-running the sweep — and the shape a range question is about is the warning attached: that strand’s succinct structure spends five times its payload on the machinery that makes it answerable, so a rank directory quoted at a quarter is an estimate rather than a measured constant.

What makes this findable #

A note on method, since the result is a deletion rather than a construction.

The chain was in a size table. That table was published when the apparatus was built, with the honest conclusion attached — the machinery costs about three times the index it sits beside — and it listed four parts with a number against each.

Reading it is what raises the question. The chain is n⌈log₂ n⌉ bits, exactly the suffix array’s width, and it exists to answer one comparison per step of one walk. A part that large answering a question that small is an invitation, and the invitation is only visible because the parts were separated.

That is the whole of the method: publish sizes as sums, then read the sum. An index has a size is the theme, and its practical content is that a structure quoted as one number is a structure nobody can subtract from.

The same reading is what produced the counting-only index in the neighbouring strand — five parts, two of them answering a question one half of a bidirectional index is never asked — and both results are deletions found by looking at a table rather than at code.