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

Теорема 8 (Карккайнен и др. [ ]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время O(k ■ \P\ ■ c(T)j + occ) для LZ78/LZW и за время O(\P\ ■ (k2 ■ jDj + k-\S\) + occ) для обычных систем коллажей, где k – заданный порог ошибок.

Теорема 9 (Макинен и др. [ ]). При использовании модели взвешенного расстояния редактирования задача ACPM для кодирования длин серий может быть решена за время O(\P\ ■ \c(P)\ - c(T)j).

Сравнение регулярных выражений с шаблоном для сжатого текста (Regular expression compressed pattern matching, RCPM) имеет место в случае, когда P может быть регулярным выражением.

Теорема 10 (Наварро [ ]). Задача RCPM решается за время O(2jPj + |P| - c(T)j + occ ■ \P\ ■ log jPj), где occ – количество вхождений P в T.