Laten we eerst eens kijken naar de beperkingen van het probleem. U wilt een woordenlijst voor een spel opslaan in een gegevensstructuur die het "anagram"-probleem efficiënt ondersteunt. Dat wil zeggen, gegeven een "rek" van n letters, wat zijn alle woorden van n of minder letters in de woordenlijst die van dat rek kunnen worden gemaakt. de woordenlijst zal ongeveer 400.000 woorden zijn, en dat is waarschijnlijk ongeveer één tot tien meg aan stringgegevens wanneer ze niet zijn gecomprimeerd.
Een tri is de klassieke gegevensstructuur die wordt gebruikt om dit probleem op te lossen, omdat het zowel geheugenefficiëntie als zoekefficiëntie combineert. Met een woordenlijst van ongeveer 400K woorden van redelijke lengte zou je de poging in het geheugen moeten kunnen houden. (In tegenstelling tot een b-tree-achtige oplossing waarbij je het grootste deel van de tree op schijf bewaart omdat het te groot is om in één keer in het geheugen te passen.)
Een trie is in feite niets meer dan een boom met 26 cijfers (ervan uitgaande dat je het Romeinse alfabet gebruikt) waarbij elke knoop een letter heeft en een extra bit op elke knoop die aangeeft of het het einde van het woord is.
Laten we dus de gegevensstructuur schetsen:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Dit is natuurlijk maar een schets; je zou waarschijnlijk willen dat deze de juiste eigendomsaccessors en constructors hebben en zo. Ook is een platte lijst misschien niet de beste gegevensstructuur; misschien is een soort woordenboek beter. Mijn advies is om het eerst werkend te krijgen en dan de prestaties te meten, en als het onaanvaardbaar is, experimenteer dan met het aanbrengen van wijzigingen om de prestaties te verbeteren.
U kunt beginnen met een lege poging:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Dat wil zeggen, dit is de "root" trie-knoop die het begin van een woord vertegenwoordigt.
Hoe voeg je het woord 'AA' toe, het eerste woord in het Scrabble-woordenboek? Wel, maak eerst een knoop voor de eerste letter:
root.Children.Add('A', false, new List<TrieNode>());
OK, onze poging is nu
^
|
A
Voeg nu een knooppunt toe voor de tweede letter:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Onze poging is nu
^
|
A
|
A$ -- we notate the end of word flag with $
Super goed. Stel nu dat we AB willen toevoegen. We hebben al een knooppunt voor "A", dus voeg het knooppunt "B$" toe:
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
en nu hebben we
^
|
A
/ \
A$ B$
Ga zo door. Natuurlijk, in plaats van "root.Children[0]..." te schrijven, schrijf je een lus die de poging doorzoekt om te zien of het gewenste knooppunt bestaat, en zo niet, maak het dan.
Om je triangel op schijf op te slaan -- eerlijk gezegd zou ik de woordenlijst gewoon als een tekstbestand opslaan en de triangel opnieuw opbouwen als dat nodig is. Het zou niet meer dan 30 seconden of zo moeten duren, en dan kun je de trie opnieuw gebruiken in het geheugen. Als je de trie wilt opslaan in een formaat dat meer op een trie lijkt, zou het niet moeilijk moeten zijn om een serialisatieformaat te bedenken.
Om de triatlon te doorzoeken op het matchen van een rek, is het de bedoeling om elk deel van de triangel te verkennen, maar de gebieden weg te snoeien waar het rek onmogelijk kan matchen. Als u geen "A"-en op het rek heeft, hoeft u geen "A"-knooppunt te gebruiken. Ik heb het zoekalgoritme in uw vorige vraag geschetst.
Ik heb een implementatie van een blijvende poging in functionele stijl waar ik al een tijdje over wilde bloggen, maar waar ik nooit aan toe kwam. Als ik dat uiteindelijk post, zal ik deze vraag bijwerken.