LINUX.ORG.RU

Алгоритм поиска сразу кучи подстрок в потоке.

 


1

3

Понимаю как это реализуется - сначала по куче искомых строк строится конечный автомат с множеством одновременных состояний. И эти состояния потенциально сдвигаются «к успеху» на каждый входной символ или убиваются или заводятся новые «процессы прохода». Состояние (процесс), которое дошло до своего успеха сигнализирует о появлении слова (N шагов назад его начало).

Как называется это по-умному? Чё за алгоритм?

если я правильно понял, то это Ахо-Корасик.

zamazan4ik ★★ ()
Последнее исправление: zamazan4ik (всего исправлений: 1)

сначала по куче искомых строк строится конечный автомат

Называется: описываем регулярный язык, содержащий все нужные слова, регулярным выражением и преобразуем регулярное выражение в недетерминированный конечный автомат (НКА или по английски - NFA), затем используя например алгоритм Томпсона, преобразуем недетерминрованный конечный автомат в детерминированный (ДКА, англ. DFA).

Построение автмоата по регуляронму выражению - вещь элементарная. Конкатенация преобразуется в последовательное соединение автоматов, «|» преобразуются в параллельное включение автоматов. * преобразуются в цикл.

invy ★★★★★ ()
Последнее исправление: invy (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.