Subject: BWT-FAQ[1/8]
         Date: Thu, 3 May 2001 13:42:47 +0000 (UTC)
         From: "Vadim Yoockin" <vy@thermosyn.com>
   Newsgroups: fido7.ru.compress




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

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

Автор статьи - Юкин Вадим (Vadim Yoockin).
(yoockinv@mtu-net.ru, vy@thermosyn.com, 2:5020/1042.50).
Редакция от 24.01.2001

Добавлено/расширено/изменено:
 - Сравнение компрессоров
 - Методы сортировки
 - Модели кодирования
 - Distance coding
 - Описание существующих BWT-компрессоров
 - Что такое MTF?
 - Как выбрать направление сортировки?
 - Как избежать зацикливания при сравнении строк?
 - Какой лучше выбрать размер блока?
 - А что, если использовать не последний столбец?
 - Что такое "reordering" и зачем он нужен?
 - Расширен список литературы для самого искушенного читателя
 - Изменен пример преобразования
В перспективе:
 - более подробное описание преобразования Шиндлера
 - <здесь могло бы быть ваше предложение :)>

Содержание.

1. BWT - что, собственно, это такое?
2. За счет мы можем добиться хорошего сжатия?
3. Возможно ли обратное преобразование?
4. Schindler Transform.
5. Чем компрессоры, использующие этот метод, лучше/хуже остальных?
6. Методы сортировки, используемые в BWT-компрессорах.
7. Hекоторые вопросы, которые действительно FAQ.
   1) Что такое MTF?
   2) Зачем используется MTF?
   3) Как выбрать направление сортировки?
   4) Как избежать зацикливания при сравнении строк?
   5) Какой лучше выбрать размер блока?
   6) А что, если использовать не последний столбец, а третий, второй,
      первый и т.п.?
   7) Что такое "reordering" и зачем он нужен?
   8) Hужен ли RLE?
8. Методы сжатия и модели, используемые в BWT и ST-компрессорах.
9. Distance coding.
10. Что такое 1-2 coding?
11. Какие существуют компрессоры/архиваторы на основе BWT и ST?
12. Сравнительная таблица BWT-компрессоров.
13. Литература.

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

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

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

1) выделяется блок из входного потока,
2) формируется матрица всех перестановок, полученных в результате
   циклического сдвига блока,
3) все перестановки сортируются в соответствии с лексикографическим
   порядком символов каждой перестановки,
4) на выход подается последний столбец матрицы и номер строки,
   соответствующей оригинальному блоку.

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

      абракадабра
      бракадабраа
      ракадабрааб
      акадабраабр
      кадабраабра
      адабраабрак
      дабраабрака
      абраабракад
      браабракада
      раабракадаб
      аабракадабр

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

      аабракадабр
      абраабракад
 ==>  абракадабра - исходная строка
      адабраабрак
      акадабраабр
      браабракада
      бракадабраа
      дабраабрака
      кадабраабра
      раабракадаб
      ракадабрааб

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

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

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

      han ...t
      he ....t
      he ....t
      hen ...t
      hen ...w
      here...t

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

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

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

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


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

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

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

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

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

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

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

Конечно, на самом деле нет необходимости воспроизводить посимвольно
все строки матрицы по одному символу. Можно заметить, что при каждом
проявлении доселе неизвестного столбца выполнялись одни и те же
действия. А именно, из строки, начинающейся с некоторого символа
последнего столбца получалась строка, в которой этот символ
находится на первой позиции. Из строки 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 }
и есть вектор обратного преобразования. Для получения исходной
строки надо всего-навсего выписать символы из строки преобразованной
("рдакраааабб") в порядке, соответствующему данному вектору, начиная
с номера, переданного нам вместе со строкой.

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

