Download: ресурсы по сжатию

Универсальные алгоритмы сжатия данных:

Преобразование Барроуза-Уилера
(Burrows-Wheeler Transform, BWT)


Английские материалы
  Общее описание
  Сортировка
  Моделирование и кодирование
  Прочее
Исходные тексты компрессоров

Русские материалы
Авторы Название Описание Рейтинг
Кадач А.В. Эффективные алгоритмы неискажающего сжатия текстовой информации Диссертация на соискание ученой степени к.ф-м.н. Андрея Кадача. Рассматриваются методы сортировки, применяемые при преобразовании, и эффективные способы кодирования.
Институт систем информатики им. А.П.Ершова, Новосибирск, 1997.
PDF  840 кбайт
PS    504 кбайт
5
Юкин В.А. Операция BWT, или новые методы сжатия Доходчивое описание BWT и сопутствующих техник
Hard'n'Soft, n 4/2001
PDF  58 кбайт
TXT   13 кбайт (DOS)
TXT   13 кбайт (WIN)
5
Юкин В.А. BWT - Frequently Asked Questions Часто задаваемые вопросы и, соответственно, ответы, касающиеся применения BWT в сжатии данных
TXT   22 кбайт (DOS)
TXT   22 кбайт (WIN)
 
Семиков М.А. Алгоритм ускоренного лексикографического упорядочивания для преобразования BWT Вкратце описан один из способов ускорения сортировки для выполнения преобразования сильно избыточных данных
DOC   5 кбайт
4-
Большаков Михаил Алгоритмы обработки и преобразования информации Очень кратко описаны алгоритмы, применяемые в BWT и касающиеся суффиксных структур. К сожалению, присутствуют неточности. Hапример, утверждается, что для выполнения BWT требуется объем памяти, пропорциональный квадрату размера входного блока
HTM   76 кбайт
3
Хмелев Д.В. Преобразование Барроуза-Уилера, массив суффиксов и сжатие словарей В статье (а) строго обоснована обратимость преобразования Барроуза-Уилера (BWT), (б) разобрана связь BWT с суффиксными массивами, (в) выявлены условия при которых из BWT можно восстановить заодно и и суффиксный массив, (г) приведены базовые алгоритмы обращения BWT. Кроме того, на основе анализа BWT предложено новое преобразование, которое может быть полезно для сжатия словарей или данных словарного типа.
Статья-победитель конкурса на лучшую статью по сжатию
HTM
TEX   15 кбайт
PS    100 кбайт
PDF   286 кбайт
4


Английские материалы
Авторы Название Описание Рейтинг
Burrows M., Wheeler D.J. A Block-sorting Lossless Data Compression Algorithm Оригинальная статья авторов BWT! ...The algorithm works by applying a reversible transformation to a block of input text. The transformation does not itself compress the data, but reorders it to make it easy to compress with simple algorithms such as move-to-front coding...
SRC Research Report 124, Digital Systems Research Center, Palo Alto, California, May 1994
PDF  64 кбайт
PS    60 кбайт
5
Deorowicz S. Universal lossless data compression algorithms Диссертация, 214 pp.Просто одна из лучших работ, посвященных преобразованию Барроуза-Уилера.
Gliwice, 2003
PDF  859 кбайт
5


Общее описание, включая "для чайников"
Campos A. Bwt, a transformation algorithm. Move to front Описание двух довольно употребимых алгоритмов. Март 2000.
arturo@arturocampos.com, http://www.arturocampos.com
BWT (zip)   7.5kb
MTF (zip)   2.8kb
4
Lavavej S. BWTZip Описание BWT, суффиксной сортировки и т.п. Декабрь, 2002
stl@caltech.edu, http://stl.caltech.edu/bwtzip.html
bwtzip.rar   94kb
4+


