Balancing and clustering of words in the Burrows-Wheeler transform

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

zbMATH Keywords

data compression; Burrows-Wheeler transform; combinatorics on words

Mathematics Subject Classification ID

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, Palindromic richness for languages invariant under more symmetries

Uses Software

• Canterbury

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