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)
- 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
- Extended suffix array construction using Lyndon factors
- 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
- Dictionary Matching with Uneven Gaps
- 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
- Approximate string matching with compressed indexes
- Lazy Lempel-Ziv Factorization Algorithms
- Self-indexed Text Compression Using Straight-Line Programs
- Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
- On Undetected Redundancy in the Burrows-Wheeler Transform
- Faster suffix sorting
- Position-Restricted Substring Searching
- Succinct Non-overlapping Indexing
- Space-time trade-offs for finding shortest unique substrings and maximal unique matches
- Geometric BWT: compressed text indexing via sparse suffixes and range searching
- Compressed text indexing with wildcards
- Wavelet trees for all
- Composite Repetition-Aware Data Structures
- Fast relative Lempel-Ziv self-index for similar sequences
- New text indexing functionalities of the compressed suffix arrays
- A framework for space-efficient string kernels
- Title not available (Why is that?)
- A grouping approach for succinct dynamic dictionary matching
- Dynamic relative compression, dynamic partial sums, and substring concatenation
- Universal compressed text indexing
- Fixed block compression boosting in FM-indexes: theory and practice
- Compressed directed acyclic word graph with application in local alignment
- Space-Efficient Frameworks for Top- k String Retrieval
- Hybrid indexes for repetitive datasets
- Online LZ77 Parsing and Matching Statistics with RLBWTs
- A new class of string transformations for compressed text indexing
- A Succinct Solution to Rmap Alignment
- The Heaviest Induced Ancestors Problem Revisited
- Fast compressed self-indexes with deterministic linear-time construction
- Arithmetics on Suffix Arrays of Fibonacci Words
- 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
- Engineering Practical Lempel-Ziv Tries
- Practical Wavelet Tree Construction
- LZ78 Compression in Low Main Memory Space
- Computing the multi-string BWT and LCP array in external memory
- Grammar compressed sequences with rank/select support
- Analysis of Min-Hashing for Variant Tolerant DNA Read Mapping
- 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
- Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds
- Computational graph pangenomics: a tutorial on data structures and their applications
- A new class of searchable and provably highly compressible string transformations
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)
