Создание систем информационного поиска
До сих пор в этой главе было приведено описание работы систем информационного поиска в общих чертах, но не показано, как добиться эффективного функционирования этих систем для того, чтобы машины поиска Web могли возвращать искомые результаты обработки коллекции, состоящей из многих миллиардов страниц, за десятые доли секунды. Двумя основными структурами данных любой системы информационного поиска являются лексикон, содержащий списки всех слов в рассматриваемой коллекции документов, и инвертированный индекс, в котором перечислены все места, где каждое слово встречается в коллекции документов.
Лексиконом называется структура данных, которая поддерживает одну важную операцию: после получения определенного слова она возвращает данные о том, в каком месте инвертированного индекса хранятся экземпляры этого слова. В некоторых версиях систем информационного поиска эта структура возвращает также данные об общем количестве документов, содержащих искомое слово. Лексикон должен быть реализован с использованием хэш-таблицы или аналогичной структуры данных, которая обеспечивает быстрое выполнение этой операции поиска. Иногда в лексикон не включают ряд широко распространенных слов, имеющих малое информационное содержание. Эти слова, называемыми запретными словами ("the", "of, "to", "be", "а" и т.д.), только занимают место в индексе, но не увеличивают ценность результата. Единственным резонным основанием для включения их в лексикон может служить вариант, в котором лексикон используется для поддержки фразовых запросов, — индекс, содержащий запретные слова, необходим для эффективной выборки результатов для таких запросов, как "to be or not to be".
Инвертированный индекс3, подобно индексу (предметному указателю), приведенному в конце данной книги, состоит из множества списков позиций — обозначений тех мест, где встречается каждое слово. Применительно к булевой модели ключевых слов список позиций представляет собой список документов. А список позиций, применяемый в модели однословных сочетаний, представляет собой список пар (документ, количество). Для обеспечения поддержки фразового поиска список позиций должен также включать обозначения позиций в каждом документе, где встречается каждое слово.
3 Термин "инвертированный индекс" (inverted index) является избыточным; лучшим термином был бы просто "индекс". Индекс называют инвертированным потому, что он задает порядок расположения слов, отличный от того порядка, в котором слова расположены в тексте, но таковы все индексы. Тем не менее по традиции в системах информационного поиска применяется термин "инвертированный индекс".
Если запрос состоит из одного слова (а такая ситуация встречается в 26% случаев, согласно [1411]), его обработка происходит очень быстро. Для этого выполняется единственная операция поиска в лексиконе для получения адреса списка позиций, а затем создается пустая очередь по приоритету. В дальнейшем происходит обработка списка позиций одновременно по одному документу и проверка количества экземпляров искомого слова в документе. Если очередь по приоритету имеет меньше, чем R элементов (где R— размер желаемого результирующего набора), то пара (документ, количество) добавляется к очереди. В противном случае, если количество экземпляров искомого слова больше по сравнению с соответствующими данными элемента с наименьшими показателями в очереди по приоритету, этот элемент с наименьшими показателями удаляется из очереди и добавляется новая пара (документ, количество). Таким образом, поиск ответа на запрос требует затрат времени, пропорциональных 0{H+RlogR), где Я— количество документов в списке позиций. Если запрос состоит из п слов, требуется выполнить слияние п списков позиций, дня чего требуется затраты времени, равные О (nH+RlogR).
В данной главе теоретический обзор средств информационного поиска представлен с использованием вероятностной модели, поскольку эта модель основана на идеях, уже описанных при изложении других тем в настоящей книге. Но в системах информационного поиска, фактически применяемых на практике, чаще всего используется другой подход, называемый моделью векторного пространства. Эта модель основана на таком же подходе с использованием мультимножества слов, как и вероятностная модель. Каждый документ представлен в виде вектора частот однословных сочетаний. Запрос также представляется полностью аналогичным образом; например, запрос [Bayes information retrieval model] представляется в виде вектора:
[О,...,1/0,...,1,0,...,1,0,...,1/0,...]
Применяемая здесь идея состоит в том, что существует по одному измерению для каждого слова в коллекции документов, а запрос получает оценку 0 по каждому измерению, кроме тех четырех, которые фактически присутствуют в запросе. Релевантные документы отбираются путем поиска среди векторов документов именно тех векторов, которые являются ближайшими соседями по отношению к вектору запроса в векторном пространстве. Одним из критериев подобия служит точечное произведение между вектором запроса и вектором документа; чем больше это произведение, тем ближе два вектора. С точки зрения алгебры указанные вычисления обеспечивают получение высоких оценок теми словами, которые часто появляются и в документе, и в запросе. А с точки зрения геометрии точечное произведение между двумя векторами равно косинусу угла между этими векторами; максимизация косинуса угла между двумя векторами (находящимися в одном и том же квадранте) равносильна уменьшению этого угла до нуля.
Это краткое описание далеко не исчерпывает всю проблематику модели векторного пространства. На практике эта модель была развита до такой степени, чтобы в ней можно было учесть целый ряд дополнительных средств, уточнений, исправлений и дополнений. Основная идея ранжирования документов по их подобию в векторном пространстве позволяет внести новые понятия в систему числового ранжирования. Некоторые специалисты утверждают, что вероятностная модель позволила бы выполнять аналогичные манипуляции более научно обоснованным способом, но исследователи в области информационного поиска вряд ли согласятся перейти на другой инструментарий до тех пор, пока не убедятся в явных преимуществах другой модели с точки зрения производительности.
Для того чтобы получить представление о том, с какими масштабами применения средств индексации приходится сталкиваться при решении типичной задачи информационного поиска, рассмотрим стандартную совокупность документов из коллекции TREC (Text REtrieval Conference), состоящую из 750 тысяч документов с общим объемом в 2 Гбайт текста. Лексикон этой коллекции содержит приблизительно 500 тысяч слов, к которым применены операции выделения основы и приведения к нижнему регистру; для хранения этих слов требуется объем памяти от 7 до 10 Мбайт. Инвертированный индекс с парами (документ, количество) занимает 324
Мбайт, хотя и остается возможность применить методы сжатия для сокращения этого объема до 83 Мбайт. Методы сжатия позволяют экономить пространство за счет небольшого увеличения потребностей в обработке. Но если сжатие позволяет держать весь индекс в памяти, а не хранить его на диске, то появляется возможность добиться существенного общего прироста производительности. Для поддержки фразовых запросов требуется увеличение этого объема примерно до 1200 Мбайт не в сжатом виде или до 600 Мбайт со сжатием. Машины поиска Web действуют в масштабах, превышающих примерно в 3000 раз указанные выше. При этом многие из описанных здесь проблем остаются теми же, а поскольку задача оперирования с терабайтами данных в одном компьютере практически не осуществима, индекс разделяется на к сегментов и каждой сегмент сохраняется на отдельном компьютере. Запрос передается параллельно на все компьютеры, а затем к результирующих наборов сливаются в один результирующий набор, который предъявляется пользователю. Кроме того, машины поиска Web вынуждены справляться с тысячами запросов, поступающих в секунду, поэтому для них требуется п копий к компьютеров. Со временем значения кип продолжают возрастать.