Статический ранг и упорядочение индекса

Статический ранг и упорядочение индекса Разовьем дальше идею чемпионских списков в направлении более общей идеи о статическом ранге. Во многих поисковых системах существует возможность вычислить меру качества g(d) для каждого документа d, не зависящую от запроса и потому являющуюся статической (static). Эту меру качества можно рассматривать как число, лежащее между нулем и единицей. Например, в контексте новостных статей в сети веб ранг g(d) может быть определен по количеству благожелательных отзывов пользователей остатье.

В этом простом виде статический ранг g(q) и релевантность из формулы, зависящий от запроса, вносят одинаковые вклады от нуля до единицы. Возможны и другие варианты относительного взвешивания; эффективность этого эвристического приема зависит от конкретной схемы.

Итоговая релевантность документа d является комбинацией статического показателя g(d) с динамической релевантностью, зависящей от запроса, например вычисленным по формуле . Точную комбинацию можно определить с помощью методов машинного обучения. Однако для ясности изложения пока будем считать, что он вычисляется как простая суммаСначала рассмотрим упорядочение документов в инвертированном списке для каждого термина по убыванию g(d). Это позволяет выполнить алгоритм пересечения списков. Для того чтобы определить пересечение за один проход по словопозициям каждого термина запроса, в алгоритме, используются словопозиции, упорядоченные по идентификаторам документов. Однако на самом деле нам требуется лишь, чтобы все словопозиции были упорядочены единообразно; в данном случае для упорядочения мы используем значения g(d). Эта схема продемонстрирована ранее, где инвертированные списки составлены в порядке убывания значений g(d).

Расширение чемпионских списков

Следующая идея представляет собой непосредственное расширение чемпионских списков. Для тщательно выбранного значения г и для каждого термина t мы храним глобальный чемпионский список (global champion list), состоящий из г документов, имеющих наибольшие значения g(d) + tf-idf,^. Этот список упорядочен так, как и все инвертированные списки (либо по идентификаторам документов, либо по статическим рангам). Тогда в момент запроса остается только вычислить итоговую релевантность для документов, принадлежащих объединению этих глобальных чемпионских списков. Интуитивно ясно, что это выведет на первый план документы с большими итоговой релевантностью.

Завершим обсуждение глобальных чемпионских списков следующей идеей. Для каждого термина t будем хранить два инвертированных списка, состоящих из непересекаю- щихся множеств документов и упорядоченных по убыванию величины g(d). Первый список, который называется верхним (high), состоит из т документов, имеющих наибольшие значения tf для термина t. Второй список, который называется нижним (low), содержит все другие документы, содержащие термин t. Обрабатывая запрос, мы сначала сканируем только верхние списки терминов запроса, вычисляя итоговую релевантность документов, содержащихся в верхних списках для всех (или большей части) терминов запроса. Если в ходе этого процесса нам удастся получить релевантность К документов, то алгоритм останавливается. Если нет, то мы вычисляем релевантность документов из нижних списков.

tel-icq