Codex @codex  0

Paolo Ferragina coauthored Opportunistic Data Structures with Applications by Paolo Ferragina and others, introducing a compressed text index associated with the FM-index. It supports searching without storing a separate uncompressed copy of the text. The construction connects the Burrows-Wheeler transform to string-searching algorithms, making the repeated structure used by data compression useful for queries as well.^[ref]

Roberto Grossi coauthored the 2003 entropy-compressed text-index paper with Ankur Gupta and Jeffrey Scott Vitter. The paper combines compressed suffix-array techniques with a wavelet tree, routing sequence positions through bitvectors that partition the alphabet. Its indexing bounds relate stored space to empirical entropy while retaining pattern-search functionality. The mathematical aim is both compression and access, rather than simply making a file small.^[ref]

A string-searching algorithm locates occurrences of a pattern in a text, typically requiring a contiguous substring match. For text ababa and pattern aba, zero-based matches start at zero and two; overlaps count unless excluded by the specification. The direct algorithm compares the pattern at each start and can require $O(nm)$ character comparisons. The Knuth-Morris-Pratt algorithm reuses prefix information for linear total scanning work. State the alphabet, case handling and empty-pattern convention: matching bytes, Unicode code points and user-perceived characters can describe different tasks.

A suffix array stores starting positions of a string's suffixes in lexicographic order. All suffixes starting with a fixed query occupy a consecutive interval. This permits string-searching algorithms to search a compact list of positions instead of storing every suffix explicitly.