4446
правок
Сравнение с шаблоном для сжатого текста: различия между версиями
Материал из WEGA
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 21:09, 5 ноября 2021
, 5 ноября 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть имеются <math>\mathbf{c}</math> – заданный алгоритм сжатия, <math>\mathbf{c}</math>(A) – результат сжатия строки A; даны строка шаблонов P и сжатый текст <math>\mathbf{c}</math>(T). Задача ''сравнения с шаблоном для сжатого текста'' (compressed pattern matching, CPM) заключается в поиске всех вхождений P в T без распаковки T. Целью является выполнение задачи за меньшее время по сравнению с распаковкой и последующим простым поиском, | Пусть имеются <math>\mathbf{c}</math> – заданный алгоритм сжатия, <math>\mathbf{c}</math>(A) – результат сжатия этим алгоритмом строки A; даны строка шаблонов P и сжатый текст <math>\mathbf{c}</math>(T). Задача ''сравнения с шаблоном для сжатого текста'' (compressed pattern matching, CPM) заключается в поиске всех вхождений P в T без распаковки T. Целью является выполнение задачи за меньшее время по сравнению с распаковкой и последующим простым поиском, которым требуется O(|P| + |T|) времени (предполагая, что для распаковки достаточно O(|T|) времени). Алгоритм CPM называется ''оптимальным'', если он выполняется за время O(|P| + |<math>\mathbf{c}</math>(T)|). Задача CPM была впервые определена в работе Амира и Бенсона [1]; было выполнено множество исследований различных форматов сжатия. | ||
| Строка 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> | ''Система коллажей'' представляет собой пару <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>a</math> для <math>a \in \Sigma \cup \{ \epsilon \}</math> (примитивное присваивание) | <math>a</math> для <math>a \in \Sigma \cup \{ \epsilon \}</math> (примитивное присваивание) | ||
