Turtle >> Индекс, подготовка данных для поиска. Поисковая система "Turle".

3.10 Индекс, подготовка данных для поиска.
Теперь рассмотрим уже упомянутое мною недостающее звено в цепи накопления данных - поиск по данным. Хочу особо обратить внимание на тот факт, что мы, разработчики этой системы, должны ввести понятие максимального времени отклика системы при поиске. Это означает, что результаты поступают на экран не позднее, чем через определенный интервал времени, и желательно, чтобы этот интервал был как можно меньше. Однако что делать в случае, если поисковый запрос содержит очень частотные поисковые термины? Передача большого количества данных с одного процессора поиска на другой определяется скоростью среды, к которой подключены компьютеры этих серверов (обычно это 100 Mb или 1Gb), и не может быть уменьшена в рамках конкретной технической реализации. Из этого факта следуют два принципиальных вывода:

Необходимо тщательно проектировать топологию подключения серверов поисковой системы, во избежание конфликтов между потоками.
Необходимо постараться минимизировать количество передаваемых данных в условиях запросов частотных терминов.
С первым пунктом все понятно - требуется работа квалифицированных инженеров. Остановимся на втором пункте. Частотным термином будем называть слово, которое встречается в таком количестве документов, передача данных для которого с одного процессора поиска на другой превысит предельную величину времени в одну секунду.
Предположим, что частотные слова распределяются равномерно в рамках всей коллекции документов. На практике это означает, что количество документов в интервале идентификаторов ID от 1 до 1000000, содержащих частотное слово "a", примерно равно количеству документов, содержащих это же частотное слово в интервале ID от 1000000 до 2000000, и так далее.
Сделаем предположение, что само по себе частотное слово является малоинформативным именно потому, что встречается в большом количестве документов разных тематик. Следовательно, для получения результатов сложного запроса, содержащего частотные слова, можно попытаться оперировать не полной информацией по частотному слову, а только ее частью, и в дальнейшем апроксиимировать количество суммарных результатов.
Мы храним индексную информацию по частотным словам некими фиксированными порциями, которые назвали "корзинами". Если оптимизатор запросов в своих расчетах убеждается, что для выполнения запроса полностью потребуется слишком много времени, то он старается составить план запроса таким образом, чтобы у частотных слов читать из индекса только ограниченное количество информации (корзин), при котором выполнение запроса не превысит некоей критической величины по времени. Ограничивая количество данных для частотных слов, система практически не ухудшает своих релевантностных характеристик, т.к. влияние самих частотных слов обычно минимально. Исключения составляют только те запросы, которые состоят только из частотных слов. Однако простая логика подсказывает, что подобные запросы обычно не имеют смысла. В качестве исключения из этого правила можно привести шекспировское "to be or not to be". Количество таких запросов не превышает сотой доли процента от общего количества, и мы решили не "ломать копья" за их удовлетворение. Для подобных запросов был разработан специальный алгоритм выбора количества корзин, однако на практике можно выбрать корзины случайным образом.
Полагаем, что каким-то подобным способом ограничивается количество частотных поисковых данных и в других системах (например, Google), которые в результатах поиска отображают примерное количество найденных результатов. Особенностью системы "Turtle" является то, что она будет стараться использовать не фиксированное количество данных для частотных поисковых слов, а максимально возможное, с учетом реалий запроса. Становится понятным, что следует понимать под стабильностью результатов поисковой машины и почему один и тот же запрос может в течение времени получить немного разные ответы. Следует также отметить, что понятие частотного слова может возникнуть при условии, что коллекция документов поисковой системы весьма велика. Если коллекция будет ограничена (например, пределами российского Интернета), то можно смело утверждать, что количество частотных слов в системе будет не так велико (или их вообще не будет).
Теперь можно описать устройство самого индекса, а также программ, которые его создают. Анализируя два возможных способа хранения поисковых терминов (лексем) в базе данных, мы для себя не обнаружили существенных решающих преимуществ хранения цифровых обозначений (ID) лексем перед хранением самих лексем. Например, хранение лексем в виде их идентификаторов лишает нас возможности искать по двоичному дереву лексемы, имеющие произвольное окончание без специальных внешних процедур.
В нашем случае индекс имеет двухуровневую структуру. Первый уровень содержит бинарное дерево поисковых терминов в качестве ключа поиска. В качестве аргументов такого ключа используются данные по полному индексу, а именно: координата в индексном файле начала данных, длина данных, компрессированная длина данных, количество корзин данных, номера URL начала и конца каждой корзины. Запись двоичного дерева имеет вид:

Если слово является частотным, то данные для него хранятся в нескольких корзинах, и в базе BTREE-лексем содержится описание каждой корзины с данными. Поле "Position" указывает на координату в файле собственно самих данных индекса данного слова. Файл данных индекса слов является вторым уровнем индекса. Хранение данных в нем производится следующим образом:

Основные компрессированные данные
Main compressed data Расширенные компрессированные данные
Extended compressed data

Как видно из схемы, реальные данные по поисковому термину состоят из двух частей, каждая из которых сохраняется в компрессированном виде. Зачем мы разделили данные на две отдельные части, а не компрессировали их вместе? Дело в том, что основная часть поисковых запросов по умолчанию не использует данные расширенной части. Они используются для искусственного ограничения области поиска (например, искать только в заголовках и пр.), и не должны считываться с диска в условиях типового запроса. Основной частью данных является первая компрессированная пачка данных, содержащих в себе структуры ID-документов, предвычисленные веса для данного поискового термина в пределах этого ID, предвычисленный на момент сканирования PageRank документа указанного ID и координатную информацию по каждому термину, включая номер фразы текста (мажор) и номер слова внутри фразы (минор). Для оптимального использования дискового пространства данные с плавающей точкой хранятся с уменьшенным количеством разрядов. Не каждая пачка информации является компрессированной, программно устанавливается предельный барьер количества данных, начиная с которого данные будут компрессированы. Это предотвращает большое количество малоэффективной работы по слабочастотным лексемам.
Для эффективной поддержки файла данных индекса нами был разработан специальный диспетчер свободного места в файле индекса. Дело в том, что в процессе обновления данных сканирования часть терминов исчезает из документов, в то же время появляются новые термины. В целом природа данных поискового термина имеет возрастающий во времени характер с учетом увеличения числа сканируемых системой документов. При обновлении индекса ранее используемое место освобождается и новые данные укладываются начиная с позиции, указанной таким диспетчером. Ему же система сообщает о координатах и размерах освободившихся кусков. В целом, используя подсистему менеджера свободного места в индексном файле каждого отдельного процессора поиска, можно достаточно долго не проводить полного перестроения индекса. Сигналом к его полному перестроению является превышение общего размера индекса к его полезной части на уровне 1.7.

<< 3.9. Язык поисковых запросов | Содержание | 3.11. Борьба за компактность. Компрессия >>

Черепаший Ранк. Реклама на Turtle Логотипы Правовая информация Конфиденциальность Контакты