One separator, or one for each

The occurrences a join invents establishes that a concatenation without separators holds strings no document holds, and that one separator makes them unmatchable. This essay is about which separator, and it is a question with a surprisingly sharp answer.

Why anybody wants distinct separators #

A shared separator solves the artefact problem completely. Anything more is for the construction, not for the search, and there are two reasons somebody would want it.

Comparability of suffixes. Some suffix-array constructions need every suffix to be strictly comparable — no suffix a prefix of another — which a single sentinel at the end of the whole string achieves and a repeated internal separator does not. With one shared separator, two documents ending identically produce suffixes that compare equal until the separator, and then compare equal again through it into the next document’s text, so the order between them is decided by content that belongs to neither.

Identifying the document from a row. Some document-retrieval structures read the document identity out of the transform itself, which needs the separator to carry the identity. Distinct separators do that for free; a shared one needs a separate document array, which is the third essay on this ladder.

Neither reason is about correctness of the search. Both are about what the surrounding machinery can be built out of, and both are real.

What each costs #

The text is nineteen distinct symbols, so:

Two of the three are the same, and the third is 1.2 times the packed collection. Nothing about the documents changed between the rows — the same characters in the same order, joined three ways.

The reason is entirely the power of two. Twenty-two symbols need five bits and so do thirty-two; thirty-five need six. A collection of fifteen documents over a nineteen-symbol alphabet lands just past the boundary, and every character of every document pays for it.

The step is the finding, not the slope #

A cost that is invisible over most of its range and then jumps by twenty per cent is a particular kind of cost, and it is worth naming what makes it awkward.

At two documents the distinct join costs the same as the shared one — alphabet twenty-two either way, five bits. At four documents, twenty-four symbols, still five bits. At eight, twenty-eight, still five. At fifteen, thirty-five, six bits and a 1.2-fold jump.

So a developer measuring at eight documents and extrapolating sees no cost at all and concludes the distinct separators are free. The cost arrives without warning at whatever document count pushes $\sigma + d$ past the next power of two, and where that is depends on the text’s alphabet as much as on the number of documents.

This collection’s own ledger records the same arithmetic biting once before, in the opposite direction: a function computing bits for a counter was used to compute bits for an index, the two differ exactly at the powers of two, and every alphabet size and array length on this site sits at one. The powers of two are where this field’s constants live, and a measurement taken between two of them measures nothing.

On a small alphabet it is much worse #

Four-symbol text is the case this field cares most about, and it is where distinct separators hurt.

An alphabet of four needs two bits. One shared separator makes it five, which needs three — so the shared separator is not free here; it is already a fifty per cent premium, because four is a power of two and every alphabet of five or more needs a third bit.

Fifteen distinct separators make it eighteen, which needs five. That is 1.67 times the shared-separator collection and 2.5 times the raw packed text, to tell fifteen boundaries apart in a text of eight thousand characters.

The general form: distinct separators multiply the packed size by $\lceil\log_2(\sigma+d)\rceil / \lceil\log_2\sigma\rceil$, which is close to one when $\sigma \gg d$ and can be several when it is not. A genome collection — four symbols, thousands of sequences — is the worst case in this field and is exactly the corpus the field is built for.

That is the sharpest thing on this ladder, and it is arithmetic rather than a measurement: the corpora that most want document boundaries are the ones where naming the boundaries costs most.

A separator is not free even when it is free #

The four-symbol case above is worth a section of its own, because it is the one where the shared separator — the design this ladder recommends everywhere else — is expensive.

Four symbols is a power of two, so a DNA-like text packs at exactly two bits a character with nothing wasted. Adding a single character to the alphabet takes it to five, and five symbols need three bits: a fifty per cent premium on the whole collection, to hold one character that appears $d-1$ times.

There is no way around it inside a fixed-width packing, and that is the point. The three bits are what a fixed-width code charges for an alphabet of five, and the actual information content of a symbol drawn from a distribution that is four symbols at high frequency and one at $d/n$ is barely more than two bits. The premium is the packing’s, not the text’s.

Which is exactly what a compressed index does not pay. The index that is smaller than the text measures a wavelet tree with a Huffman shape, where a rare symbol gets a long code and a common one a short one, so the separators cost their own $-\log_2(d/n)$ bits each and nothing per character of document.

So the step function in the table above is a property of the packed representation, and it is the right number for a reader storing the text and the wrong one for a reader storing a compressed self-index. The two differ by exactly the gap between a fixed-width code and an entropy, which is the bits a coder emits all over again.

What it does to the structures above the text #

The alphabet is not only a packing cost. It appears in three more places.

