Primeiro, vamos olhar para as restrições do problema. Você deseja armazenar uma lista de palavras para um jogo em uma estrutura de dados que suporte eficientemente o problema do "anagrama". Isto é, dado um "rack" de n letras, quais são todas as palavras de n-ou-menos letras na lista de palavras que podem ser feitas a partir desse rack. a lista de palavras terá cerca de 400 mil palavras e, provavelmente, cerca de um a dez megas de dados de string quando descompactados.
Um trie é a estrutura de dados clássica usada para resolver esse problema porque combina tanto a eficiência da memória quanto a eficiência da pesquisa. Com uma lista de palavras de cerca de 400K palavras de tamanho razoável, você deve ser capaz de manter o trie na memória. (Em vez de optar por uma solução do tipo b-tree, na qual você mantém a maior parte da árvore no disco porque é grande demais para caber na memória de uma só vez.)
Um trie é basicamente nada mais do que uma árvore de 26 ários (assumindo que você está usando o alfabeto romano) onde cada nó tem uma letra e um bit adicional em cada nó que diz se é o fim da palavra.
Então, vamos esboçar a estrutura de dados:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Isso, claro, é apenas um esboço; você provavelmente gostaria de fazer com que eles tivessem acessores e construtores de propriedade adequados e outros enfeites. Além disso, talvez uma lista simples não seja a melhor estrutura de dados; talvez algum tipo de dicionário seja melhor. Meu conselho é fazê-lo funcionar primeiro e depois medir seu desempenho e, se for inaceitável, experimentar fazer alterações para melhorar seu desempenho.
Você pode começar com uma tentativa vazia:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Ou seja, este é o nó trie "raiz" que representa o início de uma palavra.
Como você adiciona a palavra "AA", a primeira palavra no dicionário do Scrabble? Bem, primeiro faça um nó para a primeira letra:
root.Children.Add('A', false, new List<TrieNode>());
OK, nossa tentativa é agora
^
|
A
Agora adicione um nó para a segunda letra:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Nossa tentativa é agora
^
|
A
|
A$ -- we notate the end of word flag with $
Excelente. Agora suponha que queremos adicionar AB. Já temos um nó para "A", então adicione a ele o nó "B$":
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
e agora temos
^
|
A
/ \
A$ B$
Continue assim. É claro que, em vez de escrever "root.Children[0]...", você escreverá um loop que pesquisa a tentativa para ver se o nó que você deseja existe e, se não, cria-o.
Para armazenar sua tentativa em disco - francamente, eu apenas armazenaria a lista de palavras como um arquivo de texto simples e reconstruiria a tentativa quando você precisar. Não deve demorar mais de 30 segundos ou mais, e então você pode reutilizar o trie na memória. Se você deseja armazenar o trie em algum formato que seja mais parecido com um trie, não deve ser difícil criar um formato de serialização.
Para procurar o trie para combinar com um rack, a ideia é explorar todas as partes do trie, mas podar as áreas onde o rack não pode corresponder. Se você não tiver nenhum "A" no rack, não há necessidade de descer nenhum nó "A". Eu esbocei o algoritmo de pesquisa na sua pergunta anterior.
Eu tenho uma implementação de uma tentativa persistente de estilo funcional sobre a qual eu queria escrever no blog há um tempo, mas nunca consegui. Se eu eventualmente postar que eu vou atualizar esta pergunta.
