Преобразование Барроуза-Уилера | это... Что такое Преобразование Барроуза-Уилера? (original) (raw)

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

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

Содержание

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

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

На практике алгоритм сжатия вида 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, изредка перемежающуюся 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;

}

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

Если вы сортируете строку используя сравнение по стандарту

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

вместо TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

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

Ссылки

Литература

Методы сжатия
Теория Информация Собственная · Взаимная · Энтропия · Условная энтропия · Сложность · Избыточность Единицы измерения Бит · Нат · Ниббл · Хартли · Формула Хартли
Без потерь Энтропийное сжатие Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Арифметическое кодирование (Алгоритм Шеннона — Фано · Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи) Словарные методы RLE · · LZ ( · LZSS · LZW · LZWL · · · LZX · LZRW · LZJB · LZT) Прочее RLE · CTW · BWT · PPM · DMC
Аудио Теория Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова Методы LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель Прочее Dynamic range compression · Сжатие речи · Полосное кодирование
Изображения Термины Цветовое пространство · Пиксел · Chroma subsampling · Артефакты сжатия Методы RLE · DPCM · Фрактальный · Wavelet · EZW · SPIHT · LP · ДКП · ПКЛ Прочее Битрейт · Test images · PSNR · Квантование
Видео Термины Характеристики видео · Кадр · Типы кадров · Качество видео Методы Компенсация движения · ДКП · Квантование Прочее Видеокодек · Rate distortion theory (CBR · ABR · VBR)
См. также: Программы для сжатия данных • Стандарты и форматы сжатия

Wikimedia Foundation.2010.