Merkle-Patricia Trees. Часть 4

Что такое Patricia Trie?

Patricia Trie (также известная как Radix Tree или Compact Prefix Tree) - это тип Trie, в которую добавлены некоторые оптимизации для экономии места и потенциального повышения эффективности поиска. Название «Patricia» - это аббревиатура от «Практический алгоритм получения информации, закодированной в алфавитно-цифровом виде» (Practical Algorithm to Retrieve Information Coded in Alphanumeric).

Как работает Patricia Trie?

Patricia Trie отличается от стандартной Trie тем, что в ней сворачивается любой узел, имеющий только одного ребенка. Вместо того чтобы хранить в каждом узле один символ, Patricia Trie может хранить целые строки или их части, что значительно сокращает количество узлов.

Давайте посмотрим, как Patricia Trie обрабатывает слова: romane, romanus, romulus, rubens, ruber, rubicon, rubicundus.

Мы начинаем с пустого корневого узла. Затем мы начинаем добавлять слова:

1. Вставка слова «romane»: Trie в данный момент пуста, поэтому мы создаем новый узел, ответвляющийся от корня, который содержит строку «romane».

2. Вставка «romanus»: Мы замечаем, что «romanus» имеет общий префикс, «roman», с «romane». Поэтому мы создаем узел, ответвляющийся от «roman», который содержит суффикс «us». Мы также обновим существующую ветвь «romane», чтобы она теперь начиналась от «roman» и содержала суффикс «e».

3. Вставка «romulus»: Это слово имеет общий префикс «rom» с существующими словами. Поэтому мы добавляем ветвь от «rom», содержащую «ulus».

4. Вставка «rubens»: Это слово не имеет общей приставки с существующими словами, поэтому оно ответвляется непосредственно от корня.

5. Вставка «ruber»: «ruber» имеет общий префикс rub с rubens, поэтому мы создаем узел, ответвляющийся от rub, который содержит er. Ветвь «rubens» теперь также начинается от «rub» и содержит суффикс «ens».

6. Вставка «rubicon»: «rubicon» имеет общий префикс rubi с ruber, поэтому мы создаем узел, ответвляющийся от rubi, который содержит con.

7. Вставка «rubicundus»: Это слово имеет общий префикс «rubi» с остальными. Мы ответвляем от «rubi» и добавляем узел с «cundus».

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

#merkle #patricia