Преобразование Барроуза — Уилера

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «BWT»)

Преобразование Барроуза — Уилера[1] (Burrows-Wheeler transform, BWT, также исторически называется блочно-сортирующим сжатием, хотя сжатием и не является) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. BWT используется в архиваторе bzip2. Алгоритм был изобретён Майклом Барроузом[англ.] и Дэвидом Уилером[англ.].

Термином BWT также называют и полные алгоритмы сжатия, использующие BWT как один из шагов.

Краткое описание и решаемые задачи

Меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов. Таким образом, сочетание BWT и RLE выполняет задачу сжатия исключением повторяющихся подстрок, то есть задачу, аналогичную алгоритмам LZ.

Кроме того, почти точно повторяющиеся (с незначительными отличиями) подстроки входного текста дают на выходе последовательности одинаковых символов, редко перемежающиеся другими символами. Если после этого выполнить шаг по замене каждого символа расстоянием до его предыдущей встречи (т. н. алгоритм move to front, MTF), то полученный набор чисел будет иметь крайне удачное статистическое распределение для применения энтропийного сжатия типа Хаффмана или же арифметического.

На практике алгоритм сжатия вида BWT → MTF/RLE → Хаффман, применённый в архиваторе bzip2, немного превосходит лучшие реализации LZH по качеству сжатия при аналогичной скорости.

Производительность BWT и алгоритмов сжатия на его основе, потребление памяти

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

Например, такова довольно удачная в общем случае комбинация «bucket sort+qsort Седжвика в каждой корзине» на входном тексте в виде длинной последовательности ABABABAB — bucket sort создаст 2 корзины для A и B, заполнив каждую почти полностью одинаковыми строками, после чего qsort на таком наборе затянется почти навсегда.

В таких случаях приходится прерывать исполнение «затянувшегося» алгоритма и переходить на другой алгоритм (radix sort), который хуже в удачных случаях, но не подвержен обвальной деградации.

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

LZH-компрессор (gzip в максимальном режиме) немного хуже по качеству сжатия и примерно одинаков по скорости, но потребляет значительно меньше памяти.

BWT-декомпрессор намного быстрее (линейная скорость) и не потребляет значительных объёмов памяти, что отличает его от алгоритмов PPM.

Иллюстрация применения для задач сжатия

Пусть есть входной текст с повторяющимися (или почти повторяющимися) строками:

….VANYA…..VANYA….TANYA….MANYA…VANYA…

При заполнении матрицы BWT в ней обязательно окажутся строки:

  • ANYA….V несколько раз для каждой встречи последовательности VANYA
  • ANYA….T
  • ANYA….M

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

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

Описание алгоритма

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

Например, строка: 

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

трансформируется в эту строку, которая легче сжимается, потому что содержит много повторяющихся символов: 

 TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

Трансформация производится сортировкой всех циклических перестановок строки, а затем выбором последнего столбца из полученной матрицы. Например, текст «.BANANA.» трансформируется в «BNN.AA.A» при помощи этих шагов (красная точка обозначает символ конца строки):

Трансформация
Вход Все
Перестановки		 Сортировка
Строк		 Выход 
.BANANA.

.BANANA.
..BANANA
A..BANAN
NA..BANA
ANA..BAN
NANA..BA
ANANA..B
BANANA..

ANANA..B
ANA..BAN
A..BANAN
BANANA..
NANA..BA
NA..BANA
.BANANA.
..BANANA

BNN.AA.A

Следующий псевдокод даёт простой, но неэффективный способ для вычисления BWT и его инверсии. Предполагается, что специальный символ конца строки (EOL) не встречается нигде больше в тексте и игнорируется во время сортировки. 

 function BWT (string s)
   create a list of all possible rotations of s
   let each rotation be one row in a large, square table
   sort the rows of the table alphabetically, treating each row as a string
   return the last (rightmost) column of the table

 function inverseBWT (string s)
   create an empty table with no rows or columns
   repeat length(s) times
       insert s as a new column down the left side of the table
       sort the rows of the table alphabetically
   return the row that ends with the 'EOL' character

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

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

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

