una - elementos repetidos lista python

Enumera todas las palabras en un diccionario que comienzan con<user input>

Question

¿Cómo haría un programa en el que el usuario ingresa una cadena y el programa genera una lista de palabras que comienzan con esa cadena?

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

¡Gracias!

Editar: Estoy usando Python, pero supongo que este es un problema bastante independiente del lenguaje.

Answer 1

Intenta usar regex para buscar a través de tu lista de palabras, por ejemplo / ^ word / e informa todas las coincidencias.

Answer 2

Si está 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.040 en mi P200.

Answer 3

Si necesita ser realmente rápido, use un árbol:

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

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

Answer 4

Si realmente quieres ser eficiente, utiliza árboles de sufijos o matrices de sufijos. Artículo de Wikipedia .

Tu problema es qué árboles de sufijo fueron diseñados para manejar. Incluso hay implementación para Python - aquí

Answer 5

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

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

También podría usar un enfoque híbrido donde mantenga una lista ordenada que contenga su diccionario y use el gráfico dirigido como un índice en su diccionario. Luego, simplemente busque su prefijo en su gráfico dirigido y luego vaya a ese punto en su diccionario y escupe todas las palabras que coincidan con sus criterios de búsqueda.

Answer 6

Usa un trie

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

Answer 7

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)

Answer 8

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

Answer 9

No uses una bazuca para matar una mosca. Use algo simple como SQLite. Existen todas las herramientas que necesita para todos los idiomas modernos y puede hacer lo siguiente:

"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.

Tuto Python:

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

Answer 10

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 en realidad comienzan con el prefijo, mientras el escaneo completo es O (m), con n << m.

Answer 11

Si tu diccionario es realmente grande, te sugiero que indexes con un índice de texto python (PyLucene, ten en cuenta que nunca he usado la extensión python para lucene). La búsqueda sería eficiente e incluso podrías devolver una "puntuación" de búsqueda.

Además, si su diccionario es relativamente estático, ni siquiera tendrá la sobrecarga de volver a indexar con mucha frecuencia.

Answer 12

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]

Answer 13

Un escaneo lineal es lento, pero un árbol de prefijo es probablemente excesivo. Mantener las palabras ordenadas y usar una búsqueda binaria es un compromiso rápido y simple.

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'']

Answer 14

La mayoría de la solución Pythonic

# 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értalo en una lista (usando list (word_generator)) o use la función itertools.tee si espera usarlo 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 su diccionario, será mucho más rápido y eficiente.

Python obtuvo miles de DB API para ayudarte a hacer el trabajo ;-)