Эффективный поиск. Организация результатов

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

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

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

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

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

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

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

Крупная поисковая система может индексировать сотни миллионов или даже миллиарды страниц и обрабатывать миллионы запросов ежедневно. Например, к концу 2005 года поисковая система Google проиндексировала около 10 миллиардов страниц и обработала более 200 миллионов запросов в день. Чтобы удовлетворить высокие требования к вычислениям, крупная поисковая система часто использует большое количество компьютеров и эффективные методы обработки запросов.

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

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

Организация результатов. Большинство поисковых систем отображают результаты поиска в порядке убывания их соответствия заданному запросу. Некоторые поисковые системы, такие как поисковая система Vivisimo (www.vivisimo.com), объединяют результаты поиска в группы таким образом, что страницы, имеющие определенные общие характеристики, помещаются в одну группу. Известно, что кластеризация/категоризация результатов поиска эффективно помогает пользователям идентифицировать релевантные результаты в двух ситуациях.

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

Когда запрос короткий, он может быть интерпретирован по-разному, в этом случае кластеризация позволяет группировать результаты на основе различных интерпретаций, что позволяет поисковику сосредоточиться на группе с желаемой интерпретацией. Например, при отправке запроса ‘apple’ в поисковую систему Vivisimo результаты, относящиеся к компьютеру Apple (Macintosh), образуют одну группу, а результаты, относящиеся к фруктам, - другую, что позволяет пользователю легко сосредоточиться на нужных результатах.