Проделаем тоже самое при помощи простейшей программы.
Пусть, N - количество символов в блоке из входного потока
       n - количество символов в алфавите
       x - номер исходной строки в матрице перестановок
       in[N]    - входной поток
       count[n] - частоты каждого символа алфавита во входном потоке
       T[N]     - вектор обратного преобразования.

Hа первом шаге считаем частоты символов.

  for( i=0; i<n; i++) count[i]=0;
  for( i=0; i<N; i++) count[in[i]]++;

Затем упорядочиваем символы, чтобы получить первый столбец исходной
матрицы.

  sum = 0;
  for( i=0; i<n; i++) {
    sum += count[i];
    count[i] = sum - count[i];
  }

Теперь count[i] указывает на первую позицию символа i в первом столбце.
Следующий шаг - создание вектора обратного преобразования.

  for( i=0; i<N; i++) T[count[in[i]]++]]=i;

И, наконец, восстановим исходный текст.

  for( i=0,j=x; i<N; i++) {
    putc( in[j], output );
    j = T[i];
  }


4. Schindler Transform.

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

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

Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman
  (PKZIP, ARJ, RAR, CABARC), а на больших словарях (от 1Mb) -
  заметно быстрее. У сжимателя на ST, SZIP, скорость сжатия для
  малых порядков еще выше.

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

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

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

Расходы памяти при сжатии довольно близки у всех рассматриваемых
  методов и могут колебаться в больших пределах. Если не
  рассматривать специфические экономные реализации - LZHuf с
  маленьким словарем, PPM с малым числом контекстов и BWT с
  кластерной сортировкой, то основные отличия требований к памяти
  наблюдаются при декодировании. Hаиболее скромными в этом отношении
  являются архиваторы, использующие LZ77. PPM'ы памяти требуют
  столько же, сколько же и при сжатии. Промежуточное положение
  занимают BWT-компрессоры.

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

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

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

6. Методы сортировки, используемые в 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).

         book1    file2   wat_c   kennedy
  qsuf   3.30      9.23   10.00      4.23 (only sorting)
  ybs    3.13      4.77    6.76      4.15
  sbc    4.23      4.39   11.32      6.04
  dc     2.36   4:23.59    6.92      2.97
  arc    4.17      4.34    6.43      5.00
  ba     4.45      5.82    7.36      4.73

Теперь комментарии.

1) Напомню, QSuf представляет собой только сортировщик, который даже
   не пишет в выходной файл. Поскольку в данных тестах сжатие и
   запись в архив в среднем выполняется за секунду, эту самую
   секунду можно смело прибавить к показаниям QSuf. В целом QSuf вел
   себя довольно ровно, хотя на типичных файлах оказался на
   последнем-предпоследнем месте. Как я уже писал, суффиксная
   сортировка хороша, но уж больно велики накладные расходы.
2) DC провалился именно там, где ожидалось - на длинных совпадениях.
   Архиваторы, использующие QuickSort, потенциально могут отстать на
   данных с большим количеством лексикографически упорядоченных
   совпадений.
   В принципе, можно успешно бороться и с теми и другими слабостями.
   А на типичных файлах, скорее всего, MergeSort останется лучше на
   коротких контекстах, BeSe - на длинных (что видно на примере
   файла wat_c).
3) Cортировка в SBC ориентирована, по признанию самого автора, на
   длинные повторы в текстах. Так оно и есть. File2 - единственный
   файл, на котором компрессор вышел на первое место. На всех
   остальных тестах SBC немного уступил тому же QSuf'у.
4) Можно было рассмотреть ST в качестве альтернативного
   преобразования, не требующего таких хитростей при сортировке. Но
   здесь уже появляются другие требования при распаковке -бОльшие
   затраты памяти и времени. И, как правило, немного худшее сжатие.
5) Требования к памяти. SBC и DC требуют 6-кратных расходов памяти
   по отношению к размеру блока, YBS и QSuf - восьми. Впрочем, по
   крайней мере в YBS, эти требования вполне реально уменьшить также
   до 6, пусть и с небольшим замедлением работы.

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


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

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

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').

   bbbbbcccccdddddaaaaa - исходная строка
   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", а направление, обычное для
