4551
правка
Сравнение с шаблоном для сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 15:59, 31 октября 2021
, 31 октября 2021→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сравнение строк в сжатом тексте; поиск по сжатой строке == П…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть имеются c – заданный алгоритм сжатия, c(A) – результат сжатия строки A; даны строка шаблонов P и сжатый текст c(T). Задача сравнения с шаблоном для сжатого текста (compressed pattern matching, CPM) заключается в поиске всех вхождений P в T без распаковки T. Целью является выполнение задачи за меньшее время по сравнению с распаковкой и последующим простым поиском, который требует O( | Пусть имеются <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]; было выполнено множество исследований различных форматов сжатия. | ||