4551
правка
Сравнение с шаблоном для сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 13:35, 5 ноября 2021
, 5 ноября 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
Системы коллажей – это полезные 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]. | Системы коллажей – это полезные 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> – любой из форм: | ||
a для a | <math>a</math> для <math>a \in \Sigma \cup \{ \epsilon \}</math> (примитивное присваивание) | ||
<math>X_i X_j</math> для i,j< k (конкатенация) | |||
[j]Xi для i < k и целого положительного числа j ; (усечение префикса длины j) | [j]Xi для i < k и целого положительного числа j ; (усечение префикса длины j) | ||