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

Phrase index — where it appears

A self-index whose size follows the number of phrases in a Lempel-Ziv parse rather than the text's length. It finds the occurrences crossing a phrase boundary by searching and produces the rest by adding each phrase's displacement to an occurrence already known.

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

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 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 phrase lengths2,71222.6%phrase sources2,71222.6%phrase literals1,1309.4%boundary orders5,42445.3%three permutations of 226 elements: 1,808 bits each, and one is the inverse of another226 phrases · 4,096 characters45.3% in the orders

Half an index is three permutations

A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.

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

PropagationSecondary occurrenceLempel ziv parseIndex sizeTraversal orderVisited setSpace accountingWorking memoryBoundary orderCorrectnessInterval stabbingInverse permutation

All concepts