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

Occurrence — where it appears

One position where a pattern appears in a text. The count of them is what a search interval’s width gives for free, and producing the positions themselves is what costs a walk per occurrence — which is why counting and locating are priced separately here.

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

0200400200400occurrences of the patternrows read, and documents in the answerrows readdocuments in the answertwo thousand short documents · 2,214 documents1.04 occurrences a document

The crossing that never arrives

Output-sensitive document listing exists because a pattern can occur four thousand times in eight documents. On a real collection of two thousand short documents it occurs 1.04 times per document, and the whole apparatus buys nothing at all.

practice · Document range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps

The array the walk never reads

Document listing compares a chain entry against the start of a range. The comparison is true exactly when the document has not been reported yet — which the walk already knows, because it just wrote it down.

indexes · Index prose, many short documents4.31 most frequent3.07 drawn from a documentone copy per document5.75 most frequent1.81 drawn from a documentcopies cut across the boundaries5.81 most frequent1.88 drawn from a documentoccurrences per document holding the pattern16 documents · 6-character patternsall three within a tenth on the drawn pattern

One copy per document is one occurrence per document

The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.

wrong · Document

Named alongside it

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

Document collectionDocument listingOutput-sensitiveRange minimumCorpusIndex sizeSuffix arrayCrossingCrossing pointDocument arrayInvariantMeasurement design

All concepts