Compression and Indexing Based on BWT: A Survey

Author

Dengfeng Zhang ; Qing Liu ; Yuewan Wu ; Yaping Li ; Lin Xiao

Author_Institution

Sch. of Inf., Renmin Univ. of China, Beijing, China

fYear

2013

Firstpage

61

Lastpage

64

Abstract

Burrows-Wheeler Transform (BWT) is a new data transform method, firstly introduced by Burrows and Wheeler in 1994 and used in a lossless data compression algorithm. In the original version of data compression algorithm based on BWT, Burrows and Wheeler used the Move-To-Front (MTF) transform after the BWT and entropy coding (Huffman coding) for encoding the transform result in the last stage. Ferragina and Manzini combined the compression algorithm based on BWT and the suffix array data structure, and proposed a new opportunistic data structure. They shortly called it FM-index in that it is a Full-text index and occupies Minute space. This paper mainly describes the methods about compression and index based on BWT, and relationship between them. At last, the paper compares some tools.

Keywords

data compression; data structures; indexing; transforms; BWT; Burrows-Wheeler transform; FM-index; Huffman coding; data transform method; entropy coding; full-text index; indexing; lossless data compression algorithm; minute space; move-to-front transform; opportunistic data structure; suffix array data structure; Arrays; Compression algorithms; Indexes; Simple object access protocol; Sorting; Transforms; BWT; FM-index; compression algorithm; full-text indexes;

fLanguage

English

Publisher

ieee

Conference_Titel

Web Information System and Application Conference (WISA), 2013 10th

Conference_Location

Yangzhou

Print_ISBN

978-1-4799-3218-4

Type

conf

DOI

10.1109/WISA.2013.20

Filename

6778611