Indexing compressed text
From MaRDI portal
Publication:3546296
DOI10.1145/1082036.1082039zbMATH Open1323.68261OpenAlexW2159647614WikidataQ124796874 ScholiaQ124796874MaRDI QIDQ3546296FDOQ3546296
Authors: Paolo Ferragina, Giovanni Manzini 
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
Recommendations
- New text indexing functionalities of the compressed suffix arrays
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- scientific article; zbMATH DE number 2079421
- Practical approaches to reduce the space requirement of Lempel-Ziv-based compressed text indices
full-text indexingsuffix treesuffix arrayBurrows-Wheeler transformtext compressionpattern searchingindexing data structureLempel-Ziv compressor
Information storage and retrieval of data (68P20) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cited In (only showing first 100 items - show all)
- The Heaviest Induced Ancestors Problem Revisited
- Fast compressed self-indexes with deterministic linear-time construction
- The Burrows-Wheeler transform between data compression and combinatorics on words
- Edge minimization in de Bruijn graphs
- A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
- Computing the multi-string BWT and LCP array in external memory
- Grammar compressed sequences with rank/select support
- Structural Pattern Matching - Succinctly.
- Wheeler languages
- Title not available (Why is that?)
- Lightweight merging of compressed indices based on BWT variants
- Flexible indexing of repetitive collections
- An external-memory algorithm for string graph construction
- Improved and extended locating functionality on compressed suffix arrays
- Engineering a lightweight external memory suffix array construction algorithm
- Extended suffix array construction using Lyndon factors
- Computational graph pangenomics: a tutorial on data structures and their applications
- A new class of searchable and provably highly compressible string transformations
- Prefix-Free Parsing for Building Big BWTs
- Lyndon array construction during Burrows-Wheeler inversion
- Bidirectional Variable-Order de Bruijn Graphs
- Algorithms to compute the Burrows-Wheeler similarity distribution
- Dictionary Matching with Uneven Gaps
- The heaviest induced ancestors problem: better data structures and applications
- On the Hardness and Inapproximability of Recognizing Wheeler Graphs
- Refining the \(r\)-index
- Forty Years of Text Indexing
- Ranked document retrieval for multiple patterns
- Logarithmic equal-letter runs for BWT of purely morphic words
- Lempel-Ziv compressed structures for document retrieval
- Grammar-compressed indexes with logarithmic search time
- Title not available (Why is that?)
- Algorithms for Indexing Highly Similar DNA Sequences
- Compressed spaced suffix arrays
- Distribution-aware compressed full-text indexes
- Distribution-aware compressed full-text indexes
- General document retrieval in compact space
- Title not available (Why is that?)
- Space efficient merging of de Bruijn graphs and Wheeler graphs
- A brief history of parameterized matching problems
- A resource-frugal probabilistic dictionary and applications in bioinformatics
- Parallel computation of the Burrows Wheeler transform in compact space
- The alternating BWT: an algorithmic perspective
- Haplotype-aware graph indexes
- Time-space trade-offs for Lempel-Ziv compressed indexing
- FM-index of alignment with gaps
- On position restricted substring searching in succinct space
- Dictionary matching with a bounded gap in pattern or in text
- Efficient online string matching based on characters distance text sampling
- Indexing the bijective BWT
- Lightweight algorithms for constructing and inverting the BWT of string collections
- Optimal indexes for sparse bit vectors
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- Practical Compact Indexes for Top-kDocument Retrieval
- Compression and Ranking
- Multi-pattern matching with bidirectional indexes
- Space-efficient substring occurrence estimation
- Parallel algorithms for Burrows-Wheeler compression and decompression
- Ultra-succinct representation of ordered trees with applications
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Title not available (Why is that?)
- Compressed string dictionary search with edit distance one
- Space-efficient construction of Lempel-Ziv compressed text indexes
- A quick tour on suffix arrays and compressed suffix arrays
- Compressed string-matching in standard Sturmian words
- Succinct data structures for searchable partial sums with optimal worst-case performance
- Approximate all-pairs suffix/prefix overlaps
- Compression, indexing, and retrieval for massive string data
- Efficient fully-compressed sequence representations
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- Wheeler graphs: a framework for BWT-based data structures
- CUSHAW Suite: Parallel and Efficient Algorithms for NGS Read Alignment
- A simple storage scheme for strings achieving entropy bounds
- Computing the Burrows-Wheeler transform in place and in small space
- A linear lower bound on index size for text retrieval
- Compressing dictionary matching index via sparsification technique
- Self-indexing based on LZ77
- Lightweight BWT construction for very large string collections
- Lempel-Ziv factorization powered by space efficient suffix trees
- An experimental study of a compressed index
- FM-index of alignment: a compressed index for similar strings
- Indexed multi-pattern matching
- Compressed property suffix trees
- On compressing and indexing repetitive sequences
- New algorithms on wavelet trees and applications to information retrieval
- On the complexity of recognizing Wheeler graphs
- A simple storage scheme for strings achieving entropy bounds
- Succinct data structures for flexible text retrieval systems
- Rank and select revisited and extended
- Locally compressed suffix arrays
- Encoding 2D range maximum queries
- Fast BWT in small space by blockwise suffix sorting
- Wee LCP
- Succinct non-overlapping indexing
- Linked dynamic tries with applications to LZ-compression in sublinear time and space
- Stronger Lempel-Ziv based compressed text indexing
- A simpler analysis of Burrows-Wheeler-based compression
- Orthogonal range searching for text indexing
- Indexes for document retrieval with relevance
- Space-efficient frameworks for top-\(k\) string retrieval
This page was built for publication: Indexing compressed text
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546296)
