Nejprve se podívejme na omezení problému. Chcete uložit seznam slov pro hru v datové struktuře, která efektivně podporuje problém „anagramu“. To znamená, že když je dán "stojan" n písmen, jaká jsou všechna slova s n nebo méně písmeny v seznamu slov, která lze z tohoto stojanu vytvořit. seznam slov bude mít asi 400 000 slov, což je pravděpodobně asi jeden až deset megů řetězcových dat po rozbalení.
A trie je klasická datová struktura používaná k řešení tohoto problému, protože kombinuje efektivitu paměti s účinností vyhledávání. Se seznamem slov asi 400 000 slov přiměřené délky byste měli být schopni udržet trie v paměti. (Na rozdíl od řešení typu b-tree, kde většinu stromu ponecháváte na disku, protože je příliš velký na to, aby se najednou vešel do paměti.)
trie není v podstatě nic jiného než 26členný strom (za předpokladu, že používáte latinku), kde každý uzel má písmeno a jeden další bit na každém uzlu, který říká, zda se jedná o konec slova.
Pojďme si tedy načrtnout datovou strukturu:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Toto je samozřejmě jen náčrt; pravděpodobně byste chtěli, aby tyto měly správné přístupové objekty a konstruktory a cokoli jiného. Plochý seznam možná také není nejlepší datová struktura; možná je lepší nějaký slovník. Moje rada je, abyste jej nejprve uvedli do provozu a poté změřili jeho výkon, a pokud je to nepřijatelné, pak experimentujte s prováděním změn ke zlepšení jeho výkonu.
Můžete začít s prázdným pokusem:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
To znamená, že toto je "kořenový" uzel trie, který představuje začátek slova.
Jak přidáte slovo „AA“, první slovo ve slovníku Scrabble? Nejprve udělejte uzel pro první písmeno:
root.Children.Add('A', false, new List<TrieNode>());
OK, náš pokus je nyní
^
|
A
Nyní přidejte uzel pro druhé písmeno:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Náš pokus je nyní
^
|
A
|
A$ -- we notate the end of word flag with $
Skvělý. Nyní předpokládejme, že chceme přidat AB. Již máme uzel pro "A", takže k němu přidejte uzel "B$":
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
a teď máme
^
|
A
/ \
A$ B$
Pokračuj takhle dál. Samozřejmě, že místo psaní "root.Children[0]..." napíšete smyčku, která prohledá trie, zda požadovaný uzel existuje, a pokud ne, vytvořte jej.
Chcete-li uložit svůj pokus na disk - upřímně řečeno, uložil bych seznam slov jako prostý textový soubor a znovu sestavil pokus, když budete potřebovat. Nemělo by to trvat déle než 30 sekund nebo tak nějak a poté můžete pokus znovu použít v paměti. Pokud chcete uložit trie v nějakém formátu, který je spíše trie, nemělo by být těžké přijít s formátem serializace.
Chcete-li ve sbírce najít shodu se stojanem, myšlenkou je prozkoumat každou část pokusu, ale prořezat oblasti, kde se stojan nemůže shodovat. Pokud na stojanu nemáte žádná „A“, není třeba sjíždět žádný uzel „A“. Algoritmus vyhledávání jsem načrtl ve vaší předchozí otázce.
Mám implementaci trvalého pokusu ve funkčním stylu, o kterém jsem měl v úmyslu napsat blog, ale nikdy jsem se k tomu nedostal. Pokud to nakonec zveřejním, aktualizuji tuto otázku.