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

Лексиконом называется структура данных, которая поддерживает одну важную операцию: после получения определенного слова она возвращает данные о том, в каком месте инвертированного индекса хранятся экземпляры этого слова. В некоторых версиях систем информационного поиска эта структура возвращает также данные об общем количестве документов, содержащих искомое слово. Лексикон должен быть реализован с использованием хэш-таблицы или аналогичной структуры данных, которая обеспечивает быстрое выполнение этой операции поиска. Иногда в лексикон не включают ряд широко распространенных слов, имеющих малое информационное содержание. Эти слова, называемыми запретными словами ("the", "of, "to", "be", "а" и т.д.), только занимают место в индексе, но не увеличивают ценность результата. Единственным резонным основанием для включения их в лексикон может служить вариант, в котором лексикон используется для поддержки фразовых запросов, — индекс, содержащий запретные слова, необходим для эффективной выборки результатов для таких запросов, как "to be or not to be".

Инвертированный индекс, подобно индексу (предметному указателю), приведенному в конце данной книги, состоит из множества списков позиций — обозначений тех мест, где встречается каждое слово. Применительно к булевой модели ключевых слов список позиций представляет собой список документов. А список позиций, применяемый в модели однословных сочетаний, представляет собой список пар (документ, количество). Для обеспечения поддержки фразового поиска список позиций должен также включать обозначения позиций в каждом документе, где встречается каждое слово.