Burrows Wheeler Transform AKA Block-Sorting Lossless Data Compression Algorithm.
Review and Frequently Asked Questions.

Преобразование Бэрроуза-Уилера или Алгоритм сжатия информации без потерь,
основанный на сортировке блока данных. Обзор и ЧАсто задаваемые ВОпросы.

Юкин Вадим Анатольевич
(yoockinv@mtu-net.ru, 2:5020/1042.50)
24.01.2001

Содержание.

BWT - что, собственно, это такое?

Это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных.

Вкратце, процедура преобразования происходит так:

Теперь рассмотрим эту процедуру подробнее. Для примера возьмем ставшую привычной по многим статьям, посвященным описываемому алгоритму, строку "абракадабра". Как и обещалось, выполним циклические сдвиги для получения упомянутых перестановок.

Затем отсортируем полученные строки, предварительно пометив исходную.

Таким образом, в результате преобразования, взяв последний столбец, мы получили строку "рдакраааабб" и номер исходной строки в отсортированной матрице - 2 (считая с 0). Можно заметить, поскольку использовался сдвиг циклический, символы последнего столбца предшествуют продолжениям, по которым матрица сортировалась. Эти продолжения далее будут называться контекстами.

За счет мы можем добиться хорошего сжатия?

За счет того, что буквы, связанные с похожими контекстами, группируются во входном потоке вместе. Например, в английском языке часто встречается последовательность 'the'. В результате сортировки перестановок достаточного большого блока текста мы можем получить находящиеся рядом строки матрицы:

Затем, после BWT, обычно напускается процедура MoveToFront, заключающаяся в том, что при обработке очередного символа на выход идет номер этого символа в списке, и данный символ, сдвигая остальные элементы, перемещается в начало списка.

Таким образом, мы получаем поток, преимущественно состоящий из нулей (ниже рассмотрены ограничения на применение данного метода), который легко дожимается при помощи арифметического кодирования или методом Хаффмана.

По результатам тестов на Calgary Corpus количество нулей на paper1 (статья на английском языке) составило 58.4%, на progp (программа) - 74%, geo (двоичный файл) - 35.8%.

Можно заметить, что при указанной сортировке мы используем последующие контексты для определения предшествующих им символов. Если сортировать в другом, более привычном для сжатия порядке - не слева направо, а справа налево, ухудшается сжатие текстовых файлов, но улучшается сжатие бинарников и слегка возрастает скорость расжатия в силу более удобного обратного преобразования.

Возможно ли обратное преобразование?

Итак, у нас есть строка "рдакраааабб". Из нее нам надо получить ту же самую матрицу сортированных строк, которую мы использовали когда делали исходное преобразование.

Если нам отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы, поскольку, напомню, строки матрицы были отсортированы в лексикографическом порядке.

Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке (напомню, использовался циклический сдвиг). Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И т.д., пока мы не получим всю матрицу перестановок.

Зная номер исходной строки, мы воспроизводим входные данные.

Конечно, на самом деле нет необходимости воспроизводить посимвольно все строки матрицы по одному символу. Можно заметить, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции. Из строки 0 получается строка 9, из 1 - 7 и т.п.:

    0   а.........р   9
    1   а.........д   7
==> 2   а.........а   0
    3   а.........к   8
    4   а.........р  10
    5   б.........а   1
    6   б.........а   2
    7   д.........а   3
    8   к.........а   4
    9   р.........б   5
   10   р.........б   6

Теперь определяем порядок получения символов первого столбца из
символов последнего:

    2   а.........а   0
    5   б.........а   1
    6   б.........а   2
    7   д.........а   3
    8   к.........а   4
    9   р.........б   5
   10  р.........б   6
    1   а.........д   7
    3   а.........к   8
    0   а.........р   9
    4   а.........р  10

Полученные значения { 2, 5, 6, 7, 8, 9, 10, 1, 3, 0, 4 } и есть вектор обратного преобразования. Для получения исходной строки надо всего-навсего выписать символы из строки преобразованной ("рдакраааабб") в порядке, соответствующему данному вектору, начиная с номера, переданного нам вместе со строкой.

а б р а к а д а б р а Проделаем тоже самое при помощи простейшей программы:

Schindler Transform.

Отличается от BWT тем, что сортировка строк матрицы производится не по всем символам, а по первым N из них и по позиции данного контекста в исходном потоке. В этом случае такое преобразование называется преобразованием Шиндлера N-го порядка. Можно сказать, что BWT - это ST порядка, равного величине блока.

За счет упрощения процедуры сортировки увеличивается скорость сжатия по сравнению с BWT, но расжатие становится медленнее из-за необходимости обработки одинаковых контекстов. Об этом будет написано подробнее в одной из частей BWT FAQ.

Чем компрессоры, использующие этот метод, лучше/хуже остальных?

Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman (PkZip, Arj, Rar, Cabarc), а на больших словарях (от 1Mb) - заметно быстрее. У сжимателя на ST, Szip, скорость сжатия для малых порядков еще выше.

Скорость расжатия у сжимателей на BWT в 3-4 раза быстрее сжатия. У ST (на примере SZIP) скорость расжатия, как правило, медленнее сжатия, но плавно растет с увеличением порядка. В целом, классические LZ77+Huffman расжимают, конечно, быстрее.

Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее эффективно использование BWT для текстов и любых потоков со стабильными контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к PPM-сжимателям при значительно большей скорости.

