Indexing compressed text
From MaRDI portal
Publication:3546296
DOI10.1145/1082036.1082039zbMath1323.68261OpenAlexW2159647614WikidataQ124796874 ScholiaQ124796874MaRDI QIDQ3546296
Giovanni Manzini, Paolo Ferragina
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1082036.1082039
Burrows-Wheeler transformtext compressionsuffix arraysuffix treefull-text indexingpattern searchingindexing data structureLempel-Ziv compressor
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items
Arithmetics on Suffix Arrays of Fibonacci Words ⋮ Bidirectional Variable-Order de Bruijn Graphs ⋮ The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words ⋮ Kings, Name Days, Lazy Servants and Magic ⋮ A new class of string transformations for compressed text indexing ⋮ Practical Wavelet Tree Construction ⋮ Engineering Practical Lempel-Ziv Tries ⋮ String Indexing with Compressed Patterns ⋮ Computational graph pangenomics: a tutorial on data structures and their applications ⋮ Unnamed Item ⋮ Constructing and indexing the bijective and extended Burrows-Wheeler transform ⋮ Unnamed Item ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ CUSHAW Suite: Parallel and Efficient Algorithms for NGS Read Alignment ⋮ LZ78 Compression in Low Main Memory Space ⋮ Forty Years of Text Indexing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ A Succinct Solution to Rmap Alignment ⋮ A new class of searchable and provably highly compressible string transformations ⋮ Indexing the bijective BWT ⋮ Prefix-Free Parsing for Building Big BWTs ⋮ Haplotype-aware graph indexes ⋮ Analysis of Min-Hashing for Variant Tolerant DNA Read Mapping ⋮ Structural Pattern Matching - Succinctly. ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Fast Compressed Self-Indexes with Deterministic Linear-Time Construction ⋮ On Undetected Redundancy in the Burrows-Wheeler Transform ⋮ Practical Compact Indexes for Top-kDocument Retrieval ⋮ The Heaviest Induced Ancestors Problem Revisited ⋮ Online LZ77 Parsing and Matching Statistics with RLBWTs ⋮ Extended suffix array construction using Lyndon factors ⋮ Compressed string dictionary search with edit distance one ⋮ An external-memory algorithm for string graph construction ⋮ Engineering a lightweight external memory suffix array construction algorithm ⋮ Compressed spaced suffix arrays ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ FM-index of alignment: a compressed index for similar strings ⋮ Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds ⋮ Lyndon array construction during Burrows-Wheeler inversion ⋮ On position restricted substring searching in succinct space ⋮ Unnamed Item ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ The heaviest induced ancestors problem: better data structures and applications ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Grammar compressed sequences with rank/select support ⋮ Logarithmic equal-letter runs for BWT of purely morphic words ⋮ Approximate string matching with compressed indexes ⋮ Grammar-compressed indexes with logarithmic search time ⋮ A simple storage scheme for strings achieving entropy bounds ⋮ Compressed directed acyclic word graph with application in local alignment ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Space-time trade-offs for finding shortest unique substrings and maximal unique matches ⋮ Composite Repetition-Aware Data Structures ⋮ Succinct Non-overlapping Indexing ⋮ Dictionary Matching with Uneven Gaps ⋮ Compressed property suffix trees ⋮ A framework for space-efficient string kernels ⋮ Lossless Seeds for Searching Short Patterns with High Error Rates ⋮ On compressing and indexing repetitive sequences ⋮ Lightweight algorithms for constructing and inverting the BWT of string collections ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ Edge minimization in de Bruijn graphs ⋮ Multi-pattern matching with bidirectional indexes ⋮ Algorithms to compute the Burrows-Wheeler similarity distribution ⋮ String search experimentation using massive data ⋮ Hybrid indexes for repetitive datasets ⋮ Indexing a sequence for mapping reads with a single mismatch ⋮ Improved characters distance sampling for online and offline text searching ⋮ Encoding 2D range maximum queries ⋮ Ultra-succinct representation of ordered trees with applications ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Approximate all-pairs suffix/prefix overlaps ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ FM-index of alignment with gaps ⋮ Compressed text indexing with wildcards ⋮ Efficient online string matching based on characters distance text sampling ⋮ Parallel algorithms for Burrows-Wheeler compression and decompression ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ Wavelet trees for all ⋮ Fast relative Lempel-Ziv self-index for similar sequences ⋮ Succinct data structures for flexible text retrieval systems ⋮ A framework for designing space-efficient dictionaries for parameterized and order-preserving matching ⋮ Efficient fully-compressed sequence representations ⋮ Optimal indexes for sparse bit vectors ⋮ Universal compressed text indexing ⋮ Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ Fixed block compression boosting in FM-indexes: theory and practice ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ A simpler analysis of Burrows-Wheeler-based compression ⋮ Fast BWT in small space by blockwise suffix sorting ⋮ Faster suffix sorting ⋮ Rank and select revisited and extended ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Self-indexing Based on LZ77 ⋮ Lightweight BWT Construction for Very Large String Collections ⋮ A grouping approach for succinct dynamic dictionary matching ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Flexible indexing of repetitive collections ⋮ Distribution-aware compressed full-text indexes ⋮ Compressed string-matching in standard Sturmian words ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Ranked document retrieval for multiple patterns ⋮ Wee LCP ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Succinct non-overlapping indexing ⋮ A resource-frugal probabilistic dictionary and applications in bioinformatics ⋮ A brief history of parameterized matching problems ⋮ Refining the \(r\)-index ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Lightweight merging of compressed indices based on BWT variants ⋮ The alternating BWT: an algorithmic perspective ⋮ Wheeler languages ⋮ Locally Compressed Suffix Arrays ⋮ General Document Retrieval in Compact Space ⋮ Orthogonal Range Searching for Text Indexing ⋮ Indexes for Document Retrieval with Relevance ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Geometric BWT: compressed text indexing via sparse suffixes and range searching ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space ⋮ Compressing dictionary matching index via sparsification technique ⋮ Space-efficient substring occurrence estimation ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs ⋮ On the complexity of recognizing Wheeler graphs
