Improving Burrows-Wheeler block sorting compression via text filtering

• Autorzy: Grabowski S.

Warianty tytułu

PL

Poprawa efektywności algorytmu kompresji Burrowsa-Wheelera przy użyciu filtrowania tekstu

• Języki publikacji: EN

Abstrakty

EN

Burrows-Wheeler block sorting algorithm is one of the most attractive lossless compression methods. In this paper we present several ideas attempting to improve text compression while retaining the speed. All of them are performed before actual coding in an independent preprocessing (filtering) phase which yields flexibility of the coder selection. Experiments with bzip, a well known block sorting implementation, indicate 2-4 per cent compression gains for typical English texts.

PL

Algorytm Burrowsa-Wheelera jest jedną z najatrakcyjniejszych metod kompresji bezstratnej. W pracy przedstawiamy szereg idei mających na celu poprawę kompresji tekstu przy zachowaniu szybkości algorytmu. Wszystkie usprawnienia są transformacjami (filtrami) na oryginalnych danych, przeprowadzanymi przed zasadniczym kodowaniem. Umożliwia to swobodny wybór kodera. Eksperymenty z bzip, znaną implementacją algorytmu Burrowsa-Wheelera, wskazują na 2-4-procentową poprawę kompresji typowych tekstów w języku angielskim.

Słowa kluczowe

EN

compression algorithm; Burrows-Wheeler algorithm; lossless compression; text filtering

PL

algorytm kompresji; algorytm Burrowsa-Wheelera; kompresja bezstratna; filtrowanie tekstu

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Zeszyty Naukowe. Elektryka / Politechnika Łódzka
• Rocznik: 2001
• Tom: z. 95
• Strony: 5--16
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Grabowski S.

• Technical University of Lodz, Computer Engineering Department

Bibliografia

• [1] Balkenhol В. and Kurtz S.: Universal Data Compression Based on the Burrows and Wheeler-Transformation: Theory and Practice, SFB343, Discrete Strukturen in der Mathematik, 98-069, 1998.
• [2] Burrows M. and Wheeler D. J.: A block-sorting Lossless Data Compression Algorithm, SRC Research Report 124, Digital Systems Research Center, Palo Alto, CA, May 1994. Also available at http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html.
• [3] Chapin B. and. Tate S. R: Higher Compression from the Burrows-Wheeler Transform by Modified Sorting, University of North Texas, Department of Computer Science, 1998. Also available at http://www.cs.unt.edu/~srt/papers/ bwtsort.pdf.
• [4] Fenwick P.: Experiments with a Block Sorting Text Compression Algorithm, The University of Auckland, Department of Computer Science, Tech. Rep. 111, May 1995. Also available at ftp://ftp.cs.auckland.ac.nz/out/peter-f/TechRep111.ps.
• [5] Fenwick P.: Block Sorting Text Compression, Proceedings of the 19th Australasian Computer Science Conference, Melbourne, Australia. Jan 31 - Feb 2, 1996. Also available at ftp://ftp.cs.auckland. ac.nz/pub/peter-f/ACSC96paper.ps.
• [6] Teahan B.: Modelling English text, PhD thesis, Department of Computer Science, The University of Waikato, Hamilton, New Zealand, May 1998.