Balancing and clustering of words in the Burrows-Wheeler transform
From MaRDI portal
Publication:544888
DOI10.1016/j.tcs.2010.11.040zbMath1220.68081MaRDI QIDQ544888
Giovanna Rosone, Antonio Restivo
Publication date: 16 June 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.040
68R15: Combinatorics on words
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Related Items
The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words, Perfect balance and circularly rich words, Palindromic richness for languages invariant under more symmetries, Measuring the clustering effect of BWT via RLE, A combinatorial view on string attractors, When a dollar makes a BWT, The alternating BWT: an algorithmic perspective
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On a generalization of Christoffel words: epichristoffel words
- Palindromic richness
- Burrows-Wheeler transform and Sturmian words
- Words with simple Burrows-Wheeler transforms
- Sturmian words: structure, combinatorics, and their arithmetics
- Covering the positive integers by disjoint sets of the form \(\{[n\alpha+\beta: n=1,2,\dots \}\)]
- Fraenkel's conjecture for six sequences
- Episturmian words and episturmian morphisms
- Balanced words
- Characterisations of balanced words via orderings
- A new characteristic property of rich words
- Burrows-Wheeler transform and palindromic richness
- A characterization of balanced episturmian sequences
- A connection between palindromic and factor complexity using return words
- A simpler analysis of Burrows-Wheeler-based compression
- Complementing and exactly covering sequences
- An analysis of the Burrows—Wheeler transform
- Balanced sequences and optimal routing
- Move-to-Front, Distance Coding, and Inversion Frequencies Revisited
- Most Burrows-Wheeler Based Compressors Are Not Optimal
- Boosting textual compression in optimal linear time
- Balanced Words Having Simple Burrows-Wheeler Transform
- A locally adaptive data compression scheme
- Représentation géométrique de suites de complexité $2n+1$
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Episturmian morphisms and a Galois theorem on continued fractions
- Episturmian words: a survey
- The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
- Minimizing Service and Operation Costs of Periodic Scheduling
- Symbolic Dynamics II. Sturmian Trajectories
- Episturmian words and some constructions of de Luca and Rauzy