Re: Обратная задача: поиск в таблице паттернов

From

Sergei Emantayev ()

To

Vladimir A. Pertzel

Date

2002-06-30T13:40:27Z

Area

RU.ALGORITHMS

From: Sergei Emantayev <sergeie@ectel.com>


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>> на вход приходит некоторый текст. Нужно найти
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> сравнение.

Нет, к сожалению. Таблица приходит в ран-тайме.

VA> Сложнее обстоит дело, если таблица слов поступает
VA> во время выполнения программы. Тогда конечный
VA> автомат
VA> придется строить вручную. Можно, конечно,
VA> поковыряться
VA> в коде flex-а и сделать то же, но с листа
VA> написать
VA> быстрее. Ключевые слова и выражения: "Regular
VA> expression"
VA> "Deterministic finite automaton"
VA> "Non-deterministic finite
VA> automaton"

Написать автомат - нет проблем. Но боюсь я его использовать,
потому как полученная таблица будет совершенно невообразимых 
размеров, т.к. в исходной таблице может быть несколько тысяч
слов, а то и больше.

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)