usando tipos tda solución programas problemas listas lista estructuras estructura datos con algoritmos abstractos algorithm data-structures

algorithm - tda - tipos de datos abstractos en java



Buen algoritmo y estructura de datos para buscar palabras con letras faltantes. (20)

entonces necesito escribir un algoritmo eficiente para buscar palabras con letras faltantes en un diccionario y quiero el conjunto de palabras posibles.

Por ejemplo, si tengo esto, podría obtener estos, esos, tema, there.etc.

Me preguntaba si alguien puede sugerir algunas estructuras de datos o algoritmos que debería usar.

¡Gracias!

EDITAR: A Trie es demasiado ineficiente en el espacio y lo haría demasiado lento. ¿Alguna otra modificación de ideas?

ACTUALIZACIÓN: habrá hasta dos signos de interrogación y cuando se produzcan dos signos de interrogación, se producirán en secuencia.

Actualmente estoy usando 3 tablas hash para cuando es una coincidencia exacta, 1 signo de interrogación y 2 signos de interrogación. Dado un diccionario, tengo todas las palabras posibles. Por ejemplo, si tengo la palabra WORD. I hash WORD,? ORD, W? RD, WO? D, WOR ?, ?? RD, W ?? D, WO ??. en el diccionario. Luego utilizo una lista de enlaces para vincular las colisiones. Entonces, diga hash (W? RD) = hash (STR? NG) = 17. hashtab (17) apuntará a WORD y WORD apunta a STRING porque es una lista enlazada.

El tiempo de búsqueda promedio de una palabra es de aproximadamente 2e-6s. Estoy buscando hacerlo mejor, preferiblemente del orden de 1e-9.

EDITAR: No volví a examinar este problema, pero me llevó 0,5 segundos insertar entradas de 3m y tardé 4 segundos en buscar entradas de 3m.

¡Gracias!

¿Has considerado usar un Tree Search Ternary ? La velocidad de búsqueda es comparable a una trie, pero es más eficiente en el uso del espacio.

He implementado esta estructura de datos varias veces, y es una tarea bastante sencilla en la mayoría de los idiomas.

Así es como lo haría:

  1. Concatenar las palabras del diccionario en una cadena larga separada por un carácter sin palabras.
  2. Coloque todas las palabras en un TreeMap, donde la clave es la palabra y el valor es el desplazamiento del inicio de la palabra en el String grande.
  3. Encuentra la base de la cadena de búsqueda; es decir, la subcadena principal más grande que no incluye un ''?'' .
  4. Use TreeMap.higherKey(base) y TreeMap.lowerKey(next(base)) para encontrar el rango dentro de la cadena entre la cual se encontrarán las coincidencias. (El next método necesita calcular la siguiente palabra más grande a la cadena base con el mismo número o menos caracteres, por ejemplo, next("aa") es "ab" , next("az") es "b" ).
  5. Cree una expresión regular para la cadena de búsqueda y use Matcher.find() para buscar la subcadena correspondiente al rango.

Los pasos 1 y 2 se realizan de antemano dando una estructura de datos usando el espacio O(NlogN) donde N es el número de palabras.

Este enfoque degenera a una búsqueda de expresiones regulares de fuerza bruta de todo el diccionario cuando el ''?'' aparece en la primera posición, pero cuanto más a la derecha está, menos se necesita hacer.

EDITAR :

Para mejorar el rendimiento en el caso en que ''?'' es el primer personaje, crea una tabla de búsqueda secundaria que registra las compensaciones de inicio / final de las ejecuciones de palabras cuyo segundo carácter es ''a'', ''b'', y así sucesivamente. Esto se puede usar en el caso donde el primer no- ''?'' es el segundo personaje. ¿Puede nosotros un enfoque similar para los casos en que el primer no? '' es el tercer personaje, el cuarto personaje y así sucesivamente, pero terminas con números cada vez más grandes de tiradas cada vez más pequeñas, y finalmente esta "optimización" se vuelve ineficaz.

