La struttura dei dati Trie: una gemma trascurata

Fin dai primi giorni della nostra vita come programmatori, ci siamo tutti occupati di strutture dati: array, liste collegate, alberi, set, stack e code sono i nostri compagni di tutti i giorni e il programmatore esperto sa quando e perché usarli. In questo articolo vedremo come una struttura di dati spesso trascurata, il trie , brilla davvero nei domini delle applicazioni con funzionalità specifiche, come i giochi di parole.

Giochi di parole come esempio di prova

Per cominciare, consideriamo un semplice puzzle di parole: trova tutte le parole valide in una lavagna 4x4, collegando le lettere adiacenti orizzontalmente, verticalmente o diagonalmente. Ad esempio, nella scheda seguente, vediamo le lettere 'W', 'A', 'I' e 'T' che si collegano per formare la parola “WAIT”.

La soluzione ingenua per trovare tutte le parole valide sarebbe esplorare il tabellone partendo dall'angolo in alto a sinistra e poi spostandosi in profondità verso sequenze più lunghe, ricominciando dalla seconda lettera nella prima riga e così via. In una scacchiera 4x4, che consente spostamenti verticali, orizzontali e diagonali, ci sono 12029640 sequenze, di lunghezza compresa tra uno e sedici caratteri.

Ora, il nostro obiettivo è trovare la migliore struttura di dati per implementare questo correttore di parole valide, ovvero il nostro vocabolario. Alcuni punti da tenere a mente:

• Abbiamo solo bisogno di una singola copia di ogni parola, cioè il nostro vocabolario è un insieme, da un punto di vista logico.
• Dobbiamo rispondere alle seguenti domande per ogni parola data:
  • La sequenza di caratteri corrente comprende una parola valida?
  • Ci sono parole più lunghe che iniziano con questa sequenza? In caso contrario, possiamo abbandonare la nostra esplorazione in profondità, poiché andare più in profondità non produrrà parole valide.

Per illustrare il secondo punto, considera la tabella seguente: Non ha senso esplorare le mosse successive, poiché non ci sono parole nel dizionario che iniziano con “ASF”.

Ci piacerebbe che la nostra struttura dati risponda a queste domande il più rapidamente possibile. ~O(1) tempo di accesso (per il controllo di una sequenza) sarebbe l'ideale!

Possiamo definire l'interfaccia del vocabolario in questo modo (vedi qui per il repository GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Prova la struttura dei dati rispetto alle alternative

L'implementazione del metodo contains() richiede una struttura di dati di supporto che ti permetta di trovare elementi in modo efficiente, mentre il metodo isPrefix() ci richiede di trovare il "prossimo elemento più grande", cioè dobbiamo mantenere il vocabolario ordinato in qualche modo.

Possiamo facilmente escludere insiemi basati su hash dal nostro elenco di candidati: mentre una tale struttura ci darebbe un controllo a tempo costante per contains() , funzionerebbe piuttosto male su isPrefix() , nel peggiore dei casi richiedendo di scansionare l'intero impostare.

Per la ragione esattamente opposta, possiamo anche escludere le liste concatenate ordinate, in quanto richiedono la scansione della lista almeno fino al primo elemento che è maggiore o uguale alla parola o al prefisso cercati.

Due opzioni valide stanno usando un elenco ordinato di array o un albero binario.
Nell'elenco ordinato basato su array possiamo utilizzare la ricerca binaria per trovare la sequenza corrente se presente o l'elemento successivo maggiore al costo di O(log2(n)) , dove n è il numero di parole nel dizionario.

Possiamo implementare un vocabolario basato su array che mantiene sempre l'ordine in questo modo, utilizzando lo standard java.util.ArrayList e java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Se decidessimo di utilizzare un albero binario, l'implementazione potrebbe essere ancora più breve ed elegante (di nuovo, ecco un link al codice):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

In entrambi i casi, possiamo aspettarci prestazioni O(log n) per ogni metodo di accesso ( contains() e isPrefix() ). Per quanto riguarda i requisiti di spazio, sia l'implementazione array-backed che l'implementazione tree-backed richiedono O(n+M) dove n è il numero di parole nel dizionario e M è la dimensione in byte del dizionario, ovvero la somma della lunghezza di le stringhe nel dizionario.

