Half an index is three permutations

A Lempel–Ziv index over four thousand characters with two hundred and twenty-six phrases: 11,978 bits.

The parse — a length, a source and a literal per phrase — is 6,554 of them.

The boundary orders are 5,424. Forty-five per cent of the structure.

What the three orders are #

A primary occurrence crosses a phrase boundary, and finding one means splitting the pattern and asking two questions about each split point.

Which boundaries have text starting with the right half? That needs the boundaries sorted by the suffix beginning at them — bySuffix.

Which boundaries have text ending with the left half? That needs them sorted by the reversed prefix ending at them — byPrefix.

And is a given boundary inside the second range? That needs the position of a phrase in byPrefix, which is its inverse — rankInPrefix.

Three arrays of z entries at ⌈log₂ z⌉ bits each: 1,808 bits apiece.

One thing the three orders are not is a suffix array. A suffix array over the text has n entries; these have z, one per phrase boundary, and that difference is the whole reason the family is small. The orders are a suffix-array-like structure restricted to the boundaries, which on a repetitive collection is a hundredth of the positions.

So a reader who sees “three orderings of z elements” and thinks it sounds like a lot should compare against the alternative: an index over the same text with a full suffix array is n⌈log₂ n⌉ = 49,152 bits on this collection, against the whole phrase index’s 11,978.

Forty-five per cent of a structure that is a quarter of the obvious one is not a large number. It is a large share, which is a different thing, and the reason it is worth an essay is that shares are where the next saving is.

The one that is an inverse #

rankInPrefix is the inverse permutation of byPrefix. Given one, the other is a linear-time computation and a z-entry array.

Both are stored, and nothing in the index needs both at once.

The search walks a range of byPrefix — or of bySuffix, whichever is smaller — and tests membership in the other. Those are two different operations on two different arrays, and the membership test is what rankInPrefix exists for.

So the index stores a permutation and its inverse because it does two things with one ordering: iterate it and index into it. That is a completely ordinary reason and it is a time-for-space choice that has never been priced here.

1,808 bits — fifteen per cent of the whole index.

What the alternative is #

Storing a permutation and answering both directions from one array is a solved problem with a published shape: keep the permutation and a sampling of shortcut pointers, so that π⁻¹ is answered by walking a cycle to the nearest shortcut.

At a sampling of one in t, the structure is z log z + (z/t) log z bits and π⁻¹ costs t steps. At t = 4 that is a quarter of an extra array rather than a whole one, and four steps per membership test.

So the choice is: 1,808 bits, or 452 bits and four steps per test.

Whether that is worth taking depends on how many membership tests a search performs, which is the points this collection’s phrase index already counts — it is the number of candidates the intersection examines, and it is reported rather than assumed away.

That number is available and the trade is not measured. This essay prices the option; it does not take it.

There is a cheaper alternative to a shortcut structure that is worth mentioning because it costs nothing and does not always apply: iterate the other array instead.

The search filters the smaller of the two ranges against the other’s rank window. If it always filtered byPrefix — walking that range and testing membership in bySuffix — then the inverse it needs would be of bySuffix rather than of byPrefix, and the index would still store two orders and one inverse.

What it cannot do is avoid an inverse altogether, because the two operations are iterate-one and index-into-the-other, and whichever way round they are assigned, one array is being indexed into by phrase identity.

Unless the filtering is always done on the same side — which loses the “smaller range” optimisation and costs whatever that is worth. The index counts the points examined, so that trade is measurable and is not measured here.

Why the orders are so large #

Forty-five per cent is more than a reader would guess and the arithmetic explains it.

The parse costs z(2⌈log₂ n⌉ + ⌈log₂ σ⌉) — two positions and a literal per phrase. At n = 4,096 and σ = 22 that is z(12 + 12 + 5) = 29z.

The orders cost 3z⌈log₂ z⌉. At z = 226 that is 3z·8 = 24z.

So the two are within twenty per cent of each other, and the reason is that ⌈log₂ z⌉ is not much smaller than ⌈log₂ n⌉ — eight against twelve, on a collection where the parse has a phrase every eighteen characters.