На неоднородных данных известные BWT-сжиматели заметно уступают по сжатию лучшим современным сжимателям на LZhuf и чуть не дотягивают до результатов, показываемых PPM'ми. Впрочем, есть способы сильно увеличить сжатие неоднородных файлов. Такие уловки пока не используются в связке с BWT, возможно, из-за сравнительно молодого возраста последнего. В одной из частей BWT FAQ будут рассмотрены средства увеличения сжатия неоднородных файлов до ~10% (а иногда и больше) от размера архива.

В силу участившихся дискуссий по сравнению конкурирующих методов BWT и PPM в свете появления крайне быстрого на текстах PPMD Дмитрия Шкарина, считаю необходимым рассмотреть противостояние лучших представителей упомянутых методов отдельно. Замечу, что нижеизложенное является моим мнением, хотя и претендует на некоторую объективность :) Оговорюсь также, что рассматриваю только те компрессоры, которые заявлены и как сильные, и как быстрые. И, соответственно, выпускаю из рассмотрения задумчивые PPM-компрессоры, могущие себе позволить тратить большое время на выжимание из данных последних крох избыточности.

1) PPM в лице PPMD достигает лучших силы и скорости сжатия текстов, но медленнее при расжатии.

2) Данные методы по-разному реагируют на файлы с большим количеством коротких контекстов. PPM заметно замедляется, а BWT ухудшает свое сжатие.

3) PPM лучше сжимает неоднородные файлы благодаря своей лучшей адаптивности. Но, справедливости ради замечу, BWT еще не исследованы в этой области.

Конечно, следует оговориться, что BWT по сути является не методом сжатия, а алгоритмом преобразования блока данных. И, при желании, может быть использовано для поиска контекстов, например, для последующего PPM-сжатия.

Методы сортировки, используемые в BWT-компрессорах.

Начиная с BZip2, а точнее, с какого-то из Уилеровских bred'ов, идет линейка компрессоров, использующих предварительную radix-сортировку по паре байт. Полученные пакеты сортируются по очереди, начиная с наименьшего из них. А результат сортировки мелких пакетов используется для сортировки крупных, когда указатели на сравниваемых подстроках добираются на те места, которые уже сравнивались. Компрессоры, _грамотно_ реализующие такой подход очень устойчивы в вырожденным данным. К примеру, для YBS в худшем случае все равно должно бы получаться n*logn, но мне такие случаи не попадались. Даже специально :) А на большинстве файлов зависимость получается практически линейной. Для сортировки отдельных пакетов зачастую используется Multikey QuickSort, опубликованный Bentley & Sedgewick. Во многих работах используются аббревиатуры BeSe или BS для обозначения этого метода.

Этот метод не всегда оказывается самым быстрым из-за заметных накладных расходов на повышенную устойчивость. К примеру, на большинстве текстов более быстры Imp и, особенно, DC. Но последние хорошо задумываются на длинных контекстах.

В научных кругах сейчас идет борьба за достижение линейного роста времени сжатия от размера блока и уже существует ряд публикаций по этому поводу авторства Садакане, Куртца, Балкенхола, и Ларссона. Но лично я скептически отношусь к таким ухищрениям из-за слишком больших расходов на построения деревьев или сложных ковыряний с суффиксами, поскольку на большинстве файлов эти методы проигрывают в скорости.

Другое направление - уменьшение расходов памяти. В качестве варианта такой сортировки, на сегодня, правда, нигде не реализованной, может служить кластерная сортировка. Она заключается в раздельной обработке строк, поделенных на кластеры (что экономит расходы на хранение указателей), с последующим слиянием отсортированных кластеров. При надлежащем исполнении можно обойтись дополнительными расходами памяти, равными размеру входного блока.

Для справки приведу экспериментальные данные, полученные на iP233MMX/64Mb. Были выбраны наиболее оптимизированные из мне попавшихся представителей BWT-компрессоров для выявления слабых сторон различных методов.

Это - DC 0.99.015b (MergeSort), YBS 0.03e, BA 1.01br5, ARC (Bentley-Sedgewick), QSuf (только сортировщик Larsson-Sadakane, без компрессора), SBC 0.360 (я еще не классифицировал :).

Сортировались (в скобках - размер файла): book1 (768771), file2 (1000000, составленный из больших одинаковых частей book1), wat_c (tar'енные исходники watcom c 10.0, 1890501), kennedy.xls (1029744).

Далеко идущих выводов делать не буду, но видно, что выбрать метод сортировки, лучший на всех без исключения данных, практически невозможно.

Некоторые вопросы, которые действительно FAQ.

В этой главе рассмотрены вопросы, касаемые BWT, которые часто попадались в ходе обсуждения этого метода в конференциях fido7.ru.compress и comp.compression. Некоторые из них затрагивались и в других главах настоящей статьи. Здесь же им будет уделено более пристальное внимание. Искушенному читателю, возможно, будет неинтересна эта глава, хотя, может быть и он найдет в ней если не совсем новую информацию, то хотя бы новый аспект рассмотрения.

1) Что такое MTF?

