Инвертированный индекс и BM25

В этом каталоге 77 статей и 119 076 слов. Чтобы найти, где говорится о кратчайшем пути, можно прочитать их все — а можно заранее, один раз, записать для каждого слова, в каких статьях оно встречается. Тогда запрос из двух слов читает два коротких списка. Ниже — такой поиск по самому каталогу. Каждое слово запроса превращается в полоску: клетка на каждую статью, яркая — если слово там есть. Под полосками — выдача, отсортированная по формуле BM25, и вклад каждого слова в оценку.

На «кратчайший путь» поиск прочитал 48 записей индекса: «кратч» есть в 15 статьях, «путь» — в 33, хотя бы одно из двух — в 34. Первые три — A*, Беллман — Форд и Флойд — Уоршелл. Статья о Дейкстре — четвёртая и отстаёт от третьей на 0,005. Формула не знает, какая статья для темы главная: она считает слова. Ниже — как устроены полоски, как их пересекать, сжимать и превращать в порядок выдачи.

Идея

Обычно документ — это список слов. Инвертированный индекс переворачивает его: для каждого слова — список документов, где оно есть. Номера в списке идут по возрастанию, и при каждом записано, сколько раз слово встретилось в документе. Такой список называют списком вхождений (posting list). Запрос не трогает тексты: он находит в словаре списки своих слов и работает только с ними.

Это указатель в конце толстой книги: «хеш-таблица — 211, 340, 517». Строится он одним проходом по всем словам. Слово ищется в словаре — хеш-таблице или отсортированном массиве, — и в конец его списка дописывается номер текущего документа, если его там ещё нет. Документы идут по порядку, поэтому списки получаются отсортированными сами собой. С самого начала, от поисковика, который перебирает все тексты, эта идея разобрана в главе курса «Поисковик по нашим учебникам». Здесь — что происходит дальше, когда списки становятся длинными.

В индексе каталога слово — не совсем слово. Это его первые пять букв: «кратчайший», «кратчайшего» и «кратчайшая» дают один термин «кратч». Это грубая замена стеммера, который отрезает окончания по правилам языка, или лемматизатора, который приводит слово к словарной форме. Короткие слова так не склеиваются: «путь» и «пути» — разные термины. Терминов получилось 7151, пар «термин, статья» — 43 805.

Списки очень неравны. 3357 терминов, почти половина, встречаются ровно в одной статье. Тринадцать — во всех семидесяти семи: «и», «а», «в», «что», «это», «по», «на», «же», «если», «код», «задач», «больш», «сколь». Так устроен любой текст — несколько очень частых слов и длинный хвост редких. Из этого неравенства следуют три вопроса, на которых держится вся статья: как пересечь короткий список с длинным, как хранить длинные списки и как не утонуть в документах, где есть одни частые слова.

Пересечение: короткий список против длинного

Запрос «двоичный поиск» в режиме «все слова» — это пересечение двух списков: «двоичный» есть в 33 статьях, «поиск» — в 50, оба — в 27. Списки отсортированы, и стандартный способ пересечь их — два пальца, как при слиянии в сортировке слиянием: палец на меньшем номере шагает вперёд, совпадение записывается в ответ. Шагов — не больше m + n, где m и n — длины списков.

Пока списки похожей длины, лучше не сделать. Но в «Войне и мире» 31 252 предложения, и слово «бал» стоит в 18 из них, а «и» — в 13 480. Двум пальцам, чтобы найти 11 предложений, где есть оба, придётся пройти 12 246 шагов — почти весь длинный список. Короткий список задаёт, что искать; длинный нужен только для проверки. Проверять можно двоичным поиском: на каждое из 18 предложений — около log₂ 13 480 ≈ 14 взглядов в длинный список, всего 249.

Ещё лучше — галоп. Предложения короткого списка идут по возрастанию, поэтому искать очередное нужно не с начала длинного списка, а с того места, где остановился предыдущий поиск. От этого места делаем прыжки на 1, 2, 4, 8… позиций вперёд, пока не перепрыгнем искомый номер, а внутри последнего прыжка ищем двоичным поиском. Если искомое в d позициях впереди, прыжков около log₂ d, и столько же шагов двоичного поиска. На паре «бал» и «и» это 232 взгляда вместо 12 246. Выберите пару слов и посмотрите, как это выглядит: сверху весь роман, снизу лупа, где видны прыжки к очередному предложению.

