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

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

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

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

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

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

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

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

Трансформация
Вход Все
Прокрутки
Сортировка
Строк
Выход
.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

См. Демонстрация преобразования Барроуза-Уилера (англ.) на Wikisource для более подробного примера.

Следующий псевдокод даёт простой, но неэффективный способ для вычисления 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
Output
.BANANA.

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

Также нет необходимости в том, чтобы иметь символ 'EOL'. Вместо этого может использоваться указатель, в котором находится '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 = "Polska 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 рассматривает точки как символы.

Литература

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

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home