Novel results on the number of runs of the Burrows-Wheeler-transform

DOI10.1007/978-3-030-67731-2_18zbMath1490.68304arXiv2008.08506OpenAlexW3127806638MaRDI QIDQ831816

Shunsuke Inenaga, Anna Toffanello, Sara Giuliani, Marinella Sciortino, Zsuzsanna Lipták, Nicola Prezza

Publication date: 24 March 2022

Full work available at URL: https://arxiv.org/abs/2008.08506

zbMATH Keywords

repetitivenesscombinatorics on wordscompressed data structuresstring indexingBurrows-Wheeler-transform

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items (4)

Logarithmic equal-letter runs for BWT of purely morphic words ⋮ Bit catastrophes for the Burrows-Wheeler transform ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Constructing and indexing the bijective and extended Burrows-Wheeler transform

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Circular Sturmian words and Hopcroft's algorithm
• Burrows-Wheeler transform and Sturmian words
• A combinatorial property of the Fibonacci words
• Some combinatorial properties of Sturmian words
• Sturmian words: structure, combinatorics, and their arithmetics
• Sturmian words, Lyndon words and trees
• A faster implementation of online RLBWT and its application to LZ77 parsing
• Towards a definitive measure of repetitiveness
• Composite Repetition-Aware Data Structures
• On Christoffel classes
• Hopcroft’s Algorithm and Cyclic Automata
• Data compression via textual substitution
• On the Complexity of Finite Sequences
• Fast Pattern Matching in Strings
• Grammar-based codes: a new class of universal lossless source codes
• From LZ77 to the run-length encoded burrows-wheeler transform, and back
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• Online LZ77 Parsing and Matching Statistics with RLBWTs
• Complete inverted files for efficient text retrieval and analysis
• At the roots of dictionary compression: string attractors
• Optimal Construction of Compressed Indexes for Highly Repetitive Texts

This page was built for publication: Novel results on the number of runs of the Burrows-Wheeler-transform