4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 8: | Строка 8: | ||
'''Системы коллажей''' | '''Системы коллажей''' | ||
Системы коллажей – это полезные CPM-ориентированные абстракции форматов сжатия, предложенные Кидой и коллегами [9]. Алгоритмы, разработанные для систем коллажей, можно применить для множества различных форматов сжатия. В той же статье был представлен общий | Системы коллажей – это полезные CPM-ориентированные абстракции форматов сжатия, предложенные Кидой и коллегами [9]. Алгоритмы, разработанные для систем коллажей, можно применить для множества различных форматов сжатия. В той же статье был представлен общий [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BD%D1%83%D1%82%D0%B0_%E2%80%94_%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0_%E2%80%94_%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0 алгоритм Кнута-Морриса-Пратта (KMP)] для систем коллажей. Использование общего [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0 алгоритма Бойера-Мура (BM)] для систем коллажей было предложено почти той же группой авторов [18]. | ||
''Система коллажей'' представляет собой пару <math>\langle \mathcal{D}, \mathcal{S} \rangle</math>, определенную следующим образом. <math>\mathcal{D}</math> - это последовательность присваиваний <math>X_1 = expr_1, X_2 = expr_2, ..., X_n = expr_n</math>, где для каждого k = 1,..., n элемент <math>X_k</math> является переменной, а <math>expr_k</math> имеет любую из следующих форм: | ''Система коллажей'' представляет собой пару <math>\langle \mathcal{D}, \mathcal{S} \rangle</math>, определенную следующим образом. <math>\mathcal{D}</math> - это последовательность присваиваний <math>X_1 = expr_1, X_2 = expr_2, ..., X_n = expr_n</math>, где для каждого k = 1,..., n элемент <math>X_k</math> является переменной, а <math>expr_k</math> имеет любую из следующих форм: | ||
Строка 34: | Строка 34: | ||
Система коллажей называется ''свободной от усечений'', если <math>\mathcal{D}</math> не содержит операций усечения, и ''регулярной'', если <math>\mathcal{D}</math> не содержит ни повторений, ни операций усечения. Регулярная система коллажей является ''простой'', если <math>| \bar{Y} | = 1</math> или <math>| \bar{Z} | = 1</math> для каждого присваивания X = YZ. На рис. 1 представлена иерархия систем коллажей. Системы коллажей для RE-PAIR, SEQUITUR, Byte-Pair-Encoding (BPE) и схемы сжатия на основе | Система коллажей называется ''свободной от усечений'', если <math>\mathcal{D}</math> не содержит операций усечения, и ''регулярной'', если <math>\mathcal{D}</math> не содержит ни повторений, ни операций усечения. Регулярная система коллажей является ''простой'', если <math>| \bar{Y} | = 1</math> или <math>| \bar{Z} | = 1</math> для каждого присваивания X = YZ. На рис. 1 представлена иерархия систем коллажей. Системы коллажей для RE-PAIR, SEQUITUR, Byte-Pair-Encoding (BPE) и схемы сжатия на основе преобразования грамматики являются регулярными. В семействе Лемпеля-Зива системы коллажей для LZ78/LZW просты, а системы для LZ77/LZSS не являются свободными от усечений. | ||
== Основные результаты == | == Основные результаты == | ||
Строка 49: | Строка 49: | ||
Расширение [2] до задачи сравнения с несколькими шаблонами (сравнение со словарем) было предложено Кидой и коллегами в работе [10] | Расширение [2] до задачи сравнения с несколькими шаблонами (сравнение со словарем) было предложено Кидой и коллегами в работе [10] вместе с первыми экспериментальными результатами в этой области. | ||
Для схемы сжатия LZ77 Фарах и Торуп [6] представили следующий результат. | Для схемы сжатия LZ77 Фарах и Торуп [6] представили следующий результат. | ||
'''Теорема 3 (Фарах | '''Теорема 3 (Фарах, Торуп [6]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время <math>O(|Z| log^2 (|T|/|Z|) + |P|)</math>.''' | ||
Строка 59: | Строка 61: | ||
'''Теорема 4 ([Гасинец и др. [7], Риттер [16]). Факторизация Лемпеля-Зива Z по T может быть преобразована в систему коллажей размера <math>O(|Z| \cdot log|Z|)</math>, порождающую T за время <math>O(|Z| \cdot log |Z|)</math>, и в | '''Теорема 4 ([Гасинец и др. [7], Риттер [16]). Факторизация Лемпеля-Зива Z по T может быть преобразована в систему коллажей размера <math>O(|Z| \cdot log|Z|)</math>, порождающую T за время <math>O(|Z| \cdot log |Z|)</math>, и в регулярную систему коллажей размера <math>O(|Z| \cdot log |T|)</math>, порождающую T за время <math>O(|Z| \cdot log |T|)</math>.''' | ||
Строка 65: | Строка 67: | ||
'''Теорема 5 (Кида и др. [9]). Задача CPM для систем коллажей может быть решена за время <math>O((|\mathcal{D}| + |\mathcal{S}|) \cdot height(\mathcal{D})+|P|^2+occ)</math> с использованием <math>O(|\mathcal{D}| + |P|^2)</math> памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент <math>height(\mathcal{D})</math> опускается.''' | '''Теорема 5 (Кида и др. [9]). Задача CPM для систем коллажей может быть решена за время <math>O((|\mathcal{D}| + |\mathcal{S}|) \cdot height(\mathcal{D})+|P|^2+occ)</math> с использованием <math>O(|\mathcal{D}| + |P|^2)</math> памяти, где <math>occ</math> – количество вхождений шаблона. Для систем коллажей без усечений коэффициент <math>height(\mathcal{D})</math> опускается.''' | ||
Алгоритм [9] состоит из двух этапов. | Алгоритм [9] состоит из двух этапов. Вначале производится предварительная обработка <math>\mathcal{D}</math> и P, а затем – обработка переменных <math>\mathcal{S}</math>. На втором этапе имитируется перемещение автомата KMP, работающего на несжатом тексте, с помощью двух функций <math>Jump</math> и <math>Output</math>. Обе эти функции принимают на вход состояние q и переменную X. Первое используется для замены только одного перехода состояния на последовательные переходы состояний автомата KMP для строки <math>\bar{X}</math> для каждой переменной X из S; вторая – для сообщения обо всех вхождениях шаблона, найденных в процессе переходов состояний. Пусть <math>\delta</math> – функция перехода состояний KMP-автомата. Тогда <math>Jump(q, X) = \delta(q, \bar{X})</math>, а <math>Output(q, X)</math> – множество длин |w| непустых префиксов w из <math>\bar{X}</math>, таких, что <math>\delta(q, w)</math> является конечным состоянием. Наивная реализация этих двух функций в виде двумерного массива требует памяти объемом <math>\Omega(|\mathcal{D}| \cdot |P|)</math>. Структуры данных из [9] используют только <math>O(|\mathcal{D}| + |P|^2)</math> памяти, строятся за время <math>O(|\mathcal{D}| \cdot height(\mathcal{D}) + |P|^2)</math> и позволяют вычислить <math>Jump(q, X)</math> за время O(1) и перенумеровать множество <math>Output(q, X)</math> за время <math>O(height(\mathcal{D}) + \ell)</math>, где <math>\ell = |Output(q, X)|</math>. Для систем коллажей без усечений коэффициент <math>height(\mathcal{D})</math> опускается. | ||
Другой критерий алгоритмов CPM основывается на объеме дополнительной памяти [4]. Алгоритм CPM является | Другой критерий алгоритмов CPM основывается на объеме дополнительной памяти [4]. Алгоритм CPM является [https://en.wikipedia.org/wiki/In-place_algorithm алгоритмом типа inplace (англ.)], если объем дополнительной памяти пропорционален размеру входных данных P. | ||
Строка 77: | Строка 79: | ||
Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. ''Алгоритм сравнения с шаблоном для полностью сжатого текста'' (Fully-compressed pattern matching, FCPM) – это сложный вариант, | Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. | ||
''Алгоритм сравнения с шаблоном для полностью сжатого текста'' (Fully-compressed pattern matching, FCPM) – это сложный вариант, в котором и T, и P даны в сжатом формате. Прямолинейная программа представляет собой регулярную систему коллажей с <math>|\mathcal{S}| = 1</math>. | |||
Строка 86: | Строка 90: | ||
'''Теорема 8 (Карккайнен и др. [8]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время <math>O(k \cdot |P| \cdot |\mathbf{c}(T)| + occ)</math> для LZ78/LZW и за время <math>O(|P| \cdot (k^2 \cdot |\mathcal{D}| + k \cdot |\mathcal{S}|) + occ)</math> для | '''Теорема 8 (Карккайнен и др. [8]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время <math>O(k \cdot |P| \cdot |\mathbf{c}(T)| + occ)</math> для LZ78/LZW и за время <math>O(|P| \cdot (k^2 \cdot |\mathcal{D}| + k \cdot |\mathcal{S}|) + occ)</math> для регулярных систем коллажей, где k – заданный порог ошибки.''' | ||
Строка 95: | Строка 99: | ||
'''Теорема 10 (Наварро [14]). Задача RCPM решается за время <math>O(2^{|P|} + |P| \cdot |\mathbf{c}(T)| + occ \cdot |P| \cdot log |P|)</math>, где occ – количество вхождений P в T.''' | '''Теорема 10 (Наварро [14]). Задача RCPM решается за время <math>O(2^{|P|} + |P| \cdot |\mathbf{c}(T)| + occ \cdot |P| \cdot log |P|)</math>, где <math>occ</math> – количество вхождений P в T.''' | ||
== Применение == | == Применение == | ||
Строка 101: | Строка 105: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Одной из важных целей задачи CPM является получение результата за более короткое время по сравнению с распаковкой и последующим простым поиском. Кида и др. [10] экспериментально показали, что их алгоритмы достигают этой цели. Наварро и Тархио [15] представили алгоритмы типа BM (Бойера-Мура) для схем сжатия LZ78/LZW и показали, что они работают в два раза быстрее, чем декомпрессия с последующим поиском с использованием лучших алгоритмов. (Код доступен по адресу www.dcc.uchile.cl/gnavarro/software). | Одной из важных целей задачи CPM является получение результата за более короткое время по сравнению с распаковкой и последующим простым поиском. Кида и др. [10] экспериментально показали, что их алгоритмы достигают этой цели. Наварро и Тархио [15] представили алгоритмы типа BM (Бойера-Мура) для схем сжатия LZ78/LZW и показали, что они работают в два раза быстрее, чем декомпрессия с последующим поиском с использованием лучших алгоритмов. (Код доступен по адресу http://www.dcc.uchile.cl/gnavarro/software). | ||
правок