|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir A. Pertzel 2:5020/400 30 Jun 2002 12:55:44
To : All
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
"Sergei Emantayev" <sergeie@ectel.com> wrote in message
news:aaqvm4$12i$1@host.talk.ru...
>
> Теперь у меня есть обратная задача: есть таблица слов,
> на вход приходит некоторый текст. Hужно найти все слова
> из таблицы, которые находятся во входном тексте.
Я так понимаю, на вход подаются не отдельные слова,
про которые надо сказать, находятся они в таблице
или нет, а длинный непрерывный текст. (Если это не
так, то в STL смотреть описание hashed_set.)
Если таблица слов известна до компиляции,
то для *генерации* кода процедуры осуществляющей
поиск используют утилиту lex (или бесплатный вариант,
flex) http://www.combo.org/lex_yacc_page/
Он, по таблице слов строит конечный автомат, который
на вход будет получать текст, и на каждую полученную
букву делает одну выборку из массива и одно сравнение.
Сложнее обстоит дело, если таблица слов поступает
во время выполнения программы. Тогда конечный автомат
придется строить вручную. Можно, конечно, поковыряться
в коде flex-а и сделать то же, но с листа написать
быстрее. Ключевые слова и выражения: "Regular expression"
"Deterministic finite automaton" "Non-deterministic finite
automaton"
NB: one automaton -- many automata.
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Обратная задача: поиск в таблице паттернов 
