Trie: struttura dati ad albero ordinato

Il trie: cos'è e come funziona

Il trie, o albero di prefissi, è una struttura dati ad albero utilizzata per memorizzare e cercare rapidamente stringhe o sequenze di caratteri. In un trie, ogni nodo rappresenta un carattere all'interno della stringa e gli archi che collegano i nodi rappresentano le possibili scelte di caratteri successivi. Il percorso dalla radice dell'albero fino ad una foglia rappresenta una specifica stringa.

L'accesso a un valore all'interno del trie è molto veloce e richiede solo un numero di operazioni proporzionale alla lunghezza della stringa. Questa caratteristica lo rende particolarmente utile per le applicazioni che richiedono la ricerca di stringhe in un grande insieme di dati, come i suggerimenti di completamento automatico nei motori di ricerca.

La storia del trie

Il trie è stato sviluppato per la prima volta negli anni '50 come un tipo di struttura dati per la ricerca di parole in un dizionario. Il suo nome deriva dalla parola "retrieval" (recupero) e fu coniato da René de la Briandais, uno dei primi ricercatori a sviluppare questa tecnologia. Nel corso degli anni, il trie è stato esteso e utilizzato in una vasta gamma di applicazioni.

Utilizzi del trie

Il trie è utilizzato principalmente per le applicazioni che richiedono l'accesso efficiente e veloce alle stringhe. In particolare, il trie è particolarmente utile per l'implementazione di suggerimenti di completamento automatico in un motore di ricerca o in un'app di messaggistica. Ad esempio, quando un utente inizia a digitare una parola, il trie può essere utilizzato per suggerire le possibili completamenti sulla base delle stringhe già presenti nel dizionario.

Il trie è inoltre utilizzato nella compressione dei dati. In questo caso, la struttura viene utilizzata per memorizzare le sequenze di caratteri comuni all'interno di un insieme di dati, riducendo così lo spazio di archiviazione richiesto.

Benefici e svantaggi del trie

Tra i principali vantaggi del trie ci sono la velocità di ricerca, la capacità di ridurre lo spazio di archiviazione necessario per una vasta gamma di stringhe e la flessibilità nell'aggiungere e rimuovere stringhe.

Tuttavia, ci sono anche alcuni svantaggi nel suo utilizzo. La complessità di implementazione del trie può essere piuttosto elevata, soprattutto per stringhe molto lunghe. Inoltre, le prestazioni del trie possono essere influenzate dalla dimensione dell'alfabeto utilizzato nella stringa, il che può portare a un aumento delle dimensioni e della complessità della struttura dati. Infine, il trie può richiedere più spazio di archiviazione rispetto ad altre strutture dati simili, come le tabelle hash.

Coding Time

Concentriamoci su questo esempio:

Per creare questo trie, è sufficiente procedere in questo modo:

trie = new Trie();
trie.insert('HEY');

Vediamo ora i dati che ci aspettiamo nei nostri nodi del trie di esempio:

Qui, la casella all'interno del JSON indica un riferimento all'altro nodo.

1) Il nodo radice memorizza un riferimento al nodo H nella chiave H della sua proprietà children.

2) Il primo nodo memorizza un riferimento al nodo E nella chiave E della sua proprietà children.

Si noti che solo l'ultimo nodo Y ha impostato la proprietà isWord su true. Questa proprietà dovrebbe indicare se il nodo è la fine di una parola.

Partiamo creando due file Javascript: nel primo file, chiamato TrieNode.js, scriveremo il codice necessario per creare la classe TrieNode.
Questa classe è utilizzata per creare un oggetto che rappresenta un nodo all'interno di un trie, con una chiave, una lista di figli e un indicatore per segnalare se il nodo rappresenta una parola completa.

class TrieNode {
    constructor(key) {
        this.key = key;
        this.children = {};
        this.isWord = false;
    }
}

module.exports = TrieNode;

Come possiamo vedere dal codice, la classe TrieNode ha un costruttore che prende come parametro una chiave (o un carattere). La chiave è memorizzata all'interno della proprietà 'key' del nodo. Il nodo ha anche una proprietà 'children', che è un oggetto vuoto inizialmente, e viene utilizzato per memorizzare i figli del nodo. Infine, troviamo una proprietà 'isWord', inizializzata a 'false', che viene utilizzata per indicare se il nodo rappresenta la fine di una parola.

Utilizziamo poi l'espressione module.exports = TrieNode per esportare la classe TrieNode, in modo che possa essere utilizzata nel secondo file.

Nel secondo file, che ho chiamato per comodita' Trie.js, creiamo la classe Trie: essa ha un costruttore che inizializza un nodo radice utilizzando la classe TrieNode che abbiamo scritto nel file precedente. Il nodo radice rappresenta la radice del trie e ha una lista di figli vuota.

const TrieNode = require('./TrieNode');

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        let currentnode = this.root;
        const chararray = word.split("");

        for (let i = 0; i < chararray.length; i++) {
            const alphabet = chararray[i];
            if (!(alphabet in currentnode.children)) {
                currentnode.children[alphabet] = new TrieNode(alphabet);
            }
            currentnode = currentnode.children[alphabet];
        }
        currentnode.isWord = true;
    }
}

module.exports = Trie;

Parafrasando il codice..
La classe Trie ha un metodo insert(word) che prende come parametro una parola e la inserisce all'interno del trie. Il metodo crea un puntatore a 'currentnode' che viene inizializzato con il nodo radice. Successivamente, la parola viene divisa in un array di caratteri utilizzando il metodo split(). Viene quindi effettuata un'iterazione attraverso l'array di caratteri e, per ciascun carattere, viene controllato se esiste un nodo figlio corrispondente nel nodo corrente. Se non esiste, viene creato un nuovo nodo figlio per il carattere corrente. Il puntatore 'currentnode' viene quindi aggiornato per puntare al nodo figlio corrispondente al carattere corrente.

Alla fine del ciclo, il nodo corrente viene marcato come una parola completa impostando l'indicatore 'isWord' su 'true'.

Il Branching

Un aspetto importante del trie è la sua capacità di branching, ovvero di ramificarsi e di avere molti figli. Vediamo un esempio più ampio:

In questo esempio, sia la lettera E che la prima L avranno due figli.
I dati per la E sarebbero:

{
    key: "E",
    isWord: false,
    children: {
        'L': lNode,
        'R': rNode,
    }
}

In questo caso, hNode, lNode e rNode sono riferimenti agli oggetti di quei particolari nodi.

Nell'esempio precedente, ci sono tre nodi che dovrebbero avere isWord impostato su true. Si tratta di D, O e T.

Nel codice che abbiamo scritto nel secondo file, il branching nel trie viene effettuato nel metodo insert(word) della classe Trie.

if (!(alphabet in currentnode.children)) {
                currentnode.children[alphabet] = new TrieNode(alphabet);

Il branching in questo caso avviene quando incontriamo un carattere che non ha un nodo figlio corrispondente nel nodo corrente.
In questo caso, viene creato un nuovo nodo figlio per il carattere corrente e il puntatore currentnode viene aggiornato per puntare al nodo figlio appena creato.

Questo è ciò che viene comunemente definito branching all'interno del trie, poiché il flusso della struttura dati si divide in due percorsi separati, uno per la parola corrente e uno per le parole future. Questo processo viene ripetuto per ogni carattere della parola che viene inserita nel trie.