Координатные индексы

Координатные индексыПо указанным причинам двухсловный индекс не стал стандартным решением. Вместо него широкое распространение получил координатный индекс (positional index) В нем для каждого термина из лексикона хранятся словопозиции в формате docID: (positionl, position2,...) , где positionl, position2 и т.д. представляют собой координаты лексемы в документе В словопозициях обычно содержится частота термина в документе.

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

Обработка фразовых запросов. Допустим, что инвертированные списки для слов to и be имеют такой вид, а пользователь ввел запрос to be ОГ not to be. Нам необходим доступ к инвертированным спискам для слов to, be, or и not. Проверяем пересечение инвертированных списков для слов to и be. Сначала смотрим на документы, в которых содержатся оба слова. Затем находим места в списках, где координата лексемы для слова be на единицу больше координаты лексемы to. После этого находим следующее вхождение каждого слова, координата лексем которых на четыре больше, чем первое вхождение. В указанных выше списках этим условиям удовлетворяют следующие записи, to: <...; 4: <..., 429,433);...) be: <...; 4: <.... 430,434);...)

Размер координатного индекса. Применение координатного индекса существенно увеличивает объем хранимых данных, даже если использовать компактное представление координат. Действительно, переход к координатному индексу также изменяет асимптотическую сложность операции пересечения инвертированных списков, поскольку количество сравниваемых элементов теперь ограничено не количеством документов, а количеством словоупотреблений в коллекции документов Т. Иначе говоря, сложность логического запроса равна 0(7), а не Q(N). Однако в большинстве приложений это уже неизбежно, потому что большинство пользователей рассчитывают, что система обладает функциональностью поиска фразовых запросов и запросов с учетом близости терминов.

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

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

Стратегии, основанные на двухсловных и координатных индексах, можно плодотворно комбинировать. Если пользователи часто посылают запросы на поиск конкретной фразы, например Michael Jackson, то продолжать пересекать соответствующие инвертированные списки нецелесообразно. Комбинированная стратегия для обработки определенных запросов использует индекс фраз или двухсловный индекс, а для всех остальных фразовых запросов — только координатный индекс. В индекс фраз включаются часто встречающиеся запросы пользователей. Однако это не единственный критерий: наиболее дорогостоящими являются те фразовые запросы, в которых отдельные слова являются распространенными, но вся фраза встречается относительно редко. Например, добавление словосочетания Britney Spears в индекс фраз может лишь примерно в три раза ускорить обработку этого запроса, поскольку большинство документов, содержащих хотя бы одно из этих слов, будут правильными ответами, в то время как добавление The Who может ускорить обработку этого запроса в тысячу раз. Следовательно, второй вариант является более предпочтительным, хотя такой запрос встречается реже. Бесплатный DICOM Viewer. Просмотр файлов DICOM.

В работе Уильямса и др. (Williams et al., 2004) приводится оценка еще более сложной схемы, в которой используются индексы двух описанных типов, а также частичный индекс следующих слов, который представляет собой промежуточное решение по отношению к двум первым. Для каждого термина индекс “следующее слово” (next word index) хранит записи о терминах, которые следуют за указанным термином в документе. Такая стратегия позволяет обработать типичный набор фразовых веб-запросов примерно в четыре раза быстрее, чем при использовании координатного индекса, в то же время требо-вания к размеру хранимых данных увеличиваются лишь на 26%.

tel-icq