Scrabble ordsökare:bygga ett försök, lagra ett försök, använda ett försök?

Först och främst, låt oss titta på begränsningarna för problemet. Du vill lagra en ordlista för ett spel i en datastruktur som effektivt stöder "anagram"-problemet. Det vill säga, givet ett "rack" med n bokstäver, vad är alla n-eller-färre-bokstavsord i ordlistan som kan göras från det racket. ordlistan kommer att bestå av cirka 400 000 ord, och det är förmodligen ungefär en till tio meg strängdata när den är okomprimerad.

Ett försök är den klassiska datastrukturen som används för att lösa detta problem eftersom den kombinerar både minneseffektivitet med sökeffektivitet. Med en ordlista på cirka 400K ord av rimlig längd bör du kunna behålla försöket i minnet. (I motsats till att använda en b-tree-lösning där du behåller det mesta av trädet på disken eftersom det är för stort för att få plats i minnet på en gång.)

Ett försök är i princip inget annat än ett 26-arigt träd (förutsatt att du använder det romerska alfabetet) där varje nod har en bokstav och ytterligare en bit på varje nod som säger om det är slutet på ordet.

Så låt oss skissa på datastrukturen:

class TrieNode
{
    char Letter;
    bool IsEndOfWord;
    List<TrieNode> children; 
}

Detta är naturligtvis bara en skiss; du skulle antagligen vilja få dessa att ha ordentliga fastighetstillbehör och konstruktörer och sånt. Dessutom kanske en platt lista inte är den bästa datastrukturen; kanske någon sorts ordbok är bättre. Mitt råd är att få det att fungera först och sedan mäta dess prestanda, och om det är oacceptabelt, experimentera sedan med att göra ändringar för att förbättra dess prestanda.

Du kan börja med ett tomt försök:

TrieNode root = new TrieNode('^', false, new List<TrieNode>());

Det vill säga, detta är "root"-försöksnoden som representerar början av ett ord.

Hur lägger man till ordet "AA", det första ordet i Scrabble-ordboken? Tja, gör först en nod för den första bokstaven:

root.Children.Add('A', false, new List<TrieNode>());

OK, vårt försök är nu

^
|
A

Lägg nu till en nod för den andra bokstaven:

root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));

Vårt försök är nu

^
|
A
|
A$   -- we notate the end of word flag with $

Bra. Anta nu att vi vill lägga till AB. Vi har redan en nod för "A", så lägg till noden "B$":

root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());

och nu har vi

    ^
    |
    A
   / \
  A$   B$

Fortsätt så. Naturligtvis, istället för att skriva "root.Children[0]..." kommer du att skriva en loop som söker igenom försöket för att se om noden du vill ha finns, och om inte, skapa den.

För att lagra ditt försök på disk -- ärligt talat skulle jag bara lagra ordlistan som en vanlig textfil och bygga om försöket när du behöver. Det bör inte ta mer än 30 sekunder eller så, och sedan kan du återanvända försöket i minnet. Om du vill lagra försöket i något format som är mer som ett försök, borde det inte vara svårt att komma på ett serialiseringsformat.

För att söka efter trieken för att matcha ett ställ är tanken att utforska varje del av trian, men att beskära de områden där stället omöjligt kan matcha. Om du inte har några "A" på racket, behöver du inte gå ner för någon "A"-nod. Jag skissade på sökalgoritmen i din tidigare fråga.

Jag har en implementering av ett ihållande försök i funktionell stil som jag har tänkt blogga om ett tag men aldrig kommit till skott. Om jag så småningom postar det kommer jag att uppdatera den här frågan.