Задание следующее.
Создать информационную систему по математике. Система должна предоставлять регистрацию пользователей, удобное отображение содержания и, что главное, быстрый поиск по заданному слову или словосочетанию по имеющимся статьям.

Сами данные (статьи) хранятся как html-документы, только без начальных и конечных тегов <html></html> (то есть только содержание страницы). В код входит форматированный текст и изображения (графики, рисунки, формулы).

Регистрация и отображение - сделаю. Это как бы не проблема. Вопрос в поиске. Поиск будем выполнять только по тексту, по формулам искать не нужно. Поиск должен выполняться максимально быстро с учетом того, что система должна размещаться в интернете на сайте, и ей одновременно могут пользоваться много людей.

Пока рабочая версия такая: один раз по запросу администратора система должна выполнять индексацию. Применительно к ситуации индексация должна дать файл со списком уникальных слов во всех статьях, каждому слову должно соответствовать некоторое множество статей, в котором это слово встречается. Попутно должен быть сформирован обратный список, для каждой имеющейся статьи - список уникальных слов в ней. Это по идее позволит при редактировании статьи без полного переиндексирования производить изменения в файлах индексов. После таких преобразований можно упорядочить получившийся файл с уникальными словами по алфавиту и по запросу пользователя выполнять по этому файлу бинарный поиск (который даст максимально возможную скорость поиска). После обнаружения нужного слова (если оно вообще есть) выводить множество статей, ассоциированных с этим словом.

Это рабочая версия. В ней существует одна серьезная проблема. Что если пользователь захочет найти не слово, а словосочетание? В таком случае вся логика поиска должна работать как-то по-другому, а как именно? И возможно, вместо предложенной мной рабочей версии есть какой-то более производительный и удобный метод?

Так же, как и при поиске по одному слову. Отличие в том, что поиск(бинарный) будет выполняться столько раз по индексированному массиву слов, каждое слово которого ассоциировано с множеством статей, сколько слов ввёл пользователь. В результате каждой итерации поиска(для каждого слова)  мы получаем набор статей, в котором оно содержится. Необходимо сохранять эти наборы и потом вывести на экран пользователю только те статьи, которые являются общими для всех ключевых слов.


Во-первых, бинарный поиск можно улучшить(делить каждый раз отрезок не пополам, а "по-хитрому") и сделать из него интерполяционный поиск. 
Тем самым уменьшив количество сравнений с lg(N)(бинарный поиск) до lg(lg(N))(интерполяционный)
Во-вторых, максимально возможную скорость поиска O(1) даёт не бинарный поиск, а хеширование. (так в моей умной книжечке по алгоритмам написано).

Это сообщение отредактировал(а) zim22 - 20.7.2009, 19:59

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

За информацию +, спасибо.