Elenca tutte le parole di un dizionario che iniziano con < user input >

Question

Come si potrebbe fare un programma in cui l'utente inserisce una stringa e il programma genera un elenco di parole che iniziano con quella stringa?

Ex:
Utente: " abd "
Programma: addome, addome, rapimento ...

Grazie!

---

Modifica: sto usando Python, ma presumo che questo sia un problema abbastanza indipendente dalla lingua.

Answer 1

Se utilizzi una macchina debian [-like],

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

Prende tutti gli 0.040 sul mio P200.

Answer 2

Utilizza un trie .

Aggiungi il tuo elenco di parole a un trie. Ogni percorso dalla radice a una foglia è una parola valida. Un percorso da una radice a un nodo intermedio rappresenta un prefisso e i figli del nodo intermedio sono completamenti validi per il prefisso.

Answer 3

Uno dei modi migliori per farlo è utilizzare un grafico diretto per memorizzare il dizionario. Ci vuole un po 'di configurazione, ma una volta fatto è abbastanza facile fare il tipo di ricerche di cui stai parlando.

I nodi nel grafico corrispondono a una lettera nella tua parola, quindi ogni nodo avrà un collegamento in entrata e fino a 26 (in inglese) collegamenti in uscita.

È inoltre possibile utilizzare un approccio ibrido in cui si mantiene un elenco ordinato contenente il dizionario e si utilizza il grafico diretto come indice nel dizionario. Quindi basta cercare il prefisso nel grafico diretto, quindi andare a quel punto nel dizionario e sputare tutte le parole corrispondenti ai criteri di ricerca.

Answer 4

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

oh non ho visto la modifica di Python, ecco la stessa cosa in 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 5

Se vuoi davvero la velocità, usa un trie / automa. Tuttavia, qualcosa che sarà più veloce della semplice scansione dell'intero elenco, dato che l'elenco di parole è ordinato:

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)))

Nota che un automa è O (1) per quanto riguarda le dimensioni del tuo dizionario, mentre questo algoritmo è O (log (m)) e quindi O (n) per quanto riguarda il numero di stringhe che iniziano effettivamente con il prefisso, mentre la scansione completa è O (m), con n < < m.

Answer 6

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 7

Se vuoi davvero essere efficiente - usa alberi di suffisso o matrici di suffissi - articolo di wikipedia .

Il tuo problema è ciò che gli alberi di suffisso sono stati progettati per gestire. Esiste persino un'implementazione per Python - qui

Answer 8

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

Answer 9

Prova a usare regex per cercare nel tuo elenco di parole, ad es. / ^ word / e segnala tutte le corrispondenze.

Answer 10

Se devi essere veramente veloce, usa un albero:

costruisci un array e dividi le parole in 26 set in base alla prima lettera, quindi dividi ogni elemento in 26 in base alla seconda lettera, quindi di nuovo.

Quindi, se l'utente digita " abd " dovresti cercare Array [0] [1] [3] e ottenere un elenco di tutte le parole che iniziano così. A quel punto il tuo elenco dovrebbe essere abbastanza piccolo da passare al client e utilizzare javascript per filtrare.

Answer 11

La maggior parte della soluzione 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

Ricorda che i generatori possono essere usati solo una volta, quindi trasformalo in un elenco (usando list (word_generator)) o usa la funzione itertools.tee se ti aspetti di usarlo più di una volta.

Il modo migliore per farlo:

Conservalo in un database e usa SQL per cercare la parola che ti serve. Se ci sono molte parole nel tuo dizionario, sarà molto più veloce ed efficiente.

Python ha ottenuto migliaia di API DB per aiutarti a fare il lavoro ;-)

Answer 12

Puoi usare str.startswith () . registrando nei documenti ufficiali:

str.startswith (prefisso [, inizio [, fine]])

Restituisce True se la stringa inizia con il prefisso, altrimenti restituisce False. il prefisso può anche essere una tupla di prefissi da cercare. Con l'avvio opzionale, testare la stringa che inizia in quella posizione. Con l'estremità facoltativa, smetti di confrontare la stringa in quella posizione.

come sotto:

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

Answer 13

Se il tuo dizionario è davvero grande, suggerirei di indicizzare con un indice di testo in Python (PyLucene - nota che non ho mai usato l'estensione Python per Lucene) La ricerca sarebbe efficiente e potresti persino restituire un punteggio '.

Inoltre, se il tuo dizionario è relativamente statico, non avrai nemmeno il sovraccarico di reindicizzare molto spesso.

Answer 14

Non usare un bazooka per uccidere una mosca. Usa qualcosa di semplice come SQLite. Ci sono tutti gli strumenti di cui hai bisogno per ogni lingua moderna e puoi semplicemente fare:

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

È velocissimo e un bambino potrebbe farlo. Inoltre, è portatile, persistente e di facile manutenzione.

Tutorial Python:

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

Answer 15

Una scansione lineare è lenta, ma un albero di prefissi è probabilmente eccessivo. Mantenere le parole ordinate e usare una ricerca binaria è un compromesso semplice e veloce.

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 16

Se si memorizzano le parole in un file .csv, è possibile utilizzare Panda per risolverlo piuttosto ordinatamente e dopo averlo letto una volta è possibile riutilizzare il frame di dati già caricato se l'utente dovrebbe essere in grado di eseguire più di uno ricerca per sessione.

df = pd.read_csv('dictionary.csv')
matching_words = df[0].loc[df[0].str.startswith(user_entry)]