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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2006
الحدث17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006 - Barcelona, أسبانيا
المدة: ٥ يوليو ٢٠٠٦٧ يوليو ٢٠٠٦

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4009 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006


أدرس بدقة موضوعات البحث “A Simpler Analysis of Burrows-Wheeler Based Compression.'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا