data-structures
Trie (Дерево префикса / дерево Radix)

Введение в Trie

Вы когда-нибудь задумывались над тем, как работают поисковые системы? Как Google выстраивает миллионы результатов перед вами всего за несколько миллисекунд? Как огромная база данных, расположенная за тысячи километров от вас, вы узнаете информацию, которую ищете и отправляете обратно? Причина этого невозможна только при использовании более быстрого Интернета и суперкомпьютеров. За этим стоят некоторые завораживающие алгоритмы поиска и структуры данных. Одним из них является Три .

Trie , также называемое цифровым деревом, а иногда и дерево оснований или дерево префикса (поскольку они могут быть найдены префиксами), является своего рода деревом поиска - упорядоченной структурой данных дерева, которая используется для хранения динамического набора или ассоциативного массива, где ключи обычно строки. Это одна из тех структур данных, которые можно легко реализовать. Допустим, у вас есть огромная база данных из миллионов слов. Вы можете использовать trie для хранения этой информации, и сложность поиска этих слов зависит только от длины слова, которое мы ищем. Это означает, что это не зависит от того, насколько велика наша база данных. Разве это не удивительно?

Предположим, у нас есть словарь с этими словами:

algo
algea
also
tom
to

Мы хотим сохранить этот словарь в памяти таким образом, чтобы мы могли легко найти искомое слово. Один из методов будет включать в себя сортировку слов лексикографически - как в реальных словарях хранятся слова. Затем мы можем найти слово, выполнив двоичный поиск . Другой способ - использовать Prefix Tree или Trie , короче. Слово «Trie» происходит от слова Re trie val. Здесь префикс обозначает префикс строки, который может быть определен следующим образом: все подстроки, которые могут быть созданы начиная с начала строки, называются префиксами. Например: 'c', 'ca', 'cat' все являются префиксом строки 'cat'.

Теперь вернемся к Три . Как следует из названия, мы создадим дерево. Сначала у нас есть пустое дерево только с корнем:

Мы вставим слово «algo» . Мы создадим новый узел и назовем ребро между этими двумя узлами «a» . С нового узла мы создадим еще один край с именем 'l' и подключим его к другому узлу. Таким образом, мы создадим два новых ребра для 'g' и 'o' . Обратите внимание, что мы не храним никакой информации в узлах. На данный момент мы рассмотрим только создание новых ребер из этих узлов. С этого момента давайте назовем ребро с именем 'x' - edge-x

Теперь мы хотим добавить слово «алгеба» . Нам нужен край-a от root, который у нас уже есть. Поэтому нам не нужно добавлять новый край. Точно так же мы имеем ребро от 'a' до 'l' и 'l' to 'g' . Это означает, что «alg» уже в три . Мы добавим только edge-e и edge-a .

Мы добавим слово «тоже» . У нас есть префикс «al» от root. Мы добавим только «так» .

Добавим 'tom' . На этот раз мы создаем новый корень из корня, поскольку у нас нет префикса тома, созданного ранее.

Теперь как нам добавить «к» ? 'to' является полностью префиксом 'tom' , поэтому нам не нужно добавлять никаких ребер. Что мы можем сделать, мы можем помещать конечные метки в некоторые узлы. Мы помещаем конечные метки в те узлы, где завершено хотя бы одно слово. Зеленый круг обозначает конечную метку. Три будет выглядеть так:

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

Теперь вы можете спросить, какова цель хранения таких слов? Скажем, вас попросят найти слово «alice» в словаре. Вы пройдете по трое. Вы проверите, есть ли край-a от root. Затем проверьте «a» , если есть край-l . После этого, вы не найдете ни одного края-I, так что вы можете прийти к выводу , что слово алиса не существует в словаре.

Если вас попросят найти слово «alg» в словаре, вы перейдете root-> a , a-> l , l-> g , но вы не найдете зеленый узел в конце. Таким образом, слово не существует в словаре. Если вы ищете «tom» , вы попадете в зеленый узел, что означает, что слово существует в словаре.

Сложность:

Максимальное количество шагов, необходимых для поиска слова в trie, - это длина слова, которое мы ищем. Сложность - O (длина) . Сложность для вставки такая же. Объем памяти, необходимый для реализации trie, зависит от реализации. Мы увидим реализацию в другом примере, где мы можем хранить 10 ⁶ символов (а не слова, буквы) в trie .

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

• Вставка, удаление и поиск слова в словаре.
• Чтобы узнать, является ли строка префиксом другой строки.
• Чтобы узнать, сколько строк имеет общий префикс.
• Предложение имен контактов в наших телефонах в зависимости от введенного префикса.
• Выяснение «Самая длинная общая подстрока» двух строк.
• Выяснение длины «Common Prefix» для двух слов с использованием «Longest Common Ancestor»

Реализация Trie

Прежде чем читать этот пример, настоятельно рекомендуется сначала прочитать « Введение в Trie» .

Одним из самых простых способов реализации Trie является использование связанного списка.

Узел:

Узлы будут состоять из:

1. Переменная для конечного знака.
2. Массив указателя на следующий узел.

Переменная End-Mark просто укажет, является ли она конечной точкой или нет. Массив указателя будет обозначать все возможные ребра, которые могут быть созданы. Для английских алфавитов размер массива будет 26, так как максимум 26 ребер могут быть созданы из одного узла. С самого начала каждое значение массива указателей будет равно NULL, а переменная end-mark будет ложной.

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

Каждый элемент в следующем [] массиве указывает на другой узел. next [0] указывает на край обмена узлом -a , следующий [1] указывает на общий доступ к узлу -b и так далее. Мы определили конструктор узла для инициализации Endmark как false и поместили NULL во все значения следующего [] указательного массива.

Чтобы создать Trie , сначала нам нужно создать экземпляр root . Затем из корня мы создадим другие узлы для хранения информации.

Вставка:

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

Здесь мы работаем с az . Поэтому, чтобы преобразовать их значения ASCII в 0-25 , мы вычитаем из них значение ASCII 'a' . Мы проверим, имеет ли текущий узел (curr) ребро для персонажа. Если это так, мы переходим к следующему узлу с использованием этого края, если мы не создаем новый узел. В конце мы заменим endmark на true.

Поиск:

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

Этот процесс аналогичен вставке. В конце мы возвращаем конечный результат . Поэтому, если endmark является истинным, это означает, что слово существует в словаре. Если это неверно, тогда слова не существует в словаре.

Это была наша основная реализация. Теперь мы можем вставить любое слово в trie и искать его.

Удаление:

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

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

Эта функция обращается ко всем дочерним узлам Curr, удаляет их , а затем ТОК удаляется , чтобы освободить память. Если мы назовем delete (root) , он удалит всю Trie .

Trie может быть реализован с использованием массивов .