большинства традиционных методов - лучше на данных, имеющих не
лингвистическую природу. Hапример, на исполнимых файлах.

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

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

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

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

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

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

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

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

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

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

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

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

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

   001001    000101    Как легко заметить, вторые столбцы этих
   001001    001010    матриц, как и указатели на исходные
   010010    010001    строки, одинаковы. Что лишает нас
   010010    010100    возможности точно определить, какая строка
   100100    100010    была исходной в этом преобразовании.
   100100    101000

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

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 еще есть
чем привлечь разработчика и в своей нише он пока сидит достаточно
прочно.

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

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

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

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

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

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

Со временем, ежели оно у меня появится, я постараюсь описать еще
многие другие 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. Отличие от
структурной заключается в том, что в случае, когда символ не
попадает в очередную группу, на выход подается код исключения и
поиск символа осуществляется в следующей группе.


9. 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' и кодировать его не надо вовсе.

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

...abcaaabbbc<EOB>
...-24--2----

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

10. Что такое 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:

1 - z1                7 - z1z1z1
2 - z2                8 - z1z1z2
3 - z1z1              9 - z1z2z1
4 - z1z2             10 - z1z2z2
5 - z2z1             11 - z2z1z1
6 - z2z2                 ...

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

  Компрессор    Автор                 Адрес
    и версия
  ------------  --------------------  -------------------------
  imp -2  1.10  Conor McCarthy        <imp@technelysium.com.au>
                                      http://www.technelysium.com.au
  x1 -m7  0.95  Stig Valentini        <x1develop@dk-online.dk>
                                      http://www.saunalahti.fi/~x1
  szip    1.12  Michael Schindler     <michael@compressconsult.com>
                                      http://www.compressconsult.com
  bwc     0.99  Willem Monsuwe        <willem@stack.nl>
                                      ftp://ftp.stack.nl/pub/users/willem
  bzip    0.21  Julian Seward         <jseward@acm.org>
  bzip2   1.01  Julian Seward         <jseward@acm.org>
                                      http://sourceware.cygnus.com/bzip2
  bredX         D.J.Wheeler           ftp://ftp.cl.cam.ac.uk/users/djw3
  ba   1.01br5  Mikael Lundqvist      <mikael@2.sbbs.se>
                                      http://hem.spray.se/mikael.lundqvist
  zzip   0.36b  Damien Debin          <damien.debin@via.ecp.fr>
                                      http://www.zzip.f2s.com
  dc 0.99.015b  Edgar Binder          <EdgarBinder@t-online.de>
                                      ftp://ftp.elf.stuba.sk/pub/pc/pack
  eri   4.8fre  Alexander Ratushnyak  <ratush@srsc-gw.sscc.ru>
                                      http://artest.i.am
  sbc   0.361b  Sami Mдkinen          <sjm@pp.inet.fi>
                                      www.geocities.com/sbcarchiver
  ybs    0.03e  Vadim Yoockin         <yoockinv@mtu-net.ru>
                                      <vy@thermosyn.com>
                                      http://members.xoom.com/vycct

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

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

Семейство 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 по трем последним кодам.

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

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

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

Отличительная особенность 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
пока не использует фильтры.

Как ведут себя эти сжиматели по сравнению с другими можно посмотреть на
http://members.xoom.com/vycct и на русскоязычном сайте
http://arctest.cjb.net. Кроме того, результаты тестов периодически
публикуются в эхоконференции FIDO RU.COMPRESS.

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


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

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

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

Hачнем со сжатия русских текстов. Почему? Потому что 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

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

  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

13. Литература.

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

1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data
   Compression Algorithm", SRC Research Report 124, Digital Systems
   Research Center, Palo Alto, May 1994
   gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z
