Universal data compression based on the Burrows-Wheeler transformation: Theory and practice

被引：33

作者：

Balkenhol, B

Kurtz, S

机构：

[1] Univ Bielefeld, Fak Math, D-33501 Bielefeld, Germany

[2] Univ Bielefeld, Tech Fak, D-33501 Bielefeld, Germany

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2000年 / 49卷 / 10期

关键词：

lossless data compression; Burrows-Wheeler Transformation; context trees; suffix trees;

D O I：

10.1109/12.888040

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A very interesting recent development in data compression is the Burrows-Wheeler Transformation [1]. The idea is to permute the input sequence in such a way that characters with a similar context are grouped together. We provide a thorough analysis of the Burrows-Wheeler Transformation from an information theoretic point of view. Based on this analysis, the main part of the paper systematically considers techniques to efficiently implement a practical data compression program based on the transformation. We show that our program achieves a better compression rate than other programs that have similar requirements in space and time.

引用

页码：1043 / 1053

页数：11

共 36 条

[1] Universal coding of integers and unbounded search trees [J].

Ahlswede, R ;

Han, TS ;

Kobayashi, K .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1997, 43 (02) :669-682

[2] A corpus for the evaluation of lossless compression algorithms [J].

Arnold, R ;

Bell, T .

DCC '97 : DATA COMPRESSION CONFERENCE, PROCEEDINGS, 1997, :201-210

[3]

BALKENHOL B, 1998, UNIVERSAL DATA COMPR

[4]

Bell T. C., 1990, TEXT COMPRESSION

[5]

Burrows M, 1994, 124 DIG SYST RES CTR

[6]

Cleary J. G., 1995, Proceedings. DCC '95 Data Compression Conference (Cat. No.95TH8037), P52, DOI 10.1109/DCC.1995.515495

[7] DATA-COMPRESSION USING DYNAMIC MARKOV MODELING [J].

CORMACK, GV ;

HORSPOOL, RNS .

COMPUTER JOURNAL, 1987, 30 (06) :541-550

[8]

CROCHMORE M, 1997, P ANN S COMB PATT MA, P116

[9]

ELIAS P, 1975, IEEE T INFORM THEORY, V21, P194, DOI 10.1109/TIT.1975.1055349

[10]

FARACH M, 1997, P 38 ANN S FDN COMP

← 1 2 3 4 →