Основные концепции и подходы при создании контекстно-поисковых систем на основе реляционных баз данных. Доступно и просто.

• Введение
• Архитектура
• ER-модель поискового механизма
• Индексный механизм
• Поисковый механизм
• Комплексное функционирование
• Заключение

Введение

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

Архитектура

Рассмотрим классическую архитектуру, которая чаще всего реализована на корпоративных сайтах или информационных порталах. Такая архитектура изображена на рис. 1.

Рис.1

Разберем по частям, то что изображено на рисунке. Существует клиентская вычислительная машина под управлением ОС Windows и существует Web-сервер под управлением UNIX-подобной ОС. На стороне клиента запущен типичный просмоторщик web сайтой, такой как Netscape. На стороне сервера запущен web сервер, который обслуживает запросы от просмоторщика, передавая запросы презентационному слою понимающему CGI. Презентационный слой передает запросы к поисковому механизму в случае вызова услуги поиска или отображает наполнение (content) сайта. При работе администратора презентационный слой также может передавать запросы о инициировании механизма индексации нового контента, который еще не индексирован. Это необходимо, так как пока текст не индексирован, не будет осуществляется процесс поиска в этом тексте с помощью поисковой машины.

На самом деле идея заключается в следующем. Существуют мегабайты текстовой информации и скорость поиска документов содержащих заданные ключевые слова отнимает очень много процессорного времени. Предположим в 10 мегабайтах текстовой информации ключевое слово будет находится в течении 10 секунд. И вот заходит посетитель на Ваш сайт и вызывает услугу поиска и задает ключевые слова и ждет 10 секунд когда ваш сервер выдаст ему результат. Предположим случилось так, что одновременно запросило поиск 5 человек. Естественно время ответа увеличится в 5 раз. Получается, что в среднем по 50 секунд пользователь будет ждать ответа от вашего сервера. Это не приемлемо, особенно если у Вас сотни мегабайт текстовой информации и время реакции системы будет катастрофически велико. Необходимо использовать другой подход при поиске ключевых слов в текстовой информации. Время ответа сократить до миллисекунд.

ER-модель поискового механизма

Существует такая хорошая характеристика у реляционных баз данных, как очень маленькое время выборки конкретной записи из миллионов других. Это достигается созданием так называемого индекса к таблице на какое-то из полей этой таблицы. Обычно индексы реализуются с применением алгоритма сбалансированного двоичного дерева. Предположим у нас есть таблица в которой всего один столбец и в каждой записи таблицы хранится фамилия человека. Предположим мы загнали в такую таблицу 1 миллион фамилий. Нам необходимо проверить существует ли в этой таблице фамилия ИГУМНОВ. Предположим что мы еще никаких индексов на эту таблицу не сделали, так же фамилия ИГУМНОВ стоит посредине таблице. Когда мы пошлем вот такой запрос: select surname from ourtable where surname='ИГУМНОВ' база данных переберет пол миллиона записей пока не дойдет до фамилии ИГУМНОВ и не выдаст результат. Получается опять слишком медленно. Но как только мы сделаем индекс на поле нашей таблицы, как сразу все наши запросы будут обрабатываться за миллисекунды, а этого мы и добиваемся. Естественно нам одной таблице будет мало для решения нашей проблемы. Классическая структура базы данных, которая позволит решить нашу проблему изображена на рис.2.

Рис.2

Начнем с таблицы document. В этой таблице хранятся имена файлов или URL'ы страниц и каждой такой записи сопоставлен уникальный ключ id. Есть таблица dictionary там хранятся все слова, которые могут встретиться в наших документах и каждому слово сопоставлен уникальный id. Естественно создаются индексы на поле word в таблице dictionary и на поле id в таблице document. В нашем примере существует отношение многие ко многим. Это необходимо, так как в таблице match мы храним соответствие слова и документа. Другими словами в таблице match хранится информация о том в, каком документе, какие есть слова. На таблицу match создают индекс, на поле dict_id.

Индексный механизм

Прежде чем ваши документы будут доступны для поиска их необходимо индексировать. Объем индексной информации полученной из текстовой может быть в два раза больше чем исходный текст. А может еще больше в случае если вы будете не оптимально использовать память. Алгоритм выглядит следующим образом.

1. Получаем документа для индексирования

2. Регистрируем его в таблице document и запоминаем полученый его уникальный id и будем его называть doc_id

3. Разбиваем документ на отдельные слова

4. Узнаем уникальные id этих слов из таблицы dictionary и будем их называть dict_id

5. Потом заносим записи с нашим одним doc_id и разными dict_id (для каждого слова в документе) в таблицу match

Поисковый механизм

После того как мы проиндексировали наши документы теперь нужно понять какие запросы посылать в базу что бы искать эти документы по ключевым словам. Предположим поисковая фраза "река объ". Пользователю необходима получить все документы содержащие эти два слова. Сначала нужно обратиться к таблице dictionary и узнать уникальные id этих слов, далее будем их называть $dict_id1 и $dict_id2. Потом необходимо послать такой запрос в таблицу match, который выдаст только те номера документов, которые содержат эти два слова. Вот пример этого запроса: SELECT doc_id FROM match where dict_id =$dict_id1 group by doc_id INTERSECT SELECT doc_id FROM match where dict_id=$dict_id2 group by doc_id. В случае если пользователь введет три слова то вам придется добавть еще раз INTERSECT и третью часть SQL запроса. По полученным в результате запроса doc_id вы можете извлечь информацию о имени файла документа из таблицы document.

Комплексное функционирование

Что бы увидеть общее представление механизма взаимодействия с поисковой системой нужно взглянуть на рис. 3.

Рис.3

Как видно из рисунка существует три потока управления. Первый обслуживает запросы пользователя, второй выполняет поисковые запросы а третий занимается индексированием новых документов поступающих в систме. Первый это скрипт на Perl, Servlet, ASP или PHP которые из ключевых слов полученных от пользователя формирует поисковые SQL запросы, второй это база данных которая поддерживает целостность данных, индексный механизм и обслуживает SQL запросы, а третий это тоже скрипт который работает с новыми документами, индексирует их и посылает запросы в базу данных на внесения новой индексной информации.

Заключение

Разобранный пример является одним из более популярных подходов, на мой взгляд. Мой пример не претендует на полноту и оптимальность, так что у Вас могут возникнуть некоторые проблемы, которые придется Вам разрешать самим. Например: большое время на процесс индексирование, при очень больших объемов текста порядка 1Гб необходимо распределять задачу, большое количество результатов запроса и т.д. и т.п. В свое время я решил большую часть этих проблем на бумаге, но не воплощал их в код, по этой причине я и не писал об этих решениях в моей статье.

Домашняя страничка: http://ejbcorba.euro.ru