A Simpler Analysis of Burrows-Wheeler Based Compression.

Moshe Lewenstein, Gabriel Valiente, Haim Kaplan, Shir Landau, Elad Verbin

פרסום מחקרי: פרק בספר / בדוח / בכנספרקביקורת עמיתים


In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called bw0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) Encode the integers using Arithmetic code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ> 1, the length of the compressed string is bounded by μ·s Hk(s) + log(ζ(μ)) ·s + gk where Hk is the k-th order empirical entropy, gk is a consta
שפה מקוריתאנגלית
כותר פרסום המארחCombinatorial Pattern Matching
מוציא לאורSpringer Verlag
עמודים282 - 293
מספר עמודים12
מסת"ב (מודפס)9783540354550
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2006
אירוע17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006 - Barcelona, ספרד
משך הזמן: 5 יולי 20067 יולי 2006

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4009 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A Simpler Analysis of Burrows-Wheeler Based Compression.'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי