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