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

Permutation — where it appears

A bijection from a set of positions to itself, which is what two total orderings of one set of objects give. It is the cheapest possible input to a range structure: the coordinates need not be stored at all, so a grid over z points costs z log z bits including its index.

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

each row is one rotation · the table is sorted · the transform is the last columnfirstlast◇the-order-is-the-message-is-the-message◇the-order-message◇the-order-is-the-order-is-the-message◇the-the-message◇the-order-isage◇the-order-is-the-messder-is-the-message◇the-ore◇the-order-is-the-message-message◇the-order-is-the-order-is-the-message◇ther-is-the-message◇the-ordessage◇the-order-is-the-mge◇the-order-is-the-messahe-message◇the-order-is-t… 11 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38

The transform that emits nothing

The Burrows–Wheeler transform outputs exactly the characters it was given, in a different order. Its zeroth-order entropy is therefore identical to its input's, to fifteen decimal places, and by that measure it has done nothing at all. A Huffman coder handed the result spends 1.935 bits per symbol where the same coder on the same data spends 4.209, and the difference is entirely in the order.

text · Bits thousands of bits · the floor is 31.9kthe text as it is34.0k streamto undo itnothinga shuffle agreed in advance34.4k streamto undo itnothingthe characters sorted0.3k streamto undo it31.8kthe Burrows–Wheeler transform14.8k streamto undo itnothingmodel: order 0 after move-to-front · Words from a fixed vocabularydashed: coding the text as it stands

What a reordering costs to undo

Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.

floors · Bits 1010010³10⁴B — elements to the blockblock transfersthey cross near B = 4one element at a timesorted by destination, 2passesM = 4,096, B as drawnthe lower bound is the smaller of the two, and it is proved rather than measured

Permuting is the harder problem here

Rearranging 65,536 elements into a stated order costs 63,601 transfers one at a time and 4,096 by sorting them into place. In the model every other field on this site uses, the first is the cheap method and beats the second by a factor of eight. The two models disagree about which problem is easy, and they disagree by about the same factor in opposite directions.

applied · Transfer 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

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.

applied · Transfer 0.0010.010.11125102050fraction of positions reshuffled, pmean comparisons, in multiples of the mean on random inputFirst-element quicksort, 81.9×Median-of-three quicksort, 41.4×Insertion sort, 2.0×Merge sort, 1.0××: unshuffled2,048 elements · 12 shuffles a point1 = the mean on random input

A worst case ten positions wide

Sorted input costs first-element quicksort 2,096,128 comparisons on 2,048 elements, 82 times its average. Reshuffle about eleven of the 2,048 positions and the cost halves — and it takes about ten at 128 elements, and between ten and thirteen at every size between. Reversed input costs insertion sort twice its average, and reshuffling half the positions still leaves 71% of the work. A worst case is a place in the space of inputs, and the two famous ones are places of very different sizes.

counting · Count 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 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.

space · Grid plain51,600block-coded47,6687.6%run-coded60,805-17.8%plain, uniform51,600block-coded, uniform50,2422.6%run-coded, uniform67,121-30.1%bits · the lower three are a permutation with no structure3,612 points7.6% against 2.6%

A block, a class and an offset

Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.

indexes · Grid 01234characters of context the sort reads, kbits a symbol after move-to-front012481632the full transform, 1.802ties kept in text orderties sorted by symbol: the stream alonethe text's own floormodel: order 0 after move-to-front · Words from a fixed vocabularyexactly the transform from k = 24

The order inside a tie

Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.

floors · Bits 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

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.

structures · Grid 00.2500.5000.750101234567891011level of the wavelet treebits a bitthe parse's grida uniform permutation3,612 points · 12 levels0.997 bits a bit

A bit for every bit

A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.

space · Grid 024601234567891011level of the wavelet treemean runthe parse's grida uniform permutationbreak-even3,612 points · 12 levels1.23x chance

The runs a permutation does not leave

A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.

structures · Grid candidates, filtering4,355candidates, grid33rank and select, grid2,471occurrences32one query · same collection · same answer16,384 characters · 32 occurrencescandidates 132x · operations 1.76x

The operations a candidate count leaves out

The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.

wrong · Grid 02e+34e+36e+301234567891011level of the wavelet treebitsplainblock-codedrun-coded3,612 points · 12 levels24 copies of 2048 characters

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.

wrong · Grid phrase lengths2,71222.6%phrase sources2,71222.6%phrase literals1,1309.4%boundary orders5,42445.3%three permutations of 226 elements: 1,808 bits each, and one is the inverse of another226 phrases · 4,096 characters45.3% in the orders

Half an index is three permutations

A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.

space · Parse

Named alongside it

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

GridWavelet treeMeasurementBit vectorEntropyIndex sizeTrade offCompressionRank directorySpace overheadBurrows-wheeler transformControl

All concepts