Сайт о сжатии >> Раздел "Cтатьи и исходники"

WIN | KOI | LAT

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

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

Английские материалы
Авторы	Название	Описание	Рейтинг
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

наверх

Вернуться к корню раздела

Off-line книги! Конкурс ваших статей! Добавить свой материал

Последнее обновление: 17-September-2007