La migliore struttura dati per implementare un dizionario?

Question

Quale sarebbe la migliore struttura dati per memorizzare tutte le parole di un dizionario? Il meglio che ho potuto pensare è stato usare un HashMap, che verrà mappato a HashTable. Fondamentalmente, a seconda del primo carattere, otterremo il corrispondente HashTable e quindi usando questo, possiamo aggiungere le parole partendo da quel personaggio. Sceglieremo una buona funzione di hash basata sulla stringa.

C'è un approccio migliore?

Answer 1

A seconda di cosa si vuole fare, ci sono molte buone strutture di dati.

Se si desidera solo memorizzare le parole e chiedere "questa parola è qui o no?", Una tabella di hash standard senza altri macchinari di fantasia è un approccio ragionevole. Se questa parola è un elenco fissato in anticipo, prendere in considerazione l'utilizzo di perfect hash table per ottenere prestazioni eccellenti e utilizzo dello spazio.

Se si desidera essere in grado di verificare se esiste un determinato prefisso durante il supporto di ricerche veloci, un trie è una buona opzione, anche se può essere un po 'poco spazio-inefficiente. Supporta anche inserimenti o cancellazioni veloci. Inoltre consente l'iterazione in ordine alfabetico, che l'hashing non offre. Questa è essenzialmente la struttura che hai descritto nella tua risposta, ma a seconda del caso d'uso altre rappresentazioni dei tentativi potrebbero essere migliori.

Se oltre a quanto sopra, si sa per certo che l'elenco di parole è fisso, si consideri l'utilizzo di un DAWG (grafico di parola aciclica diretto), che è essenzialmente un DFA di stato minimo per la lingua. È sostanzialmente più compatto del trie, ma supporta molte delle stesse operazioni.

Se si desidera un comportamento simile a un trie, ma non si vuole pagare un'enorme penalità di spazio, il ternary search tree è un'altra opzione valida, come lo radix tree. Queste sono strutture molto diverse, ma possono essere molto meglio del trie in diverse circostanze.

Se lo spazio è un problema ma si desidera un trie, esaminare la rappresentazione succinct trie, che ha una ricerca più lenta ma solo un utilizzo teoricamente ottimale dello spazio. Il link spiega come viene utilizzato in JavaScript come un modo semplice per trasmettere una grande quantità di dati. Una rappresentazione compatta alternativa è la double-array trie, anche se devo ammettere che ne so molto poco.

Se si desidera utilizzare il dizionario per operazioni come il controllo ortografico in cui è necessario trovare parole simili ad altre parole, lo BK-tree è una struttura dati eccellente da considerare.

Spero che questo aiuti!