Упорядочение по важности

Упорядочение по важности Во всех инвертированных списках, описанных ранее, документы были упорядочены в соответствии с некоторым общим критерием: как правило, по идентификаторам документов, мы использовали статические показатели качества. Такое упорядочение позволяет осуществлять параллельный обход инвертированных списков для всех терминов запросов, ранжируя каждого обнаруженного документа. Этот процесс иногда называют ранжированием “документ за документом” (document-at-a-time scoring). Теперь опишем метод неточного поиска наилучших К документов, в котором не все словопозиции упорядочены одинаково, что препятствует осуществлению параллельного обхода. Следовательно, необходимы аккумуляторы для накопления релевантности термин за термином. Такая схема называется ранжированием “термин за термином” (term-at-a-time scoring).

Идея заключается в том, чтобы документы d в инвертированном списке для термина t были расположены в порядке убывания значения tf,/( (частоты термина t в документе d). Следовательно, упорядочение документов изменяется от одного инвертированного списка к другому, и мы не можем ранжировать их в ходе параллельного обхода инвертированных списков для всех терминов запроса. Если инвертированные списки составлены в порядке убывания значения tf,,* то существуют два способа значительно снизить количество документов, для которых аккумулируется релевантность: 1) при обходе инвертиро-ванного списка для термина запроса t мы просматриваем только начальный участок списка либо после того, как будет просмотрено фиксированное количество документов г, либо после того, как значение опустится ниже заданного порога; 2) аккумулируя релевантность во внешнем цикле алгоритма, мы рассматриваем термины запросов в порядке убывания значения idf, так что термины запроса, которые могут внести больший вклад в итоговую релевантность, рассматриваются первыми. Последняя идея допускает адаптацию в момент обработки запроса: обнаружив термин запроса с небольшим значением idf, мы можем определить, следует ли продолжить обработку на основе изменения релевантности документов, определенных в ходе обработки предыдущего термина запроса. Если эти изменения являются минимальными, то мы можем отказаться от аккумуляции релевантности для оставшихся терминов запроса или обрабатывать более короткие начальные участки их инвертированных списков.

�, �U ��Ƞ� �жащих объединению этих глобальных чемпионских списков. Интуитивно ясно, что это выведет на первый план документы с большими итоговой релевантностью.

 

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

tel-icq