Back to Search
Start Over
On fixed points of the Burrows-Wheeler transform
- Publication Year :
- 2017
- Publisher :
- IOS Press, 2017.
-
Abstract
- The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of "clustering" together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet a, b having at most four b's and those having at most four a's.
- Subjects :
- Discrete mathematics
Algebra and Number Theory
Burrows–Wheeler transform
Settore INF/01 - Informatica
Permutation
Permutations
0102 computer and information sciences
02 engineering and technology
Information System
Fixed point
01 natural sciences
Theoretical Computer Science
Computational Theory and Mathematics
010201 computation theory & mathematics
Fixed Point
Fixed Points
0202 electrical engineering, electronic engineering, information engineering
Burrows-Wheeler Transform
Information Systems
020201 artificial intelligence & image processing
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....9142b8b300585ce9476680066658b6c8