Как было написано выше, это метод очередного преобразования входного потока. Правда, в отличие от BWT, не блочный, а потоковый. По мере поступления очередного символа на выход подается номер этого символа в списке. После чего этот символ перемещается в начало списка, смещая остальные элементы в хвост.

Рассмотрим строку "рдакраааабб", полученную в результате преобразования в примере, приведенном в первой главе. Предположим, что у нас есть алфавит из пяти символов: "абдкр", а список изначально инициализирован кодами этих символов, т.е. { 'а', 'б', 'д', 'к', 'р' }.

Приступим к преобразованию. Символ 'р' является пятым элементом списка, поэтому первым выходным кодом становится код 4. После перемещения символа 'р' в начало списка, тот принимает вид {'р', 'а', 'б', 'д', 'к'}. И т.п.

Символ	Список	Выход
р	абдкр	4
д	рабдк	3
а	драбк	2
к	адрбк	4
р	кадрб	3
а	ркадб	2
а	аркдб	0
а	аркдб	0
а	аркдб	0
б	аркдб	4
б	баркд	0

2) Зачем используется MTF?

Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегаю разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе BWT-преобразования, разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".

Попробуем сжать эту последовательность при помощи, например, метода Хаффмана. Вероятности всех четырех символов в данном примере равны 1/4. Легко посчитать, что в результате кодирования мы получим последовательность длиной 20*2 = 40 бит.

Теперь проделаем тоже самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный список выглядит как 'a', 'b', 'c', 'd').

10000200003000030000 - строка после MTF

Символ	Частота	Вероятность	Код Хаффмана
0	16	4/5	0
1	2	1/10	10
2	1	1/20	110
3	1	1/20	111

В результате сжатия получаем последовательность длиной 16*1 + 2*2 + 3*2 = 26 бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.

3) Как выбрать направление сортировки?

Можно сортировать строки слева направо и на выход преобразования посылать последний столбец матрицы отсортированных строк. А можно - справа налево и использовать первый столбец. Как делать лучше с точки зрения эффективности сжатия?

Отличие направлений сортировок отличается в том, что первая как-то привычней тем, кому иногда :) приходится сортировать какие-либо данные, а вторая - привычней тем, кто искушен в области сжатия данных. Поскольку первая подразумевает предсказание символа исходя из того, какие символы за ним следуют, а вторая - исходя из того, какие были раньше. В литературе для обозначения этих двух направлений используются словосочетания "following contexts" и "preceeding contexts" соответственно.

Практика показывает, что большинство архиваторов, использующие традиционные BWT+MTF, достигают лучшего сжатия на текстовых данных при использовании "following contexts", а направление, обычное для большинства традиционных методов - лучше на данных, имеющих не лингвистическую природу. Например, на исполнимых файлах.

Для компрессоров, которые не используют MTF, а проблему адаптации кодера к потоку преобразованных данных решают как-то иначе, выбор направления сортировки может быть иным. Например, DC и YBS многие исполнимые файлы, как и текстовые, сжимают лучше при сортировке слева направо.

Проделать самостоятельное сравнение очень просто. Возьмите ваш любимый архиватор и сожмите с его помощью ваш любимый файл. Затем переверните данные этого файла задом наперед и полученное сожмите еще раз.

Некоторые программы самостоятельно пытаются определить тип данных и выбрать направление сортировки. Иногда, впрочем, ошибаясь. Простейший способ подставы - дать архиватору русский текст.

4) Как избежать зацикливания при сравнении строк?

Действительно, если при сортировать строки, полученные в результате циклических перестановок строки "abcabc", можно попасть впросак. Поэтому ради избежания таких неприятностей можно в конце исходного блока дописать уникальный символ, который будет больше или меньше всех символов, которые используются в сортируемом блоке. И при попытке сравнить с ним очередной символ какой-либо другой строки можно будет получить однозначный результат.

Разумеется, придумывать и дописывать такой символ на самом деле необязательно. Достаточно при сравнении строк периодически поглядывать -не перескочили ли мы за конец блока.

5) Какой лучше выбрать размер блока?

BWT - алгоритм, дающий наилучшую результативность при сжатии однородных данных. А однородные данные предполагают наличие сочетаний символов, которые не меняются от начала к концу потока данных. А раз сочетания не меняются, то увеличение размера блока приведут только к увеличению числа одинаковых символов кучкующихся рядом после преобразования. А увеличение кучки вдвое в идеале приводит к увеличению длины, характеризующей размер этой кучки всего на один бит. Таким образом, для однородных данных можно сделать однозначный вывод: чем блок больше - тем сжатие будет сильнее.

Что касается данных неоднородных, то здесь картина иная. Размер блока надо выбирать таким, чтобы его край приходился на то место, где данные резко меняются. Причем, для BWT страшна не сама неоднородность, как таковая, а наличие таких сочетаний символов, которые портят друг другу жизнь. Например, нас не должен пугать тот факт, что в начале файла часто встречаются строки 'abcd', а в конце их место занимают 'efgh'. Гораздо неприятнее, когда вместо строк 'abcd' начинают появляться строки 'abgh'. Я не хочу сказать, что файл, в котором наличествует вторая ситуация сожмется при помощи BWT-компрессора хуже. Но разница в сжатии по сравнению с архиваторами, использующими потоковый метод, на таких данных будет не в нашу пользу.

