Усиление степени сжатия текста

Ключевые слова и синонимы

Модели сжатия высокого порядка; сжатие с учетом контекста

Постановка задачи

Неформально техника усиления представляет собой метод, который при применении к определенному классу алгоритмов повышает их эффективность. Повышение должно быть доказуемым и четко определенным в виде одного или нескольких параметров, характеризующих эффективность работы алгоритма. Примеры подобных «усилителей» можно найти в сегментах рандомизированных алгоритмов (здесь усилитель позволяет превратить алгоритм 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] определяется как максимальная степень сжатия, которой можно достичь при просмотре не более чем 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{ Н_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 и такой структурой данных, как суффиксное дерево. Обозначим за T суффиксное дерево строки s$. У T |s| + 1 листьев, по одному на суффикс s$, а его ребра помечены подстроками s$ (см. рис. 1). Любая вершина u дерева T неявно ассоциируется с подстрокой s$, задаваемой конкатенацией меток ребер на нисходящем пути от корня T к u. В рамках этой неявной ассоциации листья T соответствуют суффиксам s$. Предположим, что ребра суффиксного дерева лексикографически отсортированы. Поскольку каждая строка матрицы bwt имеет префикс в виде суффикса s$ , а строки лексикографически отсортированы, i-й лист суффиксного дерева (считая справа налево) соответствует i-й строке матрицы bwt. Ассоциируем с i-м листом T i-й символ s = bwt(s). На рис. 1 эти символы представлены внутри кружков.

Для любой вершины суффиксного дерева u обозначим за s(u) подстроку J, полученнуюв результате конкатенации, слева направо, символов, ассоциированных с листьями, являющимися потомками вершины u. Разумеется, s(root(T)) = J. Подмножество L вершин T называется листовым покрытием, если каждый лист суффиксного дерева имеет уникального предка в L. Любое листовое покрытие L = fu1..: ; upg естественным образом порождает разбиение листьев T. В силу взаимосвязи между T и матрицей bwt также имеется разбиение s, а именно, {J(MI},. .. ,s(up}}.

Пример 3. Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение s, порожденное этим листовым покрытием, выглядит как fi;pssm; $; pi; ssiig.

Усиление степени сжатия текста, рис. 1 Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, s = bwt(s) = ipssm$pissii