Two currencies for one separator

A collection of documents has to decide what to put between them, and there are exactly three answers.

Run them together and the collection is one text. Put one shared marker between them and a pattern containing that marker can never match, so no reported occurrence spans a boundary. Give each document its own marker and, in addition, the marker itself identifies the document.

One separator or one for each priced those three on prose and found the arithmetic: the third option raises the alphabet by d, and when σ + d crosses a power of two every character of every document needs another bit. On a collection of two thousand short documents that was seven bits a character becoming twelve.

That is one currency. This essay is about what happens when the same three choices are priced in the other one, on a collection where the other one matters.

The two prices, side by side #

Thirty-two near-identical documents over a twenty-one symbol alphabet.

Running them together: sixteen thousand three hundred and eighty-four characters, twenty-one symbols, five bits a character, one thousand and seventy-four runs. That is the baseline everything else is measured against.

One shared separator: twenty-two symbols, still five bits a character, so the packed cost rises by 0.2% — the length of the text, one character per boundary. The run count is one thousand and seventy, which is three fewer than the concatenation.

Distinct separators: fifty-two symbols, which crosses the thirty-two boundary, so every character needs six bits rather than five. The packed cost rises by 20.2%. The run count is one thousand one hundred and five, a rise of 2.9%.

The same change costs a fifth of the text in one currency and a thirty-fifth in the other. That is not a small discrepancy to be reconciled; it is two correct measurements of two different things, and which one a collection actually pays is decided by which structure it is going into.

It is worth being exact about where the 20.2% comes from, because a step function has a habit of being quoted as though it were a rate. The packed cost of a text is n⌈log₂ σ⌉ bits, and both factors move: n grows by d − 1 characters and σ grows by d − 1 symbols. On this collection n goes from 16,384 to 16,415, which is 0.19%; σ goes from 21 to 52, and ⌈log₂ 52⌉ is 6 where ⌈log₂ 21⌉ is 5. So 19.9 of the 20.2 percentage points are the ceiling function and 0.3 are the extra characters.

That matters because the ceiling is discontinuous. A collection of eleven documents over twenty-one symbols reaches σ = 32 exactly and pays five bits; a collection of twelve reaches 33 and pays six. One more document costs a fifth of the whole text. Nothing about the twelfth document is special and nothing in the collection has changed by more than a hundredth of a per cent, and the size of the packed representation jumps by twenty per cent.

The run cost has no such behaviour. It is the number of changes in a block, and adding one more entry to that block adds at most one change. It is continuous in the document count in the only sense a discrete quantity can be, and it is what a reader would expect a cost to look like — which is part of why the discontinuous one is the one that surprises.

Which structure pays which #

A structure whose size is n·H₀ — an entropy-bounded self-index built from a wavelet tree over the transform — pays the first column. Its size is the text’s zeroth-order entropy, and adding d symbols that each occur once raises that entropy by very little in principle and by a whole bit a character in practice, because a wavelet tree’s depth is a code length and code lengths are integers when the shape is fixed.

A structure whose size is proportional to the run count — the run-length index, the r-index — pays the second column. Its transform is stored as heads and lengths, so the number of runs is the number of things stored, and the alphabet appears only in the width of a head.

The index that does not notice draws all three of those structures against the copy count and shows how far apart their sizes go. The point here is narrower: the same design decision has two prices and they are not proportional, so a collection that has chosen a structure has also chosen which of these numbers is its cost.

There is a subtlety in that last sentence. A run-length index does not charge nothing for the alphabet: its run heads are stored in a wavelet tree, and that tree’s depth follows the alphabet exactly as the full index’s does. The difference is that there are r heads rather than n characters, so the alphabet’s cost is multiplied by the run count rather than by the text’s length. On this collection r is about a fifteenth of n, so a bit added to every head costs a fifteenth of what a bit added to every character costs.

That is the general shape of every size in this family and it is worth carrying: an alphabet cost is multiplied by however many symbols the structure actually stores. A structure storing n symbols pays it n times, one storing r runs pays it r times, and one storing z phrases pays it z times. The three indexes in this collection differ mostly in that multiplier, and the separator decision interacts with it directly.