6) А что, если использовать не последний столбец, а третий, второй, первый и т.п.?

Лучше всего, конечно, первый. В этом случае для кодирования полученного преобразования нам потребуется только записать на выход число различных символов, начиная с самого младшего. Другое дело, что по понятным причинам получить исходные данные в данном случае не представляется возможным :)

Если взять второй столбец, то сжатие, конечно, ухудшится. Зато невозможность декодирования станет менее очевидной :) Для доказательства можно привести пример, предложенный в эхоконференции RU.COMPRESS Булатом Зиганшиным.

Итак, выполним циклические перестановки двух строк - '001001' и '000101'.

001001 000101 Как легко заметить, вторые столбцы этих

010010 010100 возможности точно определить, какая строка

100100 100010 была исходной в этом преобразовании.

Нахождение примеров, опровергающих использование других столбцов предоставим наиболее усидчивым читателям :)

7) Что такое "reordering" и зачем он нужен?

В отличие от многих других методов, сжатие, основанное на преобразовании, которому посвящена данная статья, заметно зависит от лексикографического порядка следования символов. Замечено, что символы, имеющие сходное использование в словообразованиях, лучше располагать поблизости.

Возьмем такие часто встречающихся окончания слов русского языка, как "ый" и "ий". Легко заметить, что им в большинстве случаев предшествуют одни и те же символы, например, буква "н". Если эти окончания в результате сортировки каким-то образом окажутся рядом, мы получим в последнем столбце рядом стоящие одинаковые символы.

Этот эффект особенно заметен на текстовых файлах. Для разных языков нюансы выбора лучшего переупорядочивания символов могут отличаться, но общее правило таково - все символы надо поделить на 3 лексикографически отдельных группы: гласные, согласные и знаки препинания.

8) Hужен ли RLE?

Со времен рождества BWT повелось описывать классический процесс сжатия на его основе в виде схемы RLE+BWT+MTF+RLE+ARI. Hо с тех пор многие компоненты этой схемы были подвергнуты сомнению. И, надо сказать, достаточно уверенно держится за свое место только одна из них - собственно само преобразование, в честь которого названа статья. Впрочем, пожалуй, и позиции арифметика достаточно прочны. Максимум, в чем удалось их поколебать, - это в появлении кодирования методом Хаффмана как альтернативы.

RLE (Run Length Encoding) хитер тем, что уцепился за свое место сразу двумя лапами ;). Hо с появлением эффективных алгоритмов сортировки и моделирования его польза уже начинает вызывать вопросы.

Рассмотрим его первую точку опоры. Для сортировок, которые не умеют пользоваться промежуточными результатами сравнений и каждый раз пытаются сравнить строки матрицы перестановок заново, RLE на этом этапе крайне желателен для того, чтобы избежать приличных потерь в скорости.

А если, спросите Вы, сортировка достаточно изощренная, чтобы пользоваться этим костылем? Практика показывает, что для большинства файлов, полученных естественным путем RLE вреден. Так как сжатие от него ухудшается из-за появления дополнительных кодов длины ради сокращения обычно небольших повторов. Которые и так, хоть и с грехом пополам, вписываются в схему группирования похожих контекстов.

Hо это для большинства файлов. А иногда, а для некоторых источников часто :) возникает потребность сыграть на таких случаях. Это возникает тогда, когда вследствие разбухания группы похожих контекстов, содержащих длинные повторы одинаковых символов, нам становится накладно разбираться в потоке преобразованных данных. Это возникает, как правило, тогда когда в исходном файле повторов одинаковых символов слишком много. Продвинутые архиваторы для этого используют проверку на процентное соотношение числа символов, принадлежащих этим длинным повтором, к общей длине файла. И, если их число достаточно велико, используют RLE.

RLE во второй из упомянутых фаз используется гораздо чаще, чем не используется :) Опасность на него преимущественно надвигается с двух сторон. Во-первых, это distance coding - новый метод, кощунственно покушающийся заодно на и на MTF (это метод описан ниже). Во-вторых, им брезгуют некоторые виртуальные компрессоры, написанные авторами научных статей с целью иллюстрации возможностей новых схем сжатия преобразованного потока. Hо, резюмируя выше сказанное, RLE еще есть чем привлечь разработчика и в своей нише он пока сидит достаточно прочно.

Методы сжатия, используемые в BWT и ST-компрессорах.

Исторически сложилось так, что для этого на протяжение долгого времени использовался джентльменский набор в виде MTF + арифметический кодер (или Хаффман, или rangecoder). Время от времени многие пытались сделать шаг в сторону для того, чтобы избежать MTF, эмпирически правого только на данных после BW-преобразования :)

Первая удачная попытка была сделана Шиндлером (не считая самого ST-преобразования, конечно). В SZip'e используется 3 модели. Первая, быстрая адаптивная модель обрабатывает наиболее часто используемые символы с соответствующими вероятностями, вторая - MTF-модель для менее частых, но все же актуальных символов, и третья модель подбирает оставшиеся символы. Для кодирования длинных последовательностей BWT-выхода используется RLE.

