data-structures
Trie (Prefix Tree / Radix Tree)

Introduzione a Trie

Ti sei mai chiesto come funzionano i motori di ricerca? Come fa Google a schierare milioni di risultati davanti a te in pochi millisecondi? Come fa un enorme database situato a migliaia di chilometri da te a trovare le informazioni che stai cercando e inviarle a te? La ragione di questo non è possibile solo usando internet e super-computer più veloci. Alcuni algoritmi di ricerca ipnotizzanti e strutture dati funzionano dietro di esso. Uno di questi è Trie .

Trie , chiamato anche albero digitale ea volte albero radice o albero prefisso (come possono essere ricercati dai prefissi), è un tipo di albero di ricerca: una struttura dati dell'albero ordinata che viene utilizzata per memorizzare un set dinamico o un array associativo in cui le chiavi sono di solito stringhe. È una di quelle strutture dati che possono essere facilmente implementate. Diciamo che hai un enorme database di milioni di parole. Puoi usare trie per memorizzare queste informazioni e la complessità della ricerca di queste parole dipende solo dalla lunghezza della parola che stiamo cercando. Ciò significa che non dipende da quanto è grande il nostro database. Non è fantastico?

Supponiamo di avere un dizionario con queste parole:

algo
algea
also
tom
to

Vogliamo memorizzare questo dizionario in memoria in modo tale che possiamo facilmente scoprire la parola che stiamo cercando. Uno dei metodi consisterebbe nell'ordinare le parole lessicograficamente: come i dizionari della vita reale memorizzano le parole. Quindi possiamo trovare la parola facendo una ricerca binaria . Un altro modo è usare Prefix Tree o Trie , in breve. La parola "Trie" deriva dalla parola Re trie val. Qui, il prefisso indica il prefisso della stringa che può essere definito in questo modo: Tutte le sottostringhe che possono essere create a partire dall'inizio di una stringa sono chiamate prefisso. Ad esempio: 'c', 'ca', 'cat' tutti sono il prefisso della stringa 'cat'.

Ora torniamo a Trie . Come suggerisce il nome, creeremo un albero. Inizialmente, abbiamo un albero vuoto con solo la radice:

Inseriremo la parola "algo" . Creeremo un nuovo nodo e nomineremo il bordo tra questi due nodi 'a' . Dal nuovo nodo creeremo un altro spigolo chiamato 'l' e lo collegheremo con un altro nodo. In questo modo, creeremo due nuovi bordi per 'g' e 'o' . Si noti che non stiamo memorizzando alcuna informazione nei nodi. Per ora, considereremo solo la creazione di nuovi bordi da questi nodi. D'ora in poi, chiamiamo uno spigolo chiamato 'x' - edge-x

Ora vogliamo aggiungere la parola "algea" . Abbiamo bisogno di un edge-a da root, che abbiamo già. Quindi non abbiamo bisogno di aggiungere un nuovo vantaggio. Allo stesso modo, abbiamo un vantaggio da 'a' a 'l' e 'l' a 'g' . Ciò significa che "alg" è già nel trie . Aggiungiamo solo edge-e e edge-a con esso.

Aggiungeremo la parola "anche" . Abbiamo il prefisso 'al' da root. Aggiungeremo solo "così" con esso.

Aggiungiamo "tom" . Questa volta, creiamo un nuovo edge da root in quanto non abbiamo alcun prefisso di tom creato prima.

Ora come dovremmo aggiungere "a" ? 'to' è completamente un prefisso di 'tom' , quindi non è necessario aggiungere alcun margine. Quello che possiamo fare è, possiamo mettere i segni di fine in alcuni nodi. Inseriremo i punti finali in quei nodi in cui è stata completata almeno una parola. Il cerchio verde indica il segno di fine. Il trie avrà il seguente aspetto:

Puoi facilmente capire perché abbiamo aggiunto i marchi finali. Possiamo determinare le parole memorizzate in trie. I caratteri saranno sui bordi e i nodi conterranno le estremità.

