data-structures
Trie (drzewo prefiksowe / drzewo Radix)

Wprowadzenie do Trie

Czy zastanawiałeś się kiedyś, jak działają wyszukiwarki? W jaki sposób Google przedstawia miliony wyników przed Tobą w zaledwie kilka milisekund? W jaki sposób ogromna baza danych oddalona o tysiące mil od Ciebie znajduje informacje, których szukasz, i odsyła je z powrotem? Przyczyna tego nie jest możliwa tylko przy użyciu szybszego Internetu i superkomputerów. Działają za nim niektóre hipnotyzujące algorytmy wyszukiwania i struktury danych. Jednym z nich jest Trie .

Trie , zwane także drzewem cyfrowym, a czasem drzewem radix lub drzewem prefiksu (ponieważ można je wyszukiwać za pomocą prefiksów), jest rodzajem drzewa wyszukiwania - uporządkowanej struktury danych drzewa, która służy do przechowywania zestawu dynamicznego lub tablicy asocjacyjnej, w której znajdują się klucze zwykle struny. Jest to jedna z tych struktur danych, które można łatwo wdrożyć. Załóżmy, że masz ogromną bazę milionów słów. Możesz użyć trie do przechowywania tych informacji, a złożoność wyszukiwania tych słów zależy tylko od długości szukanego słowa. Oznacza to, że nie zależy to od wielkości naszej bazy danych. Czy to nie jest niesamowite?

Załóżmy, że mamy słownik z tymi słowami:

algo
algea
also
tom
to

Chcemy przechowywać ten słownik w pamięci w taki sposób, abyśmy mogli łatwo znaleźć szukane słowo. Jedna z metod polegałaby na sortowaniu słów leksykograficznie - w jaki sposób słowniki w prawdziwym życiu przechowują słowa. Następnie możemy znaleźć słowo, przeprowadzając wyszukiwanie binarne . Innym sposobem jest użycie drzewa Prefiks lub Trie , w skrócie. Słowo „Trie” pochodzi od słowa Re trie val. Tutaj przedrostek oznacza przedrostek łańcucha, który można zdefiniować w następujący sposób: Wszystkie podciągi, które można utworzyć zaczynając od początku łańcucha, nazywane są przedrostkiem. Na przykład: „c”, „ca”, „cat” wszystkie są prefiksem ciągu „cat”.

Wróćmy teraz do Trie . Jak sama nazwa wskazuje, stworzymy drzewo. Na początku mamy puste drzewo z samym korzeniem:

Wstawimy słowo „algo” . Utworzymy nowy węzeł i nazwiemy krawędź między tymi dwoma węzłami „a” . Z nowego węzła utworzymy kolejną krawędź o nazwie „l” i połączymy ją z innym węzłem. W ten sposób utworzymy dwie nowe krawędzie dla „g” i „o” . Zauważ, że nie przechowujemy żadnych informacji w węzłach. Na razie rozważymy tworzenie nowych krawędzi tylko z tych węzłów. Od teraz nazwijmy krawędź o nazwie „x” - edge-x

Teraz chcemy dodać słowo „algea” . Potrzebujemy edge-a od roota, który już mamy. Więc nie musimy dodawać nowej krawędzi. Podobnie mamy krawędź od „a” do „l” i „l” do „g” . Oznacza to, że „ALG” jest już w trie. Dodamy tylko edge-e i edge-a .

Dodamy słowo „również” . Mamy przedrostek „al” z katalogu głównego. Dodamy tylko „tak” .

Dodajmy „tom” . Tym razem tworzymy nową krawędź od roota, ponieważ nie mamy wcześniej utworzonego prefiksu tomu.

Jak teraz dodać „do” ? „to” jest całkowicie prefiksem „tom” , więc nie musimy dodawać żadnej krawędzi. Co możemy zrobić, możemy umieścić znaki końcowe w niektórych węzłach. Umieścimy znaki końcowe w tych węzłach, w których co najmniej jedno słowo jest uzupełnione. Zielone kółko oznacza znak końca. Trie będzie wyglądać następująco:

Możesz łatwo zrozumieć, dlaczego dodaliśmy znaki końcowe. Możemy określić słowa zapisane w trie. Znaki będą na krawędziach, a węzły będą zawierać znaki końcowe.

