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

Locate — where it appears

Turning a search result into the text positions where the matches are, rather than merely counting them. It costs a walk per occurrence and is hundreds of times the price of counting, which is why a search engine reports a total instantly and ten results next.

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

1101001,00010010³position in the textLF stepsspan + sample = 64row sampling onlywith the secondsampling8,192 characters · sample one in 32 · span 32second sampling 3,598 bits

The sampling that goes the other way

An FM-index hands the text back, and the way it does it is to walk from the last character to the first. So thirty-two characters from the end cost thirty-three steps and thirty-two characters from the beginning cost eight thousand one hundred and ninety-two. The repair is a second array the same size as the first, indexed the other way round.

indexes · Index sampled positions6,99041%phi predecessor3,95223%run starts2,09712%run lengths per symbol1,97012%run heads1,5389%C table5003%English-like · n = 16,385 · r = 233the sampling is the two shaded rowsone unit = one bit17,047 bits · 1.04 bits/char

The sampling that follows the runs

A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.

indexes · Repeat text position iphi(i)anchor: a run start25 of thema text that repeats itself · 4 copies of 32r = 26 · pieces 24

A function with r pieces

Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.

machine · Index patterns of 225%60 selectspatterns of 441%94 selectspatterns of 863%118 selectspatterns of 1682%117 selectsEnglish-like · 8 copies of 512share of steps needing no lookup40 patterns a row

The occurrence carried through the search

Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.

indexes · Index sampled positions3,855grows with nsample marks2,056grows with nrun starts2,016grows with rrun lengths per symbol1,885grows with rrun heads1,563grows with rC table525grows with r11,900 bits in total16,384 characters · r = 224 · sample one in 6450% is the sampling

What is still proportional to n

An index whose size is a function of the run count still has an n in it, and at thirty-two copies of a text the n is half of it. Everything that stores the transform grew by 45 per cent; the two arrays that answer "where" grew by eighteen times, and neither of them has anything to do with repetition.

space · Repeat 1,00010,00010⁴bits12481632characters in the collection · copies aboveFM-index, compressedr-indexphrase indexEnglish-like · divergence 0z 156 · r 233

An index with z in its size

Over thirty-two copies of one text, an index built on the parse is 8,892 bits, the r-index is 17,047 and the entropy-bounded index is 34,615. Over eight thousand characters of four-symbol text the same three are 7,844, 25,177 and 20,413, and the smallest of the three has changed places twice.

indexes · Parse 1,00010,000110occurrences12481632characters in the collection · copies aboveall occurrencessecondaryprimarypattern "ss is un" · z = 1561 primary · 31 secondary

The occurrences that cross a boundary

One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.

text · Parse 1,00010,00010⁴bits12481632characters in the collection · copies aboveFM-index, compressedr-indexphrase indexEnglish-like · divergence 0z 156 · r 233

The collection decides which index is small

Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.

indexes · Repeat 10,000110sampling, bitssteps per occurrence1 in 21 in 41 in 81 in 161 in 321 in 641 in 128r-indexEnglish-like · 16 copies · r = 233pattern " time "

Every occurrence at the same price

A regular sampling has one dial and it moves two costs together — 1,495 bits at 63 LF steps an occurrence, 131,088 bits at none. A sampling at the run boundaries sits at 10,244 bits and one predecessor query, which is a point the curve reaches only at 69,649.

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

The candidates a filter cannot avoid

A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.

indexes · Grid 1,00010,00010phrases followed12481632characters in the collection · copies aboveworst depthmean depthEnglish-like · z = 156median 18 · 90th 31

The character that costs a chain

The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.

space · Parse 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 forward · wavelet tree18,377forward · rank directories5,037forward · C table100forward · sample marks8,193forward · sampled positions3,598reverse · wavelet tree18,377reverse · rank directories5,037reverse · C table100reverse · sample marks8,193droppedreverse · sampled positions3,598dropped8,192 characters · sampling every 3216.7% of both halves

The half that is never asked where

A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.

indexes · Distance forward · wavelet tree18,377forward · rank directories5,037forward · C table100forward · sample marks8,193forward · sampled positions3,598reverse · wavelet tree18,377reverse · rank directories5,037reverse · C table100reverse · sample marks8,193droppedreverse · sampled positions3,598dropped8,192 characters · sampling every 3216.7% of both halves

An index that cannot locate

Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.

space · Distance 0102030255075100125one sampled position in every …of both halves saved, per cent"about a sixth"the marks alone: 14.0%8,192 characters16.7% at one in 32

A sixth of what, exactly

The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.

wrong · Distance both halves, one in 3215.0 steps100.0% the sizeforward sampled one in 3215.0 steps83.3% the sizeforward sampled one in 167.0 steps88.4% the sizeforward sampled one in 83.0 steps98.5% the sizeforward sampled one in 41.7 steps118.8% the size8,192 characters · 6 occurrences5.0x faster, 98.5% the size

The saving, spent

A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.

practice · Distance

Named alongside it

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

Index sizeMeasurementSelf-indexFM-indexSamplingTrade offR-indexSuffix arrayRepetitionRun-lengthSpace overheadLempel ziv parse

All concepts