Applicazioni di prova: quando e perché utilizzare le prove

Le prestazioni logaritmiche e la memoria lineare non sono male. Ma ci sono alcune altre caratteristiche del nostro dominio applicativo che possono portarci a prestazioni migliori:

• Possiamo tranquillamente presumere che tutte le parole siano minuscole.
• Accettiamo solo lettere az: nessuna punteggiatura, nessun trattino, nessun accento, ecc.
• Il dizionario contiene molte forme flesse: plurali, verbi coniugati, parole composte (es. casa –> governante). Pertanto, molte parole condividono la stessa radice .
• Le parole hanno una lunghezza limitata. Ad esempio, se stiamo lavorando su una tavola 4x4, tutte le parole più lunghe di 16 caratteri possono essere scartate.

È qui che entra in gioco il trie (pronunciato "try"). Ma cos'è esattamente un trie? I tentativi sono strutture di dati trascurate, che si trovano nei libri ma raramente nelle biblioteche standard.

Per la motivazione, consideriamo prima il figlio poster di Computer Science: l'albero binario. Ora, quando analizziamo le prestazioni di un albero binario e diciamo che l'operazione x è O(log(n)) , parliamo costantemente di log base 2. Ma cosa accadrebbe se, invece di un albero binario, usassimo un albero ternario, dove ogni nodo ha tre figli (o un fan-out di tre). Quindi, parleremmo di log base 3. (Questo è un miglioramento delle prestazioni, anche se solo di un fattore costante.) In sostanza, i nostri alberi diventerebbero più larghi ma più corti e potremmo eseguire meno ricerche poiché non abbiamo bisogno di scendere abbastanza così profondo.

Facendo un ulteriore passo avanti, e se avessimo un albero con un fan-out uguale al numero di possibili valori del nostro tipo di dati?

Questa è la motivazione alla base del tentativo. E come avrai intuito, un trie è davvero un albero, un trie per così dire!

Ma, contrariamente alla maggior parte degli alberi binari che useresti per ordinare le stringhe, quelli che memorizzerebbero intere parole nei loro nodi, ogni nodo di un trie contiene un singolo carattere (e nemmeno quello, come vedremo presto) e ha un fan-out massimo pari alla lunghezza dell'alfabeto. Nel nostro caso, la lunghezza dell'alfabeto è 26; quindi i nodi del trie hanno un fan-out massimo di 26. E, mentre un albero binario bilanciato ha una profondità log2(n) , la profondità massima del trie è uguale alla lunghezza massima di una parola! (Di nuovo, più largo ma più corto.)

All'interno di un trie, le parole con la stessa radice (prefisso) condividono l'area di memoria che corrisponde alla radice.

Per visualizzare la differenza, consideriamo un piccolo dizionario composto da cinque parole. Si supponga che le lettere greche indichino puntatori e si noti che nel trie i caratteri rossi indichino nodi contenenti parole valide .

Implementazione di Java Trie

Come sappiamo, nell'albero i puntatori agli elementi figli sono solitamente implementati con una variabile sinistra e destra, perché il fan-out massimo è fissato a due.

In un trie che indicizza un alfabeto di 26 lettere, ogni nodo ha 26 possibili figli e, quindi, 26 possibili puntatori. Ogni nodo presenta quindi una matrice di 26 (puntatori a) sottoalberi, in cui ogni valore potrebbe essere nullo (se non esiste tale figlio) o un altro nodo.

Come, allora, cerchiamo una parola in un tentativo? Ecco il metodo che, data una String s , identificherà il nodo che corrisponde all'ultima lettera della parola, se presente nell'albero:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

Il metodo LOWERCASE.getIndex(s.charAt(i)) restituisce semplicemente la posizione dell'i- esimo carattere nell'alfabeto. Sul nodo restituito, un node di proprietà booleano indica che il nodo corrisponde all'ultima lettera di una parola, ovvero una lettera contrassegnata in rosso nell'esempio precedente. Poiché ogni nodo mantiene un contatore del numero di figli, se questo contatore è positivo allora ci sono parole più lunghe nel dizionario che hanno la stringa corrente come prefisso. Nota: il nodo non ha davvero bisogno di mantenere un riferimento al carattere a cui corrisponde, perché è implicito nella sua posizione nel trie.

Analisi delle prestazioni