Teraz możesz zapytać, jaki jest cel przechowywania takich słów? Powiedzmy, że jesteś poproszony o znalezienie słowa „alicja” w słowniku. Przemierzasz trie. Sprawdzisz, czy istnieje root -a od roota. Następnie sprawdź od „a” , czy jest krawędź-l . Po tym nie znajdziesz żadnej krawędzi-i , więc możesz dojść do wniosku, że słowo alicja nie istnieje w słowniku.

Jeśli zostaniesz poproszony o znalezienie słowa „alg” w słowniku, przejdziesz przez root- > a , a-> l , l-> g , ale na końcu nie znajdziesz zielonego węzła. Więc słowo nie istnieje w słowniku. Jeśli wyszukasz „tom” , skończysz w zielonym węźle, co oznacza, że słowo istnieje w słowniku.

Złożoność:

Maksymalna liczba kroków potrzebnych do wyszukania słowa w trie to długość szukanego słowa. Złożoność wynosi O (długość) . Złożoność wstawiania jest taka sama. Ilość pamięci potrzebnej do wdrożenia trie zależy od implementacji. Zobaczymy implementację w innym przykładzie, w którym możemy przechowywać 10 ⁶ znaków (nie słów, liter) w trie .

Zastosowanie Trie:

• Aby wstawić, usunąć i wyszukać słowo w słowniku.
• Aby dowiedzieć się, czy ciąg znaków jest prefiksem innego ciągu.
• Aby dowiedzieć się, ile ciągów ma wspólny przedrostek.
• Sugestie dotyczące nazw kontaktów w naszych telefonach w zależności od wprowadzanego prefiksu.
• Znalezienie „najdłuższego wspólnego podłańcucha” dwóch łańcuchów.
• Ustalanie długości „wspólnego prefiksu” dla dwóch słów za pomocą „najdłuższego wspólnego przodka”

Wdrożenie Trie

Przed przeczytaniem tego przykładu zdecydowanie zaleca się przeczytanie Wprowadzenie do Trie .

Jednym z najprostszych sposobów implementacji Trie jest użycie listy połączonej.

Węzeł:

Węzły będą się składały z:

1. Zmienna dla znaku końca.
2. Tablica wskaźników do następnego węzła.

Zmienna End-Mark będzie po prostu oznaczać, czy jest to punkt końcowy, czy nie. Tablica wskaźników będzie oznaczać wszystkie możliwe krawędzie, które można utworzyć. W przypadku alfabetu angielskiego rozmiar tablicy wyniesie 26, ponieważ z jednego węzła można utworzyć maksymalnie 26 krawędzi. Na samym początku każda wartość tablicy wskaźników będzie równa NULL, a zmienna znacznika końcowego będzie fałszywa.

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

Każdy element w tablicy następnej [] wskazuje na inny węzeł. next [0] wskazuje na węzeł współdzielący edge-a , next [1] wskazuje na węzeł współdzielący edge-b i tak dalej. Zdefiniowaliśmy konstruktor węzła, aby inicjalizować Endmark jako fałsz i umieścić NULL we wszystkich wartościach tablicy wskaźników next [] .

Aby utworzyć Trie , najpierw musimy utworzyć instancję roota . Następnie z katalogu głównego utworzymy inne węzły do przechowywania informacji.

Wprowadzenie:

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

Tutaj pracujemy z az . Aby więc przekonwertować ich wartości ASCII na 0-25 , odejmujemy od nich wartość ASCII „a” . Sprawdzimy, czy bieżący węzeł (curr) ma krawędź dla dostępnego znaku. Jeśli tak, przechodzimy do następnego węzła, używając tej krawędzi, jeśli nie, tworzymy nowy węzeł. Na koniec zmieniamy znak końcowy na true.

Badawczy:

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

Proces jest podobny do wstawiania. Na koniec zwracamy znak końcowy . Jeśli więc znak końcowy jest prawdziwy, oznacza to, że słowo istnieje w słowniku. Jeśli jest to fałsz, to słowo nie istnieje w słowniku.

To było nasze główne wdrożenie. Teraz możemy wstawić dowolne słowo w trie i wyszukać je.

Usunięcie:

Czasami będziemy musieli usunąć słowa, które nie będą już używane do oszczędzania pamięci. W tym celu musimy usunąć nieużywane słowa:

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

Ta funkcja przechodzi do wszystkich węzłów potomnych curr , usuwa je, a następnie curr jest usuwany w celu zwolnienia pamięci. Jeśli nazwiemy delete (root) , usunie całą Trie .

Trie można również zaimplementować za pomocą tablic .