On a more repetitive collection the gap widens in the orders’ favour. A collection where z is a hundredth of n has ⌈log₂ z⌉ four bits below ⌈log₂ n⌉, so the orders are relatively cheaper. On a less repetitive one they approach the parse.

What a permutation costs to store #

Since three of the four parts are permutations, it is worth being precise about what one costs and what it could cost.

A permutation of z elements has z! arrangements, so it carries log₂(z!) bits of information. By Stirling that is z log₂ z − 1.44z, which at z = 226 is 1,489 bits.

Stored as an array of indices it is z⌈log₂ z⌉ = 1,808. So the plain representation is 21% above the information content — which is small, and it is entirely the ceiling function plus Stirling’s linear term.

That gap is the whole of what any encoding of a permutation can win, and this collection has measured it once already in a different strand: sixteen per cent is the number there, on a different z, and the shape is the same.

So the three orders cannot be coded below about 4,470 bits by any means. What can be done is not storing the third, which is a structural change rather than a coding one and is worth 1,808 against the 954 a coding could win on all three.

The structural saving is larger than the coding saving, which is a reliable pattern when a structure holds something derivable: deriving beats compressing.

What the deferral had expected #

The sentence naming this strand’s work called the phrase index’s chain the largest part of a different apparatus.

It is not. The largest part is the boundary orders, and the thing the deferral called the chain — the propagation’s visited set — is query state that no accounting mentions at all.

A constant factor, not a term is that retraction, and this essay is where the actual largest part is identified. The two are a pair: a strand looking for a size result in one place found it in another, by measuring the structure in order to price something else.

That the measurement happened at all is incidental. The running maximum of the scan the order does not touch costs 2,821 bits and reporting it as a share required knowing the index’s parts, and knowing the parts is what showed that half of it is permutations.

The other size question #

There is a second thing the parts make visible and it is worth a paragraph because it is the family’s real size problem.

The parse stores each phrase’s source as an absolute position: ⌈log₂ n⌉ bits, 2,712 of the index’s 11,978.

A source is the position of an earlier occurrence, and on a collection of copies it is almost always exactly one copy-length behind the phrase. So the displacements — at − source — are highly repetitive, and storing them instead of absolute positions would compress well.

Nothing here does that, and it is the standard first optimisation in this family’s implementations. Its size is 23% of the index, so getting most of it would be worth more than the inverse permutation.

That is named rather than built, and it belongs in the same list as the shortcut permutation: two size options, both standard, both unpriced here, together worth perhaps a third of the structure.

The parts plate also makes visible something the strand’s other essays could only assert: that the index’s size does not include the query’s working memory.

At thirty-two copies the index is 20,640 bits and a query holds 420 in its visited set — two per cent, and proportional to the answer rather than to the phrase count.

So the four bars on the plate are a complete accounting of what the structure holds at rest, and an incomplete accounting of what a system running it needs. A constant factor, not a term is where that gap is named, and this plate is where it is visible: there is no fifth bar, and the thing a fifth bar would show is a function rather than a number.

Where the strand’s three results sit together #

The strand has three numbers and this essay has the largest, which is worth setting out because the ordering is instructive.

The visited set: a factor of 1.6 on query working memory, which is the deferral’s own subject and the smallest of the three. A constant factor, not a term.

The scan: a factor of 19 on phrases examined per probe, for 22% more bits. The scan the order does not touch.

The orders: 45.3% of the index, with 15.1% of it derivable. This essay, and it is a diagnosis rather than a change.

Two of the three were found by building the first, and the third was found by measuring the index in order to state the second’s cost as a share.

That chain — build a thing, price it, need a denominator, look at the parts, find something larger than the thing built — is a common enough shape in this collection to be worth naming. The denominators are where the results are, and a strand that quotes shares has to compute them.

The permutation strand, next door #

This collection has measured what can be won on a permutation once already, and the result bounds what a shortcut structure can do.

The compressed grid’s strand established that sixteen per cent is the whole of what any coding can win on a permutation of z elements, because a permutation of z elements carries log₂(z!) bits and z⌈log₂ z⌉ is only that much above it.

