Бор

Обратимся снова к поиску слова в словаре. Во всех нормальных словарях на правой границе написаны буквы (а в некоторых даже вырублены засечки), с помощью которых можно мгновенно найти место, где начинаются слова на определенную букву. Я однажды увидел справочник, в котором справа были вырублены первые буквы слов, а сверху — вторые. Таким образом в этом справочнике можно мгновенно найти блок слов по первой букве, а в нём подблок слов по второй букве. У книги три свободных стороны... теоретически, можно сделать книгу, в которой можно будет искать слова до третьей буквы!

Эта идея очень просто обобщается, и из нее создается простая и лаконичная структура данных, позволяющая очень быстро искать информацию — бор. Задача поиска данных описанным методом называется лучевым поиском.

Задача лучевого поиска. Есть алфавит $\Sigma$ размера $\sigma$ . Строки $K_i \in \Sigma^*$ будут являться ключами, с которыми ассоциированы записи $R_i$ . Нужно по заданной строке $K_i$ найти ассоциированную с ней запись $R_i$ .

Будем действовать точно так же, как в тех книжках с буквенными метками. Сделаем бор.

Бор — дерево, каждое ребро которого помечено символом из $\Sigma$ . Некоторые узлы помечены терминальными, и в них хранятся записи (или ссылки на записи). Вообще, бор полностью совпадает с деревом решений при поиске в словаре по буквенным меткам.

Вот пример бора, построенного для слов a, an, ani, anime, ant, day, done, doc, dock, have, her, him.

Хранение

Разберемся пока с абстрактным представлением. В каждом узле нам нужно хранить $\sigma$ ссылок, ассоциированных с символами из алфавита $\Sigma$ . Получается, в каждом узле нам нужно хранить ассоциативный массив размера $\sigma$ , ключами которого служат символы из алфавита $\Sigma$ , а значениями — ссылки на следующие узлы.

Структура узлов получается следующая

struct node:
    assoc[char: node] children
    bool is_terminal
    some additional data if is_terminal

На каждую вершину приходится $\sigma$ ссылок, возможно пустых. Дополнительные данные типа ссылок на записи, флаг терминальности и прочее пока не рассматриваем. Получается, что бор занимает $O(\sigma m)$ , где $m$ — количество узлов.

Поиск

При поиске в боре мы повторяем те же действия, что делали бы при поиске в словаре с буквенными метками.

Начиная с корня, мы выбираем ссылку на следующий узел на основе символа в искомой строке $K$ . Заканчиваем тогда, когда закончится строка или когда нам будет некуда идти. Если мы дошли до конца строки $K$ и в итоге попали в терминальную вершину, значит строка $K$ в боре есть, и мы сможем вытащить ассоциированную с ней запись, если надо.

function find(node root, string key) -> node:
    i = 0
    while root != none and i < length(key):
        root = root.children[key[i]]
        i += 1

    if root == none:
        return not found
    else if root.is_terminal:
        return root
    else:
        return not found

Пусть длина искомой строки $K$ равна $l$ . Во время поиска строки $K$ мы потратим максимум $l$ переходов по ассоциированным ссылкам.

Вставка

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

В самом конце мы пометим вершину как терминальную и сохраним в ней всю нужную информацию, например, ссылку на запись.

function insert(node root, string key) -> node:
    for i = 0; i < length(key):
        if root.children[key[i]] == none:
            root.children[key[i]] = node()

        root = root.children[key[i]]

    root.is_terminal = true
    save some additional data at root

Анализ строк

Рассмотрим бор на алфавите $\Sigma$ размера $\sigma$ , в котором хранится $n$ строк. Давайте проанализируем количество узлов, занимаемую бором память и смежные вопросы.

Количество ветвящихся узлов

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

С точки зрения полезного анализа (сейчас и для будущего) имеет смысл рассматривать только ветвящиеся узлы. Количество узлов интересно нам в первую очередь с точки зрения оценки затрат памяти. Как мы увидим в дальнейшем, неветвящиеся хвосты и промежуточные участки имеют маленькое влияние. А их еще можно сжимать, оставляя существенными только ветвящиеся узлы.

Рассмотрим какой-то ветвящийся узел, у которого $\sigma$ подборов, в которых суммарно хранится $n$ строк.

Вероятность того, что $k_1$ строк хранится в первом подборе, $k_2$ строк хранится во втором подборе, ..., $k_\sigma$ строк хранится в $\sigma$ -м подборе, выражается через мультиномиальный коэффициент

\prob(\cdot) = \frac{1}{\sigma^n} \cdot \binom{n}{k_1 ~ k_2 ~ \cdots ~ k_n}

Зная это, можно вычислить среднее количество ветвящихся узлов бора — $M_n$ . При этом $M_0 = M_1 = 0$ , и для $n \ge 2$

M_n = 1 + \sum\limits_{k_1 + k_2 + \dotsb + k_\sigma = n} \frac{1}{\sigma^n} \cdot \binom{n}{k_1 ~ k_2 ~ \cdots ~ k_n} \cdot (L_{k_1} + L_{k_2} + \dotsb + L{k_\sigma})

Формула симметрична относительно перестановок $k_i$ , а значит

M_n = 1 + \frac{1}{\sigma^{n-1}} \sum\limits_{k=0}^n \binom{n}{k} \cdot (\sigma - 1)^{n-k} \cdot L_k

С помощью трюка с биномиальными преобразованиями последовательностей можно получить выражение без рекурсии

M_n = \sum\limits_{k=2}^n \binom{n}{k} \cdot (-1)^k \cdot \frac{k-1}{\sigma^{k-1}-1} = \frac{n}{\ln \sigma} + O(1)

Поразрядная сортировка

Если на алфавите $\Sigma$ задан линейный порядок, то на $\Sigma^*$ естественным образом задаётся лексикографический порядок. Получается, мы можем сформулировать задачу сортировки строк из $\Sigma^*$ .

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

Итак, на алфавите $\Sigma$ задан порядок. А значит, в ассоциативном массиве мы можем получать ассоциированные с ключами ссылки по возрастанию. Если структура ассоциативного массива не предполагает извлечение колючей по порядку, можно предварительно отсортировать ключи, а в ассоциативный массиве брать ссылки по ключам в этом порядке.

Поместим все строки, которые мы хотим отсортировать, в бор. А дальше просто рекурсивно ходим по бору в соответствии с заданным порядком.

Цифровой бор

Возьмем алфавит из чисел $W = \{0, 1, 2, \dotsc, w\}$ . Тогда можно взять язык $W^+ = \NN$ . На самом деле это просто по-умному записанная фраза «представим все числа в системе счисления по основанию $w$ и будем рассматривать их как строки над алфавитом $W$ ».

Теперь бор может хранить натуральные числа. Во время вставки, удаления и поиска числа $n$ нам нужно сделать $\log_w n$ переходов по ассоциированным ссылкам. Получается, эти операции работают за время $O(\log_w n)$ .

Разберем подробнее двоичную систему счисления, $w = 2$ . Бор здесь превращается в бинарное дерево: левому ребенку соответствует цифра $0$ , а правому $1$ .