Si se le permite ignorar el caso, lo que supongo, a continuación, haga todas las palabras en su diccionario y todos los términos de búsqueda en el mismo caso antes que cualquier otra cosa. La mayúscula o minúscula no hace diferencia. Si tiene algunas palabras que distinguen entre mayúsculas y minúsculas y otras que no lo son, divida las palabras en dos grupos y busque cada una por separado.
Usted solo es palabras coincidentes, entonces usted puede partir el diccionario en una variedad de cadenas. Como solo hace una coincidencia exacta con una longitud conocida, divida la matriz de palabras en una matriz separada para cada longitud de palabra. Entonces por Longitud [3] es la matriz de todas las palabras con longitud 3. Cada matriz de palabras debe ser ordenada.
Ahora tiene una serie de palabras y una palabra con posibles comodines para encontrar. Dependiendo de dónde estén y de dónde estén los comodines, hay algunos enfoques.
Si el término de búsqueda no tiene comodines, realice una búsqueda binaria en la matriz ordenada. Podría hacer un hash en este punto, que sería más rápido pero no demasiado. Si la gran mayoría de los términos de búsqueda no tienen comodines, considere una tabla hash o una matriz asociativa con la clave hash.
Si el término de búsqueda tiene comodines después de algunos caracteres literales, realice una búsqueda binaria en la matriz ordenada para encontrar un límite superior e inferior, luego realice una búsqueda lineal en ese límite. Si los comodines están todos detrás, es suficiente encontrar un rango no vacío.
Si el término de búsqueda comienza con comodines, la matriz ordenada no es de ayuda y tendría que hacer una búsqueda lineal a menos que conserve una copia de la matriz ordenada por cadenas hacia atrás. Si crea una matriz así, selecciónela cada vez que haya más caracteres finales que literales iniciales. Si no permite comodines principales, entonces no hay necesidad.
Si el término de búsqueda comienza y termina con comodines, entonces tiene una búsqueda lineal dentro de las palabras con la misma longitud.
Así que una matriz de matrices de cadenas. Cada matriz de cadenas está ordenada y contiene cadenas de igual longitud. Opcionalmente, duplique toda la estructura con la clasificación basada en cadenas hacia atrás para el caso de comodines principales.
El espacio total es de uno o dos punteros por palabra, más las palabras. Debería poder almacenar todas las palabras en un solo buffer si su lenguaje lo permite. Por supuesto, si su lenguaje no lo permite, grep es probablemente más rápido de todos modos. Para un millón de palabras, eso es 4-16MB para las matrices y similar para las palabras reales.
Para un término de búsqueda sin comodines, el rendimiento sería muy bueno.Con comodines, ocasionalmente habrá búsquedas lineales en grupos grandes de palabras. Con el desglose por longitud y un solo personaje principal, nunca debería necesitar buscar más de un pequeño porcentaje del total del diccionario, incluso en el peor de los casos. La comparación de palabras completas de longitud conocida siempre será más rápida que la coincidencia de cadenas genéricas.
No estoy seguro, pero creo que un Suffix Tree podría ser lo que estás buscando - http://en.wikipedia.org/wiki/Suffix_tree – Rubys
Tienes que admitir todos los comodines estilo grep o solo ? (guión bajo _ en su caso)? –
¿Los comodines coinciden solo con un solo carácter o pueden coincidir con una cadena de longitud arbitraria? – drawnonward