Последовательное приближенное сравнение строк: различия между версиями

Перейти к навигации Перейти к поиску
м
нет описания правки
мНет описания правки
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Пусть даны ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math> и ''строка образца'' <math>P = p_1 p_2 ... p_m</math>, представляющие собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>, а также ''функция расстояния'' между строками d и ''порог'' k. Задача ''приближенного сравнения строк'' (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое ''приблизительное вхождение'' P в T; иначе говоря, в вычислении множества <math>\{ j, \exist i, 1 \le i \le j, d(P, t_i ... t_j) \le k \}</math>. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d.
Пусть даны ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math> и ''строка шаблона'' <math>P = p_1 p_2 ... p_m</math>, представляющие собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>, а также ''функция расстояния'' между строками d и ''порог'' k. Задача ''приближенного сравнения строк'' (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое ''приблизительное вхождение'' P в T; иначе говоря, в вычислении множества <math>\{ j, \exist i, 1 \le i \le j, d(P, t_i ... t_j) \le k \}</math>. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d.




Строка 12: Строка 12:




Далее рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что образец и текст генерируются случайным образом посредством равномерного и независимого выбора из <math>\Sigma</math>. Для простоты и практичности будем далее полагать m = o(n).
Далее рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из <math>\Sigma</math>. Для простоты и практичности будем далее полагать m = o(n).


== Основные результаты ==
== Основные результаты ==
Строка 88: Строка 88:


== Экспериментальные результаты ==
== Экспериментальные результаты ==
Исчерпывающий обзор материалов по данному вопросу [11] включает множество экспериментов. На сегодняшний день самыми быстрыми алгоритмами для расстояния редактирования на практике являются алгоритмы фильтрации [6, 12] в сочетании с битово-параллельными алгоритмами для проверки областей-кандидатов [2, 10]. Эти алгоритмы фильтрации хорошо работают для достаточно малых значений k/m, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким образцам одновременно.
Исчерпывающий обзор материалов по данному вопросу [11] включает множество экспериментов. На сегодняшний день самыми быстрыми алгоритмами для расстояния редактирования на практике являются алгоритмы фильтрации [6, 12] в сочетании с битово-параллельными алгоритмами для проверки областей-кандидатов [2, 10]. Эти алгоритмы фильтрации хорошо работают для достаточно малых значений k/m, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким шаблонам одновременно.


== Ссылка на код ==
== Ссылка на код ==
4551

правка

Навигация