2. P.M. Fenwick, "Block sorting text compression", Australasian
   Computer Science Conference, ACSC'96, Melbourne, Australia, Feb
   1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps
3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform.
   Dr. Dobbs Journal, Sept. 1996, pp 46-50.
   http://web2.airmail.net/markn/articles/bwt/bwt.htm

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

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

4.  K.Sadakane. A Fast Algorithm for Making Suffix Arrays and for BWT.
5.  K.Sadakane. On Optimality of Variants of Block-Sorting Compression.
6.  K.Sadakane. Comparison among Suffix Array Constructions Algorithms.
7.  K.Sadakane. Text Compression using Recency Rank with Context and
    Relation to Context Sorting, Block Sorting and PPM.
8.  Z.Arnavaut, S.S.Magliveras. Block Sorting and Compression. DCC99.
9.  B.Balkenhol, S.Kurtz, Y.M.Shtarkov. Modifications of the Burrows
    and Wheeler Data Compression Algorithm. In Proceedings of the
    IEEE Data Compression Conference, Snowbird, Utah, IEEE Computer
    Society Press, 1999, 188-197.
10. Z.Arnavaut, S.S.Magliveras. Lexical Permutation Sorting Algorithm.
11. N.J.Larsson. The Context Trees of Block Sorting Compression.
12. N.J.Larsson. Attack of the Mutant Suffix Tree.
13. N.J.Larsson, K.Sadakane. Faster Suffix Sorting.
14. B.Balkenhol, S.Kurtz. Universal Data Compression Based on the
    Burrows and Wheeler-Transformation: Theory and Practice.
15. S.Kurtz. Reducing the Space Requirement of Suffix Trees.
16. S.Kurtz, R.Giegerich, J.Stoye. Efficient Implementation of Lazy
    Suffix Trees. 1999
17. M.Arimura, H.Yamamoto. Asymptotic Optimality of the Block
    Sorting Data Compression Algorithm. 1998
18. S.Kurtz. Space efficient linear time computation of the Burrows
    and Wheeler - Transformation. DCC2000.
19. B.Chapin. Switching Between Two On-line List Update algorithms
    for Higher Compression of Burrows-Wheeker Transformed Data.
    DCC2000.
20. B.Balkenhol, Y.M.Shtarkov. One attempt of a compression
    algorithm using the BWT.
21. S.Deorowicz. Improvements to Burrows-Wheeler Compression
    Algorithm. 2000.
22. S.Deorowicz. An analysis of second step algorithms in the
    Burrows-Wheeler compression algorithm. 2000.
23. F.Schulz. Two New Families of List Update Algorithms. 1998.
24. P.Ferragina, G.Manzini. An experimental study of an
    opportunistic index. 2001.
25. H.Kruse, A.Mukherjee. Improve Text Compression Ratios with
    Burrows-Wheeler Transform. 1999.
26. B.Chapin, S.Tate. Higher Compression from the Burrows-Wheeler
    Transform by Modified strings. 2000.
27. D.Baron, Y.Bresler. Tree Source Identification with the BWT. 2000.
28. H.Baik, D.S.Ha, H-G.Yook, S-C.Shin, M-S.Park. Selective
    Application of Burrows-wheeler Transformation for Enhancement of
    JPEG Entropy Coding. 1999.
29. H-K.Baik, D.S.Ha, H-G.Yook, S-C.Shin, M-S.Park. A New Method to
    Improve the Performance of JPEG Entropy Coding Using
    Burrows-wheeler Transformation. 1999.
30. S.Albers, B.v.Stengel, R.Werchner. A combined BIT and TIMESTAMP
    Algorithm for the List Update Problem. 1995.
31. C.Ambuhl, B.Gartnerm B.v.Stengel. A New Lower Bound for the List
    Update Problem in the Partial Cost Model. 1999.
32. G.Manzini. The Burrows-Wheeler Transform: Theory and Practice.
    1999.