Ora potresti chiedere, qual è lo scopo di memorizzare parole come questa? Diciamo che ti viene chiesto di trovare la parola "alice" nel dizionario. Attraverserai il trie. Controllerai se c'è un edge-a da root. Quindi controlla da 'a' , se c'è un limite-l . Dopodiché, non troverai alcun limite , quindi puoi giungere alla conclusione che la parola alice non esiste nel dizionario.

Se ti viene chiesto di trovare la parola "alg" nel dizionario, attraverserai root-> a , a-> l , l-> g , ma alla fine non troverai un nodo verde. Quindi la parola non esiste nel dizionario. Se cerchi "tom" , finirai in un nodo verde, il che significa che la parola esiste nel dizionario.

Complessità:

La quantità massima di passaggi necessari per cercare una parola in un trie è la lunghezza della parola che stiamo cercando. La complessità è O (lunghezza) . La complessità per l'inserimento è la stessa. La quantità di memoria necessaria per implementare il trie dipende dall'implementazione. Vedremo un'implementazione in un altro esempio in cui possiamo memorizzare 10 ⁶ caratteri (non parole, lettere) in un trie .

Uso di Trie:

• Per inserire, cancellare e cercare una parola nel dizionario.
• Per scoprire se una stringa è un prefisso di un'altra stringa.
• Per scoprire quante stringhe ha un prefisso comune.
• Suggerimento di nomi di contatti nei nostri telefoni a seconda del prefisso che inseriamo.
• Scoprire "Sottostringa comune più lunga" di due stringhe.
• Individuazione della lunghezza di "Prefisso comune" per due parole utilizzando "Antenna comune più lunga"

Implementazione di Trie

Prima di leggere questo esempio, si consiglia vivamente di leggere prima Introduzione a Trie .

Uno dei modi più semplici per implementare Trie è l'utilizzo dell'elenco collegato.

Nodo:

I nodi consisteranno in:

1. Variabile per Fine-Mark.
2. Pointer Array al nodo successivo.

La variabile End-Mark indicherà semplicemente se si tratta di un end-point o meno. L'array di puntatori indicherà tutti i possibili bordi che possono essere creati. Per gli alfabeti inglesi, la dimensione dell'array sarà 26, poiché è possibile creare un massimo di 26 bordi da un singolo nodo. All'inizio ogni valore dell'array di puntatori sarà NULL e la variabile di fine marchio sarà falsa.

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

Ogni elemento nell'array successivo [] punta a un altro nodo. next [0] punta al nodo di condivisione del nodo -a , il prossimo [1] punta al nodo che condivide il bordo-b e così via. Abbiamo definito il costruttore del Nodo per inizializzare Endmark come falso e inserire NULL in tutti i valori dell'array puntatore successivo [] .

Per creare Trie , all'inizio dovremo creare un'istanza di root . Quindi dalla radice , creeremo altri nodi per memorizzare le informazioni.

Inserimento:

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

Qui stiamo lavorando con az . Quindi per convertire i loro valori ASCII in 0-25 , sottraiamo il valore ASCII di 'a' da loro. Controlleremo se il nodo corrente (curr) ha un margine per il personaggio a portata di mano. Se lo fa, passiamo al nodo successivo usando quel bordo, se non lo facciamo creiamo un nuovo nodo. Alla fine, cambiamo il segno di destinazione in vero.

Ricerca:

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

Il processo è simile a inserire. Alla fine, restituiamo il simbolo . Quindi, se il segno di destinazione è vero, significa che la parola esiste nel dizionario. Se è falso, la parola non esiste nel dizionario.

Questa è stata la nostra implementazione principale. Ora possiamo inserire qualsiasi parola in trie e cercarla.

Soppressione:

A volte dovremo cancellare le parole che non saranno più utilizzate per risparmiare memoria. A tale scopo, è necessario eliminare le parole non utilizzate:

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

Questa funzione va a tutti i nodi figli di curr , li cancella e quindi curr viene cancellato per liberare la memoria. Se chiamiamo delete (root) , cancellerà l'intero Trie .

Trie può essere implementato anche usando gli array .