The wavelet tree’s depth is $\lceil\log_2\sigma\rceil$ for a balanced tree, so a rank query costs one more level. With a Huffman-shaped tree — which is what this collection’s indexes use — the separators are rare and get long codes, so the mean depth barely moves and the worst case does.

The first-column table is $\sigma$ entries of $\lceil\log_2 n\rceil$ bits, which goes from 22 to 35 entries: a few hundred bits, negligible.

And the run count rises by roughly $d$, because each separator is a character occurring where nothing else does. Measured on fifteen documents: 1,854 runs with a shared separator, 1,863 with distinct ones — under half a per cent, and proportional to the document count rather than the collection size.

So the packing is the whole of the cost, and the packing is a step function of the alphabet.

What a document-retrieval structure actually needs #

The two reasons for distinct separators deserve testing rather than accepting, because one of them turns out not to be a reason.

Comparability of suffixes is real but narrow. It matters for constructions that sort suffixes by comparison and need a total order without ties; a construction using ranks and doubling, which is what this collection’s suffixArray does, breaks ties by position and needs no sentinel at all. So the requirement is a property of a particular construction algorithm rather than of suffix arrays.

Identifying the document from the transform is the one that does not survive. A structure that reads the document out of the separator character is reading it out of the nearest preceding separator, which is not something a transform supplies directly — that separator has to be found, which is a walk or a rank on something. Having the identity in the alphabet does not remove the work; it moves it.

What actually answers “which document is this position in” cheaply is a predecessor structure over the boundaries, which is the bit vector below and which is needed whether or not the separators are distinct.

So the honest case for distinct separators is one construction’s precondition, and it costs a bit a character on every document to satisfy. That is a poor trade and it is worth being explicit about, because “documents are separated by distinct sentinels” is stated as a convention in a lot of this field’s writing, without the price.

The alternative: a shared separator and a boundary vector #

There is a third design and it is the one this collection’s index uses.

Keep one shared separator, and store the document boundaries as a bit vector over the text with a one at each document’s start. The document of a position is then a rank on that vector — one operation — and the vector is $n$ bits plus a rank directory, which for eight thousand characters is about nine thousand bits.

Compare that against distinct separators on four-symbol text, where the alphabet cost is two extra bits per character over eight thousand characters: sixteen thousand bits. The bit vector wins, and it wins by more as the documents get longer, because its cost is $n$ bits regardless of $d$ while the alphabet cost is $n\lceil\log_2(\sigma+d)\rceil$.

It also composes better. A bit vector with a rank directory is a structure this field already has, is compressible when the documents are long (a sparse vector of $d$ ones in $n$ positions costs $d\log(n/d)$ bits rather than $n$), and answers the “which document” question directly rather than requiring the answer to be decoded from a transform.

This collection has the compressed version already — what is still proportional to n measures a sparse bit vector at $d\log(n/d) + o(n)$ rather than $n$ — so on a collection of fifteen documents in eight thousand characters the boundary vector costs about two hundred bits rather than nine thousand.

The fourth design: no separator at all #

Three joins are compared and the recommended one still puts a character in the text. Once the boundary vector exists, it does not have to.

The separator’s only remaining job is to make a window spanning two documents unmatchable. But a spanning window is exactly a window with a document start strictly inside it, and the boundary vector answers that in two ranks: an occurrence at $[p, p+m)$ crosses a boundary if and only if $\mathrm{rank}_1(p+m-1) > \mathrm{rank}_1(p)$. Filter the occurrences instead of poisoning the text.

The saving is the whole alphabet premium. On four-symbol text a shared separator costs a third bit a character — fifty per cent of the packed collection, 24,576 bits against 16,384 at eight thousand characters — and removing it takes the packing back to exactly two bits. A third of the collection, for two ranks per reported occurrence, on a structure that already holds the vector those ranks run on.

The precondition is one this page has already established. Distinct sentinels are needed by constructions that sort suffixes by comparison; a shared one is needed by nothing in particular; and this collection’s suffix array sorts by ranks and breaks ties by position, so it needs no sentinel — not one per document and not one at the end. The requirement that made a separator look mandatory is the same requirement the page traces to one construction and discards.

What it costs beyond the two ranks is a change in where correctness lives. With a separator, a spanning window cannot match and the index is safe by construction; without one, the index reports occurrences the collection does not contain and a filter removes them. That is a real weakening — a caller reaching past the filter gets artefacts, and the filter has to be applied everywhere an occurrence is produced, including inside a propagation queue.

