Pattern matching

From

Andrew Novikov ()

To

All

Date

2002-06-27T08:53:50Z

Area

RU.ALGORITHMS

From: "Andrew Novikov" <programmer@send-e.net>


  Привет.

 Необходим алгоритм для замены (для начала, поиска) подстроки в
строке. Строка берется из файла и может быть достаточно большой
(200К). Образец имеет вид %%имя%%, например,
%%link%% заменяется на <A href="http://www.mysite.com/myprog.cgi">
%%email%%          --> <A href="mailto:support@mysite.com">
%%very_long_link%% --> <H1>Что-то там еще</H1>
 итд.

 Наиболее критична скорость.

 Классическим решением будет алгоритм Бойера-Мура. Он будет
великолепно работать если образец только один. В общем случае его
сложность увеличивается в k раз, где k - количество определенных
тегов. Это не считая того, что промежуточный вариант надо где-то
складывать.

 Альтернативный вариант - алгоритм Карпа-Рабина. Берем, например,
длину наименьшего тега (мин. 5 символов) и по нему считаем k хешей.
На каждой итерации сравниваем целые числа k раз. В среднем должно
выходить неплохо.

 Можно попробовать его оптимизировать например так: взять два символа
%% и проходить по исходной строке методом БМ. Если совпало на символе
i, то хеши вычисляем для подстроки [i+1; i+6] (6 - для примера выше).

 И все-таки, проходить всю строку даже через два символа - O(n) при
том, что для длинных строк у БМ - O(n/m)!

 Слышал, что существует много модификаций алгоритма БМ. Мне кажется,
если образец длинный, он должен работать быстрее, чем для двух
символов. Может у кого-то есть идеи насчет того как решить задачу
наилучшим образом?

 Может, есть еще более быстрое решение (нечеткий поиск итд)?

 Andrew


--- ifmail v.2.15dev5
 * Origin: Unknown (2:5020/400)