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

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

Преобразование Барроуза — Уилера (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 слегка увеличивает размер данных. Обратное преобразование затем уменьшает их до исходного размера: при данных строке и указателе оно возвращает просто строку.

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

Примеры реализации

На языке Си

#include <unistd.h>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
 
typedef unsigned char byte;
 
byte *rotlexcmp_buf = NULL;
int rottexcmp_bufsize = 0;
 
int rotlexcmp(const void *l, const void *r)
{
    int li = *(const int*)l, ri = *(const int*)r, ac=rottexcmp_bufsize;
    while (rotlexcmp_buf[li] == rotlexcmp_buf[ri])
    {
        if (++li == rottexcmp_bufsize)
            li = 0;
        if (++ri == rottexcmp_bufsize)
            ri = 0;
        if (!--ac)
            return 0;
    }
    if (rotlexcmp_buf[li] > rotlexcmp_buf[ri])
        return 1;
    else
        return -1;
}
 
void bwt_encode(byte *buf_in, byte *buf_out, int size, int *primary_index)
{
    int indices[size];
    int i;
 
    for(i=0; i<size; i++)
        indices[i] = i;
    rotlexcmp_buf = buf_in;
    rottexcmp_bufsize = size;
    qsort (indices, size, sizeof(int), rotlexcmp);
 
    for (i=0; i<size; i++)
        buf_out[i] = buf_in[(indices[i]+size-1)%size];
    for (i=0; i<size; i++)
    {
        if (indices[i] == 1) {
            *primary_index = i;
            return;
        }
    }
    assert (0);
}
 
void bwt_decode(byte *buf_in, byte *buf_out, int size, int primary_index)
{
    byte F[size];
    int buckets[256];
    int i,j,k;
    int indices[size];
 
    for (i=0; i<256; i++)
        buckets[i] = 0;
    for (i=0; i<size; i++)
        buckets[buf_in[i]] ++;
    for (i=0,k=0; i<256; i++)
        for (j=0; j<buckets[i]; j++)
            F[k++] = i;
    assert (k==size);
    for (i=0,j=0; i<256; i++)
    {
        while (i>F[j] && j<size)
            j++;
        buckets[i] = j; // it will get fake values if there is no i in F, but
                        // that won't bring us any problems
    }
    for(i=0; i<size; i++)
        indices[buckets[buf_in[i]]++] = i;
    for(i=0,j=primary_index; i<size; i++)
    {
        buf_out[i] = buf_in[j];
        j=indices[j];
    }
}
 
int main()
{
    byte buf1[] = "Wikipedia";
    int size = strlen(buf1);
    byte buf2[size];
    byte buf3[size];
    int primary_index;
 
    bwt_encode (buf1, buf2, size, &primary_index);
    bwt_decode (buf2, buf3, size, primary_index);
 
    assert (!memcmp (buf1, buf3, size));
    printf ("Result is the same as input, that is: <%.*s>\n", size, buf3);
    return 0;
}

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

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

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

вместо

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

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

Ссылки

• ResearchIndex page for BWT paper at Penn State
• BWT paper hosted at DEC
• Article by Mark Nelson on the BWT
• Article by Mark Nelson «Data Compression with the Burrows-Wheeler Transform»

Литература

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