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 条

[11]

FENWICK P, 1996, 130 U AUCKL DEP COMP

[12]

GAILLY J, 1993, GZIP PROGRAM VERSION

[13] A comparison of imperative and purely functional suffix tree constructions [J].