В лупе шкала логарифмическая, и прыжки 1, 2, 4, 8 на ней — равные шаги. Поэтому до далёкого предложения всего на несколько прыжков больше, чем до близкого. В обзоре сверху оранжевая полоса — всё, что прошли два пальца, а редкие отметки под ней — всё, на что посмотрел галоп.

Для «бала» и «и» граница даёт 380, на деле 232. Если m = n, граница — 4n, тот же порядок, что у двух пальцев. Если m ≪ n, она растёт как m·log(n/m), а не как n. Это естественная граница: даже чтобы слить два упорядоченных списка, в худшем случае нужно log₂ C(m+n, m) сравнений — при m ≪ n это примерно m·log₂(n/m), — и Фрэнк Хван и Шэнь Линь в 1972 году построили слияние, которое почти достигает этого минимума. Замеры из листинга ниже:

Двоичный поиск с нуля хорош, только пока короткий список очень короткий: на паре «Наташа» и «Пьер» он в четыре раза хуже двух пальцев. Галоп не хуже ни того ни другого ни в одной строке. Если слов в запросе больше двух, списки берут от самого короткого: его номера — кандидаты, и каждый следующий список может их только отсеять. Кандидатов становится меньше, а проверять их приходится в списках всё длиннее — как раз там, где галоп выигрывает больше всего.

Настоящие индексы добавляют к спискам указатели пропуска: на каждый блок номеров — его первый номер и адрес в файле. По ним галоп перепрыгивает целые блоки, не распаковывая их, а распаковывает только блок, где может быть кандидат. Указатели пропуска в инвертированных файлах описали Алистер Моффат и Джастин Зобель в 1996 году; в Lucene они стоят на каждый блок из 128 номеров.

Сжатие: разности и байты

Если хранить каждую пару «статья, сколько раз» двумя 4-байтными числами, списки индекса каталога займут 350 440 байт. Но номера в списке растут, и вместо них можно хранить разности соседних: список 3, 7, 8, 15, 16 превращается в 3, 4, 1, 7, 1. У частого термина разности маленькие — он есть почти в каждой статье, — у редкого большие, но таких номеров мало. Маленькие числа пишут кодом переменной длины: по 7 бит в байте, а старший бит говорит, будет ли следующий байт. Числа до 127 занимают байт, до 16 383 — два.

После этого те же списки занимают 87 610 байт — в 4,0 раза меньше, около двух байт на пару. Выигрыш не только в месте. Сжатый индекс помещается в память целиком, а распаковать байт быстрее, чем дождаться его с диска: чтение с SSD в сотни раз дольше обращения к памяти. Lucene с версии 4.1 идёт дальше: упаковывает разности блоками по 128 чисел, отводя всем числам блока одинаковое число бит — столько, сколько нужно самому большому, а хвост списка, не заполнивший блок, пишет переменными байтами. Семейство кодов PForDelta, предложенное Марцином Жуковским и коллегами в 2006 году, выносит редкие большие разности в отдельный список исключений, чтобы одна большая разность не раздувала весь блок.

BM25: редкость, насыщение, длина

Найти статьи, где есть слова запроса, — половина дела. На «очередь с приоритетом» отзываются 76 статей из 77: предлог «с» есть почти везде. Их надо упорядочить, и самая распространённая формула для этого — BM25. Оценка статьи D — сумма вкладов слов запроса, которые в ней есть:

$$\text{BM25}(D) = \sum_{t} \text{idf}(t) \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)},$$

$$\text{idf}(t) = \ln\left(1 + \frac{N - \text{df} + 0{,}5}{\text{df} + 0{,}5}\right).$$

Здесь tf — сколько раз термин t встречается в D, |D| — длина статьи в словах, avgdl — средняя длина (в каталоге 1546 слов), N — число статей, df — в скольких из них есть t. Три сомножителя отвечают на три вопроса.

Насколько слово редкое. idf тем больше, чем меньше документов со словом: у «приор» он 2,85 (4 статьи), у «очере» — 0,88 (32 статьи), у «с» — 0,02. В исходной формуле Робертсона и Спарк Джонс единицы под логарифмом нет. Тогда у слова, которое встречается больше чем в половине документов, idf отрицательный: «алгор» есть в 56 статьях из 77 и получил бы −0,97. По запросу «алгоритм сортировки» статья со словом «алгоритм» проигрывала бы такой же статье без него. У «и», которое есть во всех статьях, было бы −5,04. Lucene добавляет под логарифмом единицу: «алгор» весит 0,32, «и» — 0,006. SQLite в FTS5 оставляет исходную формулу, но заменяет неположительный idf на 10⁻⁶ — комментарий в исходниках так и объясняет: отрицательный вес нежелателен.

