Two at binary, five at twenty-six

Every saving in this strand is a factor in σ, and a factor in σ is a small number when σ is small.

Four alphabets, one interval of sixty-four positions, one measurement.

Binary, two symbols: the loop costs four ranks and the descent costs two. A factor of 2.0.

DNA, four symbols: sixteen against six. A factor of 2.7.

Protein, twenty symbols: two hundred against forty-two. A factor of 4.8.

Latin, twenty-six letters: two hundred and sixty against fifty-four. A factor of 4.8.

Why the ordering matters more than the numbers #

Approximate string matching over a compressed index is done, overwhelmingly, on DNA. That is where the read aligners are, where the index sizes matter, and where the error budgets are. Protein search is the second-largest use and natural-language search is a distant third.

So the ordering above is exactly backwards from where the work is. The operation is worth 4.8 on the alphabet nobody uses it on and 2.7 on the one everybody does.

That is not a reason to dismiss it — a factor of 2.7 on a search costing tens of millions of operations is a real saving — and it is a reason to be careful about which number gets quoted. A factor measured on English is about four times what a genomics workload will see.

The binary row is worth pausing on because it is the degenerate case and it says what the operation is. On two symbols the loop asks two questions and the descent enters two nodes, so both do the same work in a different order. There is no saving because there is nothing to prune: with two symbols there is nothing that can be absent without the interval being empty of one of them, which the loop discovers in one question.

That the operation degenerates rather than breaking is the right behaviour, and it is worth checking rather than assuming. A version that was somehow worse on binary would indicate an overhead in the descent’s bookkeeping that the node count is not charging for.

Where the factor comes from #

The arithmetic is short enough to write and it explains both ends.

A loop asks about each of σ symbols, and a rank walk on a balanced tree over σ symbols is ⌈log₂ σ⌉ levels at two ranks a level in this accounting. So the loop costs 2σ⌈log₂ σ⌉.

The descent, on an interval holding every symbol, enters the whole tree: 2σ − 1 nodes, of which σ − 1 are internal, at two ranks each. So it costs about 2σ.

The ratio is ⌈log₂ σ⌉, halved by nothing — the two ranks a node appear on both sides. At σ = 2 that is one; at σ = 4 it is two; at σ = 20 it is five; at σ = 26 it is five.

The measured figures are 2.0, 2.7, 4.8 and 4.8, which sit slightly under those because not every symbol is present in a sixty-four position interval on the larger alphabets — twenty-three of twenty-six on Latin, nineteen of twenty on protein.

So the worst case factor is ⌈log₂ σ⌉ and the sweep above is close to it. The best case, with one symbol present, is σ.

There is an assumption buried in that arithmetic and it is the balanced tree. On a frequency-shaped tree the loop’s cost is Σ over symbols of the code length rather than σ log σ, which is n·H₀-like and smaller — so the loop is cheaper on a skewed alphabet and the factor falls.

The descent’s cost falls too, because a shaped tree is shallower for frequent symbols and a narrow interval usually holds frequent ones. Which effect is larger is not obvious and this strand does not measure it, because every measurement here uses a balanced tree for the reason proportional to the answer, not the alphabet gives: a shaped tree makes the loop’s line depend on the text, and the comparison stops being about the descent.

So the factors here are for a balanced tree, which is the shape a search index over a small alphabet actually uses — on four symbols there is nothing to shape.

Two bounds, and the range between them #

That gives the operation’s whole envelope in two lines.

Best case, one symbol present: the descent walks one root-to-leaf path, so the factor is σ.

Worst case, every symbol present: the descent walks the tree, so the factor is ⌈log₂ σ⌉.

At σ = 4 that is a range of four to two. At σ = 26 it is twenty-six to five. At σ = 256 — a byte alphabet — it is two hundred and fifty-six to eight.

The range is enormous on a large alphabet and almost nonexistent on a small one, which is the sharper version of the ordering above. On DNA the operation’s best and worst cases differ by a factor of two, so there is nothing to be gained by knowing which regime a query is in.

What a search does, which is not the census #

The census numbers above are one interval at one width. A search is thousands of intervals of varying widths, and the aggregate factor is not the average of the census factors.

