Trie, или бор¶

Про сложение строк¶

Часто сложение строк называют конкатенацией, и рассматривают как бинарную математическую операцию.

Эта операция (далее $+$) обладает интересными свойствами.

• во-первых, она ассоциативна: $abc + (de + fg) = (abc + de) + fg = abcdefg$
• во-вторых, она НЕ коммутативна: $abc + def \neq def + abc$
• в третьих, у этой операции, как и у многих други бинарных операций, есть нейтральный элемент, $ε$.
  • конкатенация интуитивно "похожа" на сложение больше, чем на умножение, а $ε$ - на ноль, чем на единицу. Поэтому $ε$ скорее назовут нулем для операции конкатенации.
  • поскольку $ε + def$ не гарантированно равно $def + ε$, можно было бы сказать, что существует два нейтральных элемента: $ε_l, ε_r$ - но это не так, посокльку $ε_l = ε_l + ε_r = ε_r$
• без $ε$ множество строк над алфавитом $\Sigma$ с операцией конкатенации является полугруппой, а с $ε$ - моноидом.

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

Их также можно отнести к моноидам.

Trie¶

Trie - структура, которая (довольно неожиданно) уже встречалась нам в контексте сортировки послеовательнсотей за линейное врем. Она использовалась в одной из модификаций Radix Sort - это довольно экзотическое применение trie.

кстати, одно из названий trie - radix trie

Само название trie получилось "урезанием" слова retrieval и намекает на то, для чего используется структура.

Зачастую trie используют как ассоциативный массив для хранения информации

Если посмотреть на листья, в trie компактно упакованы следующие строки:

• TWI, TWE
• TZA, TZI
• TALL, TALK
• US
• UNI

А если добавить узлы, не являющиеся листьями -

• ε
• T, U
• TW, TZ, TA, UN
• TAL

Использование¶

За $O(m)$, где $m$ - глубина trie, можно получить информацию о том, содержится ли в нем строка, или нет.

• в общем, trie можно использовать для хранения данных
• также используется в spell checker'ах, программах для автодополнения текста
• а еще trie применяется в алгоритме Ахо-Корасик, но в модифицированном виде

К сожалению, иногда trie может "съесть" много памяти, если получилось так, что под каждый символ каждой хранимой последовательности память выделяется отдельно

Структура данных¶

Trie - рекурсивная структура данных. И ее определение рекурсивно:

struct Trie {
    value,  -- значение любого типа для хранения в узле
    children: Mapping of type (char : pointer to Trie)  -- ассоциативный массив с указателями на другие trie
}

Поскольку trie - ассоциативный массив, он должен поддердживать:

• вставку, Insert(key, value)
• удаление, Delete(key)
• поиск, Search(key)
• Опционально, поскольку Trie во многом похоже на деревья, операцию обхода Traverse

Абстрактные вопросы¶

Можно ли сделать так, чтобы множество trie'в стало

• полугруппой?
• моноидом? (ответ, еще один - см. instance Monoid)
• коммутативной полугруппой?

Сжатое префиксное дерево¶

Рассмотрим следующую ситуацию: trie испольуют, например, для задачи сохранения всех возможных суффиксов строки.

Строка: "AAABAAAB"

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

Еще один пример

Внимание, ошибка! На самом деле нет узла "упила", а еслть узел "пила", выходящий из узла "у".

</font>