Но MTF используется по-прежнему и с не меньшим усердием. И последние компрессоры, использующие его, достигают сжатия, не уступающего SZip'у на большинстве файлов кроме, разве что, неоднородных. Hо, конечно, это не такой уж простой MTF.

Среди используемых хитростей упомяну к примеру замедленное прохождение в MTF0. Поскольку мы можем предположить, что среди последовательности одинаковых символов может запросто попасться случайный (хотя бы из-за орфографической ошибки в тексте), было бы логично установить своеобразный фильтр, чтобы не сломать эту последовательность и не пытаться кодировать через RLE этот случайный символ. Например, можем пропускать символ в MTF0 только если он уже находится в MTF1.

Такое ухищрение позволяет достичь наибольшего эффекта по сравнению с остальными трюками. Правда, на некоторых файлах он ухудшает сжатие. Например, на тех, в которых есть два почти равноправных и частых символа, привязанных к одинаковым контекстам. Вроде пробела и табуляции в исходниках.

Со временем, ежели оно у меня появится, я постараюсь описать еще многие другие MTF-трюки, благо что почти с десяток, пожалуй насчитать можно. А пока - вот, наиболее значимый, для дальнейших раздумий читателю ;)

Что касается модели MTF для сжатия, почти все, достигающие более-менее приличных результатов, используют структурную модель Фенвика с, возможно, небольшими модификациями. В авторском описании предполагалось поделить все MTF-коды на 7 групп: 1, 2-3, 4-7, 8-15, 16-31, 32-63, 64-127, 128-255 с EOB. При кодировании MTF-кода полагается сначала кодировать номер группы, а затем номер символа в этой группе.

Такое деление позволяет довольно быстро адаптироваться к изменению данных. Ведь выход BWT состоит из фрагментов, в которых присутствует небольшое количество символов с постоянной вероятностью (эти фрагменты соответствуют стабильным контекстам), перемежающихся с кусками, в которых символы попадаются как Бог на душу положит. Поэтому нам надо вовремя определить, находимся ли мы в хорошим фрагменте или попали на межфрагментное бездорожье. Сравнительно небольшое количество групп позволяет это сделать с вполне приемлемой скоростью.

Есть и другие варианты иерархических структур. Hапример, каскадная, которую описали в своих работах Balkenhol и Kurtz. Отличие от структурной заключается в том, что в случае, когда символ не попадает в очередную группу, на выход подается код исключения и поиск символа осуществляется в следующей группе.

Distance coding.

Hедавно появился сравнительно новый метод трактовки данных после преобразования Бэрроуза-Уилера. Мне он впервые повстречался в одной из статей Азнавута и Магливераса под названием IF (inversed frequencies). Hезависимо от них этот метод реализовал в своем архиваторе Эдгар Биндер, назвав его DC (distance coder). И это название мне представляется более логичным, поскольку предполагает кодировать расстояния между одинаковыми символами. Данный метод пока реализован в трех архиваторах - DC, YBS и SBC. Преимущество distance coding'а над MTF достигается в основном за счет отсутствия ложных перемещений по списку. Скорость, правда, немного уступает MTF.

Основное отличие IF состоит в том, что все символы берутся по очереди. Т.е. для очередного символа записывается последовательность расстояний между каждыми появлениями в блоке данных. После этого эти символы вычеркиваются и аналогичная операция проводится для следующего символа на соответствующим образом уменьшенном блоке.

Distance coding, используемый в упомянутых трех архиваторах, предполагает обработку различных символов по мере поступления. Для очередного символа пишется расстояние до следующего такого же, не считая позиций между ними, на которые уже есть ссылки от других символов.

Для примера рассмотрим последовательность "abcaaabbbc". Допустим, мы уже закодировали самые первые символы 'a', 'b' и очередь дошла до 'c'. Расстояние до следующего символа 'c' равно шести. Hо между этими символами есть 2 позиции, на которые уже есть ссылки, порожденными кодированием символов 'a' и 'b'. Т.о. на выход подается значение 6-2=4.

Далее можно увидеть эффект, за счет которого достигается преимущество в скорости по сравнению с IF - отсутствие необходимости кодирования длинных повторов. Когда мы, уже наловчившись на вычислении расстояний, приступим к кодированию символа 'a', находящегося в четвертой позиции рассматриваемого блока данных, обнаруживаем, что на следующий за ним символ вообще нет ссылок со стороны других обработанных символов. Что может означать лишь одно - этот символ тоже является 'a' и кодировать его не надо вовсе.

Для желающих проверить собственное понимание описанного алгоритма вычисления расстояний, привожу итог:

Подсказка: тот факт, что символы кончились, в данном примере реализовано посредством ссылки на <EOB>.

Что такое 1-2 coding?

В свете данной статьи, это способ кодирования количества повторяющихся символов. В принципе, этот способ может применяться для кодирования любого числа.

Как известно, после MTF-преобразования мы получаем последовательность, в которой при удачном раскладе присутствует большое количество нулей, соответствующих нулевому рангу MTF. Ноль возникают тогда, когда после некоторого символа идет такой же (см. ранее в статье).

