Inversion coding

被引：22

作者：

Arnavut, Z ^{[1
]}

机构：

[1] SUNY Coll Fredonia, Dept Math & Comp Sci, Fredonia, NY 14063 USA

来源：

COMPUTER JOURNAL | 2004年 / 47卷 / 01期

关键词：

D O I：

10.1093/comjnl/47.1.46

中图分类号：

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

学科分类号：

0812 ;

摘要：

The Burrows-Wheeler Compression (BWC) described by Burrows and Wheeler has received considerable attention. An essential part of BWC schemes is the Move-to-Front coder (recency ranking). In this paper we introduce a different coding (ranking) scheme, the inversion coder. We prove the information theoretic relationship between interval ranks and canonical sorting permutations. We also introduce a faster and more memory efficient-algorithm for inversion ranks. Finally, we explore the relationship between inversion ranks and recency ranks and show that inversion coding is superior to interval ranking as well as recency ranking.

引用

页码：46 / 57

页数：12

共 25 条

[1]

Arnavut Z., 2000, Proceedings DCC 2000. Data Compression Conference, P193, DOI 10.1109/DCC.2000.838159

[2] Block sorting and compression [J].

Arnavut, Z ;

Magliveras, SS .

DCC '97 : DATA COMPRESSION CONFERENCE, PROCEEDINGS, 1997, :181-190

[3]

ARNAVUT Z, 1995, THESIS U NEBRASKA LI

[4]

ARNAVUT Z, 2002, P DAT COMPR C SNOWB, P451

[5] Universal data compression based on the Burrows-Wheeler transformation: Theory and practice [J].

Balkenhol, B ;

Kurtz, S .

IEEE TRANSACTIONS ON COMPUTERS, 2000, 49 (10) :1043-1053

[6] A LOCALLY ADAPTIVE DATA-COMPRESSION SCHEME [J].

BENTLEY, JL ;

SLEATOR, DD ;

TARJAN, RE ;

WEI, VK .

COMMUNICATIONS OF THE ACM, 1986, 29 (04) :320-330

[7]

BURROWS M, 1994, 124 SRC DIG SYST RES

[8]

Chapin B., 2000, Proceedings DCC 2000. Data Compression Conference, P183, DOI 10.1109/DCC.2000.838158

[9]

Deorowicz S, 2000, SOFTWARE PRACT EXPER, V30, P1465, DOI 10.1002/1097-024X(20001110)30:13<1465::AID-SPE345>3.0.CO

[10]

2-D

← 1 2 3 →