Un enfoque alternativo que requiere mucho más espacio, pero que es más rápido en la mayoría de los casos, es preparar la estructura de datos del diccionario como se indica arriba para todas las rotaciones de las palabras en el diccionario. Por ejemplo, la primera rotación consistiría en todas las palabras de 2 caracteres o más con el primer carácter de la palabra movido al final de la palabra. La segunda rotación sería palabras de 3 caracteres o más con los dos primeros caracteres movidos hasta el final, y así sucesivamente. Luego, para hacer la búsqueda, busque la secuencia más larga de no-''?'' personajes en la cadena de búsqueda. Si el índice del primer carácter de esta subcadena es N , utilice la Nth rotación para buscar los rangos, y busque en la enésima lista de palabras de rotación.

Construye un conjunto de hash de todas las palabras. Para encontrar coincidencias, reemplace los signos de interrogación en el patrón con cada posible combinación de letras. Si hay dos signos de interrogación, una consulta consiste en 26 2 = 676 búsquedas rápidas de tabla hash de tiempo constante.

import itertools words = set(open("/usr/share/dict/words").read().split()) def query(pattern): i = pattern.index(''?'') j = pattern.rindex(''?'') + 1 for combo in itertools.product(''abcdefghijklmnopqrstuvwxyz'', repeat=j-i): attempt = pattern[:i] + ''''.join(combo) + pattern[j:] if attempt in words: print attempt

Esto utiliza menos memoria que mi otra respuesta, pero se vuelve exponencialmente más lenta a medida que agrega más signos de interrogación.

Creo que en este caso lo mejor es usar un archivo plano donde cada palabra esté en una línea. Con esto puede usar convenientemente el poder de una búsqueda de expresión regular, que está altamente optimizada y probablemente superará cualquier estructura de datos que pueda idear para este problema.

Solución n. ° 1: uso de Regex

Esto funciona con el código de Ruby para este problema:

def query(str, data) r = Regexp.new("^#{str.gsub("?", ".")}$") idx = 0 begin idx = data.index(r, idx) if idx yield data[idx, str.size] idx += str.size + 1 end end while idx end start_time = Time.now query("?r?te", File.read("wordlist.txt")) do |w| puts w end puts Time.now - start_time

El archivo wordlist.txt contiene 45425 palabras (descargables here ). La salida del programa para query ?r?te es:

brute crate Crete grate irate prate write wrote 0.013689

Por lo tanto, se necesitan solo 37 milisegundos para leer todo el archivo y encontrar todas las coincidencias en él. Y escala muy bien para todo tipo de patrones de consulta, incluso cuando un Trie es muy lento:

consulta ????????????????e

counterproductive indistinguishable microarchitecture microprogrammable 0.018681

consulta ?h?a?r?c?l?

theatricals 0.013608

Esto se ve lo suficientemente rápido para mí.

Solución n. ° 2: Regex con datos preparados

Si desea ir aún más rápido, puede dividir la lista de palabras en cadenas que contengan palabras de igual longitud y simplemente buscar la correcta en función de la longitud de su consulta. Reemplace las últimas 5 líneas con este código:

def query_split(str, data) query(str, data[str.length]) do |w| yield w end end # prepare data data = Hash.new("") File.read("wordlist.txt").each_line do |w| data[w.length-1] += w end # use prepared data for query start_time = Time.now query_split("?r?te", data) do |w| puts w end puts Time.now - start_time

La construcción de la estructura de datos ahora toma aproximadamente 0.4 segundos, pero todas las consultas son aproximadamente 10 veces más rápidas (dependiendo del número de palabras con esa longitud):

  • ?r?te 0.001112 sec
  • ?h?a?r?c?l? 0.000852 sec
  • ????????????????e 0.000169 sec

Solución n. ° 3: Una gran tabla hash (requisitos actualizados)

Como ha modificado sus requisitos, puede ampliar fácilmente su idea para usar solo una tabla hash grande que contenga todos los resultados precalculados. Pero en lugar de solucionar las colisiones, puede confiar en el rendimiento de una tabla hash correctamente implementada.

Aquí creo una gran tabla hash, donde cada consulta posible se mapea a una lista de sus resultados:

def create_big_hash(data) h = Hash.new do |h,k| h[k] = Array.new end data.each_line do |l| w = l.strip # add all words with one ? w.length.times do |i| q = String.new(w) q[i] = "?" h[q].push w end # add all words with two ?? (w.length-1).times do |i| q = String.new(w) q[i, 2] = "??" h[q].push w end end h end # prepare data t = Time.new h = create_big_hash(File.read("wordlist.txt")) puts "#{Time.new - t} sec preparing data/n#{h.size} entries in big hash" # use prepared data for query t = Time.new h["?ood"].each do |w| puts w end puts (Time.new - t)

La salida es

4.960255 sec preparing data 616745 entries in big hash food good hood mood wood 2.0e-05

El rendimiento de la consulta es O (1), es solo una búsqueda en la tabla hash. El tiempo 2.0e-05 es probablemente inferior a la precisión del temporizador. Cuando lo ejecuto 1000 veces, obtengo un promedio de 1.958e-6 segundos por consulta. Para hacerlo más rápido, cambiaría a C ++ y usaría Google Sparse Hash, que es extremadamente eficiente en cuanto a memoria y rápido.

Solución # 4: ponte realmente serio

Todas las soluciones anteriores funcionan y deberían ser lo suficientemente buenas para muchos casos de uso. Si realmente quiere ponerse serio y tener mucho tiempo libre en sus manos, lea algunos buenos documentos:

Dadas las limitaciones actuales:

  • Habrá hasta 2 signos de interrogación
  • Cuando hay 2 signos de interrogación, aparecen juntos
  • Hay ~ 100,000 palabras en el diccionario, la longitud promedio de palabra es 6.

Tengo dos soluciones viables para ti:

La solución rápida: HASH

Puede usar un hash cuyas claves son sus palabras con hasta dos ''?'', Y los valores son una lista de palabras adecuadas. Este hash tendrá alrededor de 100,000 + 100,000 * 6 + 100,000 * 5 = 1,200,000 entradas (si tiene 2 signos de interrogación, solo necesita encontrar el lugar del primero ...). Cada entrada puede guardar una lista de palabras, o una lista de punteros a las palabras existentes. Si guarda una lista de punteros, y suponemos que hay en promedio menos de 20 palabras que coinciden con cada palabra con dos ''?'', Entonces la memoria adicional es menor a 20 * 1,200,000 = 24,000,000.

Si cada tamaño de puntero es de 4 bytes, el requisito de memoria aquí es (24,000,000 + 1,200,000) * 4 bytes = 100,800,000 bytes ~ = 96 mega bytes.

Para resumir esta solución:

  • Consumo de memoria: ~ 96 MB
  • Tiempo para cada búsqueda: calcular una función hash y seguir un puntero. O (1)

Nota: si desea utilizar un hash de un tamaño más pequeño, puede hacerlo, pero luego es mejor guardar un árbol de búsqueda balanceado en cada entrada en lugar de una lista vinculada, para un mejor rendimiento.

La solución del espacio, pero aún muy rápida: variación TRIE

Esta solución usa la siguiente observación:

Si el ''?'' los signos estaban al final de la palabra, sería una excelente solución.

La búsqueda en el trie buscaría en la longitud de la palabra, y para las últimas dos letras, un cruce DFS traería todas las terminaciones. Solución muy rápida y muy inteligente para la memoria.

Entonces usemos esta observación para construir algo que funcione exactamente así.

Puedes pensar en cada palabra que tienes en el diccionario, como una palabra que termina con @ (o cualquier otro símbolo que no exista en tu diccionario). Entonces la palabra ''espacio'' sería ''espacio @''. Ahora, si gira cada una de las palabras, con el signo ''@'', obtendrá lo siguiente:

space@, pace@s, ace@sp, *ce@spa*, e@spac

(no @ como primera letra).

Si inserta todas estas variaciones en un TRIE, puede encontrar fácilmente la palabra que está buscando en la longitud de la palabra, "rotando" su palabra.

Ejemplo: Desea encontrar todas las palabras que se ajusten a ''s ?? ce'' (una de ellas es espacio, otra es una porción). Construyes la palabra: s ?? ce @, y la rotas para que la? signo es al final. es decir, ''ce @ s ??''

Todas las variaciones de rotación existen dentro del trie, y específicamente ''ce @ spa'' (marcado con * arriba). Después de encontrar el comienzo, necesita revisar todas las continuaciones en la longitud adecuada y guardarlas. Entonces, necesitas rotarlos nuevamente para que @ sea la última letra, y walla - ¡tienes todas las palabras que estabas buscando!

Para resumir esta solución:

  • Consumo de memoria: para cada palabra, todas sus rotaciones aparecen en el trie. En promedio, * 6 del tamaño de la memoria se guarda en el trie. El tamaño de trie es alrededor de * 3 (solo adivinar ...) del espacio guardado en su interior. Entonces el espacio total necesario para este trie es 6 * 3 * 100,000 = 1,800,000 palabras ~ = 6.8 mega bytes.

  • Tiempo para cada búsqueda:

    • girando la palabra: O (longitud de la palabra)
    • buscando el comienzo en el trie: O (longitud de la palabra)
    • repasando todas las terminaciones: O (número de coincidencias)
    • girando las terminaciones: O (duración total de las respuestas)

    En resumen, es muy muy rápido y depende de la longitud de la palabra * constante pequeña.

Para resumir...

La segunda opción tiene una gran complejidad de tiempo / espacio, y sería la mejor opción para su uso. Hay algunos problemas con la segunda solución (en cuyo caso es posible que desee utilizar la primera solución):

  • Más complejo de implementar No estoy seguro de si hay lenguajes de programación con intentos incorporados de fábrica. Si no lo hay, significa que tendrá que implementarlo usted mismo ...
  • No escala bien Si mañana decides que necesitas que tus signos de interrogación se extiendan por todo el mundo, y no necesariamente se unan, tendrás que pensar detenidamente cómo encajar la segunda solución. En el caso de la primera solución, es bastante fácil generalizar.

La estructura de datos que desea se llama trie ; consulte el Trie para obtener un breve resumen.

Un trie es una estructura de árbol donde los caminos a través del árbol forman el conjunto de todas las palabras que desea codificar: cada nodo puede tener hasta 26 niños, para cada letra posible en la siguiente posición del carácter. Vea el diagrama en el artículo de wikipedia para ver a qué me refiero.

La segunda solución de Anna es la inspiración para este.

Primero, cargue todas las palabras en la memoria y divida el diccionario en secciones basadas en la longitud de la palabra.

Para cada longitud, haga n copias de una matriz de punteros a las palabras. Ordene cada matriz de modo que las cadenas aparezcan en orden cuando se gira con un cierto número de letras . Por ejemplo, supongamos que la lista original de palabras de 5 letras es [plano, manzana, espacio, tren, feliz, pila, pirateo]. Entonces sus cinco matrices de punteros serán:

rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train] rotated by 1 letter: [hacks, happy, plane, space, apple, train, stack] rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy] rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy] rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy]

(En lugar de punteros, puede usar números enteros que identifiquen las palabras, si eso ahorra espacio en su plataforma).

Para buscar, solo pregunte cuánto tendría que rotar el patrón para que los signos de interrogación aparezcan al final. Entonces puedes buscar binariamente en la lista apropiada.

Si necesita encontrar coincidencias para ?? ppy, tendría que rotar eso por 2 para hacer ppy ??. Así que busque en la matriz que está en orden cuando se gira con 2 letras. Una búsqueda binaria rápida encuentra que "feliz" es la única coincidencia.

Si necesitas encontrar coincidencias para el final, deberías rotar eso por 4 para hacer gth ??. Así que mira en la matriz 4, donde una búsqueda binaria encuentra que no hay coincidencias.

Esto funciona sin importar cuántos signos de interrogación hay, siempre y cuando todos aparezcan juntos.

Espacio requerido además del diccionario en sí: para palabras de longitud N, esto requiere espacio para punteros o enteros (N veces la cantidad de palabras de longitud N).

Tiempo por búsqueda : O (log n) donde n es el número de palabras de la longitud adecuada.

Implementación en Python:

import bisect class Matcher: def __init__(self, words): # Sort the words into bins by length. bins = [] for w in words: while len(bins) <= len(w): bins.append([]) bins[len(w)].append(w) # Make n copies of each list, sorted by rotations. for n in range(len(bins)): bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)] self.bins = bins def find(self, pattern): bins = self.bins if len(pattern) >= len(bins): return [] # Figure out which array to search. r = (pattern.rindex(''?'') + 1) % len(pattern) rpat = (pattern[r:] + pattern[:r]).rstrip(''?'') if ''?'' in rpat: raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern)) a = bins[len(pattern)][r] # Binary-search the array. class RotatedArray: def __len__(self): return len(a) def __getitem__(self, i): word = a[i] return word[r:] + word[:r] ra = RotatedArray() start = bisect.bisect(ra, rpat) stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1)) # Return the matches. return a[start:stop] words = open(''/usr/share/dict/words'', ''r'').read().split() print "Building matcher..." m = Matcher(words) # takes 1-2 seconds, for me print "Done." print m.find("st??k") print m.find("ov???low")

En mi computadora, el diccionario del sistema es 909KB grande y este programa usa aproximadamente 3.2MB de memoria además de lo que se necesita solo para almacenar las palabras (los punteros son 4 bytes). Para este diccionario, puede cortarlo a la mitad usando enteros de 2 bytes en lugar de punteros, porque hay menos de 2 16 palabras de cada longitud.

Medidas: en mi máquina, m.find("st??k") ejecuta en 0.000032 segundos, m.find("ov???low") en 0.000034 segundos y m.find("????????????????e") en 0.000023 segundos.

Al escribir la búsqueda binaria en lugar de usar la class RotatedArray y la biblioteca class RotatedArray , obtuve esos dos primeros números hasta 0.000016 segundos: el doble de rápido. Implementar esto en C ++ lo haría aún más rápido.

Mi primera publicación tuvo un error que Jason encontró, ¿no funcionó bien? estaba en el comienzo. Ahora he tomado prestados los cambios cíclicos de Anna.

Mi solución: introduzca un carácter de final de palabra (@) y almacene todas las palabras cíclicas desplazadas en arreglos ordenados. Use una matriz ordenada para cada longitud de palabra. Al buscar "th e @", cambie la cadena para mover las? -marks al final (obteniendo e @ th?) Y elija la matriz que contiene palabras de longitud 5 y realice una búsqueda binaria para que aparezca la primera palabra después de la cadena "e @ th". Todas las palabras restantes en la matriz coinciden, es decir, encontraremos "e @ thoo (thoose), e @ thes (these), etc.

La solución tiene un registro de complejidad de tiempo (N), donde N es el tamaño del diccionario, y expande el tamaño de los datos por un factor de 6 o más (la longitud promedio de la palabra)

Para mí, este problema parece una buena opción para una estructura de datos Trie . Ingrese el diccionario completo en su trie, y luego busque la palabra. Para una carta que falta, deberías probar todos los sub-tries, lo que debería ser relativamente fácil de hacer con un enfoque recursivo.

EDITAR : Escribí una implementación simple de esto en Ruby justo ahora: http://gist.github.com/262667 .

Primero, necesitamos una forma de comparar la cadena de consulta con una entrada determinada. Supongamos una función usando expresiones regulares: matches(query,trialstr) .

Un algoritmo O (n) sería simplemente ejecutar a través de cada elemento de la lista (su diccionario se representaría como una lista en el programa), comparando cada uno con su cadena de consulta.

Con un poco de cálculo previo, puede mejorar esto para un gran número de consultas construyendo una lista adicional de palabras para cada letra, para que su diccionario se vea así:

wordsbyletter = { ''a'' : [''aardvark'', ''abacus'', ... ], ''b'' : [''bat'', ''bar'', ...], .... }

Sin embargo, esto sería de uso limitado, especialmente si su cadena de consulta comienza con un carácter desconocido. Entonces podemos hacerlo aún mejor al notar en qué parte de una palabra determinada se encuentra una determinada letra, lo que genera:

wordsmap = { ''a'':{ 0:[''aardvark'', ''abacus''], 1:[''bat'',''bar''] 2:[''abacus'']}, ''b'':{ 0:[''bat'',''bar''], 1:[''abacus'']}, .... }

Como puede ver, sin usar índices, terminará incrementando enormemente la cantidad de espacio de almacenamiento requerido, específicamente un diccionario de n palabras y una longitud promedio de m requerirá nm 2 de almacenamiento. Sin embargo, ahora puedes buscar rápidamente todas las palabras de cada conjunto que coincida.

La optimización final (que puede usar de forma automática) es separar también todas las palabras de la misma longitud en tiendas separadas, ya que siempre sabe cuánto dura la palabra.

Esta versión sería O ( kx ) donde k es el número de letras conocidas en la palabra de consulta, y x = x ( n ) es el tiempo para buscar un solo elemento en un diccionario de longitud n en su implementación (generalmente log ( n ).

Entonces con un diccionario final como:

allmap = { 3 : { ''a'' : { 1 : [''ant'',''all''], 2 : [''bar'',''pat''] } ''b'' : { 1 : [''bar'',''boy''], ... } 4 : { ''a'' : { 1 : [''ante''], ....

Entonces nuestro algoritmo es justo:

possiblewords = set() firsttime = True wordlen = len(query) for idx,letter in enumerate(query): if(letter is not ''?''): matchesthisletter = set(allmap[wordlen][letter][idx]) if firsttime: possiblewords = matchesthisletter else: possiblewords &= matchesthisletter

Al final, las palabras possiblewords set contendrán todas las letras coincidentes.

Puedes echar un vistazo a cómo se hace en aspell . Sugiere sugerencias de palabras correctas para las palabras mal escritas.

Si el 80-90% de precisión es aceptable, podría hacerlo con el corrector ortográfico de Peter Norvig. La implementación es pequeña y elegante.

Si genera todas las palabras posibles que coinciden con el patrón (arate, arbte, arcte ... zryte, zrzte) y luego las busca en una representación de árbol binario del diccionario, que tendrá las características de rendimiento promedio de O (e ^ N1 * log (N2)) donde N1 es el número de signos de interrogación y N2 es el tamaño del diccionario. Parece lo suficientemente bueno para mí, pero estoy seguro de que es posible encontrar un mejor algoritmo.

EDITAR : Si tiene más que decir, tres signos de interrogación, eche un vistazo a la respuesta de Phil H y su enfoque de indexación de cartas.

Supongamos que tiene suficiente memoria, podría construir un hashmap gigante para proporcionar la respuesta en tiempo constante. Aquí hay un ejemplo rápido en Python:

from array import array all_words = open("english-words").read().split() big_map = {} def populate_map(word): for i in range(pow(2, len(word))): bin = _bin(i, len(word)) candidate = array(''c'', word) for j in range(len(word)): if bin[j] == "1": candidate[j] = "?" if candidate.tostring() in big_map: big_map[candidate.tostring()].add(word) else: big_map[candidate.tostring()] = set([word]) def _bin(x, width): return ''''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1)) def run(): for word in all_words: populate_map(word) run() >>> big_map["y??r"] set([''your'', ''year'']) >>> big_map["yo?r"] set([''your'']) >>> big_map["?o?r"] set([''four'', ''poor'', ''door'', ''your'', ''hour''])