Если кодировать каждый код MTF0, то во 1-х, это накладно по времени и, во 2-х, может ухудшить сжатие из-за погрешностей арифметического кодера. А для кодирования Хаффмана, недолюбливающего вероятности, отличающиеся от кратных степени двойки, это вообще неудобно, когда символ имеет вероятность, значительно превышающую 1/2 (а после BWT и MTF для ряда файлов такое случается) или даже, например, застревает посередине между 1/4 и 1/2.

Элегантный выход был найден в отведении под MTF0 не одного, а двух символов (назовем их z1 и z2). Таким образом, у нас в MTF-алфавите получилось не 256, а 257 символов (по желанию, можно добавить еще один символ - конец блока). Эти z1 и z2 можно использовать для кодирования числа идущих подряд MTF0:

Какие существуют компрессоры/архиваторы на основе BWT и ST?

БОльшую часть из указанных архиваторов можно также взять на ftp://ftp.elf.stuba.sk/pub/pc/pack.

Количество таких программ непрерывно растет, видимо, вскоре придется оставлять упоминание только про самые интересные :) Ниже приведены краткие особенности некоторых этих и других программ:

Семейство Bred'ов написаны одним из родоначальником BWT, когда узок был круг людей, занимающихся этим методом. Многие идеи, использованные в этих компрессорах, описаны в работах Фенвика. В X1 включена реализация BWT, основанная на этих компрессорах.

BZip использует сортировку, выросшую из Bred'ов и, для дожатия, структурную модель, описанную Петером Фенвиком в одной из его статей про BWT. Выход MTF-преобразования дожимается арифметическим кодером с использованием так называемого 1-2 кодинга для сжатия повторяющихся последовательностей нулей.

BZip2, в отличие от BZIP, выход MTF-преобразования дожимает Хаффманом, также с 1-2 кодингом. Сортировка изменена незначительно - только повышена устойчивость к избыточным данным.

Bwc использует сортировку, похожую на ту, что применяется в BZip2. Для дожатия использует структурную модель, 1-2 coding, rangecoder (т.е. все то, что используется в BZip).

Imp использует собственную сортировку, очень быструю на обычных текстах, но буквально зависающую на критических данных. Дожиматель полностью позаимствован из BZip2.

Интересная реализация применена в DjVu library. Сортировку там не смотрел (вроде не особо быстрая). Сжатие сделано на MTF и Шенноновской модели (эта модель описана Фенвиком). Жмет немного лучше BZip'a, но долго.

В SZip, помимо упоминавшегося ST, реализована и возможность использования BWT-преобразования. Реализована, прямо скажем, только для примера, без затей. А вот дожиматель у SZip'a прекрасный. Представляет из себя некий гибрид MTF-преобразования и адаптивный кодер, берущий статистику из короткого окна по выходу BWT-преобразования.

BKS98 и BKS99 принадлежат сразу трем авторам (Balkenhol, Kurtz, Shtarkov) и пока есть только у них ;) Использует суффиксную сортировку и многоконтекстовую модель MTF по трем последним кодам.

Новые версии ZZip'a выпускаются часто и свойства этого компрессора постепенно улучшаются. В нем применяется все те же испытанные временем BZIP'ские структурная модель и сортировка.

BA использует сортировку, похожую на BZIP'скую тем, что все строки также делятся на пакеты, которые сортируются отдельно при помощи Multikey QuickSort. Hо повышение устойчивости реализовано в BA своим способом. В качестве дожимателя используется MTF с арифметическим кодером. Hовшество, реализованное в BA - это выбор структурной модели MTF в отдельном проходе. За счет динамического определения размера блока заметно улучшено сжатие неоднородных файлов. Для усиления сжатия английских текстов используется reordering.

DC - достаточно новый компрессор, в котором реализован целый ряд новаторских идей. Во-первых, конечно, это модель сжатия, отличная от MTF - distance coding. Во-вторых, новый метод сортировки (информация о нем, может быть, будет опубликована позже), очень быстрый на текстах, хотя и дающий слабину на сильно избыточных данных. И, наконец, большой набор текстовых фильтров, позволяющий добиться особенного успеха на английских текстах (описание этих фильтров пока выходит за рамки этого документа). Хотя, замечу, и без этого по сжатию DC опережает конкурентов. IMHO, сейчас лучший из BWT-компрессоров.

Отличительная особенность SBC - в наличии мощной криптосистемы. Ни в одном из архиваторов, пожалуй, не реализовано столько известных алгоритмов, как в SBC.

Для сжатия в нем используется BWT, ориентированный на большие блоки избыточных данных. И хотя SBC не входит в тройку самых быстрых BWT-компрессоров на типичных данных, он ловко сортирует данные с большим количеством длинных повторяющихся строк, достигая при этом очень хорошей скорости.

Вместо MTF там используется distance coding, но пока не так эффективно, как в YBS и DC - автор еще обещал позже поработать над уровнем сжатия.

ARC (автор Ian Sutton, перу которого также принадлежит PPM-архиватор BOA). Как и многие другие, использует сортировку на основе BeSe и сжатие на основе MTF. Как и в SBC, дополнительно отслеживаются очень длинные повторы данных.

