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

Katedra Algorytmiki i Oprogramowania (RAU/RAU5)

Wyniki badań: Wkład do czasopisma › Artykuł › recenzja

6 Cytowania z bazy Scopus

Abstrakt

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.

Język oryginału	angielski
Strony (od–do)	313-320
Liczba stron	8
Czasopismo	Information Processing Letters
Tom	95
Numer wydania	1
Identyfikatory DOI	https://doi.org/10.1016/j.ipl.2005.03.008
Status publikacji	Opublikowano - 16 lip 2005

Obszary tematyczne ASJC Scopus

Informatyka teoretyczna
Przetwarzanie sygnałów
Systemy informacyjne
Zastosowania informatyki

Uzyskaj dostęp do dokumentu

10.1016/j.ipl.2005.03.008

Inne pliki i linki

Link do publikacji w Scopus

Cytowanie

@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

Abstrakt

Obszary tematyczne ASJC Scopus

Uzyskaj dostęp do dokumentu

Inne pliki i linki

Fingerprint

Cytowanie