So the four designs are a ladder in both directions. Distinct separators: safe by construction, and $\lceil\log_2(\sigma+d)\rceil$ bits a character. One shared separator: safe by construction, and one alphabet symbol — free on wide alphabets and fifty per cent on four. Shared separator plus a boundary vector: the same packing cost, and the document question answered in one rank. No separator, boundary vector, filtered occurrences: the raw packing, and correctness that depends on every caller going through the filter.

On nineteen-symbol text the fourth is worth nothing, because the third is already free. On four-symbol text it is worth a third of the collection — and four-symbol text with thousands of sequences is the corpus this field is built for, which is the occurrences a join invents’s problem meeting what is still proportional to n’s sparse vector and finding that the two together make the first one’s fix unnecessary.

The general shape: a cost inside a logarithm #

Every quantity in this essay is $n$ times a ceiling of a logarithm of the alphabet, and that form has two properties worth separating.

It is nearly flat. Doubling the alphabet adds one bit a character. So a design that adds a few symbols is almost always free and a design that multiplies the alphabet is almost always affordable — the logarithm is doing its job.

It is a step. The ceiling means the cost arrives all at once, at a point determined by the base alphabet, and between the steps a measurement sees nothing. That is what makes it treacherous rather than merely expensive: the flatness invites extrapolation and the steps punish it.

This collection has the same shape in three other places. The index that is smaller than the text is $n H_0$ against $n\lceil\log_2\sigma\rceil$, where the gap is exactly the difference between an entropy and a ceiling. What is still proportional to n measures the directories that a logarithm hides. And a floor on the bits is the version where the logarithm is a floor rather than a cost.

The rule that comes out of all four: when a quantity is inside a ceiling of a logarithm, measure it on both sides of the nearest power of two or do not report it.

What a separator is bought for is worth drawing before the price is settled, because the thing it prevents is not a size at all.

So the choice below is not between a cheap join and an expensive one. It is between one separator and fifteen, both of which remove every artefact, and the question is what the second one is charging for.

Which one this collection’s index uses, and why #

A shared separator and a boundary bit vector, and the choice was made by the measurement above rather than before it.

The consequence for everything downstream is that the document of a position is a rank on a bit vector, and the document of a row — which is what a listing needs — is that rank applied to the suffix array’s entry. Neither is free and neither touches the alphabet.

The one thing given up is the construction precondition, and this collection’s suffix array does not need it: it sorts by ranks and breaks ties by position, so two identical documents produce two suffixes that compare by index and the order is total.

That is worth recording as a design note rather than as a result. A convention adopted from the literature — distinct sentinels — was measured, found to cost a bit per character on the corpora this field cares about, and traced to a requirement one construction has and this one does not. A precondition is a property of an algorithm and it travels with the algorithm, and a convention that outlives the algorithm it was for is a cost nobody is choosing.

The measurement that would settle it on a real corpus #

Everything above is on generated documents at sizes a plate can draw, and it is worth saying what a reader with a real corpus should measure rather than extrapolate.

The alphabet, exactly. Not “it is text” but the number of distinct bytes or symbols, because the whole cost is a ceiling of a logarithm of it and the ceiling is where the money is. A corpus over 200 distinct bytes is one symbol away from needing an eighth bit; a corpus over 128 is at the boundary.

The document count, against the alphabet. $\sigma + d$ against the next power of two above $\sigma$ is the whole calculation, and it takes no code.

And whether the construction in hand needs distinct sentinels at all. Most do not, and the convention travels further than the requirement.

Those three numbers decide the question before anything is built, which is unusual — most of the trades in this collection need a measurement of the data’s behaviour rather than of its shape. This one is arithmetic on two integers, and it is worth doing because the answer is either “free” or “twenty per cent of the whole collection” with nothing in between.

What is being claimed #

A shared separator solves the artefact problem the occurrences a join invents measures, and costs one alphabet symbol, which is free until the alphabet crosses a power of two — free on nineteen-symbol text and a fifty per cent premium on four-symbol text, where four is itself a power of two.

Distinct separators cost $\lceil\log_2(\sigma+d)\rceil$ bits a character rather than $\lceil\log_2\sigma\rceil$: 1.2 times the shared-separator collection at fifteen documents over nineteen symbols, and 1.67 times over four — where the shared separator has itself already cost fifty per cent.

The cost is a step function, invisible at eight documents and a fifth of the collection at fifteen, so a measurement taken between two powers of two measures nothing.

The corpora that most need document boundaries are the ones where distinct separators cost most, because they have small alphabets and many documents.

And the third design beats both. One shared separator plus a sparse bit vector over the boundaries is a few hundred bits, answers the document question in one rank, and does not touch the alphabet at all — which is what this collection’s index uses, and what the next two essays are built on.