Реализация алгебраических алгоритмов приближенного поиска по образцу в сжатых данных

Приближенный поиск по образцу — хорошо изученная проблема для строк: по тексту t и образцу p необходимо найти все подстроки в t, похожие по какому-то критерию на p. Мера сходства, которую мы используем в этой работе, — это длина наибольшей общей подпоследовательности (НОП) двух строк. Мы реализуем алгоритм, который решает задачу приближенного поиска по образцу для образца p длины m и текста t длины n за время O(mn), неявно сохраняя все значения НОП в алгебраической структуре размера O(m + n). Мы дополнительно обобщаем алгоритм для вычисления НОП несжатой строки-образца длины m и строки-текста длины n, сжатой контекстно-свободной грамматикой длины k за время O (mk log m). Используя то, что временная сложность этого алгоритма не зависит от длины несжатого текста, мы показываем, что алгоритм достигнет существенного ускорения для определенных типов сжатых текстов, даже с увеличением константы времени работы в результате сложных операций с алгебраическими структурами. Мы сравниваем время работы нашего алгоритма со стандартным алгоритмом динамического программирования и утилитой для приближенного поиска по образцу agrep и демонстрируем улучшение для некоторых специальных видов текстов в обоих случаях, хотя на случайных текстах наш алгоритм стандартным решениям проигрывает. Ключевые слова: строковые алгоритмы, приближенный поиск по образцу, наибольшая общая подпоследовательность, контекстно-свободные грамматики.