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

Backward search — where it appears

Narrowing an interval of sorted suffixes by consuming a pattern from its last character, two rank queries at a time and no character comparison at all. It performs no character comparison at all, which is why an index built for it can throw the text away and still answer.

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

0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons

A search that runs backwards

Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.

indexes · Index a text that repeats itselfH0 4.01 · H3 0.236.291.48an order-1 sourceH0 3.00 · H3 0.895.151.67English-likeH0 3.89 · H3 0.976.162.25four symbols, uniformH0 2.00 · H3 1.994.102.59eight symbols, uniformH0 3.00 · H3 2.835.143.65bits per character of textupper bar: plain bit vectors · lower bar: compressed16,384 characters each · sample rate 64sigma 21, 8, 21, 4, 8

The index that is smaller than the text

The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.

indexes · Index 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 10010³10⁴10⁵errors allowed, kacts01234index walkthe whole table4,000 characters · m = 16 · 4 symbolscrossing at k = 4

The branches an error opens

The tree multiplies by 19.6 for the first error, 12.3 for the second, 10.3 for the third and 8.8 for the fourth. A branching factor of four on a sixteen-character pattern would predict sixty-four, and the gap between sixty-four and eight is the intervals emptying.

bounds · Distance 10010³10⁴errors allowed, kacts0123index walkthe whole table3,000 characters · m = 20 · 4 symbolsno crossing in range

The search that spends a budget

A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.

indexes · Distance atgaattcatgagtgacaag00000111111112222222errorsthe pattern, left to right · D belowleast errors neededD, the bound4 symbols · m = 2090 ranks · 2 resets

The errors the rest of the pattern needs

Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.

text · Distance 1234567characters addedoccurrencesgrown leftwardsgrown rightwards"tgatatt"4,000 characters · four symbols1 occurrences

An interval that grows at both ends

A backward search step is two ranks. A bidirectional step is two ranks and the width of the interval for every symbol that sorts before the one being added — 16.5 ranks on four symbols and 138.6 on twenty-six, which is a cost no account of the structure mentions.

indexes · Distance one index35,3354.31 bits/charthe forward half35,3354.31 bits/charthe reverse half35,3354.31 bits/charboth, which is the structure70,6708.63 bits/charbits8,192 characters · sample 322.00x one index

The structure that was supposed to halve

A bidirectional index holds the transform of the text and the transform of its reversal — 35,335 bits each, 70,670 together, exactly twice one index. The deferral that named it hoped it would stop the index doubling. It does not remove the doubling; it reuses it.

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

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 level 0 · left335 keptlevel 1 · right+207 smallerlevel 2 · left61 keptlevel 3 · right+33 smallerlevel 4 · left8 keptpositions still in play, and the half the code leaves behindsmaller symbols before position 400: 240rank of "m": 8 — from the same 5 operationsσ 21 · code 010105 ranks, not 105

Every child at once

A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.

indexes · Symbol a loop over the alphabet107.9the compound walk10.0the cheapest hereone descent per step19.016 exact patterns of 12ranks per step · sigma 21

The saving that is a loss

An operation that is seventy-eight times cheaper on a branching search costs twice as much on an exact one. It reports every symbol present in order to hand back the one that was asked for, and a search that knows its character needs none of the rest.

practice · Distance

Named alongside it

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

FM-indexMeasurementIndex sizeWavelet treeBidirectional indexRankRank querySelf-indexBacktracking searchBurrows-wheeler transformIntervalLocate

All concepts