Усиление степени сжатия текста
Ключевые слова и синонимы
Постановка задачи
Неформально техника усиления представляет собой метод, который при применении к определенному классу алгоритмов повышает их эффективность. Повышение должно быть доказуемым и четко определенным в терминах одного или нескольких параметров, характеризующих эффективность работы алгоритма. Примеры подобных «усилителей» можно найти в сегментах рандомизированных алгоритмов (здесь усилитель позволяет превратить алгоритм BPP в RP [6]) и теории вычислительного обучения (в данном случае усилитель позволяет повысить точность прогнозирования у слабого обучающего алгоритма [10]). Задача усиления сжатия заключается в разработке техники, повышающей эффективность сжатия широкого класса алгоритмов. В частности, результатом работы Ферраджины и др. явилась обобщенная техника, позволяющая «заставить» компрессор, не использовавший контекстной информации вовсе, всегда использовать наилучший возможный контекст.
Классические алгоритмы Хаффмана и арифметического кодирования [1] могут служить примерами статистических алгоритмов сжатия, обычно кодирующих входной символ в соответствии с общей частотой его вхождения в данных, подлежащих сжатию. [Динамические версии этих алгоритмов рассматривают частоту вхождения символа в уже просканированной порции входных данных.] Этот подход эффективен и прост в реализации, однако обеспечивает невысокий уровень сжатия. Эффективность работы статистических алгоритмов сжатия можно повысить за счет использования моделей более высокого порядка, получающих более качественную оценку частоты встречаемости входных символов. Алгоритм сжатия PPM [9] реализует эту идею путем сбора данных о частоте вхождения всех символов, попадающих в любой контекст длины k, и сжатия их при помощи арифметического кодирования. Длина контекста k представляет собой параметр алгоритма, который определяется подлежащими сжатию данными: он будет разным при сжатии текста на английском языке, последовательности ДНК или документа в формате XML. Можно привести и другие примеры сложных программ сжатия, таких как алгоритмы Лемпеля-Зива и Барроуза-Уилера [9], использующих информацию о контексте неявным образом. Все эти алгоритмы, учитывающие контекст, обеспечивают высокую эффективность работы, однако обычно сложны для реализации и анализа.
Применение техники усиления Ферраджины и др. к алгоритмам Хаффмана и арифметического кодирования позволяет получить новый алгоритм сжатия со следующими характеристиками:
(i) новый алгоритм использует усиленный алгоритм сжатия в качестве черного ящика;
(ii) новый алгоритм выполняет сжатие в стиле PPM, автоматически выбирая оптимальное значение k;
(iii) асимптотическая эффективность нового алгоритма по соотношению времени и памяти соответствует эффективности усиленного алгоритма сжатия.
В следующих разделах будет приведено точное формальное обоснование перечисленных характеристик.
Основные результаты
Нотация. Эмпирическая энтропия
Пусть s – строка над алфавитом [math]\displaystyle{ \Sigma = \{ a_1, ..., a_h \} \; }[/math]. Обозначим для каждого [math]\displaystyle{ a_i \in \Sigma \; }[/math] за [math]\displaystyle{ n_i \; }[/math] количество вхождений [math]\displaystyle{ a_i \; }[/math] в s. Эмпирическая энтропия нулевого порядка строки s определяется как [math]\displaystyle{ H_0(s) = - \sum^h_{i = 1} (n_i / |s|) \; log (n_i / |s|) }[/math], где все алгоритмы берутся по основанияю 2, а 0 log 0 = 0. Хорошо известно, что [math]\displaystyle{ H_0 \; }[/math] представляет собой максимальный уровень сжатия, которого можно достичь при использовании уникального декодируемого кода, в котором каждому символу алфавита назначается уникальное кодовое слово. Более высокой степени сжатия можно достичь, если кодовое слово символа зависит от k символов, следующих за ним (то есть от его контекста). [Большинство алгоритмов сжатия данных обычно рассматривают контекст, предшествующий кодируемым символам. В данном описании используется нестандартный «прямой» контекст для упрощения нотации в последующих разделах. Работа с «прямым» контекстом эквивалентна работе с традиционным «обратным» контекстом для обращенной строки s (подробнее см. в [3]).] Определим [math]\displaystyle{ w_s \; }[/math] как строку единичных символов, непосредственно предшествующих вхождениям w в s. Например, для s = bcabcabdca получим [math]\displaystyle{ ca_s = bbd \; }[/math]. Значение
(1) [math]\displaystyle{ H_k(s) = \frac{1}{|s|} \sum_{w \in \Sigma^k} |w_s| \; H_0(w_s) }[/math]
представляет эмпирическую энтропию k-го порядка для s и является нижней границей степени сжатия, которой можно достичь при использовании кодовых слов, которые зависят только от k символов, непоследственно следующих за кодируемым.
Пример 1. Пусть строка s = mississippi. Для k = 1 имеем [math]\displaystyle{ i_s = mssp, s_s = isis, p_s = ip \; }[/math]. Следовательно, [math]\displaystyle{ H_1(s) = \frac{4}{11} H_0 (mssp) + \frac{4}{11} H_0 (isis) + \frac{2}{11} H_0 (ip) = \frac{6}{11} + \frac{4}{11} + \frac{2}{11} = \frac{12}{11}. }[/math]
Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для [math]\displaystyle{ s = a^n \; }[/math] имеет место [math]\displaystyle{ |s| \; H_k(s) = 0 }[/math] для любого [math]\displaystyle{ k \ge 0 \; }[/math]. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [7] было введено понятие модифицированной эмпирической энтропии нулевого порядка [math]\displaystyle{ H_0^*(s) \; }[/math], имеющей следующее свойство: [math]\displaystyle{ |s| \; H^*_0(s) }[/math] по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. Модифицированная эмпирическая энтропия k-го порядка [math]\displaystyle{ H^*_k \; }[/math] определяется через [math]\displaystyle{ H^*_0 \; }[/math] как максимальная степень сжатия, которой можно достичь при просмотре не более чем k символов, следующих за кодируемым.
Преобразование Барроуза-Уилера
Пусть дана строка s. Преобразование Барроуза-Уилера [2] (bwt) включает три основных этапа:
(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в [math]\displaystyle{ \Sigma \; }[/math];
(2) сформировать концептуальную матрицу [math]\displaystyle{ \mathcal{M} \; }[/math], строки которой содержат круговые сдвиги строки s$, отсортированные в лексикографическом порядке;
(3) построить преобразованный текст [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math], взяв последний столбец матрицы [math]\displaystyle{ \mathcal{M} \; }[/math] (см. рис. 1).
В работе [2] Барроуз и Уилер доказали, что [math]\displaystyle{ \hat{s} \; }[/math] является перестановкой s и что можно восстановить s из [math]\displaystyle{ \hat{s} \; }[/math] за время O(|s|).
Чтобы убедиться в мощи преобразования bwt, рассмотрим ситуацию с точки зрения эмпирической энтропии. Зафиксируем целое положительное число k. Первые k столбцов матрицы bwt содержат все подстроки s длины k, лексикографически упорядоченные (а также k подстрок, содержащих символ $). Для любой подстроки w строки s длиной k символы, непосредственно предшествующие каждому вхождению w в s, сгруппированы вместе в множество последовательных позиций в [math]\displaystyle{ \hat{s} \; }[/math], поскольку они являются последними символами строк матрицы [math]\displaystyle{ \mathcal{M} \; }[/math], которым предшествуют символы w. Используя нотацию, предложенную при определении [math]\displaystyle{ H_k \; }[/math], можно переформулировать это свойство так, чтобы символы [math]\displaystyle{ w_s \; }[/math] были последовательными в [math]\displaystyle{ \hat{s} \; }[/math] или, что эквивалентно, чтобы [math]\displaystyle{ \hat{s} \; }[/math] содержало в качестве подстроки перестановку [math]\displaystyle{ \pi_w (w_s) \; }[/math] строки [math]\displaystyle{ w_s \; }[/math].
Пример 2. Пусть s = mississippi и k = 1. На рис. 1 показано, что [math]\displaystyle{ \hat{s} [1, 4] = pssm \; }[/math] является перестановкой [math]\displaystyle{ i_s = mssp \; }[/math]. Кроме того, [math]\displaystyle{ \hat{s} [6, 7] = pi \; }[/math] является перестановкой [math]\displaystyle{ p_s = ip \; }[/math], а [math]\displaystyle{ \hat{s} [8, 11] = ssii \; }[/math] – перестановкой [math]\displaystyle{ s_s = isis \; }[/math].
Поскольку перестановка строки не меняет ее (модифицированной) эмпирической энтропии нулевого порядка (то есть [math]\displaystyle{ H_0 (\pi_w (w_s)) = H_0 (w_s)) \; }[/math]), преобразование Барроуза-Уилера может рассматриваться как способ свести задачу сжатия строки s вплоть до энтропии k-го порядка к задаче сжатия различных фрагментов [math]\displaystyle{ \hat{s} \; }[/math] вплоть до их энтропии нулевого порядка. Чтобы убедиться в этом, рассмотрим разбиение [math]\displaystyle{ \hat{s} \; }[/math] на подстроки [math]\displaystyle{ \pi_w (w_s) \; }[/math], изменяя w над [math]\displaystyle{ \Sigma^k \; }[/math]. Из этого следует, что [math]\displaystyle{ \hat{s} = \bigsqcup_{w \in \Sigma^k} \pi_w (w_s) \; }[/math], где [math]\displaystyle{ \bigsqcup \; }[/math] – оператор конкатенации над строками. [Помимо [math]\displaystyle{ \bigsqcup_{w \in \Sigma^k} \pi_w (w_s) \; }[/math], строка [math]\displaystyle{ \hat{s} \; }[/math] также содержит последние k символов s (не входящие ни в какой [math]\displaystyle{ w_s \; }[/math]) и специальный символ $. Для простоты в дальнейшем изложении эти символы будут игнорироваться.]
Согласно (1), отсюда следует [math]\displaystyle{ \sum_{w \in \Sigma^k} |\pi_w (w_s)| H_0 (\pi_w (w_s)) = \sum_{w \in \Sigma^k} |w_s| H_0 (w_s) = |s| H_k (s) }[/math].
Следовательно, для сжатия строки s вплоть до [math]\displaystyle{ |s| H_k (s) \; }[/math] достаточно сжать каждую подстроку [math]\displaystyle{ \pi_w (w_s)) \; }[/math] вплоть до эмпирической энтропии нулевого порядка. Заметим, однако, что при использовании вышеприведенной схемы параметр k необходимо выбрать заранее. Более того, подобную схему нельзя применить к [math]\displaystyle{ H^*_k \; }[/math], определенной в терминах контекстов длины не более k. В результате на данный момент не известно эффективной процедуры для вычисления разбиения [math]\displaystyle{ \hat{s} \; }[/math] согласно [math]\displaystyle{ H^*_k(s) \; }[/math]. Усилитель сжатия [3] представляет собой естественное дополнение bwt и позволяет сжимать любую строку s до [math]\displaystyle{ H_k(s) \; }[/math] (или [math]\displaystyle{ H^*_k(s) \; }[/math]) одновременно для всех [math]\displaystyle{ k \ge 0 \; }[/math].
Алгоритм усиления степени сжатия
Важнейшим компонентом алгоритма усиления степени сжатия является взаимосвязь между матрицей bwt и такой структурой данных, как суффиксное дерево. Обозначим за [math]\displaystyle{ \mathcal{T} \; }[/math] суффиксное дерево строки s$. У [math]\displaystyle{ \mathcal{T} \; }[/math] имеется |s| + 1 листьев, по одному на суффикс s$, а его ребра помечены подстроками s$ (см. рис. 1). Любая вершина u дерева [math]\displaystyle{ \mathcal{T} \; }[/math] неявно ассоциируется с подстрокой s$, задаваемой конкатенацией меток ребер на нисходящем пути от корня [math]\displaystyle{ \mathcal{T} \; }[/math] к u. В рамках этой неявной ассоциации листья [math]\displaystyle{ \mathcal{T} \; }[/math] соответствуют суффиксам s$. Предположим, что ребра суффиксного дерева лексикографически отсортированы. Поскольку каждая строка матрицы bwt имеет префикс в виде суффикса s$, а строки лексикографически отсортированы, i-й лист суффиксного дерева (считая справа налево) соответствует i-й строке матрицы bwt. Ассоциируем с i-м листом [math]\displaystyle{ \mathcal{T} \; }[/math] i-й символ [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math]. На рисунке эти символы представлены внутри кружков.
Для любой вершины суффиксного дерева u обозначим за [math]\displaystyle{ \hat{s}\langle u \rangle \; }[/math] подстроку [math]\displaystyle{ \hat{s} \; }[/math], полученную в результате конкатенации, слева направо, символов, ассоциированных с листьями, являющимися потомками вершины u. Разумеется, [math]\displaystyle{ \hat{s} \langle root( \mathcal{T} ) \rangle = \hat{s} \; }[/math]. Подмножество [math]\displaystyle{ \mathcal{L} \; }[/math] вершин [math]\displaystyle{ \mathcal{T} \; }[/math] называется листовым покрытием, если каждый лист суффиксного дерева имеет уникального предка в [math]\displaystyle{ \mathcal{L} \; }[/math]. Любое листовое покрытие [math]\displaystyle{ \mathcal{L} = \{ u_1, ..., u_p \} \; }[/math] естественным образом порождает разбиение листьев [math]\displaystyle{ \mathcal{T} \; }[/math]. В силу взаимосвязи между [math]\displaystyle{ \mathcal{T} \; }[/math] и матрицей bwt оно также является разбиением [math]\displaystyle{ \hat{s} \; }[/math], а именно – [math]\displaystyle{ \{ \hat{s} \langle u_1 \rangle , ..., \hat{s} \langle u_p \rangle \} \; }[/math].
Пример 3. Рассмотрим суффиксное дерево на рисунке. Листовое покрытие состоит из всех вершин, имеющих глубину 1. Разбиение [math]\displaystyle{ \hat{s}\; }[/math], порожденное этим листовым покрытием, выглядит как {i, pssm, $; pi, ssii}.
Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е. [math]\displaystyle{ \hat{s} = bwt(s) = ipssm$pissii \; }[/math].
Обозначим за C функцию, которая ассоциирует с каждой строкой x над [math]\displaystyle{ \Sigma \cup \{ $ \} \; }[/math] положительное вещественное значение C(x). Для любого листового покрытия [math]\displaystyle{ \mathcal{L} \; }[/math] определим его стоимость как [math]\displaystyle{ C(\mathcal{L}) = \sum_{u \in \mathcal{L}} C( \hat{s} \langle u \rangle) \; }[/math]. Иными словами, стоимость листового покрытия [math]\displaystyle{ \mathcal{L} \; }[/math] равна сумме стоимостей строк в разбиении, порожденном [math]\displaystyle{ \mathcal{L} \; }[/math]. Листовое покрытие [math]\displaystyle{ \mathcal{L}_{min} \; }[/math] называется оптимальным относительно C, если [math]\displaystyle{ C(\mathcal{L}_{min}) \le C(\mathcal{L}) \; }[/math] для любого листового покрытия [math]\displaystyle{ \mathcal{L} \; }[/math].
Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен [math]\displaystyle{ |x| H_0(x) + \eta |x| + \mu \; }[/math] бит, где [math]\displaystyle{ \eta \; }[/math] и [math]\displaystyle{ \mu \; }[/math] – константы. Определим функцию стоимости [math]\displaystyle{ C_A(x) = |x| H_0 (x) + \eta |x| + \mu \; }[/math]. В работе [3] Ферраджина и коллеги используют жадный алгоритм с линейным временем выполнения, вычисляющий оптимальное листовое покрытие [math]\displaystyle{ \mathcal{L}_{min} \; }[/math] относительно [math]\displaystyle{ C_A \; }[/math]. Авторы работы [3] также показали, что для любого [math]\displaystyle{ k \ge 0 \; }[/math] существует листовое покрытие [math]\displaystyle{ \mathcal{L}_k \; }[/math] стоимостью [math]\displaystyle{ C_A(\mathcal{L}_k) = |s| H_k(s) + \eta |s| + O(|\Sigma|^k) \; }[/math]. Эти два важнейших наблюдения показывают, что при использовании A для сжатия каждой подстроки в разбиении, порожденном оптимальным листовым покрытием [math]\displaystyle{ \mathcal{L}_{min} \; }[/math], общий размер выходного значения ограничен в терминах [math]\displaystyle{ |s| H_k(s) \; }[/math] для любого [math]\displaystyle{ k \ge 0 \; }[/math]. На деле [math]\displaystyle{ \sum_{u \in \mathcal{L}_{min}} C_A (\hat{s} \langle u \rangle ) = C_A(\mathcal{L}_{min}) \le C_A (\mathcal{L}_k) = |s| H_k(s) + \eta|s| + O(|\Sigma|^k) }[/math].
Суммируя все вышесказанное, усиление алгоритма сжатия A над строкой s состоит из трех основных этапов:
1. Вычислить [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math];
2. Вычислить оптимальное листовое покрытие [math]\displaystyle{ \mathcal{L}_{min} \; }[/math] относительно [math]\displaystyle{ C_A \; }[/math] и разбиение [math]\displaystyle{ \hat{s} \; }[/math], соответствующее [math]\displaystyle{ \mathcal{L}_{min} \; }[/math];
3. Сжать каждую подстроку разбиения при помощи алгоритма A.
Таким образом, парадигма усиления сводит разработку эффективных алгоритмов сжатия, использующих информацию о контексте, к (обычно более простой) разработке алгоритмов сжатия нулевого порядка. Эффективность этой парадигмы описывается следующей теоремой.
Теорема 1 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более [math]\displaystyle{ |x| H_0(x) + \eta |x| + \mu \; }[/math] бит. Механизм усиления степени сжатия, примененный к A, дает выходное значение, размер которого ограничен [math]\displaystyle{ |s| H_k(s) + log |s| + \eta |s| + O(|\Sigma|^k) \; }[/math] бит одновременно для всех [math]\displaystyle{ k \ge 0 \; }[/math]. Учитывая A, механизм усиления привносит в процесс сжатия дополнительные накладные расходы на память в размере O(|s| log |s|) бит, но не вносит дополнительных асимптотических затрат времени.
Аналогичный результат имеет место и для модифицированной энтропии [math]\displaystyle{ H^*_k \; }[/math] (однако доказать его намного сложнее): пусть дан алгоритм сжатия A, который сжимает любую строку x до не более чем [math]\displaystyle{ \lambda |x| \; H^*_0 (x) + \mu }[/math] бит. Механизм усиления степени сжатия дает выходное значение, размер которого ограничен [math]\displaystyle{ \lambda |s| \; H^*_k(s) + log |s| + O(|\Sigma|^k) }[/math] бит одновременно для всех [math]\displaystyle{ k \ge 0 \; }[/math]. В работе [3] авторы также показали, что ни один алгоритм сжатия, удовлетворяющий некоторым мягким предположениям относительно его внутренних принципов работы, не способен получить схожую границу, не включающую одновременно мультипликативный коэффициент [math]\displaystyle{ \lambda \; }[/math] и аддитивный логарифмический терм. Кроме того, в [3] была предложена конкретизация усилителя, которая сжимает любую строку s до не более чем [math]\displaystyle{ 2,5 |s| \; H^*_k(s) +log |s| + O(|\Sigma|^k) }[/math] бит. Эта граница аналитически превосходит границы, доказанные для лучших существующих алгоритмов сжатия, включая алгоритмы Лемпеля-Зива и Барроуза-Уилера и алгоритм PPM.
Применение
Помимо естественного применения в области сжатия данных, механизмы повышения степени сжатия также использовались для разработки сжатых полнотекстовых индексов [8].
Открытые вопросы
Парадигму усиления можно обобщить следующим образом. Пусть дан алгоритм компрессии A; необходимо найти и перестановку [math]\displaystyle{ \mathcal{P} \; }[/math] для символов строки s, и стратегию разбиения, такие, чтобы примененный к ним подход к усилению минимизировал размер выходных данных. Выше были приведены убедительные свидетельства того, что преобразование Барроуза-Уилера является элегантной и эффективной перестановкой [math]\displaystyle{ \mathcal{P} \; }[/math]. Как ни удивительно, другие классические задачи сжатия данных также вписываются в эту структуру: поиск кратчайшей общей надстроки (эта задача является MAX-SNP-сложной), кодирование с переменной длиной строки для множества строк (полиномиально разрешимая задача), LZ77 и нахождение минимального количества фраз (также MAX-SNP-сложная). Таким образом, подход к усилению является достаточно общим, чтобы заслуживать дальнейших теоретических и практических исследований [5].
Экспериментальные результаты
Исследование нескольких алгоритмов сжатия, основанных на усилении, и сравнение их с другими современными способами сжатия приведено в работе [4]. Эксперименты показывают, что техника усиления является более надежной по сравнению с другими подходами и хорошо работает даже с менее эффективными алгоритмами сжатия нулевого порядка. Однако положительные результаты достигаются за счет использования большего количества ресурсов (времени и памяти).
Наборы данных
Наборы данных, использовавшиеся в [4], доступны по адресу http://www.mfn.unipmn.it/~manzini/boosting. Другие наборы данных для сжатия и индексирования можно найти на сайте Pizza&Chili http://pizzachili.di.unipi.it/.
Ссылка на код
Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn.unipmn.it/~manzini/boosting) содержит исходный код всех алгоритмов, протестированных в [4]. Этот код организован в виде библиотеки с высокой степенью модульности, которая может использоваться любым алгоритмом сжатия и не требует знания алгоритма bwt или процедуры усиления.
См. также
Литература
1. Bell, T.C., Cleary, J.G., Witten, I.H.: Text compression. Prentice Hall, NJ (1990)
2. Burrows, M. Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Report 124, Digital Equipment Corporation (1994)
3. Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression inoptimal lineartime.J.ACM 52,688-713 (2005)
4. Ferragina, P., Giancarlo, R., Manzini, G.: The engineering of a compression boosting library: Theory vs practice in bwt compression. In: Proc. 14th European Symposium on Algorithms (ESA). LNCS, vol. 4168, pp. 756-767. Springer, Berlin (2006)
5. Giancarlo, R., Restivo, A., Sciortino, M.: From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization. Theor. Comput. Sci. 387(3):236-248 (2007)
6. Karp, R., Pippenger, N., Sipser, M.: A Time-Randomness trade-off. In: Proc. Conference on Probabilistic Computational Complexity, AMS, 1985, pp. 150-159
7. Manzini, G.: An analysis of the Burrows-Wheeler transform. J.ACM 48,407-430 (2001)
8. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv.39(1) (2007)
9. Salomon, D.: Data Compression: the Complete Reference, 4th edn. Springer, London (2004)
10. Schapire, R.E.: The strength of weak learnability. Mach. Learn. 2,197-227 (1990)
