Сравнение с шаблоном для сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
Система коллажей | Система коллажей <math>\langle \mathcal{D}, \mathcal{S} \rangle</math> представляет собой строку, полученную путем конкатенации строк <math>\bar{X_{i_1}}, ..., \bar{X_{j_\ell}}</math>, представленных переменными <math>X_{i_1}, ..., X_{j_\ell}</math> из <math>\mathcal{S}</math>. Следует отметить, что любая система коллажей может быть преобразована в систему с <math>|\mathcal{S}| = 1</math> путем добавления серии присваиваний с операциями конкатенации в <math>\mathcal{D}</math>. Это может означать, что <math>\mathcal{S}</math> не нужна. Однако разнообразные схемы сжатия могут быть естественным образом отражены путем разделения <math>\mathcal{D}</math> (определение ''фраз'') и <math>\mathcal{S}</math> (результатом чего является факторизация текста T на фразы). Способы выражения сжатых текстов для существующих схем сжатия можно найти в [9]. | ||
Система коллажей называется свободной от усечений, если D не содержит операций усечения, и регулярной, если D не содержит ни повторений, ни операций усечения. Регулярная система коллажей является простой, если | Система коллажей называется ''свободной от усечений'', если <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 не являются усеченными. | ||
== Основные результаты == | == Основные результаты == | ||