Первая часть статьи опубликована здесь

Оценивать запрос, сравнивая его с каждым документом, задача нереальная; для эффективной оценки запроса требуется специальная форма индекса. Большинство исследований продемонстрировали, что эффективный поиск требует рассмотрения всех терминов, встречающихся в документе, за исключением стоп слов (не несущих смысловой нагрузки терминов, например: «the», «и», к тому же). Попытки сократить объем индексных терминов до меньшего количества дескрипторов ( лексических единиц (слов, словосочетаний) информационно-поискового языка, служащих для описания основного смыслового содержания документов) не оказались успешными. Стандартная структурная единица индексируемых документов для ранжирования - это инвертированный файл (структура данных, в которой хранится информация о том, в каких документах и на каких позициях встречаются термины). Это единственно правильная структура индекса, состоящая из двух компонентов: словаря с определенными терминами и инвертированного списка для каждого термина.

Список должен включать идентификатор (identifier) каждого документа, где есть данный термин, частота вхождения термина в документе, возможно, позиция слов в документе для определения близости запросу. Для эффективной обработки, инвертированные списки должены быть отсортированы по увеличению идентификатора документа. Для эффективного поиска, инвертированные списки должны быть отсортированы по тематикам. Данный подход может стать причиной увеличения затрат и фрагментации дискового пространства (disk fragmentation), однако для оценки запроса в нем есть преимущества. В данной работе допускается, что инвертированные списки отсортированы, используя методы компрессии на основе кодов разной длинны.