An analysis of the Burrows—Wheeler transform
From MaRDI portal
Publication:3196619
DOI10.1145/382780.382782zbMath1323.68262OpenAlexW1965853364MaRDI QIDQ3196619
Publication date: 30 October 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/382780.382782
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items (73)
Compressed string dictionary search with edit distance one ⋮ Top-\(k\) term-proximity in succinct space ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Compressed Data Structures for Dynamic Sequences ⋮ Large alphabets and incompressibility ⋮ Dynamic Shannon coding ⋮ The myriad virtues of wavelet trees ⋮ Succinct 2D dictionary matching ⋮ Approximate string matching with compressed indexes ⋮ A simple storage scheme for strings achieving entropy bounds ⋮ The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words ⋮ Can Burrows-Wheeler transform be replaced in chain code compression? ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Measuring the clustering effect of BWT via RLE ⋮ Colored range queries and document retrieval ⋮ On compressing and indexing repetitive sequences ⋮ A new class of string transformations for compressed text indexing ⋮ Bounds from a card trick ⋮ Efficient chain code compression with interpolative coding ⋮ Finding range minima in the middle: approximations and applications ⋮ Quasi-distinct parsing and optimal compression methods ⋮ Monge properties of sequence alignment ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ Unnamed Item ⋮ On optimally partitioning a text to improve its compression ⋮ Lempel-Ziv-like parsing in small space ⋮ Wavelet trees for all ⋮ When a dollar makes a BWT ⋮ Efficient fully-compressed sequence representations ⋮ A framework for succinct labeled ordinal trees over large alphabets ⋮ Practical compressed suffix trees ⋮ High-order entropy compressed bit vectors with rank/select ⋮ Fixed block compression boosting in FM-indexes: theory and practice ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ A simpler analysis of Burrows-Wheeler-based compression ⋮ From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization ⋮ Fast BWT in small space by blockwise suffix sorting ⋮ Faster suffix sorting ⋮ Compressing table data with column dependency ⋮ Rank and select revisited and extended ⋮ Two Combinatorial Criteria for BWT Images ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Self-indexing Based on LZ77 ⋮ Balancing and clustering of words in the Burrows-Wheeler transform ⋮ Spaces, Trees, and Colors ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ A note on the Burrows-Wheeler transformation ⋮ New space/time tradeoffs for top-\(k\) document retrieval on sequences ⋮ Move-to-front, distance coding, and inversion frequencies revisited ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Wee LCP ⋮ Space efficient algorithms for the Burrows-Wheeler backtransformation ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Dynamic rank/select structures with applications to run-length encoded texts ⋮ Rank/select on dynamic compressed sequences and applications ⋮ Burrows-Wheeler transform and Sturmian words ⋮ The alternating BWT: an algorithmic perspective ⋮ Quasi-distinct Parsing and Optimal Compression Methods ⋮ On the Value of Multiple Read/Write Streams for Data Compression ⋮ Compressed Multiple Pattern Matching ⋮ A new class of searchable and provably highly compressible string transformations ⋮ Locally Compressed Suffix Arrays ⋮ General Document Retrieval in Compact Space ⋮ Faster entropy-bounded compressed suffix trees ⋮ Random Access to High-Order Entropy Compressed Text ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Parameterized analysis of paging and list update algorithms ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Faster Compressed Suffix Trees for Repetitive Collections ⋮ Fast Compressed Self-Indexes with Deterministic Linear-Time Construction ⋮ Space-efficient substring occurrence estimation ⋮ Succinct dynamic cardinal trees
This page was built for publication: An analysis of the Burrows—Wheeler transform
