Бор: дерево, в котором путь от корня - это слово

Если ты нарисуешь бор для слов log, login, logout, ls, объяснишь, зачем узлу пометка конца слова, и скажешь, чем бор лучше хеш-таблицы и чем хуже, - листай до «Теперь сам».

Как думаешь, чем ответит хеш-таблица

В словаре миллион слов. Вопрос первый: есть ли в нём слово chmod? Хеш-таблица из раздела про хеширование отвечает за одно обращение - быстрее некуда.

Вопрос второй: какие слова словаря начинаются на ch? Прежде чем читать дальше, подумай, что придётся сделать с хеш-таблицей, чтобы на него ответить. И вопрос третий: дана строка chmodern, надо найти самое длинное слово словаря, с которого она начинается. Сколько обращений к таблице понадобится?

На что это похоже

Представь дерево каталогов на диске. Пути /usr/bin/git и /usr/bin/gzip идут вместе до каталога bin и расходятся только на последнем шаге. Каталог usr существует один раз, сколько бы файлов под ним ни лежало.

Чтобы найти файл, ты не перебираешь все файлы диска. Ты идёшь по пути: один шаг на каждое имя в нём. А команда «покажи всё, что лежит под /usr/bin» вообще не требует поиска - надо дойти до каталога и обойти его поддерево. Бор - это такое же дерево, в котором «имя каталога» - один символ.

Механизм: узлы, рёбра и пометки

Бор (его же называют префиксным деревом) - дерево, в котором каждое ребро помечено символом, из одного узла не выходит двух рёбер с одинаковым символом, а узлы, где кончаются слова набора, помечены.

Пять слов - cat, cd, chmod, chown, cp:

(корень)
   └ c
     ├ a ─ t*
     ├ d*
     ├ h ┬ m ─ o ─ d*
     │   └ o ─ w ─ n*
     └ p*

* - здесь кончается слово

На схеме буква стоит на месте узла, в который ведёт ребро с этой буквой: у каждого узла, кроме корня, ровно одно входящее ребро, и их удобно рисовать вместе. В пяти словах 17 букв, а узлов в дереве 12: буква c хранится один раз на все пять слов, ch - один раз на два.

Пометка конца нужна потому, что путь в дереве есть не только у слов, но и у всех их начал. Путь c-h-m существует, но слова chm в наборе нет. Без пометок бор не отличает «это слово» от «с этого слова что-то начинается».

В программе узел - это номер. Для каждого узла хранится словарь «символ → номер сына» и пометка:

def bor(slova):
    deti = [{}]                       # deti[v][c] - сын узла v по символу c; узел 0 - корень
    konec = [-1]                      # konec[v] - номер слова, которое кончается в v, или -1
    nomer = 0
    for w in slova:
        v = 0
        for c in w:
            if c not in deti[v]:      # такого ребра ещё нет - создаём узел
                deti.append({})
                konec.append(-1)
                deti[v][c] = len(deti) - 1
            v = deti[v][c]
        konec[v] = nomer
        nomer = nomer + 1
    return [deti, konec]

Правило

Вставка и поиск слова длины L в боре стоят L переходов и не зависят от числа слов в наборе. Слово есть в наборе, если путь по его символам существует И последний узел пути помечен. Все слова с данным началом лежат в поддереве узла, к которому это начало приводит. Память - по узлу на каждое РАЗЛИЧНОЕ начало слов набора; в худшем случае, когда общих начал нет, это сумма длин всех слов.

Разбор: поиск слова и все слова с началом

def est(deti, konec, w):
    v = 0
    for c in w:
        if c not in deti[v]:
            return False              # путь оборвался - слова нет
        v = deti[v][c]
    return konec[v] >= 0              # путь есть; слово ли это - решает пометка

def sobrat(deti, konec, v, nachalo, otvet):
    if konec[v] >= 0:
        otvet.append(nachalo)
    for c in sorted(deti[v].keys()):
        sobrat(deti, konec, deti[v][c], nachalo + c, otvet)
    return 0

def s_nachalom(deti, konec, nachalo):
    v = 0
    for c in nachalo:
        if c not in deti[v]:
            return []
        v = deti[v][c]
    otvet = []
    sobrat(deti, konec, v, nachalo, otvet)        # обходим поддерево
    return otvet

Набор - тринадцать команд: cat, cd, chmod, chown, cp, curl, cut, date, dd, df, diff, dig, du. В них 41 буква, в боре 27 узлов, не считая корня.

