En primer lugar, veamos las restricciones del problema. Desea almacenar una lista de palabras para un juego en una estructura de datos que admita de manera eficiente el problema del "anagrama". Es decir, dado un "rack" de n letras, ¿cuáles son todas las palabras de n o menos letras en la lista de palabras que se pueden formar a partir de ese rack? la lista de palabras tendrá unas 400 000 palabras, por lo que es probable que tenga entre uno y diez megas de datos de cadenas sin comprimir.
Un trie es la estructura de datos clásica utilizada para resolver este problema porque combina la eficiencia de la memoria con la eficiencia de la búsqueda. Con una lista de palabras de unas 400 000 palabras de longitud razonable, debería poder mantener el trie en la memoria. (A diferencia de optar por una solución tipo b-tree en la que mantiene la mayor parte del árbol en el disco porque es demasiado grande para caber en la memoria de una sola vez).
Un trie es básicamente nada más que un árbol de 26 arios (asumiendo que estás usando el alfabeto romano) donde cada nodo tiene una letra y un bit adicional en cada nodo que dice si es el final de la palabra.
Entonces, dibujemos la estructura de datos:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Esto, por supuesto, es solo un boceto; probablemente querrá hacer que estos tengan accesos y constructores de propiedad adecuados y todo eso. Además, tal vez una lista plana no sea la mejor estructura de datos; tal vez algún tipo de diccionario es mejor. Mi consejo es hacer que funcione primero y luego medir su rendimiento y, si es inaceptable, experimentar con cambios para mejorar su rendimiento.
Puede comenzar con un trie vacío:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Es decir, este es el nodo trie "raíz" que representa el comienzo de una palabra.
¿Cómo se agrega la palabra "AA", la primera palabra en el diccionario de Scrabble? Bueno, primero haz un nodo para la primera letra:
root.Children.Add('A', false, new List<TrieNode>());
Bien, nuestra prueba es ahora
^
|
A
Ahora agregue un nodo para la segunda letra:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Nuestro intento es ahora
^
|
A
|
A$ -- we notate the end of word flag with $
Estupendo. Ahora supongamos que queremos agregar AB. Ya tenemos un nodo para "A", así que añádele el nodo "B$":
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
y ahora tenemos
^
|
A
/ \
A$ B$
Sigue así. Por supuesto, en lugar de escribir "root.Children[0]...", escribirá un bucle que busca en el trie para ver si existe el nodo que desea y, si no, lo crea.
Para almacenar su trie en el disco, francamente, simplemente almacenaría la lista de palabras como un archivo de texto sin formato y reconstruiría el trie cuando lo necesite. No debería tomar más de 30 segundos más o menos, y luego puede volver a usar el trie en la memoria. Si desea almacenar el trie en algún formato que se parezca más a un trie, no debería ser difícil encontrar un formato de serialización.
Para buscar el trie para que coincida con un bastidor, la idea es explorar cada parte del trie, pero eliminar las áreas donde el bastidor no puede coincidir. Si no tiene ninguna "A" en el bastidor, no es necesario bajar ningún nodo "A". Esbocé el algoritmo de búsqueda en su pregunta anterior.
Tengo una implementación de un intento persistente de estilo funcional sobre el que he tenido la intención de escribir un blog durante un tiempo, pero nunca lo logré. Si finalmente lo publico, actualizaré esta pregunta.
