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

Bidirectional index — where it appears

An index of a text held together with an index of its reversal, so that a search interval can be extended at either end. It does not save space — it holds both transforms — and what it buys is the freedom to consume a pattern in any contiguous order, which is worth a factor of between two and five on a search with errors.

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

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 right to left8302.74xleft to right8772.89xone per piece4471.48xthe scheme3031.00xinterval extensionsall four found the same 6 positions15 characters · k = 22.74x apart

The search that starts in the middle

The same pattern, the same six occurrences, the same index — and 830 interval extensions, or 303, according to which end the search begins at. A pattern cut into three pieces has an error-free one, and only a search with two ends can start there.

text · 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 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 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 errors, by piecetaken by(0, 0, 0)1(0, 0, 1)1(0, 0, 2)1(0, 1, 0)1(0, 1, 1)1(0, 2, 0)3(1, 0, 0)2(1, 0, 1)2(1, 1, 0)3(2, 0, 0)30 of 10 covered more than once · the numbers are the searchesk = 2 · 3 pieces10 distributions

A schedule nobody writes down

A search scheme is valid when its searches between them cover every way the errors can fall — ten cases at two errors, enumerable in a line. A scheme missing one of them finds seven occurrences of eight, all real, at the right error counts, and reports nothing wrong.

wrong · Distance 051015510152025symbols in the alphabetfactor saved, and per cent paidranks saved, as a factorbits paid, per cent8,192 characters · 2 errorsx14.0 for 0.04%

A factor of fourteen, for four per cent

The compound walk removes a factor of σ from every interval extension. It requires a tree whose leaves are in order, which costs between nothing and five per cent of the wavelet tree. Both numbers on one plate, and the trade is not close.

bounds · Symbol 025507510000.50011.502errors permittedfactor against the published loop64.5%55.8%74.7%the walk: 11xthe descentthe label is the shareof dead extensions6 patterns · sigma 2198x to 105x

Flat in the budget, and not

One saving is eleven times at every error budget, because it is a property of the alphabet. The other moves between ninety-eight and a hundred and five, because it follows the share of extensions that find nothing. Two savings, two shapes, and neither line crosses the other.

bounds · Distance a loop over the alphabet1,478,400the compound walk, inside the loop134,40011xone descent per node18,91678x6 patterns · 1 error · sigma 2155.8% of the extensions were dead

Three savings on one structure

A factor of eleven on an extension, a factor of seven on a branching search, and a sixth of the bits. Applied to one bidirectional index they do not give a factor of seventy-seven, and the reason is that two of the three are the same saving.

indexes · Distance a fixed-length codeleaves in order␣acdefghilmnoprstuvwythe best ordered treeleaves in order␣acdefghilmnoprstuvwythe best tree of any shapeleaves in frequency order␣eahnrstdiloucfgmpvwythe symbols, in the order the descent reports them21 symbols in 2,048 positionsone set, 2 of 3 sorted

One set, three orders

The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.

wrong · Symbol both halves locate250,584100.0%the reverse half counts only226,50490.4%and its marks are Elias-Fano210,93484.2%the saving spent on sampling241,47596.4%16,384 characters · one in 3284.2% smaller, or the same size and faster

The ladder, and the rung that spends

Two hundred and fifty thousand bits, then two hundred and twenty-six, then two hundred and eleven. The fourth rung takes the whole saving and buys a four-times denser sampling with it, landing at ninety-six per cent of where it started and locating several times faster.

space · Distance 0102030100200one sampled position in every …of both halves saved, per centplain marks: 13.5%Elias-Fano: 1.8%16,384 characters17.6x against 2.3x

The floor was the marks

A saving reported as about a sixth of a bidirectional index, falling to an eighth and levelling off. Represent one array properly and it falls to a fiftieth instead — most of what was being dropped was a badly encoded bit vector.

practice · Space factor against the published loopthe compound walk11xthe enumeration78xthe two, multiplied860xnothing measures thisan index with both78xthe shortfall is 11x, and the walk's factor is 11x6 patterns · 1 error · sigma 21the larger of the two, not the product

Two factors that do not multiply

Eleven times and seventy-eight times against the same baseline, so an index with both should be eight hundred and sixty. It is seventy-eight, and the shortfall is eleven — the first factor, exactly, because the second operation already contains it.

wrong · Distance 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 020406080255075100125one sampled position in every …of the plain index, per centsize: 84.7%67.5 steps16,384 characters · 8-character patternssize falls, the walk lengthens

Bits and steps on one frame

The size falls from ninety-nine per cent to eighty-six as the sampling thins, and the walk to a sampled position rises from two and a half steps to sixty-four. Neither line is the answer; the answer is a point on the pair.

structures · Distance

Named alongside it

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

Index sizeRankWavelet treeBackward searchFM-indexSearch schemeIntervalInterval symbolsSamplingAlphabetCompound walkConstant factor

All concepts