Бор (префиксное дерево)

Наберите «нат» — и телефон уже предлагает «Наташа». Где-то лежит словарь, который по началу слова за долю миллисекунды находит все слова с этим началом и выбирает самое частое. Ниже весь словарь «Войны и мира», 47 585 разных слов, в виде бора: каждая полоса — узел, её ширина — сколько раз в романе встречаются слова, которые начинаются так. Печатайте или касайтесь полос.

Под корнем четыре почти равные полосы — «с», «н», «п» и «в»: с каждой из этих букв начинается примерно каждое десятое слово текста. По числу разных слов впереди одна «п» — 8732 слова, почти пятая часть словаря: приставки по-, при-, пере-, про- плодят слова. Наберите «нат»: три шага вниз, под узлом 49 слов, и пять лучших продолжений — от «наташа» (827 раз) до «наташей» (58) — уже лежат в узле, их не нужно искать. Отсортированному списку слов на тот же вопрос пришлось бы на каждую нажатую букву заново делать двоичный поиск — до 16 сравнений строк — и потом перебирать найденный отрезок.

Идея

Слова хранятся не целиком, а по буквам на рёбрах дерева: путь от корня до узла читается как начало слова, и слова с общим началом идут общим путём, пока не разойдутся. Узел, где слово кончается, помечен. Найти слово или все слова с данным началом — значит спуститься по буквам запроса: шагов столько, сколько в запросе букв, и размер словаря на них не влияет.

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

Узел — это начало

У каждого узла бора ровно одно начало — строка на пути от корня, — и у каждого начала любого слова словаря ровно один узел. Поэтому узлов в бору столько, сколько у словаря разных начал, плюс корень: для романа — 113 171 узел на 401 702 буквы. Это даёт простое сравнение с хеш-таблицей. Таблица находит слово целиком за одну-две пробы, но чтобы отвечать на вопросы о началах, ей пришлось бы хранить все начала как отдельные ключи — 113 170 штук, ровно по узлу на ключ. Бор хранит то же самое, только начала у него делят буквы: «наташа» не хранит заново «нат», оно лежит выше.

Всё, что известно о поддереве, можно держать в его корне. Сколько слов под узлом, сколько раз они встречаются вместе, какие пять из них самые частые — один проход снизу вверх после построения, и ответ на любое начало — спуск плюс чтение готового. Так делают подсказки в поисковиках и клавиатурах: обходить поддерево на каждое нажатие некогда. Ценой — память: пять ссылок в каждом из 113 тысяч узлов.

Остаётся решить, как узел хранит детей. Массив на весь алфавит — 33 ячейки на узел для русского — отвечает за одно обращение, но почти весь пустой: у большинства узлов один-два ребёнка. Словарь «буква → узел», как в Python, экономнее, но каждый словарь — отдельный объект. В сцене выше дети хранятся связным списком братьев, упорядоченным по буквам: у узла есть ссылка на первого ребёнка, у каждого ребёнка — на следующего брата. Весь бор умещается в несколько числовых массивов, а поиск ребёнка — короткий проход по братьям.

Бор экономит буквы, но не память

Кажется, что общие начала должны сделать бор компактнее списка слов. Замер на словаре романа говорит обратное. Слова уже лежат в памяти, и считается только структура вокруг них:

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

Сжатие: общие начала и общие окончания

Посмотрите на бор адресов сайта — переключатель «адреса сайта» в сцене. Адреса начинаются с длинных общих кусков: /en/open-source/ общий у 1584 страниц, /utilities/unit-converter/ — у 950. В обычном бору каждый такой кусок — цепочка узлов по букве, и у большинства из них по одному ребёнку. Сжатый бор сливает такие цепочки в одно ребро с подстрокой: узлами остаются только корень, концы слов и развилки. Для адресов это 12 649 узлов вместо 71 587 — в пять с половиной раз меньше. Для слов романа — 63 014 вместо 113 171: русские слова ветвятся чаще, и выигрыш меньше. Сжатый бор ещё называют радиксным деревом, а его двоичный вариант — PATRICIA, по статье Дональда Моррисона 1968 года. Маршрутизатор httprouter для Go хранит маршруты именно так, а на сжатых двоичных борах ищут самый длинный подходящий префикс в таблицах маршрутизации.