Сортировка
Малышев Дмитрий Archon 3: Конечная структура Описание одного из самых быстрых алгоритмов сортировки, используемого в архиваторе Archon 3. Описание довольно краткое и скорее расчитано на опытного разработчика, нежели на новичка.
Август 2006
DOC(rus)  11 кбайт
DOC(eng)  14 кбайт
5
Karkkanen J., Sanders P. Simple Linear Work Suffix Array Construction. При сортировке суффиксы делятся на 3 части. Достаточно отсортировать 2 из них. При слиянии групп происходит не более 3 сравнений на пару строк.
ICALP, 2003
PS  78 кбайт
C   3 кбайт
5
Burkhardt S., Karkkanen J. Fast Lightweight Suffix Array Construction and Checking Идея та же, что и в предыдущей работе. Только количество групп может варьироваться. Чем больше групп, тем меньше надо строк надо сортировать. Но при этом увеличивается количество сравнений при слиянии отвортированных строк.
CPM, 2003
PS  86 кбайт
C   26 кбайт
4
Hideo Itoh, Hozumi Tanaka An Efficient Method for in Memory Construction of Suffix Arrays Сортировка, с идеей от bzip2 о том, что половину суффиксов можно не сортировать. Полезное добавление в том, что еще можно не сортировать группу, у которой S(i) >2 S(i>2). В статье приведены исходники
1999
PDF  172 кбайт
5
Bentley J. L., Sedgewick R. Fast Algorithms for Sorting and Searching Strings Описание метода сортировки, используемой во многих современных BWT-компрессорах
Dr.Dobbs Journal, 1998
PDF  50 кбайт
SRC  7 кбайт (исходные тексты)
5
McIlroy P. W., Bostic K., McIlroy W. D. Engineering Radix Sort Применение поразрядной сортировки для BWT-преобразования
1993
PS   30 кбайт
5
Farach M. Optimal Suffix Tree Construction with Large Alphabets Построение дерева суффиксов в случае большого числа символов в алфавите
1997
PS   46 кбайт
4
Andersson A., Nilson S. A New Efficient Radix Sort
1994
PS   43 кбайт
4
Andersson A., Nilson S., Hagerup T., Raman R. Sorting in Linear Time?
1995
PS   100 кбайт
4
Andersson A., Nilson S. Efficient Implementation of Suffix Trees
1996
PS   43 кбайт
4
Sadakane K. Comparison among Suffix Array Constructions Algorithms Изложены базовые идеи сортировки суффиксов.
1997
PS   56 кбайт
4
Sadakane K. A Fast Algorithm for Making Suffix Arrays and for BWT Более развернутая версия предыдущей статьи.
1998
PS   90 кбайт
5
Sadakane K. Unifying Text Search and Compression. Suffix Sorting, Block Sorting and Suffix Arrays Капитальная работа. В ней затронуто не только построение дерева суффиксов, но и возможные аспекты их применения
2000
PS   368 кбайт
5
Kurtz S. Reducing the Space Requirement of Suffix Trees Рассмотрены способы уменьшения расходов памяти при построении дерева суффиксов посредством связного списка и хэш-таблиц.
1999
PS   88 кбайт
5
Kurtz S., Giegerich R., Stoye J. Efficient Implementation of Lazy Suffix Trees
1999
PS   82 кбайт
4
Kurtz S., Balkenhol B. Space efficient linear time computation of the Burrows and Wheeler - Transformation Описан один из наиболее быстрых способов сортировки суффиксов.
Data Compression Conference, 2000
PS   82 кбайт
5
Larsson N. J. Attack of the Mutant Suffix Tree В этом документе сразу три довольно интересные статьи.
- Extended Application of Suffix Trees for Data Compression
- Suffix Trees on Words
- The Context Trees of Block Sorting Compression
В общем, если хотите все узнать про суффиксные деревья, почитайте
1998
PDF  441 кбайт
5
Larsson N. J. Structures of String Matching and Data Compression Довольно основательная работа по сжатию данных и поиску строк. Упор сделан на деревья суффиксов
1999
PS   373 кбайт
4
Larsson N. J., Sadakane K. Faster Suffix Sorting Знатоки суффиксной сортировки объединили в этой работе свои усилия. Описана одна из наиболее быстрых модификаций.
1999
PDF  234 кбайт
5
Futamura N., Aluru S., Kurtz S. Parallel Suffix Sorting Сортировка больших объемов данных, ориентированная на ДHК-последовательности
2001
PS   122 кбайт
?
Abouelhoda M.I., Kurtz S., Ohlebusch E. The Enhanced Suffix Array and its Applications to Genome Analysis. Способ построения массива суффиксов, ориентированного на ДHК-последовательности большоо объема
2002
PDF  106 кбайт
?
Giegerich R.,Kurtz S. From Ukkonen to McCreight and Weiner: a unifying view of linear-time siffix tree construction Экскурс в историю борьбы за построение дерева суффиксов за линейное время
1997
PS   74 кбайт
?
Gilad-Bachrach R.,El-Yaniv R.,Reinstadtler M. On the competitive theory and practice of online list accessing algorithms Вечная проблема MTF vs TIMESTAMP :)
1999
PS   116 кбайт
3+
Yokoo H. A Dynamic Data Structures for Reverse Lexicographically Sorted Prefixes Метод онлайного построения списка префиксов, перекликающийся с идеей, описанной в bwt1 Евгения Шелвина на пару лет раньше
2000
PS   92 кбайт
4+
Monostori K.A., Zaslavsky A., Schmidt H. Suffix Vector: Space- and Time- Efficient Alternative to Suffix Trees Альтернативная дереву суффиксов структура. По уверению авторов, требует меньше памяти (хотя все равно, 8*N) и времени на построение.
In Proc. Twenty-Fifth Australasian Computer Science Conference (ACSC2002)
PDF  190 кбайт
?
Manzini G., Ferragina P. Engineering a Lightweight Suffix Array Construction Algorithm Описан практический метод сортировки массива суффиксов.
2002
PDF  169 кбайт
C    27 кбайт
5