Una solución basada en expresiones regulares considerará todos los valores posibles en su diccionario. Si el rendimiento es su mayor restricción, se podría construir un índice para acelerarlo considerablemente.

Podría comenzar con un índice en cada longitud de palabra que contenga un índice de cada índice = juego de palabras que coincidan con los caracteres. Para longitud 5 palabras, por ejemplo, 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group} , etc. Para obtener las posibles coincidencias para la consulta original, diga '' ? ro ?? '', los conjuntos de palabras se intersecarán, lo que da como resultado {wrote, group} en este caso.

Esto supone que el único comodín será un solo carácter y que la longitud de la palabra se conoce desde el principio. Si no se trata de suposiciones válidas, puedo recomendar la coincidencia de texto basada en n-gramas, tal como se analiza en este documento .

Una solución perezosa es permitir que SQLite u otro DBMS hagan el trabajo por usted.

Simplemente cree una base de datos en memoria, cargue sus palabras y ejecute una selección usando el operador LIKE.

Dirigido Acyclic Word Graph sería la estructura de datos perfecta para este problema. Combina la eficiencia de un trie (trie se puede ver como un caso especial de DAWG), pero es mucho más eficiente en el uso del espacio. El típico DAWG tomará una fracción del tamaño que tomaría el archivo de texto sin formato con las palabras.