Насколько повторы что-то значат. Дробь с tf растёт с числом повторов, но всё медленнее и упирается в потолок k₁ + 1: десятое упоминание добавляет меньше первого. Это насыщение — простое приближение модели, в которой документ либо посвящён слову, либо упоминает его мимоходом: Стивен Робертсон и Стив Уокер искали такую замену модели «двух Пуассонов» в 1994 году. При k₁ = 0 считается только факт присутствия, при большом k₁ оценка почти пропорциональна tf.

Насколько статья длинная. В длинной статье слово чаще встречается просто потому, что слов больше. Множитель 1 − b + b·|D|/avgdl сравнивает длину со средней, а b решает, насколько строго: при b = 0 длина не важна, при b = 1 частоту делят на длину полностью. Формулы с b = 1 и b = 0 команда системы Okapi называла BM11 и BM15; на конференции TREC-3 в 1994 году она объединила их в одну, BM25, с b между ними.

Подвигайте ручки на запросе «очередь с приоритетом». Кривые показывают вклад слова в зависимости от числа повторов для статьи вдвое короче средней, средней и вдвое длиннее.

Спор идёт между тремя статьями. В «Двоичной куче» «очередь» встречается 6 раз и «приоритет» 5, но это самая длинная статья каталога — 2978 слов. В «Стеке и очереди» «очередь» — 36 раз, «приоритет» — 2, длина 1690. В статье «Как выбрать структуру данных» — 2 и 1 при длине 662. При k₁ = 0 у всех трёх ровно 3,75: каждая содержит все три термина, и считается только это. При k₁ = 1,2 впереди куча, 5,94 против 5,72. При k₁ = 3 тридцать шесть «очередей» перевешивают, и первой становится «Стек и очередь», 7,66 против 7,62. Ручка b двигает другое: при b = 0 длинная куча уходит в отрыв, 6,71 против 5,83, а при b = 1 короткая статья о выборе структуры догоняет её — у обеих 5,72.

Для запроса из одного слова k₁ порядок не меняет вовсе. Документ 1 обходит документ 2, если tf₁/(tf₁ + k₁L₁) > tf₂/(tf₂ + k₁L₂), где L — множитель длины. Перемножив крест-накрест, получаем tf₁·L₂ > tf₂·L₁, и k₁ сокращается. Насыщение решает, сколько стоят повторы одного слова против присутствия другого, — поэтому оно и важно только в запросах из нескольких слов. Обычные значения — k₁ от 1,2 до 2 и b = 0,75; в Lucene по умолчанию 1,2 и 0,75, в SQLite эти числа зашиты в код.

Лучшие десять, не считая всех

Листинг ниже ранжирует «термин за термином»: проходит список каждого слова запроса и копит оценки в массиве, по ячейке на документ. Работа пропорциональна сумме длин списков, и для частого слова это почти все документы. Но читателю нужны первые десять. Можно ли выбрать их, не досчитывая остальных?

Можно, если знать потолок каждого термина — самый большой вклад, который он даёт хоть одному документу. Его считают заранее, при индексации. Пусть уже найдены k документов, и худший из них набрал θ. Расставим термины запроса по возрастанию потолка. Если потолки нескольких первых в сумме не больше θ, документ, где есть только эти термины, в лучшие уже не попадёт, и смотреть на него не нужно. Значит, документы-кандидаты берутся только из списков остальных терминов, а в «слабых» списках ищутся галопом — для проверки. Чем лучше найденные, тем выше θ и тем больше терминов становятся слабыми. Это алгоритм MaxScore Говарда Тёртла и Джеймса Флуда, 1995 год.

На «кратчайший путь» с тремя лучшими MaxScore посмотрел на 16 статей из 34, где есть хоть одно слово, и досчитал до конца 7. Ответ тот же: A*, Беллман — Форд, Флойд — Уоршелл. На миллионах документов разница намного больше: частые слова дают длинные списки, но с маленькими потолками, и почти весь их список не читается. Андрей Бродер с соавторами в 2003 году предложили алгоритм WAND, а Шуай Дин и Торстен Зуэль в 2011-м — хранить потолки не на весь список, а на каждый блок. Такой block-max WAND вошёл в Lucene 8.0 и Elasticsearch 7.0 в 2019 году. Разработчики Elasticsearch сообщили об ускорении запросов из одного термина в 3–7 раз. Плата — точное число найденных документов: пропущенные документы никто не считал. Поэтому Elasticsearch с версии 7.0 по умолчанию считает совпадения точно только до 10 000, а дальше отвечает «не меньше 10 000».

