data-structures
Trie (Prefix Tree / Radix Tree)

Introductie tot Trie

Heb je je ooit afgevraagd hoe de zoekmachines werken? Hoe plaatst Google miljoenen resultaten voor u in slechts enkele milliseconden? Hoe komt een enorme database op duizenden kilometers afstand van u te weten welke informatie u zoekt en stuurt u deze terug? De reden hiervoor is niet alleen mogelijk door sneller internet en supercomputers te gebruiken. Sommige betoverende zoekalgoritmen en gegevensstructuren werken erachter. Een van hen is Trie .

Trie , ook wel digitale boom en soms radixboom of prefixboom genoemd (omdat ze op prefixen kunnen worden doorzocht), is een soort zoekboom - een geordende boomgegevensstructuur die wordt gebruikt om een dynamische set of associatieve array op te slaan waar de sleutels zich bevinden meestal tekenreeksen. Het is een van die gegevensstructuren die eenvoudig kunnen worden geïmplementeerd. Stel dat u een enorme database met miljoenen woorden hebt. U kunt trie gebruiken om deze informatie op te slaan en de complexiteit van het zoeken in deze woorden hangt alleen af van de lengte van het woord waarnaar we zoeken. Dat betekent dat het niet afhangt van hoe groot onze database is. Is dat niet geweldig?

Laten we aannemen dat we een woordenboek hebben met deze woorden:

algo
algea
also
tom
to

We willen dit woordenboek zo opslaan dat we gemakkelijk het woord kunnen vinden waarnaar we op zoek zijn. Een van de methoden zou zijn om de woorden lexicografisch te sorteren - hoe de echte woordenboeken woorden opslaan. Dan kunnen we het woord vinden door een binaire zoekopdracht uit te voeren . Een andere manier is om Prefix Tree of Trie te gebruiken , kortom. Het woord 'Trie' komt van het woord Re trie val. Hier, prefix duidt het voorvoegsel van de string die kan worden omschreven als volgt: Alle substrings die kunnen worden gemaakt vanaf het begin van een string worden genoemd prefix. Bijvoorbeeld: 'c', 'ca', 'cat' zijn allemaal het voorvoegsel van de string 'cat'.

Laten we nu teruggaan naar Trie . Zoals de naam al doet vermoeden, maken we een boomstructuur. Eerst hebben we een lege boom met alleen de wortel:

We voegen het woord 'algo' in . We maken een nieuw knooppunt en noemen de rand tussen deze twee knooppunten 'a' . Van het nieuwe knooppunt maken we een andere rand met de naam 'l' en verbinden deze met een ander knooppunt. Op deze manier maken we twee nieuwe randen voor 'g' en 'o' . Merk op dat we geen informatie opslaan in de knooppunten. Voor nu zullen we alleen overwegen om nieuwe randen te maken van deze knooppunten. Laten we vanaf nu een rand met de naam 'x' noemen - edge-x

Nu willen we het woord 'algea' toevoegen . We hebben een edge-a van root nodig, die we al hebben. We hoeven dus geen nieuwe rand toe te voegen. Op dezelfde manier hebben we een rand van 'a' naar 'l' en 'l' naar 'g' . Dat betekent dat 'alg' al in de trie zit . We voegen er alleen edge-e en edge-a aan toe.

We voegen het woord 'ook' toe . We hebben het voorvoegsel 'al' van root. We voegen er alleen 'zo' aan toe.

Laten we 'tom' toevoegen . Deze keer maken we een nieuwe voorsprong vanuit root omdat we nog geen voorvoegsel van tom hebben gemaakt.

Hoe moeten we nu 'aan' toevoegen ? 'to' is volledig een voorvoegsel van 'tom' , dus we hoeven geen rand toe te voegen. Wat we kunnen doen, is dat we eindmarkeringen in sommige knooppunten kunnen plaatsen. We plaatsen eindmarkeringen in die knooppunten waar ten minste één woord is voltooid. Groene cirkel geeft het eindpunt aan. De trie ziet eruit als:

U kunt gemakkelijk begrijpen waarom we de eindmerken hebben toegevoegd. We kunnen de in trie opgeslagen woorden bepalen. De tekens staan aan de randen en knooppunten bevatten de eindmarkeringen.