Обратное преобразование
Вход 
BNN.AA.A
Добавление 1 Сортировка 1 Добавление 2 Сортировка 2 
B
N
N
.
A
A
.
A

A
A
A
B
N
N
.
.

BA
NA
NA
.B
AN
AN
..
A.

AN
AN
A.
BA
NA
NA
.B
..
Добавление 3 Сортировка 3 Добавление 4 Сортировка 4 
BAN
NAN
NA.
.BA
ANA
ANA
..B
A..

ANA
ANA
A..
BAN
NAN
NA.
.BA
..B

BANA
NANA
NA..
.BAN
ANAN
ANA.
..BA
A..B

ANAN
ANA.
A..B
BANA
NANA
NA..
.BAN
..BA
Добавление 5 Сортировка 5 Добавление 6 Сортировка 6 
BANAN
NANA.
NA..B
.BANA
ANANA
ANA..
..BAN
A..BA

ANANA
ANA..
A..BA
BANAN
NANA.
NA..B
.BANA
..BAN

BANANA
NANA..
NA..BA
.BANAN
ANANA.
ANA..B
..BANA
A..BAN

ANANA.
ANA..B
A..BAN
BANANA
NANA..
NA..BA
.BANAN
..BANA
Добавление 7 Сортировка 7 Добавление 8 Сортировка 8 
BANANA.
NANA..B
NA..BAN
.BANANA
ANANA..
ANA..BA
..BANAN
A..BANA

ANANA..
ANA..BA
A..BANA
BANANA.
NANA..B
NA..BAN
.BANANA
..BANAN

BANANA..
NANA..BA
NA..BANA
.BANANA.
ANANA..B
ANA..BAN
..BANANA
A..BANAN

ANANA..B
ANA..BAN
A..BANAN
BANANA..
NANA..BA
NA..BANA
.BANANA.
..BANANA
Результат 
.BANANA.

Некоторое количество оптимизаций может сделать эти алгоритмы более эффективными без изменения выходных данных. В BWT нет необходимости полностью хранить таблицу в памяти, потому что каждая строка таблицы может быть представлена указателем на некоторую позицию исходной строки. В обратном BWT нет необходимости хранить таблицу или делать множество сортировок. Достаточно отсортировать строку один раз, используя стабильную сортировку, и запомнить, куда переместился каждый символ. Это даёт нам циклическую перестановку, которая достаточна для того, чтобы получить выходные данные. «Символ» в алгоритме может быть байтом или битом, или любого другого подходящего размера.

Также нет необходимости в том, чтобы иметь символ конца строки. Вместо этого может использоваться указатель, в котором находится 'EOL', как если бы он существовал. В данном подходе выходные данные BWT должны включать в себя и трансформированную строку и окончательное значение этого указателя. Это означает, что BWT слегка увеличивает размер данных. Обратное преобразование затем уменьшает их до исходного размера: при данных строке и указателе оно возвращает просто строку.

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

Примечание: о сортировке

Если вы сортируете строку, используя сравнение по стандарту POSIX, то получаете слегка отличную строку на выходе: 

TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

вместо 

TEXYDST.E.XIIXIXXSMPPSS.B..S.EEUSFXDIOIIIIT

ISO 8859 имеет сложные правила сравнения, но в данном случае точки игнорируются. Сравнение POSIX рассматривает точки как символы.

Примечания

  1. ↑ В литературе на русском языке закрепился термин преобразование Барроуза — Уилера. Хотя корректная транскрипция фамилии Burrows — Берроуз [ˈbɜroʊz], такой вариант встречается реже. Фамилию Wheeler также иногда ошибочно транскрибируют как Уиллер.

Литература

  • M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Преобразование_Барроуза_—_Уилера&oldid=5902658