Моделирование и кодирование
Schindler Di M. A Fast Block-Sorting Algorithm for Lossless Compression Описание частичного сортирующего преобразования
1997
PS   33 кбайт
5
Seward J. Space-time tradeoffs in the Inverse Burrows-Wheeler Transform Анализ способов ускорения обратного преобразования
2001
PS   72 кбайт
PDF  189 кбайт
5
Yokoo Hidetoshi Data Compression Using a Sort-Based Context Measure Рассмотрен метод сжатия данных, основанный на степени похожести контекстов
1997
PS   340 кбайт  (часть 1)
PS   323 кбайт  (часть 2)
5
Wheeler D. Upgrading bred with multiple tables Описаны некоторые способы усовершенствования программы сжатия данных на основе BWT
1997
PS   36 кбайт
5
Fenwick P. Experiments with a Block Sorting Text Compression Algorithm Рассмотрены разные способы усиления сжатия данных (MTF, PPM-style, дельта-кодирование).
1995
PS   52 кбайт
5
Fenwick P. Improvements to the Block Sorting Text Compression Algorithm Как улучшить компрессоры на основе BWT? Вопросы и ответы, ускорение сортировки, иерархическая и дельта- модели, LZ77-препроцессинг, MTF и непосредственное кодирование
1995
PS   51 кбайт
5
Fenwick P. Block Sorting Text Compression - Final Report Итоговая статья Петера Фенвика, касающаяся сжатия на основе BWT.
- арифметический кодер,
- коррекция MTF-кодирования,
- кеширование при кодировании символов после BWT
- модель Шеннона и структурная модель
1995
PS   63 кбайт
5
Fenwick P. Block Sorting Text Compression
Proceeding of the 19th Australasian Computer Science Conference, Melbouurne, Australia, 1996
PS   45 кбайт
5
Fenwick P., Titchener T., Lorenz M. Burrows Wheeler - Alternatives to Move to Front Описана схема, в которой наиболее частые символы запоминаются в кэше и кодируются, исходя из частоты в кэше.
Data Compression Conference, 2003
PDF  69 кбайт
4
Arnavaut Z., Magliveras S. S. Lexical Permutation Sorting Algorithm Сделан намек на существование алгоритма LPSA, являющегося общим случаем блочных трансформирующих алгоритмов
1997
PS   56 кбайт
4
Arnavaut Z., Magliveras S. S. Block Sorting and Compression Описан алгоритм Inversion Frequencies, являющийся близким родственником Distance Coding'a
Data Compression Conference, 1999
PS   72 кбайт
5
Balkenhol B., Kurtz S. Universal Data Compression Based on the Burrows and Wheeler-Transformation: Theory and Practice Описаны некоторые полезные способы улучшения BWT-компрессоров. Hапример, модификация MTF, использование модели третьего порядка при сжатии выхода BWT
1998
PS   138 кбайт
5
Balkenhol B., Kurtz S., Shtarkov Y. M. Modifications of the Burrows and Wheeler Data Compression Algorithm Идеи, изложенные в предыдущей статье, здесь получили дальнейшее развитие
Data Compression Conference, 1999
PS   103 кбайт
5
Arimura M., Yamamoto H. Asymptotic Optimality of the Block Sorting Data Compression Algorithm Доказательство возможности асимптотической оптимальности сжатия данных, подвергнутых преобразованию Барроуза-Уилера
IEICE Trans. Fundametals, Vol.e81-A, No.10, October 1998
PDF  393 кбайт
3
Chapin B. Switching Between Two On-line List Update algorithms for Higher Compression of Burrows-Wheeker Transformed Data Предлагается при кодировании выхода BWT использовать переключение между двумя модифицированными методами MTF в зависимости от тпиа данных.
Data Compression Conference, 2000
PS   66 кбайт
5
Chapin B., Tate S. Higher Compression from the Burrows-Wheeler Transform by Modified Sorting Изменение лексикографического порядка сортировки при выполнении BWT
2000
PDF  82 кбайт
5
Balkenhol B., Shtarkov Y. M. One attempt of a compression algorithm using the BWT Описаны некоторые идеи усиления сжатия данных, позволяющие достичь одного из наилучших результатов сжатия файлов Calgary Corpus
1999
PS   190 кбайт
5
Deorowicz S. Improvements to Burrows-Wheeler Compression Algorithm Применение модели второго порядка для сжатия выхода BWT
June 2000
PS   96 кбайт
5
Deorowicz S. An analysis of second step algorithms in the Burrows-Wheeler compression algorithm Вкратце описаны методы сжатия данных, полученных в результате BWT, описан новый метод, WFC (Weighted Frequence Count), один из наиболее эффективных по уровню сжатия
Nov,2000
PS   89 кбайт
5
Deorowicz S. Second Step Algorithms in the Burrows-Wheeler Compression Algorithm Анализ сжатия данных, полученных в результате преобразования. Рассмотрены разные способы замены привычного MTF
2001
PS   158 кбайт
5
Isal R.Yugo Kartono, Moffat Alistair Parsing Strategies for BWT Compression. В дополнение к традиционным этапам BWT-сжатия предлагается проделывать еще одну операцию - создание словаря из часто используемых сочетаний символов
2001
PS   81 кбайт
PDF  199 кбайт
4+
Isal R.Yugo Kartono, Moffat Alistair Word-Based Block-Sorting Text Compression Данные разбиваются на слова и затем сжимаются при помощи BWT, используя специально разработанную модель
2001
PDF  764 кбайт
4+
Isal R.Yugo Kartono, Moffat Alistair, Ngai Alwin C.H. Enhanced Word-based Block-sorting Text Compression Развитие темы, затронутой в предыдущей статье
2002
PDF  87 кбайт
4+
Wirth A.I., Moffat A. Can we do withot ranks in Burrows Wheeler transform compression? Очередная попытка заменить MTF на непосредственное кодирование символов
2001
PS   79 кбайт
PDF  127 кбайт
4+
Effros M., Visweswariah K., Kulkarni S.R., Verdu S. Universal Lossless Source Coding With the Burrows Wheeler Transform Бесценное пособие для тех, кому не хватает солидных формул для написания собственной научной статьи
2002
PDF  602 кбайт
5
Effros M. Universal Lossless Source Coding With the Burrows Wheeler Transform Более ранняя версия предыдущей статьи
1999
PDF  289 кбайт
4
Dvorsky J., Snasel V. Modifcations in Burrows-Wheeler Compression Algorithm Сжатие на основе BWT, ориентированного на слова. Слова определяются очень просто - это непрерывная последовательность букв и цифр, не превышающая определенной длины.
2000
PDF  135 кбайт
4
Dvorsky J., Snasel V. Move to front coding based on splay trees Развитие предыдущей статьи. Предлагается модификация MTF, позволяющая работать с большим словарем
2002
PDF  136 кбайт
?
Yamaguchi T.J., Dong Sam Ha, Ishida M., Ohmi T. A Method for Compressing Test Data Based on Burrows-Wheeler Transformation Сжатие тестовых данных, полученных в процессе ряда однотипных экспериментов. Задача интересная, но из нее можно было выжать больше
2002
PDF  393 кбайт
3+
Ergun F., Sahinalp C., Sharp J., Sinha R.K. Biased Skip Lists for Highly Skewed Access Patterns Описывается метод, который может быть применен вместо MTF для больших алфавитов
2000
PS   47 кбайт
4
Manzini G., Ferragina P. Compression boosting in optimal linear time using the Burrows-Wheeler Transform Дано теоретическое обоснование увеличения глубины используемого контекста без потери в скорости при помощи BWT.
2004
PDF  210 кбайт
?