La enumeración de palabras que cumplen condiciones específicas es simple y lo mismo que en trie; debe atravesar el gráfico en profundidad.

Resumen: utilice dos índices compactos de búsqueda binaria, una de las palabras y una de las palabras invertidas . El costo de espacio es 2N punteros para los índices; casi todas las búsquedas van muy rápido; el peor de los casos, "e", sigue siendo decente. Si crea tablas separadas para cada longitud de palabra, eso haría que incluso el peor caso sea muy rápido.

Detalles: Stephen C. publicó una buena idea : buscar un diccionario ordenado para encontrar el rango donde puede aparecer el patrón. Esto no ayuda, sin embargo, cuando el patrón comienza con un comodín. También puede indexar por longitud de palabra, pero aquí hay otra idea: agregue un índice ordenado en las palabras del diccionario invertidas ; luego, un patrón siempre arroja un pequeño rango en el índice directo o en el índice de palabra inversa (ya que nos dicen que no hay patrones como? ABCD?). Las palabras mismas deben almacenarse solo una vez, con las entradas de ambas estructuras apuntando a las mismas palabras, y el procedimiento de búsqueda visualizándolas hacia adelante o hacia atrás; but to use Python''s built-in binary-search function I''ve made two separate strings arrays instead, wasting some space. (I''m using a sorted array instead of a tree as others have suggested, as it saves space and goes at least as fast.)

