Экспоненциальный поиск

Обычный двоичный поиск начинает с вопроса «где середина?» — и для этого надо знать, где конец. А конец известен не всегда. Сломалась страница, и известно только, что в последней версии она сломана; хорошей версии никто не помнит. Журнал растёт, и его длины не знает никто. Ниже настоящая история этого сайта, 904 коммита, и вопрос «когда появилась эта часть сайта?». Поиск идёт от последнего коммита назад шагами 1, 2, 4, 8, … пока не найдёт коммит, где этой части ещё нет, — и только потом делит пополам.

Каталог алгоритмов появился в третьем с конца коммите, и поиск назад находит это место за 4 проверки, а git bisect по всей истории — за 10. Зато учебник математики появился 420 коммитов назад, и там поиску назад нужно 18 проверок против 10. Цена такого поиска зависит не от длины истории, а от того, как далеко ответ. Если ответ близко — выгодно; если граница неизвестна вовсе — это единственный способ.

Идея

Экспоненциальный поиск состоит из двух фаз. Сначала шаги удваиваются: проверяем позиции 1, 2, 4, 8, … пока ответ не окажется позади. Теперь искомое лежит между последней и предпоследней проверкой, на отрезке от 2^k−1 до 2^k, и его находит обычный двоичный поиск. Обе фазы занимают примерно log₂ i шагов, где i — позиция ответа, и длина данных нигде не участвует.

Его называют ещё поиском удвоением и галопом. Галоп — тот же приём, когда искать нужно не с начала, а от места, где остановились в прошлый раз: так Timsort сливает серии, а поисковый индекс пересекает списки вхождений. Оба случая разобраны в статьях о Timsort и об инвертированном индексе. Здесь — сам поиск и то, сколько вопросов ему нужно.

Сколько вопросов

Поставим задачу в чистом виде. Загадано целое x ≥ 1, верхней границы нет, а спрашивать можно только о сравнении x с числом. Удвоение спрашивает «x < 2?», «x < 4?», «x < 8?», … пока не услышит «да», а потом выясняет остальные двоичные цифры x по одной, спрашивая «x ≥ t?» для середины оставшегося отрезка.

Запишем ответы: «да» — 1, «нет» — 0. Сначала m нулей и единица, потом m младших цифр x. Это x в двоичной записи, перед которой стоит столько нулей, сколько у x цифр после первой. Такую запись придумал Питер Элиас в 1975 году и назвал её кодом γ. Ответы поиска и есть код числа. Попробуйте сами: загадайте число, и сцена покажет вопросы и строку ответов.

Второй ряд в сцене — улучшение Джона Бентли и Эндрю Яо. Удвоение тратит половину вопросов на то, чтобы узнать, сколько у x цифр, — а это число m + 1 само можно найти тем же удвоением, быстрее. Бентли и Яо так и делают: сначала поиском удвоением находят число цифр, задавая вопросы «x < 2^2j−1?» и затем «x ≥ 2^t−1?», потом выясняют цифры самого x. Ответы складываются в код δ того же Элиаса, и вопросов выходит ⌊log₂ x⌋ + 2⌊log₂(⌊log₂ x⌋ + 1)⌋ + 1: для 10¹⁸ — 70 вместо 119. Идею можно повторять и дальше — число цифр числа цифр, — и каждый уровень снимает ещё немного.

Сколько нужно на самом деле

Двоичный поиск на известном отрезке длины N тратит log₂ N вопросов, и меньше нельзя. Без границы можно ли обойтись log₂ x вопросами и небольшой добавкой? Нельзя, и это видно как раз через коды.

Любой способ задавать вопросы-сравнения без границы, который всегда находит x, задаёт для каждого x свою строку ответов. Эти строки образуют префиксный код: если строка для x — начало строки для y, то после этих ответов поиск остановился бы с ответом x, хотя мог быть и y.