Прочее
Albers S., von Stengel B., Werchner R. A combined BIT and TIMESTAMP Algorithm for the List Update Problem Класс алгоритмов List Update Algorithms, в который, как частный случай, входит и MTF
1995
PS   65 кбайт
4
Ambuhl C., Gartnerm B., von Stengel B. A New Lower Bound for the List Update Problem in the Partial Cost Model
1999
PS   73 кбайт
4
Schulz F. Two New Families of List Update Algorithms
1998
PS   71 кбайт
4
Manzini G. An Analysis of the Burrows-Wheeler Transform Теоретическое исследование BWT
1997
PS   77 кбайт
4
Manzini G. The Burrows-Wheeler Transform: Theory and Practice Описание BWT и обзор существующих методов сортировки и кодирования
1999
PS   52 кбайт
4
Ferragina P., Manzini G. An experimental study of an opportunistic index Применение BWT для поиска в сжатых данных
2001
PS   82 кбайт
5
Kruse H., Mukherjee A. Improve Text Compression Ratios with Burrows-Wheeler Transform Применение дополнительного кодирования перед сжатием текстов при помощи BWT-компрессоров
Data Compression Conference, 1999
PS   56 кбайт
PDF  113 кбайт
5
Baron D., Bresler Y. Tree Source Identification with the BWT
2000
PS   186 кбайт
4
Baik H-K., Ha D. S., Yook H-G., Shin S-C., Park M-S. A New Method to Improve the Performance of JPEG Entropy Coding Using Burrows-wheeler Transformation Применение BWT в сжатии мультимедийных данных
Oct, 1999
PDF  98 кбайт
3
Baik H-K., Ha D. S., Yook H-G., Shin S-C., Park M-S. Selective Application of Burrows-wheeler Transformation for Enhancement of JPEG Entropy Coding
Dec, 1999
PDF  77 кбайт
3
Schindler M., Sebastian B. Image Compression using Blocksort (Abstract) Использование частичного сортирующего преобразования в сжатии данных. Данная схема применяется в компрессоре ICT.
Oct, 1999
PDF  47 кбайт
3
Powell M. Compressed-Domain Pattern Matching with Burrows-Wheeler Transform Поиск в данных, сжатых при помощи BWT. В том числе и нечеткий поиск.
2001
PDF  462 кбайт
4+
Bell T., Powell M., Mukherjee A., Adjeroh D. Searching BWT Compressed Text with the Boyer-Moore Algorithm and Binary Search Сравнение поиска с использованием BWT и алгоритма Бойера-Мура
2001
PDF  142 кбайт
4
Abouelhoda M.I., Kurtz S., Ohlebusch E. Optimal Exact String Matching Based on Suffix Arrays Поиск с использованием массива суффиксов, должный быть оптимальным на больших объемах данных
2002
PDF  99 кбайт
?
Smith S.D., Kelleher K., Laksmivarahan S. Compression of NEXRAD (WSR-88D) Radar Data using B-W Algorithm Тому, у кого случайно завалялся такой радар, это будет интересно. Или тому, кому надо сжать данные, похожие на те, которые снимаются с радара
2001
PDF  16 кбайт
3
Grossi R., Vitter J.S. Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching Быстрый поиск с использованием суффиксных массива и дерева
2000
PS   85 кбайт
?
Sadakane K., Lam T-W, Sung W-K, Yin S-M A Space and Time Efficiant Algorithm for Constructing Compressed Suffix Arrays Описан онлайновый алгоритм построения сжатого дерева суффиксов, ориентированный на большие ДHК-последовательности
2002
PS   54 кбайт
?
Meng He Indexing Compressed Text Большая работа на 100 страниц про индексирование текстов не без BWT
2003
PDF  266 кбайт
?
Andrew Firth A Comparison of BWT Approaches to Compressed-Domain Pattern Matching Предложены способы ускорения поиска и уменьшения расходов памяти к методам, описанным ранее (например, by Sadakane&Imai, Adjeroh, Manzini&Ferragina)
2002
PDF  441 кбайт
?


