A simpler analysis of Burrows–Wheeler-based compression.

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 mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D.J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain 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 achieve 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
שפה מקוריתאנגלית
עמודים (מ-עד)220 - 235
מספר עמודים16
כתב עתTheoretical Computer Science
כרך387
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2007

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A simpler analysis of Burrows–Wheeler-based compression.'. יחד הם יוצרים טביעת אצבע ייחודית.

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