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

Separator — where it appears

A character placed between concatenated documents that no document contains, so that no pattern can match across a join. It costs one alphabet symbol, which is free until the alphabet crosses a power of two; giving each document its own costs d symbols and a bit per character.

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

2·0·1·20101206·7·3·25·012012201012102rowsdocumentfirstpattern " was t" · 30 occurrences · 7 documentsA filled row is the first of its document. Reporting one costs a range minimum;reading every row costs one visit per occurrence.English-like · 8 documents30 rows · 7 documents

A list of documents is not a list of occurrences

A pattern occurring 790 times in eight documents has an answer of size eight. Reading every occurrence to find out costs 790 array reads; the question a collection has that a text does not is the one its index does not answer.

indexes · Document run together38,400 bitsσ 21 · 5 bitsone separator38,470 bitsσ 22 · 5 bitsa separator each46,164 bitsσ 35 · 6 bits15 documents of 512 charactersthe separators are the only differenceEnglish-like · 15 documents1.20x for the distinct marks

One separator, or one for each

A shared separator costs one alphabet symbol and is free. Fifteen distinct ones take the alphabet from twenty-two to thirty-five, which crosses a power of two, so every character of every document costs a sixth bit — 1.2 times the packed collection, to tell the boundaries apart.

space · Document run together867 bits a characterone separator877 bits a charactera separator each897 bits a charactergenerated, run together215 bits a characterdistinct symbolstwelve essays0.0% premium

Documents that are not the same length

A separator per document costs a whole bit per character — on a generated collection whose alphabet is 21 symbols, where adding a few crosses 32. Real prose has 87 symbols and sits 41 short of the next power of two, so the same separators cost 0.04%.

indexes · Document ① prose12,33512① code13,1508① revisions7,77410② essays12,33582② captions2302,214② history12,96314documentscharacters in a document① the first freeze · ② the secondmedian marked

Two thousand documents of two hundred characters

Every collection this field has measured has been a dozen documents of ten thousand characters. A real collection is usually the other shape, and the other shape moves every term in a document index — one of them by a factor of seventy.

indexes · 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

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 46812windowswindow lengthspanning a joinin no documentwith a separatorEnglish-like · 8 documents44 invented at m = 12

The occurrences a join invents

Eight documents run together hold forty-nine eight-character windows that span a join, twenty-three of which occur in no document at all. Every index built over the concatenation reports them, and five essays of this collection paid that cost silently.

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

Document collectionIndex sizeRepetitionAlphabet sizeBurrows-wheeler runsCorpusSelf-indexAlphabetControlDocument arrayDocument listingMeasurement

All concepts