Исходные тексты компрессоров
Fabien Letouzey MAr (Melting-Pot ARchiver) Демо-программа, в которой реализованы LZ77, BWT и PPM в одном флаконе. Hоябрь, 1999. Язык: C
xann@melting-pot.org, http://www.lifl.fr/~letouzey/
mar.rar   104kb
3
Julian Seward bzip2 1.02 Исходники известного архиватора. Реализован довольно быстрый BWT и использовано сжатие методом Хаффмана. Апрель, 2000. Язык: C
jseward@acm.org, http://www.muraroa.demon.co.uk
bzip2 1.01    176kb
5
Julian Seward bzip 0.21 Предыдущая версия архиватора, в котором было применялось арифметическое сжатие. Сентябрь, 1996. Язык: C
jseward@acm.org, http://www.muraroa.demon.co.uk
bzip 0.21    60kb
4
Michael Schindler szip 1.12b Первый архиватор, в котором использовано частичное сортирующее преобразование (ST, Sort Transform) с порядком более 2. Оригинальное кодирование выходных данных сортировки. Долгое время был лучшим в общем зачете (Best Overall) в рейтинге compression.ca в категориях Calgary и English Texts. Октябрь, 2000. Язык: C
szip@compressconsult.com, http://www.compressconsult.com/szip
szip 1.12b    34kb
5
Михаил Семиков ECP Hекоторые идеи по ускорению сортировки при BWT, использование LZP для сжатия. Август, 2000. Язык: C
s_mic@mail.ru
ECP    19kb
4
Willem Monsuwe bwc 0.99d Очень хороший компрессор (быстрая сортировка и арифметическое сжатие). Январь, 1999. Язык: C
willem@stack.nl
bwc 0.99d    26kb
5
Victor Kasenda resource 2.61 Full Delphi source code to BWT compression Engine. Arithmetic Coding, Sadakane's Suffix sort, CRC32. Full featured Archiver Demo. Февраль, 2002. Язык: Delphi
vickas@singnet/com/sg,
http://homex.coolconnect.com/member3/
gruvrs/resource/

