4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 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 не являются свободными от усечений. | ||
== Основные результаты == | == Основные результаты == | ||
Строка 70: | Строка 70: | ||
Алгоритм [9] состоит из двух этапов. Вначале производится предварительная обработка <math>\mathcal{D}</math> и P, а затем – обработка переменных <math>\mathcal{S}</math>. На втором этапе имитируется перемещение автомата KMP, работающего на несжатом тексте, с помощью двух функций <math>Jump</math> и <math>Output</math>. Обе эти функции принимают на вход состояние q и переменную X. Первое используется для замены только одного перехода состояния на последовательные переходы | Алгоритм [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> опускается. | ||
правок