Аноним

Сравнение с шаблоном для сжатого текста: различия между версиями

Материал из WEGA
м
Строка 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. Целью является выполнение задачи за меньшее время по сравнению с распаковкой и последующим простым поиском, который требует O(|P| + |T|) времени (предполагая, что для распаковки достаточно O(|T|) времени). Алгоритм CPM называется оптимальным, если он выполняется за время O(|P| + |<math>\mathbf{c}</math>(T)|). CPM была впервые определена в работе Амира и Бенсона [1]; было выполнено множество исследований различных форматов сжатия.
Пусть имеются <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> (примитивное присваивание)
4551

правка