Ciò che rende la struttura trie davvero efficace in queste situazioni è che il costo per cercare una parola o un prefisso è fisso e dipende solo dal numero di caratteri nella parola e non dalla dimensione del vocabolario.

Nel nostro specifico dominio, poiché abbiamo stringhe che sono al massimo 16 caratteri, sono necessari esattamente 16 passaggi per trovare una parola che è nel vocabolario, mentre si può ottenere qualsiasi risposta negativa, cioè la parola o il prefisso non è nel trie anche in un massimo di 16 passaggi! Considerando che in precedenza abbiamo ignorato la lunghezza della stringa durante il calcolo della complessità del tempo di esecuzione sia per l'elenco ordinato supportato dall'array che per l'albero, che è nascosto nei confronti delle stringhe, possiamo anche ignorarlo qui e affermare in sicurezza che la ricerca è stata eseguita nel tempo O(1) .

Considerando i requisiti di spazio (e ricordando che abbiamo indicato con M la dimensione in byte del dizionario), il trie potrebbe avere M nodi nel peggiore dei casi, se due stringhe non condividono un prefisso. Ma poiché abbiamo osservato che c'è un alto grado di ridondanza nel dizionario, c'è molta compressione da fare. Il dizionario inglese utilizzato nel codice di esempio è 935.017 byte e richiede 250.264 nodi, con un rapporto di compressione di circa il 73%.

Tuttavia, nonostante ciò, anche un trie compresso di solito richiede più memoria di un albero o di un array. Questo perché, per ogni nodo, sono necessari almeno 26 x sizeof(pointer) byte, più un po' di sovraccarico per l'oggetto e attributi aggiuntivi. Su una macchina a 64 bit, ogni nodo richiede più di 200 byte, mentre un carattere stringa richiede un singolo byte o due se consideriamo le stringhe UTF.

Prove e test delle prestazioni

Allora, che dire delle prestazioni? Le implementazioni del vocabolario sono state testate in due diverse situazioni: verificando la presenza di 20.000.000 di stringhe casuali e trovando tutte le parole in 15.000 schede generate casualmente dallo stesso elenco di parole.

Sono state analizzate quattro strutture di dati: un elenco ordinato basato su array, un albero binario, il trie sopra descritto e un trie che utilizza array di byte corrispondenti all'indice alfabetico dei caratteri stessi (un'ottimizzazione delle prestazioni minore e facilmente implementabile). Ecco i risultati, in ms:

Il numero medio di mosse fatte per risolvere il tabellone è 2.188. Per ogni mossa viene eseguita una ricerca di parole e una ricerca di prefissi, ovvero, per controllare tutte le schede, sono state eseguite più di 32 milioni di ricerche di parole e 32 milioni di ricerche di prefissi. Nota: questi potrebbero essere fatti in un unico passaggio, li ho tenuti separati per chiarezza nell'esposizione. Compattarli in un solo passaggio ridurrebbe quasi della metà i tempi di risoluzione delle schede e probabilmente favorirebbe ancora di più il tentativo.

Come si può vedere sopra, la ricerca di parole ha prestazioni migliori con il trie anche quando si utilizzano stringhe ed è ancora più veloce quando si utilizzano indici alfabetici, con quest'ultimo che si comporta più del doppio di un albero binario standard. La differenza nella risoluzione delle schede è ancora più evidente, con la soluzione veloce trie-alphabet-index più di quattro volte più veloce dell'elenco e dell'albero.

Avvolgendo

Il trie è una struttura di dati molto specializzata che richiede molta più memoria di alberi ed elenchi. Tuttavia, quando si applicano caratteristiche di dominio specifiche, come un alfabeto limitato e un'elevata ridondanza nella prima parte delle stringhe, può essere molto efficace nell'affrontare l'ottimizzazione delle prestazioni.

Riferimenti

Un'ampia spiegazione di tentativi e alfabeti può essere trovata nel capitolo 5 del libro di Robert Sedgewick "Algoritmi, 4a edizione". Il sito web associato a Princeton ha il codice per un'implementazione di Alphabet e TrieST che è più ampio del mio esempio.

La descrizione del trie e delle implementazioni per varie lingue può essere trovata anche su Wikipedia e puoi anche dare un'occhiata a questa risorsa del trie della Boston University.