Prima di tutto, diamo un'occhiata ai vincoli del problema. Vuoi memorizzare un elenco di parole per un gioco in una struttura di dati che supporti in modo efficiente il problema dell'"anagramma". Cioè, dato un "rack" di n lettere, quali sono tutte le parole di n o meno lettere nell'elenco di parole che possono essere create da quel rack. l'elenco di parole sarà di circa 400.000 parole, e quindi è probabilmente da uno a dieci mega di dati di stringa quando non compresso.
Un trie è la classica struttura dati utilizzata per risolvere questo problema perché combina sia l'efficienza della memoria che l'efficienza della ricerca. Con un elenco di parole di circa 400.000 parole di lunghezza ragionevole dovresti essere in grado di mantenere il trie in memoria. (Invece di utilizzare una sorta di soluzione b-tree in cui mantieni la maggior parte dell'albero su disco perché è troppo grande per stare in memoria tutto in una volta.)
Un trie non è fondamentalmente altro che un albero di 26 ary (supponendo che tu stia usando l'alfabeto romano) in cui ogni nodo ha una lettera e un bit aggiuntivo su ogni nodo che dice se è la fine della parola.
Quindi abbozziamo la struttura dei dati:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Questo ovviamente è solo uno schizzo; probabilmente vorresti che questi abbiano accessor e costruttori di proprietà adeguati e quant'altro. Inoltre, forse un elenco piatto non è la migliore struttura di dati; forse è meglio una specie di dizionario. Il mio consiglio è di farlo funzionare prima, quindi misurarne le prestazioni e, se è inaccettabile, provare ad apportare modifiche per migliorarne le prestazioni.
Puoi iniziare con un tentativo vuoto:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Cioè, questo è il nodo trie "radice" che rappresenta l'inizio di una parola.
Come si aggiunge la parola "AA", la prima parola nel dizionario di Scrabble? Bene, prima crea un nodo per la prima lettera:
root.Children.Add('A', false, new List<TrieNode>());
OK, il nostro tentativo è ora
^
|
A
Ora aggiungi un nodo per la seconda lettera:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
La nostra prova è ora
^
|
A
|
A$ -- we notate the end of word flag with $
Grande. Supponiamo ora di voler aggiungere AB. Abbiamo già un nodo per "A", quindi aggiungi ad esso il nodo "B$":
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
e ora abbiamo
^
|
A
/ \
A$ B$
Continua così. Ovviamente, invece di scrivere "root.Children[0]...", scriverai un ciclo che cerca nel tentativo per vedere se il nodo che desideri esiste e, in caso contrario, crealo.
Per archiviare la tua prova su disco, francamente, memorizzerei semplicemente l'elenco di parole come un file di testo normale e ricostruirei la prova quando necessario. Non dovrebbero volerci più di 30 secondi circa, quindi puoi riutilizzare il tentativo in memoria. Se vuoi archiviare il trie in un formato più simile a un trie, non dovrebbe essere difficile trovare un formato di serializzazione.
Per cercare il trie per abbinare un rack, l'idea è di esplorare ogni parte del trie, ma per eliminare le aree in cui il rack non può corrispondere. Se non hai "A" sul rack, non è necessario scendere in nessun nodo "A". Ho abbozzato l'algoritmo di ricerca nella tua domanda precedente.
Ho un'implementazione di un tentativo persistente in stile funzionale di cui avevo intenzione di scrivere un blog per un po', ma non ci sono mai riuscito. Se alla fine lo pubblico, aggiornerò questa domanda.
