BK-дерево

В списке ста тысяч самых частых паролей из утечек qwerty123 стоит на 310-м месте. В одной правке от него — ещё восемь паролей списка: Qwerty123, qwert123, qwerty12, qwerty1234, qwerty13… Тот, кто подбирает пароль, начинает именно с таких: частое слово и одна-две правки. Чтобы найти в словаре все слова в k правках от данного, не обязательно сравнивать его со всеми: если сложить словарь в BK-дерево, для qwerty123 при одной правке хватит 722 сравнений из 99 999. Наберите своё слово — только не настоящий пароль.

Сверху — дети корня по расстоянию от него, снизу — всё дерево: ширина куска — сколько слов под ним. Светлое — что сравнили с запросом, серое — что отбросили, не открывая. Попробуйте длинную фразу вроде correcthorsebatterystaple: до корня 123456 от неё 25 правок, а все дети корня лежат не дальше 19 — дерево отбрасывает весь список за одно сравнение. И попробуйте три правки: светлого становится больше трети.

Идея

Расстояние редактирования — наименьшее число вставок, удалений и замен букв — ведёт себя как настоящее расстояние: оно равно нулю только у одинаковых слов, симметрично и подчиняется неравенству треугольника: d(a, c) ≤ d(a, b) + d(b, c), ведь правки из a в b и из b в c вместе превращают a в c.

Возьмём любое слово корнем. Остальные разложим по расстоянию до него: на ребре 1 — поддерево слов в одной правке от корня, на ребре 2 — в двух, и так далее. В каждом поддереве повторим то же с его первым словом. Строится всё по одному слову: новое слово спускается от корня, на каждом узле считает расстояние d и идёт по ребру d; если такого ребра нет, становится новым ребёнком. Это и есть BK-дерево, по фамилиям Буркхарда и Келлера.

Если от запроса до узла d, то слова под ребром e лежат от запроса не ближе |d − e|. Поэтому для поиска в пределах k правок достаточно спускаться только по рёбрам с e от d − k до d + k — остальные поддеревья отбрасываются целиком, не открывая.

Тот же обход ищет и самого близкого соседа: радиус — расстояние до лучшего найденного, и он сужается по ходу; узлы удобно брать из очереди по нижней оценке |d − e|. Но выгода тут скромнее: на 6156 названиях городов от ста тысяч жителей поиск ближайшего к названию с одной-тремя опечатками сравнивает в среднем 27 % названий.

Ничего, кроме этих трёх свойств, дерево от расстояния не требует. Расстояние Хэмминга между перцептивными хешами картинок — числом различающихся битов — тоже метрика, и BK-деревом ищут похожие фотографии. Важно лишь, чтобы значения были целыми и небольшими: иначе у узла слишком много разных рёбер.

Код

Дерево хранится двумя списками: слово узла и словарь «расстояние → ребёнок». Листинг берёт 10 000 самых частых паролей: на Python каждое добавление стоит десятка-другого сравнений по полной таблице, и сто тысяч слов строились бы почти девять секунд. Сцена выше строит дерево из всех 99 999 так же, по порядку частоты.

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

Здесь у BK-дерева нет красивой оценки, и это главное, что о нём стоит знать. Отсечение работает, когда расстояния до узла разнообразны, а окно [d − k, d + k] узкое. У коротких паролей расстояния сбиты в кучу: у корня 123456 почти сорок тысяч слов лежат на расстоянии 6, а с 5 по 8 — больше девяноста тысяч. Окно шириной 2k + 1 при k = 2 захватывает почти всё.

Это сто запросов — частые пароли с одной случайной правкой — к дереву из 99 999 паролей. Глубина дерева — 40. Замер ниже сравнивает дерево с прямым сравнением со всеми при пределе в две правки.

На ста тысячах паролей поиск в одну правку быстрее перебора почти в шесть раз на Go, а в две — меньше чем в полтора, и на маленьких словарях дерево перебору даже проигрывает: обход и словари рёбер стоят дороже сэкономленных сравнений. Для двух и больше правок на коротких словах стоит смотреть на приёмы, которые вообще не перебирают словарь, — симметричное удаление и автомат Левенштейна по бору из статьи о расстоянии редактирования.

Где легко ошибиться

• Не метрика. Если «расстояние» нарушает неравенство треугольника, отсечение может выбросить настоящего соседа. Так ведёт себя упрощённое расстояние с перестановкой соседних букв, где переставленную пару потом нельзя править: от CA до ABC по нему три правки, а через AC — одна плюс одна. Полное расстояние Дамерау — Левенштейна — метрика, и с ним дерево работает.
• Окно не с той стороны. Спускаться нужно по рёбрам в [d − k, d + k], а не только меньше d + k: при d = 10 и k = 1 ребро 3 точно не нужно.
• Повторы. Слово на расстоянии 0 от узла — то же слово. Его не вешают ребёнком на ребро 0, иначе поиск будет находить дубликаты.
• Порядок вставки. Дерево зависит от порядка слов: отсортированный по алфавиту словарь даёт длинные цепочки похожих слов и глубокое дерево. Частотный или случайный порядок лучше.
• Рекурсия. Глубина дерева паролей — 40, а у неудачного порядка вставки бывает и тысяча. Обход со своим стеком безопаснее.

Где работает

Исправление опечаток и подсказки при одной правке; поиск похожих картинок по расстоянию Хэмминга между 64-битными перцептивными хешами — там расстояния от 0 до 64 разнообразнее, чем у коротких слов; проверка, не лежит ли новый пароль в паре правок от утёкшего. Вообще — любая целочисленная метрика, где нужны все соседи в небольшом радиусе, а свойства пространства неизвестны. Для чисел и точек есть свои деревья: k-d-дерево, а для вещественных метрик — деревья точек обзора.

История

Уолтер Буркхард и Роберт Келлер описали это дерево в 1973 году в статье «Некоторые подходы к поиску лучшего совпадения в файле» в журнале Communications of the ACM — среди нескольких способов искать в файле ключ, ближайший к запросу, по любой целочисленной метрике. Идея разложить данные по расстояниям до выбранных точек потом стала основой целого семейства метрических деревьев — деревьев точек обзора, M-деревьев. Набор из десяти миллионов паролей из утечек опубликовал в 2015 году исследователь безопасности Марк Бёрнетт; сто тысяч самых частых из него лежат в открытом списке SecLists.

Задачи

Соседи пароля: сколько слов словаря в k правках от запроса и какое из них самое частое.