Пусть какой-то поиск тратит на x не больше log₂ x + c вопросов. Тогда 2^−ℓ_x ≥ 2^−c/x, а сумма Σ 1/x бесконечна — неравенство Крафта нарушено. Значит, такого поиска нет. Тот же довод отсекает и log₂ x + log₂ log₂ x + c: сумма Σ 1/(x log₂ x) тоже бесконечна. Её кусок от 2^k до 2^k+1 содержит 2^k слагаемых не меньше 1/(2^k+1(k + 1)), то есть не меньше 1/(2(k + 1)), а сумма таких кусков — половина гармонического ряда. А вот Σ 1/(x (log₂ x)²) конечна, и код δ с его двумя логарифмами логарифма помещается в неравенство с запасом. Граница между возможным и невозможным проходит через то, какие ряды сходятся.

Код

Листинг делает оба дела. Поиск назад от последнего коммита сравнивается с git bisect по всей истории. Потом загаданные числа угадываются удвоением и способом Бентли и Яо, и строки ответов сверяются с кодами γ и δ: программа проверяет, что они совпадают символ в символ.

part of the site               first  back from HEAD  bisect all
the maths textbook               483              18          10
the Computer Science course      674              16          10
the Rubik's cube tutorial        415              18          10
the black hole visualisation     652              16          10
this algorithms catalog          901               4          10

            hidden x  doubling  Bentley-Yao  floor log2 x
                   1         1            1             0
                   2         3            4             1
                   5         5            5             2
                 100        13           11             6
             1000000        39           28            19
       1000000000000        79           50            39
 1000000000000000000       119           70            59

У маленьких чисел способ Бентли и Яо иногда даже проигрывает: для 2 ему нужно 4 вопроса против 3. Выигрыш начинается с чисел в сотни и растёт: на 10¹⁸ — 70 вопросов против 119 при 60 цифрах в самом числе.

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

Удвоение выгоднее двоичного поиска по всему отрезку, когда ответ ближе, чем примерно √N от начала: 2 log₂ i < log₂ N ровно тогда, когда i < √N. На истории из 904 коммитов это первые три десятка коммитов от конца. Памяти поиск не требует, а каждая проверка обращается к данным один раз — это важно, когда проверка дорогая: собрать версию, скачать страницу, прочитать блок с диска.

Где работает

• Поиск сломавшей версии. Если хорошая версия неизвестна, шаги назад 1, 2, 4, … от сломанной находят её, а дальше работает обычный git bisect. Если поломка свежая, это ещё и быстрее.
• Галоп. Слияние серий в Timsort и пересечение списков вхождений в поисковом индексе ищут следующий элемент не с начала, а от предыдущего, — и платят логарифм расстояния, а не всего списка.
• Двоичный поиск по ответу без границы. Когда неизвестно, насколько большим может быть ответ, его верхнюю границу находят удвоением, а потом ищут двоичным поиском по ответу.
• Замеры. timeit.Timer.autorange в Python подбирает число повторений: пробует 1, 2, 5, 10, 20, 50, … пока замер не займёт хотя бы 0,2 секунды. Так же эмпирическую сложность меряют на размерах, которые растут вдвое.
• Сжатие. Коды Элиаса γ и δ — те самые строки ответов — сжимают промежутки между номерами в поисковых индексах: маленькие числа получают короткие коды, большие — подлиннее, и разделители не нужны. Об этом задача статьи.

История

В 1975 году Питер Элиас в статье о «универсальных» кодах целых чисел построил коды γ и δ и показал, что их длина почти наименьшая из возможных. Через год Джон Бентли и Эндрю Яо в заметке «Почти оптимальный алгоритм поиска без границы» посмотрели на ту же задачу как на поиск: описали удвоение, свой улучшенный способ и бесконечную лестницу дальнейших улучшений и доказали, что лучше в принципе почти нельзя. Связь поиска с префиксными кодами, которая стоит за этой нижней оценкой, — пример того, как теория информации отвечает на вопросы о сравнениях.

Задачи

В задаче список вхождений слова в «Войну и мир» сжат кодами δ — строками ответов поиска Бентли и Яо, — и его нужно раскодировать, читая коды без разделителей.