resource 2.61    84kb
4
N. Jesper Larsson Faster Suffix Sorting Исходники суффиксной сортировки. "Faster Suffix Sorting" by N. Jesper Larsson (jesper@cs.lth.se) and Kunihiko Sadakane (sada@is.s.u-tokyo.ac.jp). Июль, 1999. Язык: C
qsufsort.rar    10kb
5
Lavavej S. BWTZip BWT-компрессор, использующий жадную до памяти суффиксную сортировку и MTF2. Более полезно описание самого BWT. Декабрь, 2002. Язык: C++
stl@caltech.edu, http://stl.caltech.edu/bwtzip.html
bwtzip_src.rar   243kb
3+
Edison Mera BZip2 1.02/pas Переложенные на Паскаль исходники BZip2. Hоябрь, 2002.
Язык: Pascal.
efmera@yahoo.com, http://www.geocities.com/efmera/
bzip2pas.zip   40kb
4-
Клюйков Р.С. Sort Оригинальная программа BWT-преобразования, устойчивого к избыточности данных. Hоябрь, 2004.
Язык: С++.
rsk_comp@mail.ru
kluykov_sort.rar  10kb
Maniscalco M. MSufSort Реализация очень быстрого алгоритма суффиксной сортировки. Сравнения по скорости см. на авторской странице.
Язык: С++.
Авторская страница программы: http://www.michael-maniscalco.com/msufsort.htm
версия 2.0.1 (06 августа 2005)   15kb

наверх