Nu vraagt u zich misschien af, wat is het doel van het opslaan van dit soort woorden? Laten we zeggen dat u wordt gevraagd het woord 'alice' in het woordenboek te vinden. Je doorkruist de trie. Je zult controleren of er een edge-a van root is. Controleer vervolgens vanaf 'a' of er een edge-l is . Daarna zult u geen edge-i meer vinden , dus u kunt tot de conclusie komen dat het woord alice niet voorkomt in het woordenboek.

Als je wordt gevraagd om het woord 'alg' in het woordenboek te vinden, doorloop je root-> a , a-> l , l-> g , maar aan het einde vind je geen groene knoop. Het woord bestaat dus niet in het woordenboek. Als u naar 'tom' zoekt, komt u in een groen knooppunt, wat betekent dat het woord in het woordenboek voorkomt.

complexiteit:

Het maximale aantal stappen dat nodig is om naar een woord in een trie te zoeken, is de lengte van het woord waarnaar we op zoek zijn. De complexiteit is O (lengte) . De complexiteit voor het invoegen is hetzelfde. De hoeveelheid geheugen die nodig is om trie te implementeren, is afhankelijk van de implementatie. We zullen een implementatie te zien in een ander voorbeeld waar we 10 ⁶ karakters (geen woorden, letters) kunt opslaan in een trie.

Gebruik van Trie:

• Een woord in het woordenboek invoegen, verwijderen en zoeken.
• Om erachter te komen of een string een prefix is van een andere string.
• Om erachter te komen hoeveel strings een gemeenschappelijk voorvoegsel heeft.
• Suggestie van namen van contactpersonen in onze telefoons, afhankelijk van het voorvoegsel dat we invoeren.
• Uitzoeken van 'Langste Common Substring' van twee strings.
• De lengte van 'Common Prefix' achterhalen voor twee woorden met 'Longest Common Ancestor'

Implementatie van Trie

Voordat u dit voorbeeld leest, wordt het ten zeerste aanbevolen om eerst Inleiding tot Trie te lezen.

Een van de eenvoudigste manieren om Trie te implementeren, is het gebruik van de gekoppelde lijst.

Knooppunt:

De knooppunten zullen bestaan uit:

1. Variabel voor eindmarkering.
2. Pointer Array naar het volgende knooppunt.

De variabele Eindpunt geeft eenvoudig aan of het een eindpunt is of niet. De aanwijzerarray geeft alle mogelijke randen aan die kunnen worden gemaakt. Voor Engelse alfabetten is de grootte van de array 26, omdat er maximaal 26 randen kunnen worden gemaakt vanuit een enkel knooppunt. Helemaal aan het begin is elke waarde van pointer array NULL en is de variabele eindmarkering false.

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

Elk element in de volgende [] array verwijst naar een ander knooppunt. volgende [0] wijst naar de knoop die rand-a deelt, volgende [1] wijst naar de knoop die rand-b deelt enzovoort. We hebben de constructor van Node gedefinieerd om Endmark te initialiseren als false en NULL in alle waarden van de volgende [] pointer array te plaatsen.

Om Trie te maken, moeten we eerst root instantiëren. Vervolgens maken we vanuit de root andere knooppunten om informatie op te slaan.

Invoeging:

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

Hier werken we met az . Dus om hun ASCII-waarden te converteren naar 0-25 , trekken we de ASCII-waarde van 'a' ervan af. We zullen controleren of het huidige knooppunt (curr) een rand heeft voor het karakter bij de hand. Als dit het geval is, gaan we met die rand naar het volgende knooppunt, anders maken we een nieuw knooppunt. Aan het einde veranderen we het eindmerk in true.

Zoeken:

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

Het proces is vergelijkbaar met invoegen. Aan het einde geven we het eindmerk terug . Dus als het eindmerk waar is, betekent dit dat het woord in het woordenboek voorkomt. Als het onwaar is, bestaat het woord niet in het woordenboek.

Dit was onze belangrijkste implementatie. Nu kunnen we elk woord in trie invoegen en ernaar zoeken.

verwijdering:

Soms moeten we de woorden wissen die niet langer worden gebruikt om geheugen te besparen. Voor dit doel moeten we de ongebruikte woorden verwijderen:

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

Deze functie gaat naar alle onderliggende knooppunten van curr , verwijdert ze en vervolgens wordt curr verwijderd om het geheugen vrij te maken. Als we delete (root) aanroepen, wordt de hele Trie verwijderd .

Trie kan ook worden geïmplementeerd met Arrays .