So the three orders cannot be compressed below about 4,556 bits by any encoding. What a shortcut structure does is different — it removes one of the three rather than coding them better — and the two are complementary.

Taking both: 4,556 bits for two coded permutations, plus a sampled inverse at a quarter of one, is about 5,000 against the current 5,424. Which is a disappointing total, and it is the honest one: the orders are near their information content already, and the only real saving is not storing the third.

How the parts move with the collection #

The plate is one collection and the parts scale differently, so it is worth saying which way each goes.

The parse is z(2⌈log₂ n⌉ + ⌈log₂ σ⌉). It grows with z linearly and with n logarithmically.

The orders are 3z⌈log₂ z⌉. They grow with z slightly faster than linearly.

So as a collection becomes more repetitive — z falling at fixed n — both shrink, and the orders shrink faster because ⌈log₂ z⌉ falls too. On a highly repetitive collection the orders’ share falls toward a third.

As a collection becomes larger at fixed repetitiveness — n and z growing together — the parse’s ⌈log₂ n⌉ and the orders’ ⌈log₂ z⌉ both grow, and they grow at the same rate, so the shares hold.

So 45% is roughly stable across sizes and falls on more repetitive collections. That means the inverse permutation’s 15% is a share a reader can carry, and it is on the high side for the collections this family is built for.

What the plate is for #

A parts plate is the least interesting kind of figure and it is the one that produced the strand’s largest number, which is worth noting as a habit rather than as a result.

Nothing about this measurement is clever. It is the index’s own bits() method, drawn as four bars. It required no new structure, no sweep, no control, and no comparison.

What it required was asking. The index has reported its parts since it was built and nothing had drawn them, because a size in parts is what a structure returns when something asks for a share — and this strand had a share to compute.

An index larger than what it indexes is this collection’s first essay on a size that was not what its account said, and the instrument then was the same: add the parts up and look.

Why the boundaries need orderings at all #

Stepping back to what the orders are for, because a reader coming to this family fresh might reasonably ask why a parse needs three sorted arrays.

The index’s whole idea is that a pattern’s occurrences split in two. The ones lying inside a phrase are copies and are produced by arithmetic. The ones crossing a boundary have to be searched for, and there are z boundaries rather than n positions — which is the size saving the family exists for.

Searching z boundaries for “does the pattern’s right half start here” means having them sorted by what follows them. Searching for “does its left half end here” means having them sorted by what precedes. Two questions, two orders.

The third array is the machinery for combining the two answers, which is an intersection: a boundary is a primary occurrence’s location if it appears in both ranges.

So the three arrays are the price of the family’s central idea, and the parse alone would be a compressor rather than an index. The occurrences that cross a boundary is where that split was established here.

That framing also says what the orders’ 45% is buying: it is the difference between a structure that can decompress and one that can search. Compared against that, forty-five per cent is cheap.

What to carry #

Three numbers about a phrase index.

The boundary orders are 45.3% of it, at three permutations of z elements each.

One of the three is the inverse of another, worth 15.1% of the structure, replaceable by a sampled shortcut structure at a quarter of the cost and four steps per membership test.

And the phrase sources are 22.6%, stored as absolute positions where their displacements would compress.

Together those are 38% of a structure whose selling point is being proportional to z, available to two standard techniques, and unpriced in this collection until a strand about something else needed a denominator.

Why an accounting is worth keeping current #

The general lesson is not about phrase indexes and it is short.

A structure that reports its size in parts can be asked where its bits are, at any time, for nothing. A structure that reports a total cannot, and the difference shows up years later when somebody wants a share.

Every structure in this collection reports parts, and the convention costs a few lines per bits() method. What it bought here is that a strand about a traversal could, in one call, discover that half the index it was working on is permutations — which is a fact nobody was looking for and which is larger than anything the strand set out to find.

An index larger than what it indexes is where the convention started, on a structure whose total was surprising. The parts convention came out of it and this is the third or fourth time the parts have said something the total could not.

The instruction: report a size in parts, name every part, and never fold two parts together because they are conceptually related. The boundary orders are one part here because they are three arrays serving one purpose, and that grouping is exactly what made the fifteen per cent inside it invisible until somebody divided by three.