On Fixed Points of the Burrows-Wheeler Transform

• Autorzy: Mantaci S. , Restivo A. , Rosone G. , Russo F. , Sciortino M.

Identyfikatory

DOI

10.3233/FI-2017-1566

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Burrows-Wheeler transform; permutations; fixed points

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 277--288
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Mantaci S.

• Dipartimento di Matematica e Informatica, University of Palermo, Italy

autor

Restivo A.

• Dipartimento di Matematica e Informatica, University of Palermo, Italy

autor

Rosone G.

• Dipartimento di Informatica, University of Pisa, Italy

autor

Russo F.

• Dipartimento di Matematica e Informatica, University of Palermo, Italy

autor

Sciortino M.

• Dipartimento di Matematica e Informatica, University of Palermo, Italy

Bibliografia

• [1] Seward J. The BZIP2 Home Page. URL http://www.bzip.org.
• [2] Schindler M. A Fast Block-Sorting Algorithm for Lossless Data Compression. Data Compression Conference, IEEE Computer Society 1997. doi:10.1109/DCC.1997.582137.
• [3] Ferragina P, Manzini G. Indexing compressed text. J. ACM, 2005;52(4):552–581. doi:10.1145/1082036.1082039.
• [4] Burrows M, Wheeler DJ. A Block Sorting data Compression Algorithm. Technical report, DIGITAL System Research Center, 1994. URL https://books.google.pl/books?id=wPIkAQAAIAAJ.
• [5] Gessel IM, Reutenauer C. Counting permutations with given cycle structure and descent set. J. Combin. Theory Ser. A, 1993;64(2):189–215. URL https://doi.org/10.1016/0097-3165(93)90095-P.
• [6] Crochemore M, Désarménien J, Perrin D. A note on the Burrows-Wheeler transformation. Theoret. Comput. Sci., 2005;332(1-3):567–572. URL https://doi.org/10.1016/j.tcs.2004.11.014.
• [7] Mantaci S, Restivo A, Rosone G, Sciortino M. An extension of the Burrows-Wheeler Transform. Theoret. Comput. Sci., 2007;387(3):298–312. URL https://doi.org/10.1016/j.tcs.2007.07.014.
• [8] Mantaci S, Restivo A, Rosone G, Sciortino M. A New Combinatorial Approach to Sequence Comparison. Theory Comput. Syst., 2008;42(3):411–429. doi:10.1007/s00224-007-9078-6.
• [9] Likhomanov KM, Shur AM. Two Combinatorial Criteria for BWT Images. volume 6651 of LNCS, pp. 385–396. Springer. ISBN 978-3-642-20711-2,_2011.
• [10] Higgins PM. Burrows-Wheeler transformations and de Bruijn words. Theor. Comput. Sci., 2012. 457:128–136. doi:10.1016/j.tcs.2012.07.019. URL http://dx.doi.org/10.1016/j.tcs.2012.07.019.
• [11] Mantaci S, Restivo A, Sciortino M. Burrows-Wheeler transform and Sturmian words. Information Processing Letters, 2003;86:241–246. URL https://doi.org/10.1016/S0020-0190(02)00512-4.
• [12] Lothaire M. Algebraic Combinatorics on Words. Cambridge University Press, 2002. URL https://doi.org/10.1017/CBO9781107326019.
• [13] Simpson J, Puglisi SJ. Words with simple Burrows-Wheeler transforms. Electronic Journal of Combinatorics, article R83, vol. 15, 2008.
• [14] Restivo A, Rosone G. Burrows-Wheeler transform and palindromic richness. Theoret. Comput. Sci., 2009;410(30-32):3018–3026. doi:10.1016/j.tcs.2009.03.008.
• [15] Ferenczi S, Zamboni LQ. Clustering Words and Interval Exchanges. Journal of Integer Sequences, 2013;16(2):Article 13.2.1. URL https://hal.archives-ouvertes.fr/hal-01263786.
• [16] Restivo A, Rosone G. Balancing and clustering of words in the Burrows-Wheeler transform. Theoret. Comput. Sci., 2011;412(27):3019–3032. URL https://doi.org/10.1016/j.tcs.2010.11.040.
• [17] Perrin D, Restivo A. Words. In: Handbook of Enumerative Combinatorics. CRC Press, 2015.