4488
правок
Irina (обсуждение | вклад) м (→Ссылка на код) |
Irina (обсуждение | вклад) |
||
(не показаны 23 промежуточные версии этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Неформально техника усиления представляет собой метод, который при применении к определенному классу алгоритмов повышает их эффективность. Повышение должно быть доказуемым и четко определенным в | Неформально техника усиления представляет собой метод, который при применении к определенному классу алгоритмов повышает их эффективность. Повышение должно быть доказуемым и четко определенным в терминах одного или нескольких параметров, характеризующих эффективность работы алгоритма. Примеры подобных «усилителей» можно найти в сегментах рандомизированных алгоритмов (здесь усилитель позволяет превратить алгоритм BPP в RP [6]) и теории вычислительного обучения (в данном случае усилитель позволяет повысить точность прогнозирования у слабого обучающего алгоритма [10]). Задача усиления сжатия заключается в разработке техники, повышающей эффективность сжатия широкого класса алгоритмов. В частности, результатом работы Ферраджины и др. явилась обобщенная техника, позволяющая «заставить» компрессор, не использовавший контекстной информации вовсе, всегда использовать наилучший возможный контекст. | ||
Классические алгоритмы Хаффмана и арифметического кодирования [1] могут служить примерами ''статистических'' алгоритмов сжатия, обычно кодирующих входной символ в соответствии с ''общей'' частотой его вхождения в данных, подлежащих сжатию. [''Динамические версии этих алгоритмов рассматривают частоту | Классические алгоритмы Хаффмана и арифметического кодирования [1] могут служить примерами ''статистических'' алгоритмов сжатия, обычно кодирующих входной символ в соответствии с ''общей'' частотой его вхождения в данных, подлежащих сжатию. [''Динамические версии этих алгоритмов рассматривают частоту вхождения символа в уже просканированной порции входных данных''.] Этот подход эффективен и прост в реализации, однако обеспечивает невысокий уровень сжатия. Эффективность работы статистических алгоритмов сжатия можно повысить за счет использования моделей ''более высокого порядка'', получающих более качественную оценку частоты встречаемости входных символов. Алгоритм сжатия PPM [9] реализует эту идею путем сбора данных о частоте вхождения всех символов, попадающих в ''любой'' контекст длины k, и сжатия их при помощи арифметического кодирования. Длина контекста k представляет собой параметр алгоритма, который определяется подлежащими сжатию данными: он будет разным при сжатии текста на английском языке, последовательности ДНК или документа в формате XML. Можно привести и другие примеры сложных программ сжатия, таких как алгоритмы Лемпеля-Зива и [[Преобразование Барроуза-Уилера|Барроуза-Уилера]] [9], использующих информацию о контексте ''неявным'' образом. Все эти алгоритмы, учитывающие контекст, обеспечивают высокую эффективность работы, однако обычно сложны для реализации и анализа. | ||
Строка 18: | Строка 18: | ||
В следующих разделах будет | В следующих разделах будет приведено точное формальное обоснование перечисленных характеристик. | ||
== Основные результаты == | == Основные результаты == | ||
Строка 35: | Строка 35: | ||
Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для <math>s = a^n \;</math> имеет место <math>|s| \; H_k(s) = 0</math> для любого <math>k \ge 0 \;</math>. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [7] было введено понятие ''модифицированной эмпирической энтропии нулевого порядка'' <math>H_0^*(s) \;</math>, имеющей следующее свойство: <math>|s| \; H^*_0(s)</math> по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. ''Модифицированная эмпирическая энтропия k-го порядка'' <math>H^*_k \;</math> определяется как максимальная степень сжатия, которой можно достичь при просмотре ''не более чем'' k символов, следующих за кодируемым. | Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для <math>s = a^n \;</math> имеет место <math>|s| \; H_k(s) = 0</math> для любого <math>k \ge 0 \;</math>. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [7] было введено понятие ''модифицированной эмпирической энтропии нулевого порядка'' <math>H_0^*(s) \;</math>, имеющей следующее свойство: <math>|s| \; H^*_0(s)</math> по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. ''Модифицированная эмпирическая энтропия k-го порядка'' <math>H^*_k \;</math> определяется через <math>H^*_0 \;</math> как максимальная степень сжатия, которой можно достичь при просмотре ''не более чем'' k символов, следующих за кодируемым. | ||
== Преобразование Барроуза-Уилера == | == Преобразование Барроуза-Уилера == | ||
Строка 42: | Строка 42: | ||
(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | (1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | ||
(2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат | (2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат циклические сдвиги строки s$, отсортированные в лексикографическом порядке; | ||
(3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1). | (3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1). | ||
Строка 50: | Строка 50: | ||
Чтобы убедиться в мощи преобразования bwt, рассмотрим ситуацию с точки зрения эмпирической энтропии. Зафиксируем целое положительное число k. Первые k столбцов матрицы bwt содержат все подстроки s длины k, лексикографически упорядоченные (а также k подстрок, содержащих символ $). Для любой подстроки w строки s | Чтобы убедиться в мощи преобразования bwt, рассмотрим ситуацию с точки зрения эмпирической энтропии. Зафиксируем целое положительное число k. Первые k столбцов матрицы bwt содержат все подстроки s длины k, лексикографически упорядоченные (а также k подстрок, содержащих символ $). Для любой подстроки w строки s длиной k символы, непосредственно предшествующие каждому вхождению w в s, сгруппированы вместе в множество последовательных позиций в <math>\hat{s} \;</math>, поскольку они являются последними символами строк матрицы <math>\mathcal{M} \;</math>, которым предшествуют символы w. Используя нотацию, предложенную при определении <math>H_k \;</math>, можно переформулировать это свойство так, чтобы символы <math>w_s \;</math> были последовательными в <math>\hat{s} \;</math> или, что эквивалентно, чтобы <math>\hat{s} \;</math> содержало в качестве подстроки перестановку <math>\pi_w (w_s) \;</math> строки <math>w_s \;</math>. | ||
Строка 59: | Строка 59: | ||
Согласно (1), отсюда следует <math>\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>|s| H_k (s) \;</math> достаточно сжать каждую | Следовательно, для сжатия строки s вплоть до <math>|s| H_k (s) \;</math> достаточно сжать каждую подстроку <math>\pi_w (w_s)) \;</math> вплоть до эмпирической энтропии нулевого порядка. Заметим, однако, что при использовании вышеприведенной схемы параметр k необходимо выбрать заранее. Более того, подобную схему нельзя применить к <math>H^*_k \;</math>, определенной в терминах контекстов длины ''не более'' k. В результате на данный момент не известно эффективной процедуры для вычисления разбиения <math>\hat{s} \;</math> согласно <math>H^*_k(s) \;</math>. Усилитель сжатия [3] представляет собой естественное дополнение bwt и позволяет сжимать любую строку s до <math>H_k(s) \;</math> (или <math>H^*_k(s) \;</math>) одновременно для всех <math>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). На | Важнейшим компонентом алгоритма усиления степени сжатия является взаимосвязь между матрицей bwt и такой структурой данных, как [[суффиксное дерево]]. Обозначим за <math>\mathcal{T} \;</math> суффиксное дерево строки s$. У <math>\mathcal{T} \;</math> имеется |s| + 1 листьев, по одному на суффикс s$, а его ребра помечены подстроками s$ (см. рис. 1). Любая вершина u дерева <math>\mathcal{T} \;</math> ''неявно ассоциируется'' с подстрокой s$, задаваемой конкатенацией меток ребер на нисходящем пути от корня <math>\mathcal{T} \;</math> к u. В рамках этой неявной ассоциации листья <math>\mathcal{T} \;</math> соответствуют суффиксам s$. Предположим, что ребра суффиксного дерева лексикографически отсортированы. Поскольку каждая строка матрицы bwt имеет префикс в виде суффикса s$, а строки лексикографически отсортированы, i-й лист суффиксного дерева (считая справа налево) соответствует i-й строке матрицы bwt. Ассоциируем с i-м листом <math>\mathcal{T} \;</math> i-й символ <math>\hat{s} = bwt(s) \;</math>. На рисунке эти символы представлены внутри кружков. | ||
Для любой вершины суффиксного дерева u обозначим за s | Для любой вершины суффиксного дерева u обозначим за <math>\hat{s}\langle u \rangle \;</math> подстроку <math>\hat{s} \;</math>, полученную в результате конкатенации, слева направо, символов, ассоциированных с листьями, являющимися потомками вершины u. Разумеется, <math>\hat{s} \langle root( \mathcal{T} ) \rangle = \hat{s} \;</math>. Подмножество <math>\mathcal{L} \;</math> вершин <math>\mathcal{T} \;</math> называется ''листовым покрытием'', если каждый лист суффиксного дерева имеет ''уникального'' предка в <math>\mathcal{L} \;</math>. Любое листовое покрытие <math>\mathcal{L} = \{ u_1, ..., u_p \} \;</math> естественным образом порождает разбиение листьев <math>\mathcal{T} \;</math>. В силу взаимосвязи между <math>\mathcal{T} \;</math> и матрицей bwt оно также является разбиением <math>\hat{s} \;</math>, а именно – <math>\{ \hat{s} \langle u_1 \rangle , ..., \hat{s} \langle u_p \rangle \} \;</math>. | ||
'''Пример 3.''' Рассмотрим суффиксное дерево на | '''Пример 3.''' Рассмотрим суффиксное дерево на рисунке. Листовое покрытие состоит из всех вершин, имеющих глубину 1. Разбиение <math>\hat{s}\;</math>, порожденное этим листовым покрытием, выглядит как {i, pssm, $; pi, ssii}. | ||
[[Файл:BTC_1.png]] | |||
Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е. <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>. | |||
Обозначим за C функцию, которая ассоциирует с каждой строкой x над <math>\Sigma \cup \{ $ \} \;</math> положительное вещественное значение C(x). Для любого листового покрытия <math>\mathcal{L} \;</math> определим его стоимость как <math>C(\mathcal{L}) = \sum_{u \in \mathcal{L}} C( \hat{s} \langle u \rangle) \;</math>. Иными словами, стоимость листового покрытия <math>\mathcal{L} \;</math> равна сумме стоимостей строк в разбиении, порожденном <math>\mathcal{L} \;</math>. Листовое покрытие <math>\mathcal{L}_{min} \;</math> называется ''оптимальным'' относительно C, если <math>C(\mathcal{L}_{min}) \le C(\mathcal{L}) \;</math> для любого листового покрытия <math>\mathcal{L} \;</math>. | |||
Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен | |||
Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит, где <math>\eta \;</math> и <math>\mu \;</math> – константы. Определим функцию стоимости <math>C_A(x) = |x| H_0 (x) + \eta |x| + \mu \;</math>. В работе [3] Ферраджина и коллеги используют жадный алгоритм с линейным временем выполнения, вычисляющий оптимальное листовое покрытие <math>\mathcal{L}_{min} \;</math> относительно <math>C_A \;</math>. Авторы работы [3] также показали, что для любого <math>k \ge 0 \;</math> существует листовое покрытие <math>\mathcal{L}_k \;</math> стоимостью <math>C_A(\mathcal{L}_k) = |s| H_k(s) + \eta |s| + O(|\Sigma|^k) \;</math>. Эти два важнейших наблюдения показывают, что при использовании A для сжатия каждой подстроки в разбиении, порожденном оптимальным листовым покрытием <math>\mathcal{L}_{min} \;</math>, общий размер выходного значения ограничен в терминах <math>|s| H_k(s) \;</math> для любого <math>k \ge 0 \;</math>. На деле <math>\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 состоит из трех основных этапов: | Суммируя все вышесказанное, усиление алгоритма сжатия A над строкой s состоит из трех основных этапов: | ||
1. Вычислить | 1. Вычислить <math>\hat{s} = bwt(s) \;</math>; | ||
2. Вычислить оптимальное листовое покрытие | 2. Вычислить оптимальное листовое покрытие <math>\mathcal{L}_{min} \;</math> относительно <math>C_A \;</math> и разбиение <math>\hat{s} \;</math>, соответствующее <math>\mathcal{L}_{min} \;</math>; | ||
3. Сжать каждую подстроку разбиения при помощи алгоритма A. | 3. Сжать каждую подстроку разбиения при помощи алгоритма A. | ||
Таким образом, парадигма усиления сводит разработку эффективных алгоритмов сжатия, использующих информацию контексте, к (обычно более простой) разработке алгоритмов сжатия нулевого порядка. Эффективность этой парадигмы описывается следующей теоремой. | Таким образом, парадигма усиления сводит разработку эффективных алгоритмов сжатия, использующих информацию о контексте, к (обычно более простой) разработке алгоритмов сжатия нулевого порядка. Эффективность этой парадигмы описывается следующей теоремой. | ||
Теорема 1 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более | '''Теорема 1 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит. Механизм усиления степени сжатия, примененный к A, дает выходное значение, размер которого ограничен <math>|s| H_k(s) + log |s| + \eta |s| + O(|\Sigma|^k) \;</math> бит одновременно для всех <math>k \ge 0 \;</math>. Учитывая A, механизм усиления привносит в процесс сжатия дополнительные накладные расходы на память в размере O(|s| log |s|) бит, но не вносит дополнительных асимптотических затрат времени.''' | ||
Аналогичный результат имеет место и для модифицированной энтропии <math>H^*_k \;</math> (однако доказать его намного сложнее): пусть дан алгоритм сжатия A, который сжимает любую строку x до не более чем <math>\lambda |x| \; H^*_0 (x) + \mu</math> бит. Механизм усиления степени сжатия дает выходное значение, размер которого ограничен <math>\lambda |s| \; H^*_k(s) + log |s| + O(|\Sigma|^k)</math> бит одновременно для всех <math>k \ge 0 \;</math>. В работе [3] авторы также показали, что ни один алгоритм сжатия, удовлетворяющий некоторым мягким предположениям относительно его внутренних принципов работы, не способен получить схожую границу, не включающую одновременно мультипликативный коэффициент <math>\lambda \;</math> и аддитивный логарифмический терм. Кроме того, в [3] была предложена конкретизация усилителя, которая сжимает любую строку s до не более чем <math>2,5 |s| \; H^*_k(s) +log |s| + O(|\Sigma|^k)</math> бит. Эта граница аналитически превосходит границы, доказанные для лучших существующих алгоритмов сжатия, включая алгоритмы Лемпеля-Зива и [[преобразование Барроуза-Уилера|Барроуза-Уилера]] и алгоритм PPM. | |||
Аналогичный результат имеет место и для модифицированной энтропии (однако доказать его намного сложнее): пусть дан алгоритм сжатия A, который сжимает любую строку x до не более чем | |||
== Применение == | == Применение == | ||
Строка 109: | Строка 106: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Парадигму усиления можно обобщить следующим образом. Пусть дан алгоритм компрессии A; необходимо найти перестановку P для символов строки s и стратегию разбиения, такие, чтобы примененный к ним подход к усилению минимизировал размер выходных данных. Выше были приведены убедительные свидетельства того, что преобразование Барроуза-Уилера является элегантной и эффективной перестановкой P. Как ни удивительно, другие классические задачи сжатия данных также вписываются в эту структуру: поиск кратчайшей общей надстроки (эта задача является MAX-SNP-сложной), кодирование с переменной длиной строки для множества строк (полиномиально разрешимая задача), LZ77 и нахождение минимального количества фраз (также MAX-SNP-сложная). Таким образом, подход к усилению является достаточно общим, чтобы заслуживать дальнейших теоретических и практических исследований [5]. | Парадигму усиления можно обобщить следующим образом. Пусть дан алгоритм компрессии A; необходимо найти и перестановку <math>\mathcal{P} \;</math> для символов строки s, и стратегию разбиения, такие, чтобы примененный к ним подход к усилению минимизировал размер выходных данных. Выше были приведены убедительные свидетельства того, что преобразование Барроуза-Уилера является элегантной и эффективной перестановкой <math>\mathcal{P} \;</math>. Как ни удивительно, другие классические задачи сжатия данных также вписываются в эту структуру: поиск кратчайшей общей надстроки (эта задача является MAX-SNP-сложной), кодирование с переменной длиной строки для множества строк (полиномиально разрешимая задача), LZ77 и нахождение минимального количества фраз (также MAX-SNP-сложная). Таким образом, подход к усилению является достаточно общим, чтобы заслуживать дальнейших теоретических и практических исследований [5]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Исследование нескольких алгоритмов сжатия, основанных на усилении, и сравнение их с другими современными способами сжатия приведено в работе [ ]. Эксперименты показывают, что техника усиления является более надежной по сравнению с другими подходами и хорошо работает даже с менее эффективными алгоритмами сжатия нулевого порядка. Однако положительные результаты достигаются за счет использования большего количества ресурсов (времени и памяти). | Исследование нескольких алгоритмов сжатия, основанных на усилении, и сравнение их с другими современными способами сжатия приведено в работе [4]. Эксперименты показывают, что техника усиления является более надежной по сравнению с другими подходами на базе алгоритма bwt и хорошо работает даже с менее эффективными алгоритмами сжатия нулевого порядка. Однако положительные результаты достигаются за счет использования большего количества ресурсов (времени и памяти). | ||
== Наборы данных == | == Наборы данных == | ||
Наборы данных, использовавшиеся в [ ], доступны по адресу http://www.mfn.unipmn.it/~manzini/boosting. Другие наборы данных для сжатия и индексирования можно найти на сайте Pizza&Chili http://pizzachili.di.unipi.it/. | Наборы данных, использовавшиеся в [4], доступны по адресу http://www.mfn.unipmn.it/~manzini/boosting. Другие наборы данных для сжатия и индексирования можно найти на сайте Pizza&Chili http://pizzachili.di.unipi.it/. | ||
== Ссылка на код == | == Ссылка на код == | ||
Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn.unipmn.it/~manzini/boosting) содержит исходный код всех алгоритмов, протестированных в [ ]. Этот код организован в виде библиотеки с высокой степенью модульности, которая может использоваться любым алгоритмом сжатия и не требует знания алгоритма bwt или процедуры усиления. | Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn.unipmn.it/~manzini/boosting) содержит исходный код всех алгоритмов, протестированных в [4]. Этот код организован в виде библиотеки с высокой степенью модульности, которая может использоваться любым алгоритмом сжатия и не требует знания алгоритма bwt или процедуры усиления. | ||
== См. также == | == См. также == |
правок