Code :

import bisect, re def forward(string): return string def reverse(string): return string[::-1] index_forward = sorted(line.rstrip(''/n'') for line in open(''/usr/share/dict/words'')) index_reverse = sorted(map(reverse, index_forward)) def lookup(pattern): "Return a list of the dictionary words that match pattern." if reverse(pattern).find(''?'') <= pattern.find(''?''): key, index, fixup = pattern, index_forward, forward else: key, index, fixup = reverse(pattern), index_reverse, reverse assert all(c.isalpha() or c == ''?'' for c in pattern) lo = bisect.bisect_left(index, key.replace(''?'', ''A'')) hi = bisect.bisect_right(index, key.replace(''?'', ''z'')) r = re.compile(pattern.replace(''?'', ''.'') + ''$'') return filter(r.match, (fixup(index[i]) for i in range(lo, hi)))

Tests: (The code also works for patterns like ?AB?D?, though without the speed guarantee.)

>>> lookup(''hello'') [''hello''] >>> lookup(''??llo'') [''callo'', ''cello'', ''hello'', ''uhllo'', ''Rollo'', ''hollo'', ''nullo''] >>> lookup(''hel??'') [''helio'', ''helix'', ''hello'', ''helly'', ''heloe'', ''helve''] >>> lookup(''he?l'') [''heal'', ''heel'', ''hell'', ''heml'', ''herl''] >>> lookup(''hx?l'') []

