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


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

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

Преобразование Барроуза — Уилера (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 рассматривает точки как символы.

Ссылки

Литература

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

Wikimedia Foundation. 2010.

Смотреть что такое "Преобразование Барроуза — Уилера" в других словарях:

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

  • Преобразование Барроуза — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Преобразование Барроуза Уилера (Burrows Wheeler transform, BWT, также исторически называется блочно сортирующим сжат …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • bzip2 — Расширение .bz2 MIME application/x bzip Сигнатура BZh Разработан Джулиан Сюард Тип формата Сжатие данных Открытый формат? …   Википедия

  • Сжатие без потерь — У этого термина существуют и другие значения, см. Сжатие. Сжатие данных без потерь (англ. Lossless data compression)  метод сжатия данных: видео, аудио, графики, документов представленных в цифровом виде, при использовании которого… …   Википедия

  • Bzip2 — бесплатная свободная утилита командной строки (а также алгоритм) с открытым исходным кодом для сжатия данных. Разработана и впервые опубликована Джулианом Сьюардом (англ. Julian Seward) в июле 1996 (версия 0.15). Стабильность и популярность… …   Википедия

  • Компрессор данных — Сжатие без потерь (англ. Lossless data compression)  метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого… …   Википедия

  • Move-To-Front — Движение к началу (англ. move to front, MTF)  преобразование для кодирования данных (обычно потока байтов), разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно достаточно быстро для… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.