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

Secondary occurrence — where it appears

An occurrence lying entirely inside one phrase, and therefore a copy of an occurrence earlier in the text. It is produced by adding a phrase's displacement to a known occurrence rather than searched for, which is what lets a search over z boundaries find every occurrence in a much longer text.

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

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 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 occurrences reportedin text order16from the right2 — 14 lostevery one it reports is real, so the answer is short rather than wrong1 of them were found by the boundary search and never propagated16 copies · 6-character pattern87.5% lost

From the right, two of sixteen

Run the same sweep in the opposite direction and every occurrence it produces lands behind its own cursor. It reports two of sixteen, every one of them genuinely there, and nothing about the answer says fourteen are missing.

floors · Parse 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 01,024120 phrases · 1,024 characters60 drawn, every one pointing right

Every copy points right

A greedy self-referential parse chooses each phrase's source from text already produced, so an occurrence copied from another lies strictly to its right. That one fact removes a visited set from a propagation, exactly as a left-first walk removed an array one strand ago.

structures · Parse "t than"8 found · set 8 · frontier 4"of her"7 found · set 7 · frontier 4" that "16 found · set 16 · frontier 11" every"31 found · set 31 · frontier 19"the ev"8 found · set 8 · frontier 4"o of c"8 found · set 8 · frontier 5" than "15 found · set 15 · frontier 9"ime ra"7 found · set 7 · frontier 4the visited set, pale; the sweep's frontier, dark17,715 phrases examined either way1.67x on what is held

The same occurrences, less bookkeeping

Two traversals examine identically many phrases and report identically many occurrences. What differs is that one holds every occurrence found so far in a set and the other holds an ordered list and a cursor.

indexes · Parse 0100200300400102030copies of the basebits held during one querythe visited set: 420the frontier: 2666-character patterns20x to 1.58x

A constant factor, not a term

The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.

wrong · Parse phrases examined per probethe linear scan207.0sorted, with a running maximum10.9 — 19xthe running maximum costs 2,821 bits — 21.6% of the index40 of 40 positions checked, and the two agree at all of them238 phrases · 6,144 characters19x on the scan

The scan the order does not touch

Two hundred and seven phrases examined per probe, against eleven. A running maximum of the source regions' right ends lets a leftward walk stop for good, and it costs twenty-two per cent more bits.

practice · Parse

Named alongside it

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

Lempel ziv parseIndex sizePhrase indexPropagationPrimary occurrenceSelf-indexLocateMeasurementPhraseTraversal orderVisited setGrid

All concepts