4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Ссылка на код) |
||
(не показано 10 промежуточных версий этого же участника) | |||
Строка 6: | Строка 6: | ||
До публикации преобразования Барроуза-Уилера в области сжатия данных без потерь доминировали два подхода (см. исчерпывающий обзор в работах [1, 15]). Первый подход был предложен в революционных работах Шеннона и Хаффмана и основан на идее использования более коротких кодовых слов для самых часто встречающихся символов. Идея этого подхода была основана на технике Хаффмана и алгоритме арифметического кодирования | До публикации преобразования Барроуза-Уилера в области сжатия данных без потерь доминировали два подхода (см. исчерпывающий обзор в работах [1, 15]). Первый подход был предложен в революционных работах Шеннона и Хаффмана и основан на идее использования более коротких кодовых слов для самых часто встречающихся символов. Идея этого подхода была основана на технике Хаффмана и алгоритме арифметического кодирования, а в более поздний период – и на семействе алгоритмов сжатия PPM (Prediction by Partial Matching, прогнозирование по частичному совпадению). Второй подход был предложен в работах Лемпеля и Зива и основан на идее адаптивного построения словаря и представления входной строки в виде конкатенации словарных слов. Лучшие известные алгоритмы сжатия, основанные на этом подходе, составляют так называемое семейство ZIP; они давно уже являются стандартом и доступны практически на всех вычислительных платформах (в их числе gzip, zip, winzip и многие другие). | ||
Строка 19: | Строка 19: | ||
'''Преобразование Барроуза-Уилера''' | '''Преобразование Барроуза-Уилера''' | ||
В работе [3] Барроуз и Уилер предложили новый алгоритм сжатия, основанный на обратимом преобразовании, которое ныне называется преобразованием Барроуза-Уилера (bwt). Пусть имеется строка s. Вычисление значения bwt(s) состоит из трех основных этапов см. рис. 1): | В работе [3] Барроуз и Уилер предложили новый алгоритм сжатия, основанный на обратимом преобразовании, которое ныне называется преобразованием Барроуза-Уилера (bwt). Пусть имеется строка s. Вычисление значения bwt(s) состоит из трех основных этапов (см. рис. 1): | ||
1. добавить | 1. добавить к концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | ||
2. сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат | 2. сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат циклические сдвиги строки s$, отсортированные в лексикографическом порядке; | ||
3. построить | 3. построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math>. | ||
Заметим, что каждый столбец матрицы <math>\mathcal{M} \;</math> – и, следовательно, преобразованный текст s – представляет собой перестановку строки s$. В нашем примере F, первый столбец bwt-матрицы <math>\mathcal{M} \;</math>, состоит из всех символов s, отсортированных по алфавиту. На рис. 1 F = $iiiimppssss. | Заметим, что каждый столбец матрицы <math>\mathcal{M} \;</math> – и, следовательно, преобразованный текст <math>\hat{s} \;</math> – представляет собой перестановку строки s$. В нашем примере F, первый столбец bwt-матрицы <math>\mathcal{M} \;</math>, состоит из всех символов s, отсортированных по алфавиту. На рис. 1 F = $iiiimppssss. | ||
{| class="wikitable" | {| class="wikitable" | ||
|mississippi$ | |mississippi$ | ||
| | |||
|$ | |$ | ||
|mississipp | |mississipp | ||
|i | |i | ||
|- | |- | ||
|ississippi$m | |ississippi$m | ||
| | |||
|i | |i | ||
|$mississip | |$mississip | ||
|p | |p | ||
|- | |- | ||
|ssissippi$mi | |ssissippi$mi | ||
| | |||
|i | |i | ||
|ppi$missis | |ppi$missis | ||
|s | |s | ||
|- | |- | ||
|sissippi$mis | |sissippi$mis | ||
| | |||
|i | |i | ||
|ssippi$mis | |ssippi$mis | ||
|s | |s | ||
|- | |- | ||
|issippi$miss | |issippi$miss | ||
| | |||
|i | |i | ||
|ssissippi$ | |ssissippi$ | ||
|m | |m | ||
|- | |- | ||
|ssippi$missi | |ssippi$missi | ||
| <math>\Longrightarrow</math> | |||
|m | |m | ||
|ississippi | |ississippi | ||
|$ | |$ | ||
|- | |- | ||
|sippi$missis | |sippi$missis | ||
| | |||
|p | |p | ||
|i$mississi | |i$mississi | ||
|p | |p | ||
|- | |- | ||
|ippi$mississ | |ippi$mississ | ||
| | |||
|p | |p | ||
|pi$mississ | |pi$mississ | ||
|i | |i | ||
|- | |- | ||
|ppi$mississi | |ppi$mississi | ||
| | |||
|s | |s | ||
|ippi$missi | |ippi$missi | ||
|s | |s | ||
|- | |- | ||
|pi$mississip | |pi$mississip | ||
| | |||
|s | |s | ||
|issippi$mi | |issippi$mi | ||
|s | |s | ||
|- | |- | ||
|i$mississipp | |i$mississipp | ||
| | |||
|s | |s | ||
|sippi$miss | |sippi$miss | ||
|i | |i | ||
|- | |- | ||
|$mississippi | |$mississippi | ||
| | |||
|s | |s | ||
|sissippi$m | |sissippi$m | ||
|i | |i | ||
Строка 111: | Строка 111: | ||
'''Определение 1.''' Для <math>1 \le i \le n \;</math> обозначим за <math>s[k_i, n - 1] \;</math> суффикс строки s, | '''Определение 1.''' Для <math>1 \le i \le n \;</math> обозначим за <math>s[k_i, n - 1] \;</math> суффикс строки s, являющийся префиксом строки i матрицы <math>\mathcal{M} \;</math>, и определим <math>\Psi(i) \;</math> как индекс строки, которой предшествует префикс <math>s[k_{i + 1}, n - 1] \;</math>. | ||
Например, на рис. 1 <math>\Psi(2) = 7 \;</math>, так как строка 2 матрицы <math>\mathcal{M} \;</math> имеет префикс ippi, а строка 7 – ppi. Отметим, что <math>\Psi(i) \;</math> не определено для i = 0, поскольку у строки 0 не имеется надлежащего суффикса s. ''[В [3] вместо <math>\Psi \;</math> авторы используют отображение, в сущности, являющееся | Например, на рис. 1 <math>\Psi(2) = 7 \;</math>, так как строка 2 матрицы <math>\mathcal{M} \;</math> имеет префикс ippi, а строка 7 – ppi. Отметим, что <math>\Psi(i) \;</math> не определено для i = 0, поскольку у строки 0 не имеется надлежащего суффикса s. ''[В работе [3] вместо <math>\Psi \;</math> авторы используют отображение, в сущности, являющееся обращением <math>\Psi \;</math>. Использование <math>\Psi \;</math> было предложено в литературе, посвященной сжатым индексам, где <math>\Psi \;</math> и его обращение играют важную роль (см. [14]).]'' | ||
'''Лемма 1. Для i = 1, ... , n имеет место <math>F[i] = \hat{s}[ \Psi(i)] \;</math>.''' | '''Лемма 1. Для i = 1, ... , n имеет место <math>F[i] = \hat{s}[ \Psi(i)] \;</math>.''' | ||
Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является <math>s[ | Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является <math>s[k_i + 1, n - 1] \;</math>, является <math>s[k_i] \;</math>. Из этого, согласно определению 1, следует <math>\hat{s} [\Psi(i)] = s[k_i] = F[i] \;</math>, что и требовалось доказать. □ | ||
'''Лемма 2. Если <math>1 \le i < j \le n \;</math> и F[i] = F[j], то <math>\Psi(i) < \Psi(j) \;</math>.''' | '''Лемма 2. Если <math>1 \le i < j \le n \;</math> и F[i] = F[j], то <math>\Psi(i) < \Psi(j) \;</math>.''' | ||
Доказательство. Пусть <math>s[k_i, n - 1] \;</math> (соответственно, <math>s[k_j, n - 1]) \;</math> обозначает суффикс s, являющийся префиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что <math>s[k_i, n - 1] \prec s[k_j, n - 1] \;</math>. Из гипотезы F[i] = F[j] следует, что <math>s[k_i] = s[k_j] \;</math>, поскольку должно иметь место <math>s[ | Доказательство. Пусть <math>s[k_i, n - 1] \;</math> (соответственно, <math>s[k_j, n - 1]) \;</math> обозначает суффикс s, являющийся префиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что <math>s[k_i, n - 1] \prec s[k_j, n - 1] \;</math>. Из гипотезы F[i] = F[j] следует, что <math>s[k_i] = s[k_j] \;</math>, поскольку должно иметь место <math>s[k_i + 1, n - 1] \prec s[k_j + 1, n - 1] \;</math>. Из этого следует утверждение леммы, поскольку по построению <math>\Psi(i) \;</math> (<math>\Psi(j) \;</math>, соответственно) является лексикографической позицией строки, префиксом которой является <math>s[k_i + 1, n - 1] \;</math> (<math>s[k_j + 1, n - 1] \;</math>, соответственно). □ | ||
Строка 132: | Строка 132: | ||
На рис. 1 имеет место <math>\Psi(2) = 7 \;</math>, и <math>F[2] \;</math> и <math>\hat{s}[7] \;</math> | На рис. 1 имеет место <math>\Psi(2) = 7 \;</math>, и <math>F[2] \;</math> и <math>\hat{s}[7] \;</math> являются вторыми вхождениями i в соответствующих строках. Это свойство обычно формулируется так: соответствующие символы имеют ''один и тот же относительный порядок'' в строках F и <math>\hat{s}</math>. | ||
Строка 186: | Строка 186: | ||
Рисунок 2. Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) | Рисунок 2. Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) из исходной строки s и ее суффиксного массива sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение <math>\Psi \;</math>, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива <math>[1, | \Sigma] | \;</math>, который изначально содержит в позиции count[i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения <math>j_0 \;</math>. | ||
'''Теорема 6. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. Строка <math>\hat{s} = bwt(s) \;</math> может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | '''Теорема 6. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. Строка <math>\hat{s} = bwt(s) \;</math> может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | ||
Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n | Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) бит рабочего пространства при помощи, например, алгоритма из [11]. Суффиксный массив представляет собой массив целых чисел sa[1, n], такой, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы <math>\mathcal{M} \;</math> является уникальный суффикс s, за которым следует специальный символ $, суффиксный массив обеспечивает упорядочение строк в <math>\mathcal{M} \;</math>. Следовательно, bwt(s) можно вычислить из массива sa за линейное время при помощи процедуры sa2bwt на рис. 2. □ | ||
'''Теорема 7. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. При наличии bwt(s) строка s может быть | '''Теорема 7. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. При наличии bwt(s) строка s может быть восстановлена за время O(n) с использованием O(n log n) бит рабочего пространства.''' | ||
Доказательство. Алгоритм | Доказательство. Алгоритм восстановления s практически дословно воспроизводит процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения <math>\Psi \;</math> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует массив count (счетчик), являющийся «компактным» представлением F. В момент начала работы процедуры для любого символа <math>c \in \Sigma \;</math> счетчик count[c] выдает индекс первой строки матрицы <math>\mathcal{M} \;</math>, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основном цикле for процедуры bwt2psi сканируется массив bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс <math>\ell</math>-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi[h] значение <math>i = \Psi(h) \;</math>. После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5. | ||
Строка 207: | Строка 207: | ||
Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку <math>\hat{s} \;</math> с использованием кодирования по модели «движение к началу» (move-to-front) [ ] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся | Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку <math>\hat{s} \;</math> с использованием кодирования по модели «движение к началу» (move-to-front) [2] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся с момента предыдущего вхождения этого же символа. Для этого mtf ведет список символов, упорядоченный по давности вхождения; когда встречается следующий символ, алгоритм выводит его текущий ранг и перемещает его в начало списка. Заметим, что mtf вычисляет строку, имеющую ту же длину, что и <math>\hat{s} \;</math> и в случае, если <math>\hat{s} \;</math> является локально гомогенной, строка <math>mtf(\hat{s}) \;</math> будет в основном состоять из целых чисел малой величины. ''[Если s – текст на английском языке, <math>mtf(\hat{s}) \;</math> обычно содержит более 50% нулей.]'' | ||
Учитывая это смещенное распределение, строку <math>mtf(\hat{s}) \;</math> можно легко сжать: Барроуз и Уилер предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел. | Учитывая это смещенное распределение, строку <math>mtf(\hat{s}) \;</math> можно легко сжать: Барроуз и Уилер предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел. | ||
Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия | Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия без потерь. Через несколько лет после публикации bwt в работах [9, 12] было показано, что коэффициент сжатия алгоритма Барроуза-Уилера может быть ограничен в терминах эмпирической энтропии k-го порядка входной строки для любого <math>k \ge 0 \;</math>. К примеру, Каплан и др. [9] показали, что для любой входной строки s и вещественного числа <math>\mu > 1 \;</math> длина сжатой строки ограничена <math>\mu \; n \; H_k (s) + n \; log(\zeta (\mu)) + \mu \; g_k + O(log \; n)</math> бит, где <math>\zeta (\mu) \;</math> – стандартная дзета-функция, а <math>g_k \;</math> – функция, зависящая только от k и от размера <math>\Sigma \;</math>. Эта граница ''поточечно'' верна для ''любой'' строки s, ''одновременно'' для любых <math>k \ge O \;</math> и <math>\mu > 1 \;</math>; и это весьма примечательно, поскольку ни для одного другого алгоритма сжатия аналогичные границы не были доказаны. Теоретическое изучение эффективности алгоритмов сжатия на базе преобразования bwt в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы. | ||
== Применение == | == Применение == | ||
После выхода основополагающей работы Барроуза и Уилера многие исследователи предложили собственные алгоритмы сжатия на базе bwt (см. [4, 5] и ссылки в этих статьях). Особенно интересны в | После выхода основополагающей работы Барроуза и Уилера многие исследователи предложили собственные алгоритмы сжатия на базе bwt (см. [4, 5] и ссылки в этих статьях). Особенно интересны в теоретическом плане результаты работы [6], демонстрирующие, что преобразование bwt может быть использовано для разработки «[[Усиление_степени_сжатия_текста|усилителей сжатия]]» (или механизмов повышения степени сжатия), которые служат инструментом повышения эффективности других алгоритмов сжатия вполне определенным и измеримым образом. | ||
Строка 229: | Строка 229: | ||
== Ссылка на код == | == Ссылка на код == | ||
Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn. unipmn.it/~manzini/boosting) содержит исходный код алгоритмов, протестированных в [ ]. «Облегченный» код для вычисления преобразования bwt и его обращения (без сжатия) доступен по адресу http://www.mfn.unipmn.it/~manzini/lightweight. Код bzip2 доступен по адресу http://www.bzip.org. | Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn. unipmn.it/~manzini/boosting) содержит исходный код алгоритмов, протестированных в работе [4]. «Облегченный» код для вычисления преобразования bwt и его обращения (без сжатия) доступен по адресу http://www.mfn.unipmn.it/~manzini/lightweight. Код bzip2 доступен по адресу http://www.bzip.org. | ||
== См. также == | == См. также == |
правок