ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Novikov                       2:5020/400     27 Jun 2002  08:53:50
 To : All
 Subject : Pattern matching
 -------------------------------------------------------------------------------- 
 

 
   Привет.
 
  Hеобходим алгоритм для замены (для начала, поиска) подстроки в
 строке. Строка берется из файла и может быть достаточно большой
 (200К). Образец имеет вид %%имя%%, например,
 %%link%% заменяется на <A href="http://www.mysite.com/myprog.cgi">
 %%email%%          --> <A href="mailto:support@mysite.com">
 %%very_long_link%% --> <H1>Что-то там еще</H1>
  итд.
 
  Hаиболее критична скорость.
 
  Классическим решением будет алгоритм Бойера-Мура. Он будет
 великолепно работать если образец только один. В общем случае его
 сложность увеличивается в k раз, где k - количество определенных
 тегов. Это не считая того, что промежуточный вариант надо где-то
 складывать.
 
  Альтернативный вариант - алгоритм Карпа-Рабина. Берем, например,
 длину наименьшего тега (мин. 5 символов) и по нему считаем k хешей.
 Hа каждой итерации сравниваем целые числа k раз. В среднем должно
 выходить неплохо.
 
  Можно попробовать его оптимизировать например так: взять два символа
 %% и проходить по исходной строке методом БМ. Если совпало на символе
 i, то хеши вычисляем для подстроки [i+1; i+6] (6 - для примера выше).
 
  И все-таки, проходить всю строку даже через два символа - O(n) при
 том, что для длинных строк у БМ - O(n/m)!
 
  Слышал, что существует много модификаций алгоритма БМ. Мне кажется,
 если образец длинный, он должен работать быстрее, чем для двух
 символов. Может у кого-то есть идеи насчет того как решить задачу
 наилучшим образом?
 
  Может, есть еще более быстрое решение (нечеткий поиск итд)?
 
  Andrew
 --- ifmail v.2.15dev5
  * Origin: Unknown (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Pattern matching   Andrew Novikov   27 Jun 2002 08:53:50   Re: Pattern matching   Nick Kovaliov   27 Jun 2002 14:54:20