Интернет магазин китайских планшетных компьютеров |
|||
Компьютеры - Преобразование Барроуза Уилера - Иллюстрация применения для задач сжатия23 января 2011Оглавление: 1. Преобразование Барроуза Уилера 2. Производительность BWT и алгоритмов сжатия на его основе, потребление памяти 3. Иллюстрация применения для задач сжатия 4. Примеры реализации Пусть есть входной текст с повторяющимися строками: ….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» при помощи этих шагов:
Следующий псевдокод даёт простой, но неэффективный способ для вычисления BWT и его инверсии. Предполагается, что специальный символ конца строки не встречается нигде больше в тексте и игнорируется во время сортировки.
function BWT
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 column of the table
function inverseBWT
create an empty table with no rows or columns
repeat length 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 не в том, что оно создаёт более легко кодируемые выходные данные — многие тривиальные операции позволяют это сделать, а в том, что оно обратимо, позволяя восстановить исходный документ из данных последнего столбца. Обратное преобразование может быть легко понято следующим образом. Возьмём последнюю таблицу и сотрём все столбцы, кроме последнего. При помощи только этой информации вы можете легко восстановить первый столбец. В последнем столбце находятся все символы текста, поэтому сортируя их, мы получаем первый столбец. Затем, первая и последняя колонка вместе дают вам все пары символов в строке. Сортируя список пар получаем первую и вторую колонку. Продолжая таким образом, вы можете восстановить полный список. Затем, строка с «символом конца строки» в конце и есть оригинальная строка. Обращая пример данный выше получаем нечто вроде этого:
Некоторое количество оптимизаций могут сделать эти алгоритмы более эффективными без изменения выходных данных. В BWT нет необходимости полностью хранить таблицу в памяти, потому что каждая строка таблицы может быть представлена указателем на некоторую позицию исходной строки. В обратном BWT нет необходимости хранить таблицу или делать множество сортировок. Достаточно отсортировать строку один раз, используя стабильную сортировку, и запомнить — куда переместился каждый символ. Это даёт нам циклическую перестановку, которая достаточна для того, чтобы получить выходные данные. «Символ» в алгоритме может быть байтом, или битом, или любого другого подходящего размера. Также нет необходимости в том, чтобы иметь символ конца строки. Вместо этого может использоваться указатель, в котором находится 'EOL', как если бы он существовал. В данном подходе выходные данные BWT должны включать в себя и трансформированную строку и окончательное значение этого указателя. Это означает, что BWT слегка увеличивает размер данных. Обратное преобразование затем уменьшает их до исходного размера: при данных строке и указателе оно возвращает просто строку. Полное описание алгоритмов может быть найдено в статье Барроуза и Уилера, или в некотором количестве источников доступных в сети. Просмотров: 5851
|
|||