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

The thread: There is a floor — page 2

Page 2 of 2, continuing the same thread in the same order.
00.2500.5000.750101234567891011level of the wavelet treebits a bitthe parse's grida uniform permutation3,612 points · 12 levels0.997 bits a bit The other axis

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.

 024bits a symbolequalzipftwoSizesoneLargeone bit a symbolentropyplain vectorscompressed blocks32 documents1.26x on the skewed collection What a bound is

A code word is at least one bit

A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.

 05e+31e+41.5e+40246bits kept in the low partbits⌊log₂(n/m)⌋ = 2low partshigh vector2,049 marks in 16,385 positions1 bits between the two roundings What a bound is

The flat bottom of a shallow curve

The low width is chosen as the floor of log of the universe over the count. Rounding it up instead costs one bit on five thousand, because the total is m·w plus n over two to the w and the minimum is where those two are equal.

 110100k, the operators after the alternationstatesits DFA: 512its NFA: 30a literal's DFA: 11alphabet ab2^(k+1), exactly What a bound is

The exponential is in the expression

The subset construction on one family reaches two to the k plus one states, exactly and not approximately. A literal of the same length gives eleven. Both are regular expressions and the difference is that one of them asks the machine to remember something.

 4,097 rows · one in 32 marked3.1% of the rows The other axis

The array that says where is twice the samples

An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.

 02040255075100125one sampled position in every …of the index, per centplain marks: 18.5%Elias-Fano: 3.8%16,384 characters14.9% off at one in 32 The index that replaces the text

What the locating apparatus becomes

The two parts that answer "where" are half an index at a dense sampling and a fifth at a sparse one, and the fifth does not fall further. Represent the marks properly and it keeps falling, to under four per cent.

 0102030100200one sampled position in every …of both halves saved, per centplain marks: 13.5%Elias-Fano: 1.8%16,384 characters17.6x against 2.3x What the libraries do

The floor was the marks

A saving reported as about a sixth of a bidirectional index, falling to an eighth and levelling off. Represent one array properly and it falls to a fiftieth instead — most of what was being dropped was a badly encoded bit vector.

All threads