 |
Личные заметки на Zaharov.info / Естествознание / Алгоритм поиска фразы в тексте по словарю |
| Автор | Сообщение |
|
dimedrol
Администратор |
# Дата: 21 Сен 2007 04:21
Ответить Для этого нужно построить инверсное множество по словарю. Для каждого слова — список номеров документов номеров слов в документе. При поиске для фразы для каждого слова вытаскиваем вышеуказанные списки. Далее сливаем эти списки в один чтобы разница в координатах меджу идущими подряд словами фразы была равна 1. Так как словарь обычно большой, от миллиона до десятка миллионов слов, то искать по нему лучше бинарным поиском, а не строить огромный хэш. Итого время поиска будет = ln(Размер Словаря) + Количество упоминаний слова 1 + Количество упоминаний слова 2 + ... + Количество упоминаний слова n. И это в самом худшем случае (фраза встретилась в каждом документе). На практике время поиска фразы в среднем составляет ln(Размер Словаря) + ln(Количество упоминаний слова 1) + ln(Количество упоминаний слова 2) + ... + ln(Количество упоминаний слова n). |