Efficiency: This needs 2N pointers plus the space needed to store the dictionary-word text (in the tuned version). The worst-case time comes on the pattern ''??e'' which looks at 44062 candidates in my 235k-word /usr/share/dict/words; but almost all queries are much faster, like ''h??lo'' looking at 190, and indexing first on word-length would reduce ''??e'' almost to nothing if we need to. Each candidate-check goes faster than the hashtable lookups others have suggested.

This resembles the rotations-index solution, which avoids all false match candidates at the cost of needing about 10N pointers instead of 2N (supposing an average word-length of about 10, as in my /usr/share/dict/words).

You could do a single binary search per lookup, instead of two, using a custom search function that searches for both low-bound and high-bound together (so the shared part of the search isn''t repeated).

If you only have ? wildcards, no * wildcards that match a variable number of characters, you could try this: For each character index, build a dictionary from characters to sets of words. ie if the words are write, wrote, drate, arete, arite , your dictionary structure would look like this:

Character Index 0: ''a'' -> {"arete", "arite"} ''d'' -> {"drate"} ''w'' -> {"write", "wrote"} Character Index 1: ''r'' -> {"write", "wrote", "drate", "arete", "arite"} Character Index 2: ''a'' -> {"drate"} ''e'' -> {"arete"} ''i'' -> {"write", "arite"} ''o'' -> {"wrote"} ...

If you want to look up a?i?? you would take the set that corresponds to character index 0 => ''a'' {"arete", "arite"} and the set that corresponds to character index 2 = ''i'' => {"write", "arite"} and take the set intersection.

If you seriously want something on the order of a billion searches per second (though i can''t dream why anyone outside of someone making the next grand-master scrabble AI or something for a huge web service would want that fast), i recommend utilizing threading to spawn [number of cores on your machine] threads + a master thread that delegates work to all of those threads. Then apply the best solution you have found so far and hope you don''t run out of memory.

An idea i had is that you can speed up some cases by preparing sliced down dictionaries by letter then if you know the first letter of the selection you can resort to looking in a much smaller haystack.

Otro pensamiento que tuve fue que intentabas forzar a la fuerza bruta algo - ¿quizás construir una base de datos o una lista o algo para scrabble?