Measured on a backtracking search for eight-character patterns within one error: DNA gives 2.8 and protein gives 7.0.

Protein’s 7.0 is above its census worst case of 4.8 and below its best case of 20. That is because a search spends most of its time in narrow intervals, where few symbols are present, and the aggregate is weighted toward the good end.

DNA’s 2.8 is barely above its census figure of 2.7, because its range is 4 to 2 and there is nowhere for the weighting to take it.

So the alphabet decides not only the factor but how much the query’s shape can improve it. On a large alphabet a search’s own behaviour buys extra; on a small one it does not.

The other thing σ decides #

There is a second effect of the alphabet that runs the other way and it is worth putting beside the first.

A larger alphabet makes a backtracking search more expensive in absolute terms, because each level branches over more characters. An eight-character search within one error on twenty symbols attempts 16,800 extensions; on four symbols it attempts far fewer.

So a large alphabet gives a large saving on a large cost and a small alphabet gives a small saving on a small cost. Whether the absolute saving is larger on protein than on DNA is a different question from whether the factor is, and the answer is yes by a wide margin: 144,000 ranks saved against 38,000.

The branches an error opens is where the branching factor of an approximate search was first measured here, and its numbers are on DNA for the reason given above — that is where the workloads are. Reading the two together: the alphabet where the search is cheapest is the alphabet where this operation helps least, and the two effects partly cancel.

The dead share, by alphabet #

The mechanism the operation exploits is the dead branch, so its share by alphabet is the useful diagnostic.

On DNA at one error, 19% of extensions find nothing. On protein at one error, 55%.

That difference is the whole of why the factors differ. A four-symbol alphabet in a narrow interval usually has most of its symbols present — an interval of twenty rows over four symbols almost certainly holds all four — so there is little to prune. A twenty-symbol alphabet in the same interval holds maybe six, and fourteen extensions per node are wasted.

So the dead share is roughly 1 − E[d]/σ, and E[d] is bounded by the interval’s width. On a narrow interval and a large alphabet the share approaches one.

There is a third thing the alphabet decides and it is the one that limits how far any of this can be pushed. The number of symbols an interval can hold is bounded by its width. An interval of six rows holds at most six distinct symbols, whatever σ is.

So on a large alphabet the deep intervals of a search are automatically in the good regime — six symbols out of two hundred and fifty-six is a factor near the ceiling — and on a small alphabet they cannot be, because six rows over four symbols probably holds all four.

That bound is why the dead share and the alphabet are not independent, and it is why a single sweep over σ tells most of the story. The interval’s width and the alphabet interact through min(width, σ), and once the width is below σ the alphabet stops mattering to the descent while continuing to matter to the loop.

What this means for a claim #

The general form is one this collection keeps arriving at and this is a clean instance.

A factor quoted without its alphabet is a factor about one workload. The operation’s saving spans 2.0 to 4.8 across four ordinary alphabets and 2.8 to 7.0 across the same four on a real search, and there is no single number.

That is the same shape as a sixth of what, exactly, where a saving quoted as “about a sixth” turned out to be 14.0% at one sampling rate and 30.5% at another. The dial there was a setting; here it is a property of the data.

What makes the alphabet version worse is that it is not a choice. A sampling rate can be tuned; an alphabet is what the data has. So a reader on DNA cannot get to protein’s factor by adjusting anything, and quoting protein’s factor to them is not merely imprecise but unactionable.

Reading the two sweeps together #

Two axes have now been swept and they are not independent, so it is worth saying how a reader should combine them.

Proportional to the answer, not the alphabet fixes σ and moves d, producing a factor from σ down to log σ. This essay fixes d/σ roughly and moves σ, producing a factor from 2.0 to 4.8.

The single expression covering both is the ratio of the loop’s 2σ⌈log₂ σ⌉ to the descent’s 2d(1 + log₂(σ/d)), which is σ⌈log σ⌉ / (d + d log(σ/d)). Two parameters, one surface, and the two sweeps are two cuts through it.

