Generator

What the document array can be compressed to is the length distribution

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
What the document array can be compressed to is the length distributionThe zeroth-order entropy of the document array, for four collections of 32 documents and 8,192 characters. The array holds each document once per character it contributed, so its symbol distribution is the length distribution and nothing else. On equal-length documents H0 is 5.000 against a ceiling of log2 32 = 5.000 — the two are the same number, and a wavelet tree over that array is 100.0% of the plain n⌈log₂ d⌉ array, which is to say it saves nothing. On a collection where one document holds four fifths of the text H0 falls to 1.688 and the array to 39.5%. The dashed line is the ceiling every row is measured against.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 the document array can be compressed to is the length distribution

The zeroth-order entropy of the document array, for four collections of 32 documents and 8,192 characters. The array holds each document once per character it contributed, so its symbol distribution is the length distribution and nothing else. On equal-length documents H0 is 5.000 against a ceiling of log2 32 = 5.000 — the two are the same number, and a wavelet tree over that array is 100.0% of the plain n⌈log₂ d⌉ array, which is to say it saves nothing. On a collection where one document holds four fifths of the text H0 falls to 1.688 and the array to 39.5%. The dashed line is the ceiling every row is measured against.

Drawn at 700 × 236, wide on the page. Everything above is what document-array returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

14 essays call document-array. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

1010010³documents in the answeroperations inside the structureevery occurrencerange minimumone descent17 to 324 rows5.14 to 1.94 per document The floors

Work that falls as the answer grows

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

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

every occurrence5610 documentsrange minimum and chain32510 documentsrange minimum, no chain9610 documentsone descent over D3810 documentsthe document arraythe document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree56 occurrences in 10 documentsoperations inside the structure The index that replaces the text

The tree answers the question

range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus Structures

The last array in the apparatus

range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus The other axis

The apparatus, three times smaller again

bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree What the libraries do

The smaller tree hands it back unsorted

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

rounding of ⌈log₂ d⌉skew of the lengthsthe estimate, 17%source files10.5% · d 222essay paragraphs11.5% · d 522technical paragraphs11.9% · d 179revision paragraphs16.5% · d 30whole essays9.1% · d 12whole technical documents2.1% · d 8share of the plain array's bitssource files at one version The index that replaces the text

The collections the saving was quoted for

468files in the directory (logarithmic)bits a symbol of the document array2050100222the fitplain, ⌈log₂ d⌉ bitsfitted at 56 files, aone-document escapefitted at 56 files, awhole-collection escapethe same, its escape subtreerebuiltrefitted at every version47 versions, one project's source filesdashed vertical: the version of the fit The index that replaces the text

The shape arrived early and the bytes late

0%25%50%75%100%the escape's share of the coding spaceversion 020 filesversion 1040 filesversion 2281 filesversion 44175 filesin each group: growth seen, growth to come, half, one documentat each refit The index that replaces the text

One doubling late

00.2000.4000.60002.5057.5010bytes read by refits and rebuilds, in final arraysmean loss, bits a symbolas one documentas half the coding spaceby the growth seengrowth seen, half at firstby the growth to comeclock, held to 1.5×clock, held to 1.25×clock, no holdlower and left is better47 versions, 20 to 222 files The index that replaces the text

Refitting when the escape is wrong

00.1000.2000.3000.40002.5057.5010bytes read by refits and rebuilds, in final arraysmean loss, bits a symbolc 0.05c 0.2c 0.8c 3.2doubling, best a store can computedoubling, growth to comeclock, held to 1.25×priced clocklower and left is better47 versions, 20 to 222 files The index that replaces the text

A price that cannot see the array

00.1000.20046810bytes read by refits and rebuilds, in final arraysmean loss, bits a symbola quarterhold, sweptprice with the waitingprice, size-blindfaint dots: beaten on both countsescape as one document The index that replaces the text

The quarter was a lucky number

The library, page 2 of 5 — where document-array sits