Бор делит начала, но не окончания: «белые», «белый», «белым», «белыми», «белых» и «быстрые», «быстрый», «быстрым», «быстрыми», «быстрых» — в бору это по пять узлов окончаний у каждой основы, хотя окончания одни и те же. Можно пойти дальше и склеить узлы с одинаковым будущим: если два узла оба кончают слово или оба не кончают, а их рёбра ведут по тем же буквам в одинаковые узлы, то и продолжения у них одни и те же, и хранить их дважды незачем.

Пять основ — «пьер», «граф», «дом», «стол», «полк» — и пять одинаковых окончаний: -, -а, -у, -ом, -е. В бору это 44 узла, в автомате 17 состояний: все пять основ сходятся в одно состояние, за которым лежат общие окончания. Такой граф называют минимальным ациклическим автоматом, или DAWG. Для всего словаря романа в нём 27 205 состояний — вчетверо меньше, чем узлов в бору. Русскому языку с его окончаниями это особенно выгодно: в листинге ниже видно, что набор окончаний -е, -й, -м, -ми, -х делят 94 основы. Поэтому морфологический анализатор pymorphy2 хранит словарь форм русских слов в DAWG, а поисковый движок Lucene, на котором построен Elasticsearch, держит индекс своего словаря терминов в конечном автомате — его строят минимальным, подавая слова по алфавиту. Плата — автомат умеет сказать, есть ли слово, но не может держать в узле данные одного слова: узел теперь общий для многих.

Код

Бор с подсказками на всём романе. Узел хранит словарь детей, слово, которое в нём кончается, его частоту и пять лучших продолжений. Узлы складываются в список в порядке создания: родитель всегда раньше детей, поэтому проход по этому списку с конца обходит детей раньше родителей, и подсказки собираются снизу вверх без рекурсии.

47,585 words, 401,702 letters, 113,171 trie nodes
   нат (3 steps): наташа 827, наташи 149, наташу 118, наташе 111, наташей 58
   кут (3 steps): кутузов 314, кутузова 141, кутузову 60, кутузовым 24, кутузове 4
   бор (3 steps): борис 179, бориса 66, борису 30, бородинского 25, бородинское 21

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

                           keys   letters     trie  compressed  automaton
  War and Peace, words   47,585   401,702  113,171      63,014     27,205
     94 stems end in: е й м ми х
     59 stems end in: - е й м ми х
     28 stems end in: го е й м му
  legost.in, addresses    8,966   304,172   71,587      12,649     16,112

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

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

Время бора не зависит от числа слов — только от длины запроса. Память — O(суммы длин) узлов, на практике в разы больше, чем у хеш-таблицы, если узлы — отдельные объекты. Отсортированный массив с двоичным поиском отвечает на вопросы о началах почти так же хорошо и занимает меньше всех, пока словарь не меняется; бор нужен, когда слова добавляются на ходу, когда важна цена каждого нажатия и когда нужен самый длинный префикс — как в маршрутизаторе из второй задачи.

Где работает

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

История

В 1959 году Рене де ла Брианде описал поиск в файле по ключам переменной длины с помощью дерева, где каждый уровень отвечает за очередную букву ключа. Через год Эдвард Фредкин независимо предложил ту же структуру и назвал её trie — от середины слова retrieval, «выборка»; сам он произносил это как tree. Абстрактно похожую конструкцию ещё в 1912 году описывал математик Аксель Туэ. По-русски бор называют также префиксным деревом. Сжатый двоичный бор PATRICIA Дональд Моррисон опубликовал в 1968 году.

Задачи

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