Enumere todas las palabras en un diccionario que comiencen con <entrada del usuario>

StackOverflow https://stackoverflow.com/questions/112532

  •  02-07-2019
  •  | 
  •  

Pregunta

¿Cómo se haría un programa en el que el usuario ingrese una cadena y el programa genere una lista de palabras que comiencen con esa cadena?

Ex:
Usuario:"abd"
Programa: abdicar, abdomen, abducir...

¡Gracias!

Editar:Estoy usando Python, pero supongo que se trata de un problema bastante independiente del idioma.

¿Fue útil?

Solución

Si estás en una máquina Debian[-like], 

#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words

Toma todos los 0.040s en mi P200.

Otros consejos

Usar una intentarlo.

Agregue su lista de palabras a un intento.Cada camino desde la raíz hasta la hoja es una palabra válida.Una ruta desde una raíz a un nodo intermedio representa un prefijo y los hijos del nodo intermedio son terminaciones válidas para el prefijo.

Una de las mejores formas de hacerlo es utilizar un gráfico dirigido para almacenar su diccionario.Se necesita un poco de configuración, pero una vez hecho esto, es bastante fácil realizar el tipo de búsquedas del que estás hablando.

Los nodos del gráfico corresponden a una letra de tu palabra, por lo que cada nodo tendrá un enlace entrante y hasta 26 (en inglés) enlaces salientes.

También puede utilizar un enfoque híbrido en el que mantenga una lista ordenada que contenga su diccionario y utilice el gráfico dirigido como índice en su diccionario.Luego simplemente busca su prefijo en su gráfico dirigido y luego va a ese punto en su diccionario y escupe todas las palabras que coinciden con sus criterios de búsqueda.

egrep `read input && echo ^$input` /usr/share/dict/words

oh, no vi la edición de Python, aquí está lo mismo en Python

my_input = raw_input("Enter beginning of word: ")
my_words = open("/usr/share/dict/words").readlines()
my_found_words = [x for x in my_words if x[0:len(my_input)] == my_input]

Si realmente quieres velocidad, usa un trie/autómata.Sin embargo, algo que será más rápido que simplemente escanear toda la lista, dado que la lista de palabras está ordenada:

from itertools import takewhile, islice
import bisect

def prefixes(words, pfx):
    return list(
             takewhile(lambda x: x.startswith(pfx), 
                       islice(words, 
                              bisect.bisect_right(words, pfx), 
                              len(words)))

Tenga en cuenta que un autómata es O(1) con respecto al tamaño de su diccionario, mientras que este algoritmo es O(log(m)) y luego O(n) con respecto al número de cadenas que realmente comienzan con el prefijo, mientras que el escaneo completo es O(m), con n << m.

def main(script, name):
    for word in open("/usr/share/dict/words"):
        if word.startswith(name):
            print word,

if __name__ == "__main__":
    import sys
    main(*sys.argv)

Si realmente quiere ser eficiente, utilice árboles de sufijos o matrices de sufijos. artículo de wikipedia.

Su problema es para qué fueron diseñados los árboles de sufijos.Incluso hay una implementación para Python: aquí

var words = from word in dictionary
            where word.key.StartsWith("bla-bla-bla");
            select word;

Intente usar expresiones regulares para buscar en su lista de palabras, p./^word/ e informar todas las coincidencias.

Si necesitas ser en realidad rápido, usa un árbol:

construya una matriz y divida las palabras en 26 conjuntos según la primera letra, luego divida cada elemento en 26 según la segunda letra, y luego nuevamente.

Entonces, si su usuario escribe "abd", buscará Array[0][1][3] y obtendrá una lista de todas las palabras que comienzan así.En ese punto, su lista debería ser lo suficientemente pequeña como para pasarla al cliente y usar javascript para filtrar.

La solución más pitónica

# set your list of words, whatever the source
words_list = ('cat', 'dog', 'banana')
# get the word from the user inpuit
user_word = raw_input("Enter a word:\n")
# create an generator, so your output is flexible and store almost nothing in memory
word_generator = (word for word in words_list if word.startswith(user_word))

# now you in, you can make anything you want with it 
# here we just list it :

for word in word_generator :
    print word

Recuerde que los generadores solo se pueden usar una vez, así que conviértalos en una lista (usando list(word_generator)) o use la función itertools.tee si espera usarlos más de una vez.

La mejor manera de hacerlo :

Guárdelo en una base de datos y use SQL para buscar la palabra que necesita.Si hay muchas palabras en tu diccionario, será mucho más rápido y eficiente.

Python tiene miles de API de base de datos para ayudarte a hacer el trabajo ;-)

Puedes usar str.startswith().grabación de los documentos oficiales:

str.startswith(prefijo[, inicio[, fin]])

Devuelve Verdadero si la cadena comienza con el prefijo; de lo contrario, devuelve Falso.El prefijo también puede ser una tupla de prefijos a buscar.Con inicio opcional, pruebe la cadena comenzando en esa posición.Con el final opcional, deje de comparar cadenas en esa posición.

como abajo:

user_input = input('Enter something: ')
for word in dictionary:
    if str.startswith(user_input):
        return word

Si su diccionario es realmente grande, sugeriría indexar con un índice de texto de Python (PyLucene; tenga en cuenta que nunca he usado la extensión de Python para lucene). La búsqueda sería eficiente e incluso podría devolver una 'puntuación' de búsqueda.

Además, si su diccionario es relativamente estático, ni siquiera tendrá que volver a indexarlo con mucha frecuencia.

No uses una bazuca para matar una mosca.Utilice algo simple como SQLite.Existen todas las herramientas que necesitas para todos los idiomas modernos y puedes simplemente hacer:

"SELECT word FROM dict WHERE word LIKE "user_entry%"

Es muy rápido y un bebé podría hacerlo.Además, es portátil, persistente y muy fácil de mantener.

Tutorial de Python:

http://www.initd.org/pub/software/pysqlite/doc/usage-guide.html

Un escaneo lineal es lento, pero un árbol de prefijos probablemente sea excesivo.Mantener las palabras ordenadas y utilizar una búsqueda binaria es un compromiso rápido y sencillo.

import bisect
words = sorted(map(str.strip, open('/usr/share/dict/words')))
def lookup(prefix):
    return words[bisect.bisect_left(words, prefix):bisect.bisect_right(words, prefix+'~')]

>>> lookup('abdicat')
['abdicate', 'abdication', 'abdicative', 'abdicator']

Si almacena las palabras en un archivo .csv, puede usar pandas para resolver esto de manera bastante clara, y después de haberlo leído una vez, puede reutilizar el marco de datos ya cargado si el usuario debe poder realizar más de una búsqueda por sesión. .

df = pd.read_csv('dictionary.csv')
matching_words = df[0].loc[df[0].str.startswith(user_entry)]
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top