Algorithms & Data Structures
the bound is a claim, and it is checkable
Theme

The thread: The measure decides the structure

A compressed index is proportional to some measure of how much a text repeats itself — the runs in its transform, the phrases in its parse, an entropy. Which measure it is decides what the structure is small on, what a query costs against it, and whether relabelling the alphabet can change its size.
sampled positions6,99041%phi predecessor3,95223%run starts2,09712%run lengths per symbol1,97012%run heads1,5389%C table5003%English-like · n = 16,385 · r = 233the sampling is the two shaded rowsone unit = one bit17,047 bits · 1.04 bits/char The index that replaces the text

The sampling that follows the runs

A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.

 text position iphi(i)anchor: a run start25 of thema text that repeats itself · 4 copies of 32r = 26 · pieces 24 What the machine does

A function with r pieces

Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.

 patterns of 225%60 selectspatterns of 441%94 selectspatterns of 863%118 selectspatterns of 1682%117 selectsEnglish-like · 8 copies of 512share of steps needing no lookup40 patterns a row The index that replaces the text

The occurrence carried through the search

Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.

 is·holds·no·the·the·of·of·rather·count·class·that·is·algorithm·o1111111211111151141131111111211122213111111212phrase lengths below each block · a shaded block is a literalEnglish-like · 64 charactersz = 46 · 17 literals The data that is not a number

The phrases a text copies from itself

Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.

 1,00010,00010⁴bits12481632characters in the collection · copies aboveFM-index, compressedr-indexphrase indexEnglish-like · divergence 0z 156 · r 233 The index that replaces the text

An index with z in its size

Over thirty-two copies of one text, an index built on the parse is 8,892 bits, the r-index is 17,047 and the entropy-bounded index is 34,615. Over eight thousand characters of four-symbol text the same three are 7,844, 25,177 and 20,413, and the smallest of the three has changed places twice.

 1,00010,000110occurrences12481632characters in the collection · copies aboveall occurrencessecondaryprimarypattern "ss is un" · z = 1561 primary · 31 secondary The data that is not a number

The occurrences that cross a boundary

One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.

 10⁵10⁶10⁷10³10⁴inversions in the permutationblock transfers to carry it outsort by destination, 1,536w 8w 32w 128w 512w 2048w 819216 swaps64 swaps256 swaps1024 swapsshuffled inside windowsa few pairs swapped farn = 16,384, B = 64, M = 512 (M/B = 8)inversions do not order the cost When it does not fit

The permutation that moves almost nothing

Two ways to scramble sixteen thousand elements. Shuffling them inside windows of five hundred and twelve puts two million pairs out of order and costs 3,095 block transfers to carry out. Swapping a thousand pairs across the whole array puts seven million out of order and costs 1,189. Inversions are the textbook measure of disorder, and on a disk they rank these two backwards.

 1,00010,00010⁴bits12481632characters in the collection · copies aboveFM-index, compressedr-indexphrase indexEnglish-like · divergence 0z 156 · r 233 The index that replaces the text

The collection decides which index is small

Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.

 10,000110sampling, bitssteps per occurrence1 in 21 in 41 in 81 in 161 in 321 in 641 in 128r-indexEnglish-like · 16 copies · r = 233pattern " time " The other axis

Every occurrence at the same price

A regular sampling has one dial and it moves two costs together — 1,495 bits at 63 LF steps an occurrence, 131,088 bits at none. A sampling at the run boundaries sits at 10,244 bits and one predecessor query, which is a point the curve reaches only at 69,649.

 rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing The index that replaces the text

The candidates a filter cannot avoid

A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.

 124816nonephrasescap on the copy chainphrasesworst chainEnglish-like · 8,192 charactersz 156 to 7,351 The data that is not a number

A parse that will not follow a long chain

A greedy self-referential parse bounds the copy depth by nothing at all — thirty-two copies of a text give a position costing twenty-two phrase follows. Restricting every phrase to sources no deeper than D holds it at D, and the whole question is what that costs.

 1,00010,00010phrases followed12481632characters in the collection · copies aboveworst depthmean depthEnglish-like · z = 156median 18 · 90th 31 The other axis

The character that costs a chain

The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.

 11010⁴10⁵worst copy chain, phrases followedbits124816noneno capcap on each pointEnglish-like · 16 copies of 512z 156 to 7,351 The index that replaces the text