The cut that matters for a workload is neither of them. It is the distribution of (d, σ) pairs a real search visits, weighted by how much work each costs — and that is what the search measurements report as a single aggregate factor. Protein’s 7.0 is that weighted aggregate, and it sits above the census figure because the weighting favours narrow intervals.

So the two sweeps explain the aggregate rather than predicting it, and the aggregate is the number a reader should use. That ordering — sweeps for the mechanism, aggregate for the decision — is the one this collection has settled on wherever a cost has two arguments.

Where the operation is worth most #

Collecting the conditions under which the factor is large.

A large alphabet. The factor’s ceiling is σ and its floor is log σ, and both grow.

Narrow intervals. Which means a long pattern, a specific query, or a deep position in a search.

A high error budget. Which produces narrow intervals in quantity — the dead share rises from 31% to 75% between zero and two errors on protein.

And a search that branches at all. An exact search knows which symbol it wants, and enumerating every present symbol to hand back one of them costs about twice the walk. The saving that is a loss is that measurement.

Three of those four are properties of the query rather than of the data, which is the encouraging part: a reader on a small alphabet can still reach the good end of the range by asking harder questions, and asking harder questions is what the operation exists to make affordable.

The alphabet that is not the alphabet #

There is a way to change σ without changing the data, and it is worth naming because it turns this essay’s ordering from a fact into a design choice.

Index pairs of characters rather than characters. A DNA text over four symbols becomes a text over sixteen, of half the length; over triples it is sixty-four symbols and a third the length. The searches are then over a coarser alphabet with a finer factor, and this operation’s saving rises from 2.7 toward 4.8.

That is a real technique and it has costs this strand does not price: patterns must align to the grouping or be searched at every offset, the wavelet tree gets deeper per symbol, and the sampling and marks all change shape. It is named here because the alphabet appears in this essay as a fixed property of the data, and it is not quite one.

What it does not change is the ordering of the workloads. A grouped DNA alphabet is a design decision made for other reasons — mostly cache behaviour — and a search over it pays elsewhere for what it gains here.

The byte alphabet nobody measured #

There is a case at the far end of the range that this strand does not measure and that is worth naming, because it is where a general-purpose implementation lives.

A byte alphabet — 256 symbols — has a factor of 256 in the best case and 8 in the worst. Real text over bytes uses maybe eighty of them and a narrow interval holds a handful, so a search on it would sit far toward the good end.

That is not measured here for a reason: the texts this collection generates are over the alphabets named above, and building a byte-alphabet corpus that is representative of anything would be building a corpus rather than an instrument. The prediction from the arithmetic is a factor in the tens, and it is a prediction.

The one thing worth saying about it without a measurement is that the loop on a byte alphabet is 256 rank walks a node, which is an implementation nobody ships — real byte-alphabet searches use a different structure entirely. So the comparison would be against something that does not exist, and a factor against a straw implementation is not a factor.

What the small alphabet gets instead #

Ending on “DNA gets 2.8” would be a fair reading of this essay and an incomplete one, because the same field has other savings whose alphabet dependence runs the other way.

The half that is never asked where drops a bidirectional index’s reverse locating apparatus, and that saving is a share of the structure — it does not depend on σ at all. The array that says where is twice the samples replaces a mark vector with a sparse representation, and that saving depends on the sampling rate rather than the alphabet.

So a DNA workload getting 2.8 from this operation is not a DNA workload that has been left out of the field’s improvements. It is one whose improvements come from elsewhere, and the strand that measures three savings together — three savings on one structure — is where the composition is worked out.

The general point is that a strand reporting a σ-dependent factor should say which of the field’s other savings are not σ-dependent, so that a reader on a small alphabet knows whether they have been served or skipped. Here they have been served, by different machinery.

What to quote #

Two numbers and a condition.

On DNA, 2.8 on an approximate search. That is the workload most of this field is about and it is the smallest of the factors.

On protein, 7.0 at the same budget. That is the second-largest workload.

And the condition: the search has to branch. Everything above is about a query that extends by more than one symbol, which is an approximate search or a wildcard or a regular expression. An exact search gets nothing from this operation and pays about twice for it.

Anything else — a factor from a census, a factor from natural language, a factor with no alphabet attached — is a number about a different measurement.