Context exhumation after the Burrows-Wheeler transform

Sebastian Deorowicz

doi:10.1016/j.ipl.2005.03.008

Context exhumation after the Burrows-Wheeler transform

Sebastian Deorowicz

Department of Algorithmics and Software (RAU/RAU5)

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

The essence of compression algorithms based on the Burrows-Wheeler transform is their first stage. In this stage, the information about the symbol contexts in the original sequence is lost and cannot be used in the rest of the algorithm. We show how to obtain some knowledge of the symbol contexts after the BWT. Using this information makes the prediction of symbol occurrence in further stages more accurate, which is confirmed by experiments.

Original language	English
Pages (from-to)	313-320
Number of pages	8
Journal	Information Processing Letters
Volume	95
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2005.03.008
Publication status	Published - 16 Jul 2005

Keywords

Algorithms
Burrows-Wheeler transform
Data compression
Prediction by partial matching

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2005.03.008

Cite this

@article{633451f4568e4054a5c1005a69e400aa,

title = "Context exhumation after the Burrows-Wheeler transform",

abstract = "The essence of compression algorithms based on the Burrows-Wheeler transform is their first stage. In this stage, the information about the symbol contexts in the original sequence is lost and cannot be used in the rest of the algorithm. We show how to obtain some knowledge of the symbol contexts after the BWT. Using this information makes the prediction of symbol occurrence in further stages more accurate, which is confirmed by experiments.",

keywords = "Algorithms, Burrows-Wheeler transform, Data compression, Prediction by partial matching",

author = "Sebastian Deorowicz",

year = "2005",

month = jul,

day = "16",

doi = "10.1016/j.ipl.2005.03.008",

language = "English",

volume = "95",

pages = "313--320",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Context exhumation after the Burrows-Wheeler transform

AU - Deorowicz, Sebastian

PY - 2005/7/16

Y1 - 2005/7/16

N2 - The essence of compression algorithms based on the Burrows-Wheeler transform is their first stage. In this stage, the information about the symbol contexts in the original sequence is lost and cannot be used in the rest of the algorithm. We show how to obtain some knowledge of the symbol contexts after the BWT. Using this information makes the prediction of symbol occurrence in further stages more accurate, which is confirmed by experiments.

AB - The essence of compression algorithms based on the Burrows-Wheeler transform is their first stage. In this stage, the information about the symbol contexts in the original sequence is lost and cannot be used in the rest of the algorithm. We show how to obtain some knowledge of the symbol contexts after the BWT. Using this information makes the prediction of symbol occurrence in further stages more accurate, which is confirmed by experiments.

KW - Algorithms

KW - Burrows-Wheeler transform

KW - Data compression

KW - Prediction by partial matching

UR - https://www.scopus.com/pages/publications/18844433909

U2 - 10.1016/j.ipl.2005.03.008

DO - 10.1016/j.ipl.2005.03.008

M3 - Article

AN - SCOPUS:18844433909

SN - 0020-0190

VL - 95

SP - 313

EP - 320

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Context exhumation after the Burrows-Wheeler transform

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this