est("chmod")          True     пять переходов, последний узел помечен
est("chmo")           False    путь есть, пометки нет
est("ls")             False    путь оборвался на первом символе
s_nachalom("ch")      ['chmod', 'chown']
s_nachalom("d")       ['date', 'dd', 'df', 'diff', 'dig', 'du']

Ответы на вопросы из начала урока. Слова на ch хеш-таблица найти не может иначе, чем перебрав ВСЕ свои ключи: хеш слова chmod ничего не говорит о хеше слова chown. Бор делает два перехода и обходит поддерево. Для chmodern хеш-таблице нужно обращение на каждое начало строки - c, ch, chm и так далее, восемь раз, и каждое заново считает хеш от начала. Бор идёт по строке один раз и запоминает последний помеченный узел: chmod, пять переходов, на шестом путь обрывается.

def samoe_dlinnoe(deti, konec, s):
    v = 0
    dlina = 0                         # длина самого длинного слова-начала; 0 - такого нет
    i = 0
    while i < len(s) and s[i] in deti[v]:
        v = deti[v][s[i]]
        i = i + 1
        if konec[v] >= 0:
            dlina = i                 # последний помеченный узел на пути
    return s[0:dlina]

print(samoe_dlinnoe(deti, konec, "chmodern"))     # chmod

Разбор: цена памяти и сжатый бор

Скорость бора честная, а память - его слабое место. Вопрос в том, как хранить сыновей узла.

способ хранения сыновей            память на узел       переход
массив на весь алфавит             k ячеек              одно обращение
словарь (хеш-таблица)              по числу сыновей     одно обращение, но дороже
отсортированный список             по числу сыновей     двоичный поиск

Для наших 27 узлов и корня массив на 26 букв - это 28 · 26 = 728 ячеек ради 41 буквы; почти все пустые. Для Юникода массив на алфавит невозможен вовсе. Словарь в каждом узле экономит ячейки, но каждый словарь - отдельный объект со своими накладными расходами.

Второй резерв - цепочки. У узла m в слове chmod один сын, у него тоже один: развилок нет до самого конца слова. Сжатый бор склеивает такую цепочку в одно ребро с подписью-строкой: вместо m ─ o ─ d одно ребро mod. Узлы остаются только там, где путь ветвится или кончается слово. Для тринадцати команд это 18 узлов вместо 27. Правило для любого набора: у сжатого бора узлов не больше удвоенного числа слов, какой бы длины слова ни были. Каждый оставшийся узел - либо помечен, а таких не больше, чем слов, либо развилка, а развилок в дереве меньше, чем листьев. Через главу на этом свойстве будет держаться суффиксное деревоРазбирается в разделе 17, глава «Суффиксный массив, LCP и суффиксное дерево»: Суффиксное дерево: сжатый бор всех суффиксов.

Что ломается без этого

Первое: бор без пометок. Функция est возвращает True за то, что путь существует. Тогда в словаре «есть» слова c, ch, chm, chmo - все начала всех слов.

Второе: массив сыновей на большой алфавит. Память равна числу узлов, умноженному на размер алфавита. Сто тысяч узлов над байтами - 25 миллионов ячеек. Над Юникодом счёт идёт на сотню миллиардов и больше.

Третье: удаление слова сносом пути. Удаляя cd, нельзя трогать узел c: через него идут ещё шесть слов. Правильно - снять пометку, а узлы удалять с конца и только пока у узла нет сыновей и нет пометки.

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

Зачем это в работе

Первый сюжет - автодополнение. Оболочка по клавише Tab, поле поиска, редактор кода: по набранному началу надо выдать продолжения. Это буквально s_nachalom.

Второй - самое длинное совпадающее начало. Маршрутизатор выбирает маршрут для адреса 192.168.1.77: в таблице есть и 192.168.0.0/16, и 192.168.1.0/24 (число после черты - сколько первых битов адреса задают сеть), побеждает более длинный префикс. Таблицу маршрутов хранят как бор по битам адреса, и поиск - один спуск по дереву с запоминанием последнего помеченного узла.

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

Теперь сам

В бор вставили слова log, login, logout, ls. Сколько в нём узлов, не считая корня? Сколько из них помечены? Что вернёт est для строки logo и почему?

(корень)
   └ l
     ├ o ─ g* ┬ i ─ n*
     │        └ o ─ u ─ t*
     └ s*