Завершающая часть очередного патента Google: "Определение спам-документов системой получения информации, основанное на фразах." Часть 3 (ОКОНЧАНИЕ).
III. Поисковая система
Поисковая система 120 служит для получения запроса, поиска релевантных запросу документов и предоставления списка этих документов (со ссылками на документы) в виде набора поисковых результатов.
Рис. 6 иллюстрирует основные функциональные операции поисковой системы 120:
- 600: Определение фраз в запросе
- 602: Получение документов, релевантных поисковым фразам
- 604: Ранжирование документов в поисковых результатах, в соответствии с фразами
Теперь подробнее обо всех стадиях.
Определение фраз в запросе и расширение запроса
Первая стадия 600 действий поисковой системы 120 состоит в определении всех фраз, которые присутствуют в запросе, чтобы обеспечить эффективный поиск в индексе. В данном разделе используется следующая терминология:
q: запрос как он был введен и получен поисковой системой 120
Qp: фразы, присутствующие в запросе
Qr: соотнесенные с Qp фразы
Q: объединение Qp и Qr
Запрос q получается от клиента 190, и в нем содержится определенное количество знаков или слов, ограниченное неким лимитом
Окно фраз размером N (т.е., 5), используется поисковой системой 120 для траверсирования терминов в запросе q. Окно фраз начинает с первого термина запроса, затем расширяется на N терминов вправо. Это окно затем перемещается вправо M-N раз, где M – количество терминов в запросе.
В каждой позиции в окне будет находиться N (или меньше) терминов. Эти термины означают возможную фразу запроса. Список хороших фраз 208 проверяется на предмет наличия в нем возможной фразы, чтобы определить, хорошая она или нет. Если возможная фраза присутствует в списке хороших фраз 208, то возвращается номер этой фразы. Теперь возможная фраза становится фразой-кандидатом.
После того, как протестируются все возможные фразы во всех положениях окна фраз, и будут определены все хорошие фразы-кандидаты, поисковая система 120 получит набор номеров фраз для соответствующих фраз в запросе. Эти номера фраз потом сортируются (в нисходящем порядке).
Начиная с наибольшего номера фразы, как первой фразы-кандидата, поисковая система 120 определяет, присутствует ли другая фраза-кандидат в пределах фиксированного числового расстояния в отсортированном списке, т.е., разница между номерами фраз не должна превышать определенного порогового расстояния – напр., 20000. Если это условие выполняется, то фраза, находящаяся в запросе слева, выбирается в качестве действительной фразы запроса Qp. Эта фраза запроса и все ее суб-фразы удаляются из списка кандидатов, а список пересортируется и процесс повторяется. В результате этого процесса получается набор действительных фраз запроса Qp.
К примеру, предположим, что поисковый запрос – “Hillary rodham Clinton Bill on the Senate Floor”, Поисковая система 120 определит следующие фразы-кадидаты: “Hillary rodham Clinton Bill on”, “Hillary Rodham Clinton Bill” и “Hillary Rodham Clinton”. Первые две будут опущены, а третья сохранится в качестве действительной фразы запроса. Далее, поисковая система 120 определит “Bill on the Senate Floor” и суб-фразы “Bill on the Senate”, “Bill on the”, “Bill on”, “Bill”, и выберет “Bill” в качестве действительной фразы запроса Qp. И, наконец, поисковая система 120 проанализирует фразу “on the Senate Floor” и определит “Senate Floor” как действительную фразу запроса.
Далее поисковая система 120 корректирует действительные фразы Qp по заглавным буквам. Во время парсинга запроса, поисковая система 120 определяет потенциальные заглавные буквы в каждой действительной фразе. Это может быть сделано на основании таблицы известных заглавных слов, например “united states” может быть воспринято как “United States”, или на основании грамматического алгоритма. В результате получается набор должным образом озаглавленных поисковых фраз.
Затем поисковая система делает второй проход по озаглавленным фразам, и выбирает только те, которые расположены левее и написаны с заглавной буквы, причем и фраза, и ее суб-фраза должны присутствовать в наборе. Например, поиск по “president of the united states” будет исправлен на заглавные буквы “President of the United States”.
На следующей стадии, поисковая система 120 определяет 602 документы, которые релевантны поисковым фразам Q. Поисковая система 120 получает постинг-списки поисковых фраз Q, и если необходимо, делает скрестный анализ этих списков, чтобы определить, какие документы появляются во всех (или в некоторых) постинг-списках по поисковым фразам. Если фраза Q в запросе обладает набором расширений фразы Qe (это объясняется ниже), то поисковая система 120 сначала формирует набор постинг-списков расширений фразы, а затем делает скрестный анализ списков. Поисковая система 120 определяет расширения фразы путем проверки каждой фразы запроса Q в списке неполных фраз 216, как описывалось выше.