Word-based block-sorting text compression

R. Yugo Kartono Isal; A. Moffat

doi:10.1109/ACSC.2001.906628

Word-based block-sorting text compression

R. Yugo Kartono Isal, A. Moffat

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Citations (Scopus)

Abstract

Block sorting is an innovative compression mechanism introduced in by M. Burrows and D.J. Wheeler (1994). 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 transformations as an alternative to MTF, and are able to show improved compression results compared to MTF. For large text files, the combination of word-based modelling, BWT and MTF-like transformations allows excellent compression effectiveness to be attained within reasonable resource costs.

Original language	English
Title of host publication	Proceedings - 24th Australasian Computer Science Conference, ACSC 2001
Editors	Michael Oudshoom
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	92-99
Number of pages	8
ISBN (Electronic)	0769509630, 9780769509631
DOIs	https://doi.org/10.1109/ACSC.2001.906628
Publication status	Published - 2001
Event	24th Australasian Computer Science Conference, ACSC 2001 - Gold Coast, Australia Duration: 29 Jan 2001 → 2 Feb 2001

Publication series

Name	Proceedings - 24th Australasian Computer Science Conference, ACSC 2001

Conference

Conference	24th Australasian Computer Science Conference, ACSC 2001
Country/Territory	Australia
City	Gold Coast
Period	29/01/01 → 2/02/01

Access to Document

10.1109/ACSC.2001.906628

Cite this

Isal, R. Y. K., & Moffat, A. (2001). Word-based block-sorting text compression. In M. Oudshoom (Ed.), Proceedings - 24th Australasian Computer Science Conference, ACSC 2001 (pp. 92-99). Article 906628 (Proceedings - 24th Australasian Computer Science Conference, ACSC 2001). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACSC.2001.906628

@inproceedings{d8eca01ac17c4eee9eed302f12d64660,

title = "Word-based block-sorting text compression",

abstract = "Block sorting is an innovative compression mechanism introduced in by M. Burrows and D.J. Wheeler (1994). 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 transformations as an alternative to MTF, and are able to show improved compression results compared to MTF. For large text files, the combination of word-based modelling, BWT and MTF-like transformations allows excellent compression effectiveness to be attained within reasonable resource costs.",

author = "Isal, {R. Yugo Kartono} and A. Moffat",

note = "Publisher Copyright: {\textcopyright} 2001 IEEE.; 24th Australasian Computer Science Conference, ACSC 2001 ; Conference date: 29-01-2001 Through 02-02-2001",

year = "2001",

doi = "10.1109/ACSC.2001.906628",

language = "English",

series = "Proceedings - 24th Australasian Computer Science Conference, ACSC 2001",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "92--99",

editor = "Michael Oudshoom",

booktitle = "Proceedings - 24th Australasian Computer Science Conference, ACSC 2001",

address = "United States",

}

Isal, RYK & Moffat, A 2001, Word-based block-sorting text compression. in M Oudshoom (ed.), Proceedings - 24th Australasian Computer Science Conference, ACSC 2001., 906628, Proceedings - 24th Australasian Computer Science Conference, ACSC 2001, Institute of Electrical and Electronics Engineers Inc., pp. 92-99, 24th Australasian Computer Science Conference, ACSC 2001, Gold Coast, Australia, 29/01/01. https://doi.org/10.1109/ACSC.2001.906628

Word-based block-sorting text compression. / Isal, R. Yugo Kartono; Moffat, A.
Proceedings - 24th Australasian Computer Science Conference, ACSC 2001. ed. / Michael Oudshoom. Institute of Electrical and Electronics Engineers Inc., 2001. p. 92-99 906628 (Proceedings - 24th Australasian Computer Science Conference, ACSC 2001).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Word-based block-sorting text compression

AU - Isal, R. Yugo Kartono

AU - Moffat, A.

PY - 2001

Y1 - 2001

N2 - Block sorting is an innovative compression mechanism introduced in by M. Burrows and D.J. Wheeler (1994). 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 transformations as an alternative to MTF, and are able to show improved compression results compared to MTF. For large text files, the combination of word-based modelling, BWT and MTF-like transformations allows excellent compression effectiveness to be attained within reasonable resource costs.

AB - Block sorting is an innovative compression mechanism introduced in by M. Burrows and D.J. Wheeler (1994). 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 transformations as an alternative to MTF, and are able to show improved compression results compared to MTF. For large text files, the combination of word-based modelling, BWT and MTF-like transformations allows excellent compression effectiveness to be attained within reasonable resource costs.

UR - http://www.scopus.com/inward/record.url?scp=34547622455&partnerID=8YFLogxK

U2 - 10.1109/ACSC.2001.906628

DO - 10.1109/ACSC.2001.906628

M3 - Conference contribution

AN - SCOPUS:34547622455

T3 - Proceedings - 24th Australasian Computer Science Conference, ACSC 2001

SP - 92

EP - 99

BT - Proceedings - 24th Australasian Computer Science Conference, ACSC 2001

A2 - Oudshoom, Michael

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 24th Australasian Computer Science Conference, ACSC 2001

Y2 - 29 January 2001 through 2 February 2001

ER -

Word-based block-sorting text compression

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this