Compressed representations of sequences and full-text indexes
From MaRDI portal
Publication:2944557
DOI10.1145/1240233.1240243zbMath1321.68263MaRDI QIDQ2944557
Veli Mäkinen, Paolo Ferragina, Giovanni Manzini, Gonzalo Navarro
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1240233.1240243
entropy; Burrows-Wheeler transform; text compression; text indexing; rank and select; wavelet tree; compression boosting
68P15: Database theory
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
68W32: Algorithms on strings
Related Items
Space-efficient substring occurrence estimation, Succinct dynamic cardinal trees, Compressed string dictionary search with edit distance one, Automata evaluation and text search protocols with simulation-based security, Fast construction of wavelet trees, Approximate string matching using a bidirectional index, Compressed property suffix trees, Compact binary relation representations with rich functionality, Space efficient data structures for dynamic orthogonal range counting, Compressed indexes for text with wildcards, Colored range queries and document retrieval, On compressing and indexing repetitive sequences, On compressing permutations and adaptive sorting, Top-\(k\) document retrieval in optimal space, On-line construction of position heaps, Multi-pattern matching with bidirectional indexes, Cross-document pattern matching, Bounds from a card trick, On the number of elements to reorder when updating a suffix array, Bidirectional search in a string with wavelet trees and bidirectional matching statistics, Approximate all-pairs suffix/prefix overlaps, New algorithms on wavelet trees and applications to information retrieval, Efficient fully-compressed sequence representations, Tight and simple web graph compression for forward and reverse neighbor queries, Tighter bounds for the sum of irreducible LCP values, Combined data structure for previous- and next-smaller-values, A quick tour on suffix arrays and compressed suffix arrays, Space-efficient construction of Lempel-Ziv compressed text indexes, Improved data structures for the orthogonal range successor problem, Finding range minima in the middle: approximations and applications, On approximate jumbled pattern matching in strings, Succinct data structures for searchable partial sums with optimal worst-case performance, Lempel-Ziv-78 compressed string dictionaries, On prefix normal words and prefix normal forms, A four-stage algorithm for updating a Burrows-Wheeler transform, Dynamic rank/select structures with applications to run-length encoded texts, Rank/select on dynamic compressed sequences and applications, Computationally secure pattern matching in the presence of malicious adversaries, Improved parallel construction of wavelet trees and rank/select structures, Large alphabets and incompressibility, Counting suffix arrays and strings, Dynamic extended suffix arrays, Optimal prefix and suffix queries on texts, Move-to-front, distance coding, and inversion frequencies revisited, On compact representations of all-pairs-shortest-path-distance matrices, Wee LCP, Faster entropy-bounded compressed suffix trees, Lyndon array construction during Burrows-Wheeler inversion, Approximate string matching with compressed indexes, Towards efficient positional inverted index, Wheeler graphs: a framework for BWT-based data structures, Time-space trade-offs for Lempel-Ziv compressed indexing, Practical compressed suffix trees, Fixed block compression boosting in FM-indexes: theory and practice, LRM-trees: compressed indices, adaptive sorting, and compressed permutations, Ranked document retrieval for multiple patterns, Fast compressed self-indexes with deterministic linear-time construction, New space/time tradeoffs for top-\(k\) document retrieval on sequences, Distribution-aware compressed full-text indexes, Range majorities and minorities in arrays, The exact multiple pattern matching problem solved by a reference tree approach, Top tree compression of tries, Faster online computation of the succinct longest previous factor array, Space efficient merging of de Bruijn graphs and Wheeler graphs, Practical space-efficient index for structural pattern matching, Using compressed suffix-arrays for a compact representation of temporal-graphs, A framework for designing space-efficient dictionaries for parameterized and order-preserving matching, Lempel-Ziv compressed structures for document retrieval, Lightweight merging of compressed indices based on BWT variants, Sliding suffix tree, Improved and extended locating functionality on compressed suffix arrays, Bottom-\(k\) document retrieval, Geometric BWT: compressed text indexing via sparse suffixes and range searching, Top-\(k\) term-proximity in succinct space, Succinct indices for path minimum, with applications, Engineering a lightweight external memory suffix array construction algorithm, Faster average case low memory semi-external construction of the Burrows-Wheeler transform, On position restricted substring searching in succinct space, The myriad virtues of wavelet trees, Grammar compressed sequences with rank/select support, Algorithms to compute the Burrows-Wheeler similarity distribution, Stronger Lempel-Ziv based compressed text indexing, Lightweight data indexing and compression in external memory, Compressed text indexing with wildcards, Wavelet trees for all, On the combinatorics of suffix arrays, Fast relative Lempel-Ziv self-index for similar sequences, Faster semi-external suffix sorting, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, Fast BWT in small space by blockwise suffix sorting, Rank and select revisited and extended, The affix array data structure and its applications to RNA secondary structure analysis, Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds, Grammar-compressed indexes with logarithmic search time, Faster repetition-aware compressed suffix trees based on block trees, Fully Functional Static and Dynamic Succinct Trees, Locally Compressed Suffix Arrays, General Document Retrieval in Compact Space, Random Access to High-Order Entropy Compressed Text, Succinct and Implicit Data Structures for Computational Geometry, Better External Memory LCP Array Construction, Unnamed Item, Unnamed Item, Unnamed Item, Lightweight BWT and LCP Merging via the Gap Algorithm, Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression, Compressed Multiple Pattern Matching, A new class of searchable and provably highly compressible string transformations, Indexing the bijective BWT, LZ-End Parsing in Linear Time, Structural Pattern Matching - Succinctly., Lazy Lempel-Ziv Factorization Algorithms, LCP Array Construction in External Memory, Faster Compressed Suffix Trees for Repetitive Collections, Fast Compressed Self-Indexes with Deterministic Linear-Time Construction, Practical Compact Indexes for Top-kDocument Retrieval, Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies, Bidirectional Variable-Order de Bruijn Graphs, Efficient Data Structures for the Orthogonal Range Successor Problem, SpliceTAPyR — An Efficient Method for Transcriptome Alignment, Unnamed Item, Space efficient algorithms for the Burrows-Wheeler backtransformation, Unnamed Item, Compact representations of spatial hierarchical structures with support for topological queries, A new class of string transformations for compressed text indexing, String Indexing with Compressed Patterns, Random access in persistent strings and segment selection, Orthogonal Range Searching for Text Indexing, Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts, Succinct Non-overlapping Indexing, Lossless Seeds for Searching Short Patterns with High Error Rates, Time-Optimal Top-$k$ Document Retrieval, The longest common substring problem, Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet, Succincter Text Indexing with Wildcards, Self-indexing Based on LZ77, Counting Colours in Compressed Strings, LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations, Unnamed Item, Self-indexed Text Compression Using Straight-Line Programs, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing, Space-Efficient Frameworks for Top- k String Retrieval, Algorithms for Indexing Highly Similar DNA Sequences, Full-Text Indexes for High-Throughput Sequencing, Access, Rank, and Select in Grammar-compressed Strings, Compressed Data Structures for Dynamic Sequences, An Online Algorithm for Finding the Longest Previous Factors, On the Value of Multiple Read/Write Streams for Data Compression, Permuted Longest-Common-Prefix Array
