Word-based text compression using the Burrows-Wheeler transform

Alistair Moffat, R. Yugo Kartono Isal

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

Block-sorting is an innovative compression mechanism introduced in 1994 by Burrows and Wheeler. It involves three steps: permuting the input one block at a time through the use of the Burrows-Wheeler transform (bwt); applying a move-to-front (mtf) transform to each of the permuted blocks; and then entropy coding the output with a Huffman or arithmetic coder. Until now, block-sorting implementations have assumed that the input message is a sequence of characters. In this paper we extend the block-sorting mechanism to word-based models. We also consider other recency transformations, and are able to show improved compression results compared to mtf and uniform arithmetic coding. For large files of text, the combination of word-based modeling, bwt, and mtf-like transformations allows excellent compression effectiveness to be attained within reasonable resource costs.

Original languageEnglish
Pages (from-to)1175-1192
Number of pages18
JournalInformation Processing and Management
Volume41
Issue number5
DOIs
Publication statusPublished - 1 Sep 2005

Keywords

  • Burrows-Wheeler transformation
  • Move-to-Front
  • Recency ranking
  • Text compression
  • Word-based model

Fingerprint Dive into the research topics of 'Word-based text compression using the Burrows-Wheeler transform'. Together they form a unique fingerprint.

Cite this