YBS основан на сортировке, аналогичной Bzip2. В перспективе думаю сделать сортировку, более экономно расходующую память и дающую значительное ускорение на коротких контекстах. Сейчас на текстах уступает по скорости IMP'у и DC, но на очень избыточных данных их обгоняет. Скорость сжатия на данный момент одна из самых быстрых среди BWT-компрессоров, использующих арифметическое кодирование.

Собственно жмущая часть использует distance coding. В прошлом применялась MTF со структурной моделью Фенвика (именно эта версия фигурирует в предыдущем CCT 5.6 августа 2000 года). Эта же модель и послужила в качестве прототипа для новой версии. Hа текущий момент достигнута степень сжатия близкая к DC, за исключением того, что YBS пока не использует фильтры.

Как ведут себя эти сжиматели по сравнению с другими можно посмотреть на здесь в разделе сравнительных тестов. Или найти периодически помещаемый в RU.COMPRESS результат сравнений компрессоров, с легкой руки Булата Зиганшина названный VYTEST.

Избранные фрагменты, позволяющие оценить боевые и летные качества приведены ниже.

Сравнительная таблица BWT-компрессоров.

Для всех архиваторов выбран такой режим блока, который позволяет добиться наилучших результатов в сжатии без особого ущерба скорости. И параметры, которые, если специально не оговорено, отключают всякого рода ухищрения, особенно, если те ухудшают эффективность :)

Во всех таблицах данной главы результаты указаны в следующем порядке: после названия компрессора и параметров идут размер полученного файла, время сжатия и время разжатия. Тестирование производилось на компьютере с конфигурацией iPIII-840, 256 SDRAM, Quantum FB 4.3Gb, NT 4.0sp3.

Начнем со сжатия русских текстов. Почему? Потому что BWT особенно эффективно именно для сжатия текстов. А русские выбраны для того, чтобы показать эффективность сжатия в чистом виде, без использования всякого рода ухищрений типа текстовых фильтров, которые для русских текстов еще не созданы авторами описываемых программ.

Файл имеет длину 1,639,139 байтов. Как можно отметить, первенство удерживают компрессоры, использующие distance coding.

ybs 0.3e                   446,151     1.81     0.93
dc 0.99.015b -a            449,474     1.30     1.31
arc' (I.Sutton) b20        459,409     2.08     1.37
compressia' b2048          462,873     2.92     2.66
ba 1.01b5 -24-m            463,214     2.17     1.26
zzip 0.35g -mx -b8         467,383     1.96     1.65
szip 1.12 b21 o0           470,894     3.34     0.78
ICT UC 1.0                 472,556     2.54     1.27
szip 1.12 b21 o8           472,577     2.32     1.12
sbc 0.360 -b3              474,298     2.11     1.08
bwc/PGCC 0.99 m2m          479,162     1.69     0.83
sbc 0.360                  499,079     1.97     1.03
bwc/PGCC 0.99 m900k        503,556     1.56     0.83
szip 1.12 b21 o4           506,348     0.48     0.94
imp 1.10 -2 u1000          506,524     1.07     0.64
bzip2/PGCC 1.0b7 -9        507,828     1.55     0.66

На английском тексте (2,042,760 байтов) некоторые архиваторы используют фильтры, тем самым заметно улучшая сжатие. Они отмечены знаком '*'. Ниже приведены результаты, принадлежащие тем программам, которые показали наилучшие результаты в первом тесте.

dc 0.99.015b               478,812     1.43     1.52 *
ybs 0.3e                   496,703     2.32     1.09
dc 0.99.015b -a            500,430     1.61     1.55
arc' (I.Sutton) b20        508,737     2.62     1.71
ba 1.01b5 -24              512,696     2.87     1.53 *
zzip 0.35g -mx -b8         515,672     2.84     2.08 *
compressia' b2048          517,484     3.67     2.12
ba 1.01b5 -24-x            517,626     2.75     1.42

При сжатии данных, представляющих собой исходные тексты программ, распределение среди лидеров тестов практически не меняется.

Для иллюстрации поведения BWT-архиваторов на неоднородных данных используется исполнимый модуль из дистрибутива компилятора Watcom 10.0 wcc386.exe (536,624 байта). Для того, чтобы можно было судить об эффективности различных методов и режимов, некоторые строки помечены специальными знаками:

*** - размер блока определяется автоматически;

? - нет информации про использование фильтров;

ybs 0.3e -m512k            275,396     0.66     0.51 * **
ybs 0.3e                   276,035     0.66     0.57 *
arc' (I.Sutton) b5mm1      278,392     1.33     0.48 * **
arc' (I.Sutton) mm1        280,052     1.34     0.46 *
dc 0.99.015b               282,011     0.63     0.52 *
zzip 0.35g -mx             291,199     0.74     0.66
arc' (I.Sutton) b5         291,345     0.58     0.48   **
arc' (I.Sutton)            292,979     0.58     0.48
ba 1.01b5 -24-z            293,489     0.82     0.64   ***
dc 0.99.015b -a            293,985     0.56     0.49
imp 1.10 -2 u1000          294,679     0.38     0.18 *
compressia' b512           297,647     0.97     1.16 ?
ICT UC 1.0                 298,348     0.75     0.53
ba 1.01b5                  298,617     0.82     0.66
szip 1.12 b21 o0           298,668     0.76     0.31
szip 1.12 b21 o4           299,249     0.27     0.39
sbc 0.360                  303,049     0.75     0.44
bwc/PGCC 0.99 m600k        304,996     0.58     0.37
bzip2/PGCC 1.0b7 -6        308,624     0.63     0.26