Код

Первый листинг работает с тем же индексом каталога, что и сцена: BM25 «термин за термином», три лучших по MaxScore, пересечение двумя пальцами и размер списков до и после сжатия. Индекс — снимок: 77 статей, какими они были 16 октября 2026 года.

Второй строит индекс предложений «Войны и мира» и пересекает списки тремя способами. Вывод — та же таблица, что выше, и те же числа, что показывает сцена с прыжками.

В обоих листингах индекс — словарь списков в памяти. Для текстов, которые не помещаются в память, его строят иначе: выписывают пары «термин, документ», сортируют их кусками и сливают — так строили индекс и первые веб-поисковики. Lucene пишет маленькие неизменяемые сегменты — каждый сам себе индекс — и в фоне сливает их в большие, как LSM-дерево. Удалённый документ не вычёркивается из списков, а помечается и исчезает при следующем слиянии.

Сколько это стоит

Построение — один проход по всем словам, O(число слов) с хеш-таблицей в памяти; на диске — сортировка пар. Память — O(число пар «термин, документ»): в каталоге 43 805 пар на 119 076 слов, около двух байт на пару после сжатия. Позиции слов, нужные для поиска фраз, добавили бы по записи на каждое слово текста.

Запрос «все слова» — O(m·log(n/m)) на каждый список, где m — длина самого короткого, если пересекать галопом, и O(m + n) двумя пальцами. Ранжирование «термин за термином» — O(сумма длин списков слов запроса), плюс выбор k лучших кучей — O(T·log k) для T затронутых документов. MaxScore и WAND в худшем случае не лучше, но на живых запросах пропускают большую часть длинных списков.

Слабые места — в том, что индекс знает только слова. «Куча» и «очередь с приоритетом» для него не связаны. Опечатка — другой термин, и нужны отдельные приёмы: n-граммы или поиск с редакционным расстоянием. Фраза «двоичный поиск» и слова «поиск», «двоичный» в разных абзацах для индекса без позиций одинаковы. Поэтому рядом с BM25 часто ставят векторный поиск по смыслу и смешивают выдачи двух систем.

Где работает

Поисковые библиотеки. Lucene и построенные на нём Elasticsearch, OpenSearch и Solr хранят именно такие списки, сжатые блоками, с указателями пропуска, и ранжируют по BM25 — по умолчанию с Lucene 6.0 в 2016 году, до этого там был вариант TF-IDF.

Базы данных. В SQLite полнотекстовая таблица FTS5 — инвертированный индекс, а функция bm25() возвращает оценку с минусом, чтобы ORDER BY bm25(t) по возрастанию выдавал лучшие первыми. В PostgreSQL полнотекстовый поиск опирается на GIN-индекс — тоже инвертированный — над столбцом tsvector, но ранжирует своими функциями ts_rank, не BM25.

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

История

Первый указатель слов к большому тексту — конкорданцию латинской Библии — в 1230–1240-х годах составили монахи-доминиканцы под руководством Гуго Сен-Шерского. Номеров стихов тогда ещё не было, и ссылка выглядела как книга, глава и буква от a до g — одна из семи частей главы. Это список вхождений с грубыми позициями. Карен Спарк Джонс в 1972 году предложила взвешивать слова по редкости — то, что потом назвали idf. Вероятностную модель, из которой вышла BM25, развивали Стивен Робертсон и Карен Спарк Джонс с 1976 года. Сама формула появилась в отчёте команды Okapi на TREC-3 в 1994 году.

Алгоритмы для списков шли параллельно. Слияние Хвана и Линя — 1972 год. Поиск прыжками в неограниченном массиве описали Джон Бентли и Эндрю Яо в 1976 году. Указатели пропуска в инвертированных файлах — Моффат и Зобель, 1996. Адаптивное пересечение множеств, где число шагов зависит от того, как перемешаны списки, — Эрик Демейн, Алехандро Лопес-Ортис и Иэн Манро, 2000. MaxScore, WAND и block-max WAND — 1995, 2003 и 2011 годы.

Задачи