The gap grows with fragmentation #

The natural expectation is that the two currencies converge as the collection gets more fragmented, because at some point the separators are a large fraction of the characters and everything must feel them. They diverge instead.

At a hundred and twenty-eight documents of a hundred and twenty-eight characters, the separators are just under one per cent of the text by count. The alphabet is now σ + 128, which crosses another power of two, so the packed cost rises again — a seventh bit for texts over a twenty-one symbol base. The run cost stays where it was, because the run cost is the entropy of a hundred and twenty-seven ending characters and there are still only a handful of distinct endings.

The mechanism for the divergence is that the two costs have different arguments. The packed cost is ⌈log₂(σ + d)⌉ per character of the whole collection, so it is a step function of d multiplied by n. The run cost is the number of changes in a block of d − 1 characters, so it is at most d and typically far less. One is n log d and the other is d, and n is much larger than d in every collection worth the name.

Stated that way the divergence is obvious in hindsight, and it is still not what anyone predicts, because the phrase “distinct separators are expensive” carries no information about which of n and d it is expensive in.

Two further things move with d and neither of them helps. The number of characters the separators add is d − 1, which is a term proportional to the document count in the length of the text — small, but it is there and it is paid by every structure. And the sampled-position array of a self-index, which is n/s values of ⌈log₂ n⌉ bits, grows with the same n. Those are second-order beside the ceiling function, and they are the reason a fragmented collection is slightly larger in every structure even before the alphabet is considered.

The one term that genuinely does not move is the phrase count. Cutting the text into a hundred and twenty-eight documents raises z by three per cent, and giving each document its own separator raises it by eleven — because a phrase cannot copy a separator it has never seen, so each distinct separator forces at least one literal phrase. Eleven per cent of a phrase index is a real cost and it is still the smallest of the three columns.

The correctness argument, and where it lands #

The reason to want distinct separators at all is that a shared one does not prevent everything.

With one shared marker, a pattern containing that marker can never match — so no reported occurrence spans a boundary, which is the property the join was for. But a query that legitimately contains the marker cannot be asked, and more importantly the collection still contains strings formed by a document’s tail, the marker, and the next document’s head. Those strings are in the index. A pattern drawn from a document cannot contain the marker, so it cannot match one of them, which is why the shared marker is enough for pattern search. It is not enough for anything that walks the index directly — a longest-common-substring computation, a repeat finder, a suffix-tree traversal — because those enumerate strings rather than search for one.

The occurrences a join invents measured the invented strings on a concatenation and found that on near-identical documents almost every window spanning a join is a string no document holds. Those are exactly the collections where the invented strings are most damaging, and — by the ending mechanism — exactly the collections where the separator is cheapest in runs.

That is a coincidence rather than a theorem, and it is a useful one. The careful choice and the cheap choice usually agree on a repetitive collection. On prose they do not, and prose is also the case where the invented strings are least likely to be matched by anything a reader asks for.

There is one more asymmetry worth recording, because it decides what a query can be. With distinct separators the marker itself identifies the document, so an occurrence’s document can be read by extracting backwards from the occurrence until a marker is reached. That is an extraction of expected length n/d characters, each costing an LF step, so it is a query-time cost proportional to the average document length — which on a collection of short documents is cheap and on a collection with one long document is not.

With a shared separator that route gives the document index only if the separators are counted, which is a rank over the separator’s own rows and is one operation. So the shared separator is not merely cheaper; it supports the attribution query at a lower cost, provided the structure can rank a symbol, which every structure here can.

That inverts the usual reason for reaching for distinct separators. They are chosen because they make attribution direct, and on these structures attribution is more direct with the shared one.

What a real decision looks like #

Put the two currencies and the correctness question together and the decision has a shape.

A collection heading for an entropy-bounded index, with many documents, should use one shared separator and accept that index-walking operations see the joins. The distinct-separator cost is a fifth of the structure and it buys a property most workloads do not use.