What a ceiling costs in phrases

A cap of sixteen costs one phrase of a hundred and fifty-six and halves the worst chain. A cap of four costs six times the phrases. The curve between them is flat at one end and vertical at the other, and the elbow is where a structure should be built.

 phrase table5,148 bitsboundary orders3,744 bitsintersection grid1,696 bitspropagation grid1,544 bitsz = 156 · ⌈log₂ z⌉ = 8 levels16,384 characters · 12,132 bitsgrids 26.7% · 20.8 bits a point The other axis

The structure paid for before the first query

The two grids that make a phrase index's search proportional to its answer are 3,240 bits on an 8,892-bit index — twenty-seven per cent of the whole structure, answering nothing on their own, and 38% of them is rank directory rather than payload — the lower-order term of the published bound, measured.

 124816nonephrasescap on the copy chainphrasesworst chainEnglish-like · 8,192 charactersz 156 to 7,351 The other axis

The term that came back

A phrase index is worth building because 8,192 characters parse into 156 phrases. Cap the copy depth at one and the same text parses into 7,351 — ninety per cent of the characters — and the structure is proportional to the text again.

 rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing Structures

A rectangle over a permutation

Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.

 English-like, 32 copies0.05x0.017 runs/charEnglish-like, 8 copies0.12x0.045 runs/chara text that repeats itself0.08x0.029 runs/charEnglish-like0.80x0.292 runs/charfour symbols, uniform2.07x0.753 runs/charthe whole suffix arraysampling bits, run boundaries / every valuen = 8,192 What is taught wrongly

A sampling that costs more than the array

On four-symbol text the transform has 0.75 runs a character, so a sampling of two suffix-array values per run is one and a half values per position — 271,565 bits against the 131,088 that keeping every value costs. The structure built to remove a term proportional to the text is twice the thing it replaced.

 1001,00010characters in the wordruns · phrasesr, worse orderz, either orderr, better orderFibonacci words · two symbolsspread 1.50x to 3.17x What is taught wrongly

The measure that cannot see the alphabet

Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.

 one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty The data that is not a number

The cell nobody filled

Every structure here was measured either on one long repetitive text or on prose cut into short documents. The collection that is both is a two-by-two with one empty corner, and what is in it is not the product of its margins.

 equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5% The data that is not a number

The array is the length distribution

The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.

 a text that repeats itself2.96xchain 13 · z 110English-like1.31xchain 10 · z 604four symbols, uniform1.28xchain 10 · z 816periodic, period 171.11xchain 9 · z 1,285phrases under a cap of four, against no cap4,096 characters each2.96x to 1.11x What is taught wrongly

The cap that binds on one text and not another

A periodic text looks like the one made of chains and pays 1.11 times the phrases for a cap of four. A text that repeats itself pays 2.96. The guess is backwards, and the reason is that depth measures nesting rather than repetition.

 02e+34e+36e+301234567891011level of the wavelet treebitsplainblock-codedrun-coded3,612 points · 12 levels24 copies of 2048 characters What is taught wrongly

The level where compression stops paying

Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.

 051015204060documents, which here is also the copy countbits a characterFM-indexrun-length indexphrase index8,192 characters throughout2665 runs down to 427 The index that replaces the text

The index that does not notice

Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.

 1101000.1documentsruns of the transform, per characterprose: 1.10xcopies: 1.02x8,192 characters, cutthe control rises further What is taught wrongly

A boundary that costs nothing

A separator occurs nowhere else in the collection, so it must break a phrase that would have spanned it. Cutting a repetitive text into a hundred and twenty-eight documents raises its run count by two per cent, and cutting prose raises it by ten.

 prose, many short documents4.31 most frequent3.07 drawn from a documentone copy per document5.75 most frequent1.81 drawn from a documentcopies cut across the boundaries5.81 most frequent1.88 drawn from a documentoccurrences per document holding the pattern16 documents · 6-character patternsall three within a tenth on the drawn pattern What is taught wrongly

One copy per document is one occurrence per document

The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.

 one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty What the libraries do

A collection is a construction

The same characters, arranged as one copy per document or cut across the copies, give a different run count, a different boundary cost and a different answer about which structure to build. Which one a benchmark used is usually not recorded.

 equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5% What is taught wrongly

A saving quoted without its collection

A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.

All threads