Преобразование Барроуза — Уилера
Материал из Википедии — свободной энциклопедии
Преобразование Барроуза-Уилера (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.
