Improving Burrows-Wheeler block sorting compression via text filtering

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.

---

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.