|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 21 May 2001 22:04:23
To : All
Subject : Re: Поиск набора слов в тексте с помощью конечных автоматов
--------------------------------------------------------------------------------
Ihor Bobak wrote:
>
> дано набор слов (словарь) P1, P2, ... PN (N<=200, |Pi|<=20) и
> длинный текст T (|T|<=2000000). Для каждого слова из словаря
> нужно найти количество вхождений в текст.
>
> По коду суддейского (эталонного) решения видно, что строится
> автомат, а потом посимвольно читается текст и обрабатывается
> этим автоматом. Hо из-за сложности кода я не могу понять принцип
> построения такого автомата.
Hе факт, что у него был именно автомат. С той же производительностью
можно использовать дерево цифрового поиска "trie", описанное в
3-м томе Кнута. В принципе, можно сказать, что TRIE от конечного
автомата отличается только тем, что в дереве есть терминальные
узлы - листься, тогда как в автомате из этих терминалюных
узлов стоят связи на ROOT - то есть КА можно рассматривать как
закольцованное TRIE.
>
> Кто-нибудь знает алгоритм построения конечного автомата для
> этой задачи?
Hу если все же упереться в КА, есть 3 способа построить такую
байду:
1. По набору слов статически ручками прописать автомат и
интерпретатор дла него.
2. Воспользоваться программой LEX, которая тебе по набору слов
построит автомат и интерпретатор.
3. Динамически создавать TRIE в памяти, а потом закольцевать его.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Поиск набора слов в тексте с помощью конечных автоматов 
