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

Burrows-wheeler runs — where it appears

The number of maximal stretches of equal characters in the last column of a text's sorted rotations, written r. It falls when a text repeats and not when a text is merely predictable, so a structure whose size follows it is small on a collection of copies and large on ordinary prose.

Named by 7 essays across 6 fields — each of them below, with the objects they name alongside it.

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 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.

text · Document 10⁴0.1charactersphrases of the parse, per charactershuffled: 1.45xthe collection: 4.71x4,111 to 65,551 charactersworth 3.24x after the control

What repetition is worth once the logarithm is gone

On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.

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

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.

indexes · Document 1101000.1documentsruns of the transform, per characterprose: 1.10xcopies: 1.02x8,192 characters, cutthe control rises further

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.

wrong · Document 051015255075100125documentsdistinct characters the documents end with+7+52+162+293+4+-1+9+19prosecopies of one basethe label is the runsthe cut added128 documents0.15 against 2.31 runs a separator

The price of a boundary is what precedes it

A separator sorts before everything, so its rows sit at the top of the suffix array and hold the documents' last characters. What a document boundary costs the transform is the entropy of the character in front of it, and nothing else.

structures · Document run together1.00xsigma 21 · 5 bitsone separator1.00xsigma 22 · 5 bitsa separator each1.20xsigma 36 · 6 bitsruns 1.00xruns 1.00xruns 1.02x16 documents of 512 characterspacked bits, against running them together

Two currencies for one separator

Giving every document its own boundary marker costs a fifth of the packed text and three per cent of the run count. Both numbers are right, they are about the same change, and which one a collection pays depends on a structure nobody named.

space · Document 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

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.

practice · Document

Named alongside it

The objects these essays reach for when they reach for this one.

RepetitionDocument collectionAlphabet sizeMeasurement designPhrase countSeparatorControlCorpusSelf-indexIndex sizeEntropyBurrows-wheeler transform

All concepts