data-structures
Trie (Prefix Tree / Radix Tree)

Introduktion till Trie

Har du någonsin undrat hur sökmotorerna fungerar? Hur ställer Google upp miljontals resultat framför dig på bara några millisekunder? Hur hittar en enorm databas som ligger tusentals mil bort från dig information du söker efter och skickar dem tillbaka till dig? Anledningen till detta är inte bara möjligt genom att använda snabbare internet och superdatorer. Vissa fascinerande sökande algoritmer och datastrukturer arbetar bakom det. En av dem är Trie .

Trie , även kallad digitalt träd och ibland radixträd eller prefixträd (eftersom de kan sökas med prefix), är ett slags sökträd - en ordnad träddatastruktur som används för att lagra en dynamisk uppsättning eller associerande grupp där nycklarna är vanligtvis strängar. Det är en av de datastrukturer som enkelt kan implementeras. Låt oss säga att du har en enorm databas med miljoner ord. Du kan använda trie för att lagra denna information och komplexiteten i att söka efter dessa ord beror bara på längden på ordet som vi söker efter. Det betyder att det inte beror på hur stor vår databas är. Är det inte fantastiskt?

Låt oss anta att vi har en ordlista med dessa ord:

algo
algea
also
tom
to

Vi vill lagra denna ordlista i minnet på ett sådant sätt att vi enkelt kan ta reda på ordet vi letar efter. En av metoderna skulle involvera sortering av orden leksikografiskt - hur de verkliga ordböckerna lagrar ord. Då kan vi hitta ordet genom att göra en binär sökning . Ett annat sätt är att använda Prefix Tree eller Trie , kort sagt. Ordet 'Trie' kommer från ordet Re trie val. Här betecknar prefixet prefixet snöre som kan definieras så här: Alla strängar som kan skapas från början av en sträng kallas prefix. Till exempel: 'c', 'ca', 'cat' är alla prefixet för strängen 'cat'.

Låt oss komma tillbaka till Trie . Som namnet antyder skapar vi ett träd. Först har vi ett tomt träd med bara roten:

Vi sätter in ordet "algo" . Vi skapar en ny nod och namnger kanten mellan dessa två noder 'a' . Från den nya noden skapar vi en annan kant som heter 'l' och ansluter den till en annan nod. På detta sätt skapar vi två nya kanter för 'g' och 'o' . Observera att vi inte lagrar någon information i noderna. För tillfället överväger vi bara att skapa nya kanter från dessa noder. Låt oss nu kalla en kant med namnet 'x' - kant-x

Nu vill vi lägga till ordet 'algea' . Vi behöver en kant-a från roten, som vi redan har. Så vi behöver inte lägga till ny kant. På liknande sätt har vi en kant från 'a' till 'l' och 'l' till 'g' . Det betyder att "alg" redan finns i trie . Vi lägger bara till edge-e och edge-a med det.

Vi lägger till ordet 'också' . Vi har prefixet 'al' från roten. Vi lägger bara till "så" med det.

Låt oss lägga till "tom" . Den här gången skapar vi en ny kant från roten eftersom vi inte har något prefix för tom skapat tidigare.

Hur ska vi nu lägga till "till" ? 'till' är helt ett prefix av 'tom' , så vi behöver inte lägga till någon kant. Det vi kan göra är att vi kan sätta slutmärken i vissa noder. Vi sätter slutmärken i de noder där minst ett ord är slutfört. Grön cirkel anger slutmärket. Trie kommer att se ut:

Du kan lätt förstå varför vi lagt till slutmärkena. Vi kan bestämma orden lagrade i trie. Tecknen finns på kanterna och noderna kommer att innehålla slutmärken.

Nu kanske du frågar, vad är syftet med att lagra ord som detta? Låt oss säga att du ombeds hitta ordet "alice" i ordboken. Du går igenom trijen. Du kontrollerar om det finns en kant-a från roten. Kontrollera sedan från "a" , om det finns en kant-l . Efter det hittar du inget edge-i , så du kan komma till slutsatsen att ordet alice inte finns i ordboken.

Om du blir ombedd att hitta ordet 'alg' i ordboken går du igenom root-> a , a-> l , l-> g , men du hittar inte en grön nod i slutet. Så ordet finns inte i ordboken. Om du söker efter "tom" hamnar du i en grön nod, vilket betyder att ordet finns i ordboken.

Komplexitet:

Den maximala mängden steg som behövs för att söka efter ett ord i en trie är längden på ordet som vi letar efter. Komplexiteten är O (längd) . Komplexiteten för införande är densamma. Hur mycket minne som behövs för att implementera trie beror på implementeringen. Vi ser en implementering i ett annat exempel där vi kan lagra 10 ⁶ tecken (inte ord, bokstäver) i en trie .

Användning av Trie:

• För att infoga, ta bort och söka efter ett ord i ordboken.
• För att ta reda på om en sträng är ett prefix för en annan sträng.
• För att ta reda på hur många strängar som har ett gemensamt prefix.
• Förslag på kontaktnamn i våra telefoner beroende på prefixet vi anger.
• Ta reda på "Längsta vanliga underlag" av två strängar.
• Ta reda på längden på "Common Prefix" för två ord med "Longest Common Ancestor"

Implementering av Trie

Innan du läser detta exempel rekommenderas det starkt att du läser Introduktion till Trie först.

Ett av de enklaste sätten att implementera Trie är att använda länkad lista.

Nod:

Noderna kommer att bestå av:

1. Variabel för slutmärke.
2. Pekaren Array till nästa nod.

End-Mark variabeln anger helt enkelt om det är en slutpunkt eller inte. Pekarrayen anger alla möjliga kanter som kan skapas. För engelska alfabet är storleken på matrisen 26, eftersom maximalt 26 kanter kan skapas från en enda nod. I början kommer varje värde på pekarrayen att vara NULL och ändmarkeringsvariabeln är falsk.

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

Varje element i nästa array [] pekar på en annan nod. nästa [0] pekar på noddelningskant -a , nästa [1] pekar mot noddelningskant -b och så vidare. Vi har definierat Node-konstruktören för att initiera Endmark som falskt och lägga NULL i alla värden för nästa [] pekarray.

För att skapa Trie , till en början måste vi anpassa roten . Sedan kommer vi från roten att skapa andra noder för att lagra information.

Införande:

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

Här arbetar vi med az . Så för att konvertera deras ASCII-värden till 0-25 , subtraherar vi ASCII-värdet för 'a' från dem. Vi kontrollerar om den aktuella noden (curr) har en kant för det tecken som finns. Om det gör det, flyttar vi till nästa nod med den kanten, om det inte skapar vi en ny nod. I slutet ändrar vi ändmärket till sant.

Sökande:

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

Processen liknar insättningen. I slutet returnerar vi ändmärket . Så om slutmärket är sant, betyder det att ordet finns i ordboken. Om det är falskt finns det inte ordet i ordboken.

Detta var vår viktigaste implementering. Nu kan vi infoga valfritt ord i trie och söka efter det.

Radering:

Ibland måste vi radera orden som inte längre kommer att användas för att spara minne. För detta ändamål måste vi ta bort de oanvända orden:

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

Den här funktionen går till alla barnnoder i curr , raderar dem och sedan raderas curr för att frigöra minnet. Om vi kallar delete (root) kommer det att ta bort hela Trie .

Trie kan implementeras med hjälp av Arrays också.