4551
правка
Сравнение с шаблоном для сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 18:57, 5 ноября 2021
, 5 ноября 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 72: | Строка 72: | ||
Теорема 6 (Амир и др,. [ ]). Существует CPM-алгоритм типа inplace для двумерной схемы кодирования длин серий, который работает за время O( | '''Теорема 6 (Амир и др,. [4]). Существует CPM-алгоритм типа inplace для двумерной схемы кодирования длин серий, который работает за время <math>O(|\mathbf{c} (T)| + |P| \; log \; \sigma)</math>, используя <math>O(\mathbf{c}(P))</math> дополнительной памяти, где <math>\sigma</math> – минимальное значение из |P| и размера алфавита.''' | ||
Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. Алгоритм сравнения с шаблоном для полностью сжатого текста (Fully-compressed pattern matching, FCPM) – это сложный вариант, когда и T, и P даны в сжатом формате. Прямолинейная программа представляет собой регулярную систему коллажей с | Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. ''Алгоритм сравнения с шаблоном для полностью сжатого текста'' (Fully-compressed pattern matching, FCPM) – это сложный вариант, когда и T, и P даны в сжатом формате. Прямолинейная программа представляет собой регулярную систему коллажей с <math>|\mathcal{S}| = 1</math>. | ||
Теорема 7 (Миядзаки и др. [ ]). Задача FCPM для прямолинейных программ решается за время O( | '''Теорема 7 (Миядзаки и др. [13]). Задача FCPM для прямолинейных программ решается за время <math>O(|\mathbf{c}(T)|^2 \cdot |\mathbf{c}(P)|^2)</math> с использованием <math>O(|\mathbf{c}(T)| \cdot |\mathbf{c}(P)|)</math> памяти.''' | ||
Приближенное сравнение с шаблоном для сжатого текста (Approximate compressed pattern matching, ACPM) относится к случаю, когда допускаются ошибки. | ''Приближенное сравнение с шаблоном для сжатого текста'' (Approximate compressed pattern matching, ACPM) относится к случаю, когда допускаются ошибки. | ||