В качестве файла, содержащего смесь текстовых и бинарных данных использовался Fileware.doc из поставки русского MS Office'95 (427,520 байтов). Данный пример показывает, что иногда модель, использующая MTF оказывается лучше прочих.

arc' (I.Sutton) b2         128,685     0.38     0.23 ** *
ybs 0.3e -m256k            130,356     0.37     0.24 **
compressia' b256           131,737     0.61     0.40 **
ba 1.01b5 -24-r            132,651     0.41     0.30
zzip 0.35g -a1             132,711     0.65     0.40
dc 0.99.015b               133,912     0.42     0.35
ybs 0.3e                   133,915     0.37     0.25
bwc/PGCC 0.99 m600k        134,183     0.33     0.19 **
sbc 0.360 -e               134,510     0.54     0.27 ***
bzip2/PGCC 1.0b7 -6        134,932     0.44     0.14 **
szip 1.12 b21 o0           134,945     0.90     0.15
imp 1.10 -2 u1000          135,431     0.30     0.12
sbc 0.360                  135,783     0.52     0.26
ICT UC 1.0                 136,842     0.41     0.29
ba 1.01b5 -24-z            137,566     0.49     0.31 ***
szip 1.12 b21 o4           141,784     0.17     0.18

Литература.

Литературы по BWT становится все больше и больше, поэтому сперва приведу список публикаций для начального ознакомления.

Для желающих более подробно изучить предмет могу посоветовать следующую литературу. С сожалением предупреждаю, что рассылкой заниматься не буду, поскольку бОльшая часть из указанных статей доступна в интернете и на раз находится при помощи поисковых серверов. А почтовый ящик у меня все-таки один... пардон, два ;-)

Прошу также не обращаться с вопросами, где находится та или иная статья - скорее всего, точный адрес я или забыл, или не знал.

Может, я забыл какие-то статьи упомянуть. Тогда рекомендую сходить на http://dogma.net/DataCompression/BWT.shtml. Там много всяких ссылок по данной тематике.

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

Для начала рассмотрим такое преобразование текста:

пусть у нас есть строка S длиной N. Запишем ее, непосредственно под ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже - на 2 символа, и т.д. Всего N раз. Hапример, для S = карамба, N = 7.

И запишем последнюю колонку букв L=БРКМААА и номер строки массива, в которой оказалась оригинальная строка S - в данном случае это 5.

А теперь фокус! Этого достаточно, чтобы восстановить исходную строку! Как это делается: запишем данную нам последовательность букв L в колонку и припишем к ней ее же, но с отсортированными буквами L F

Как нетрудно видеть, это в точности первая колонка матрицы Y. Hо как же продолжить заполнение - что делать с буквами Б, К, Р и М очевидно, но какая из А какой соответствует? Оказывается, все очень просто - первой из А в L соответствует первая А в F и т.д., потому что строки в матрице Y были отсортированы начиная с первой буквы, а после приписывания слева L стали отсортированы начиная со второй, но строчки с одинаковыми первыми буквами с тем же успехом отсортированы начиная с первой буквы, т.е. находятся в том же порядке, что и строчки в матрице Y. Таким образом, получаем, что строка 1 получилась из 5, 2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного нам числа 5, имеем: 5372641, и читаем буквы в соответствующих позициях колонки F: КАРАМБА, ко всеобщему удивлению.

Но спрашивается, где тут компрессия? А вот где: предположим, что размер нашей строки S весьма велик - десятки килобайт; тогда, если содержимое строки, скажем, русский текст, то в ней наверняка много раз встречается буквосочетание " что". Тогда в матрице Y будет много строчек, начинающихся на "то" и кончающихся на "ч" подряд, например:

.....
то он говорил.... ....ч
то он сказал... ....ч
то он такой?.. ....К
то она увидела ....ч
то они приехали... ....ч

т.е. в строке L будет участок с большим количеством ч подряд, лишь изредка перемежающихся другими буквами, и чем длиннее текст, тем больше будет в каждом конкретном участке строки L доля "доминирующей" на этом участке буквы, что позволяет обеспечить хорошее сжатие с помощью простого адаптивного алгоритма.

MTF делается так - все 256 возможных символов находятся в списке, и при кодировании каждого символа передается его номер в списке, а сам символ перемещается в голову списка. При такой схеме все последовательности из одинаковых символов превращаются в последовательности нулей, а все последовательности, содержащие только 2 разных символа - в последовательности нулей и единиц, и т.п.

PS. Простая демонстрационная программа из RLE, BWT, MTF и адаптивного арифметического кодера по степени сжатия покрывает PkZip как бык овцу, а результат 856233 байта на Калгари корпусе (3141622 байт) достигается оптимизированной программой, описанной в оригинальной статье за время, сравнимое с затрачиваемым GZIP-ом (всего на 20% медленнее). Расход памяти при этом, разумеется, побольше, чем у GZIP-а - мегабайта 4.

Burrows Wheeler Transform FAQ