A collection heading for a run-length index should feel free to use distinct separators, because the cost is three per cent and the run count is the only thing that structure charges for. That is the opposite recommendation from the same corpus, and it is not a matter of taste.

A collection whose documents end unpredictably — arbitrary cuts through prose — pays about a run per boundary, and at that point the run cost of distinct separators is comparable to the run cost of the boundaries themselves. The two decisions stop being separable, and both of them should be made against a measurement rather than against a rule.

Underneath all three recommendations is a measurement that takes a second and that almost nobody makes: read the last character of every document and count the distinct ones. That single number decides the run cost of the whole boundary decision, and it is available before any structure has been built. A collection reporting one distinct ending can be cut and marked freely as far as the run-based structures are concerned. A collection reporting twenty is going to pay about a run per boundary whatever it does, and should be cut as coarsely as the workload allows.

The third option nobody prices #

There is a fourth answer to the original question that this collection has never built, and it belongs in the accounting even though it is not measured here.

Instead of a marker in the text, keep a bit vector over the n positions with a one at each document start. That is n bits plainly, or — since it has d ones in n positions — about d(2 + log₂(n/d)) bits in a sparse representation. At thirty-two documents over sixteen thousand characters that is a few hundred bits, against the several thousand a distinct-separator alphabet costs and the several dozen a shared separator costs in runs.

It does not do the same job. A bit vector says which document a position is in, which is what a document array does; it does not stop a pattern from matching across a boundary, because the text still contains the concatenation. So it is the right structure for the which document question and the wrong one for the no spanning matches question, and a collection needing both needs both.

This is worth stating because the three joins are usually presented as an exhaustive choice, and the fourth option is what a real system does — a shared separator for correctness and a sparse bit vector for attribution — at a total cost of 0.2% of the packed text plus a few hundred bits. Neither of the two expensive columns above is necessary.

The bit-vector option also composes with the compression this field is about, which the separator options do not. A bit vector with d ones in n positions is exactly the shape the marks that are almost all zero is about, and the same Elias–Fano representation applies: d(2 + log₂(n/d)) bits, which at thirty-two documents over sixteen thousand characters is under three hundred. Compared with the three thousand two hundred bits a sixth bit per character costs, the difference is not a trade-off.

What the earlier measurement was actually about #

The prose collection this arithmetic was first measured on is worth revisiting, because the two currencies were not separated there and the conclusion drawn was about the wrong one.

Two thousand documents of two hundred characters found that a separator per document costs nothing on twelve documents and 71% on two thousand — a step function crossing five powers of two as σ + d went from 115 symbols to 2,321, seven bits a character to twelve. That is the packed cost, and it is the right number for the structure that collection was heading into.

What was not measured there is the run cost, and on that collection it would have been substantial for a reason that has nothing to do with the document count. The captions were arbitrary prose, so they ended with many distinct characters — a comma, a full stop, a letter, a digit — and by the ending mechanism each boundary would have cost close to a full run. Two thousand documents, two thousand runs, on a collection whose transform holds a few tens of thousands.

So the same collection would report 71% in one currency and something like five per cent in the other, and the conclusion “distinct separators are unaffordable at this scale” is a conclusion about a structure rather than about the collection. The crossing that never arrives drew the other half of that collection’s story, and neither essay named the structure whose cost it was quoting.

Two numbers, one change #

The general form of this is a rule about how to report a cost, and it is one this collection keeps arriving at from different directions.

The half that is never asked where reported a saving that turned out to be 14% or 30% depending on a dial nobody quotes. A sixth of what, exactly made the general case: a share is a share of something, and quoting it without the denominator is quoting a number about nothing.

This is the same shape one level up. A cost is a cost in something, and the two somethings a compressed index is built out of — the entropy of the text and the runs of its transform — disagree by an order of magnitude about one of the commonest decisions a collection makes. Neither is the real cost. The real cost is whichever one the structure charges, and naming the structure is not optional.