4551
правка
Сравнение с шаблоном для сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
м
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 21:29, 5 ноября 2021
, 5 ноября 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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) и схемы сжатия на основе грамматического преобразования являются регулярными. В семействе Лемпеля-Зива системы коллажей для LZ78/LZW просты, а системы для LZ77/LZSS не являются | Система коллажей называется ''свободной от усечений'', если <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 не являются свободными от усечений. | ||
== Основные результаты == | == Основные результаты == | ||