Todas palavras em um dicionário que começam com

Question

Como é que um vai sobre fazer um programa onde o usuário digita uma string, eo programa gera uma lista de palavras que começam com essa seqüência?

Ex:
Usuário: "abd"
Programa: abdicar, abdômen, sequestre ...

Obrigado!

---

Edit:. Eu estou usando python, mas eu suponho que este é um problema bastante-linguagem independente

Answer 1

Se você em um debian [-como] máquina,

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

Toma todos 0.040s no meu P200.

Answer 2

Use a trie .

Adicione a sua lista de palavras a um trie. Cada caminho da raiz para uma folha é uma palavra válida. Um caminho de uma raiz de um nó intermediário representa um prefixo, e os filhos do nó intermediário são conclusões válidas para o prefixo.

Answer 3

Uma das melhores maneiras de fazer isso é usar um grafo direcionado para armazenar seu dicionário. É preciso um pouco de configuração, mas uma vez feito, é bastante fácil, em seguida, fazer o tipo de pesquisas que você está falando.

Os nós no correspondem gráfico para uma carta em sua palavra, para cada nó terá um link de entrada e até 26 (em Inglês) links de saída.

Você também pode usar uma abordagem híbrida onde você manter uma lista ordenada contendo seu dicionário e usar o gráfico dirigido como um índice em seu dicionário. Então você só olhar para cima seu prefixo em seu gráfico dirigido e depois ir a esse ponto em seu dicionário e cuspir todas as palavras correspondentes aos seus critérios de busca.

Answer 4

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

oh eu não vi a edição Python, aqui é a mesma coisa em 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 você realmente quiser velocidade, usar um trie / autômato. No entanto, algo que será mais rápido do que simplesmente a digitalização de toda a lista, uma vez que a lista de palavras é 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)))

Note que um autômato é O (1) no que diz respeito ao tamanho do seu dicionário, enquanto este algoritmo é O (log (m)) e, em seguida, O (n) em relação ao número de cordas que realmente começar com o prefixo, enquanto a verificação completa é o (m), com 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 você realmente quer ser eficiente - árvores uso sufixo ou arranjos de sufixos - wikipedia artigo .

Seu problema é que árvores de sufixo foram projetados para lidar. Existe ainda a implementação de Python - aqui

Answer 8

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

Answer 9

Tente usar regex para pesquisa através de sua lista de palavras, por exemplo, / ^ Word / e relatar todos os jogos.

Answer 10

Se você precisa estar realmente rápido, usar uma árvore:

construir um array e dividir as palavras em 26 conjuntos com base na primeira carta, em seguida, dividir cada item no 26 com base na segunda carta, em seguida, novamente.

Portanto, se seus tipos de usuário "abd" você olharia para Array [0] [1] [3] e obter uma lista de todas as palavras que começam assim. Nesse ponto, sua lista deve ser pequeno o suficiente para passar para o cliente e usar o JavaScript para filtro.

Answer 11

Solução mais 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

Lembre-se de geradores só pode ser usado uma vez, de modo a transformar a uma lista (usando a lista (word_generator)) ou usar a função itertools.tee se você espera usá-lo mais de uma vez.

A melhor maneira de fazê-lo:

loja-lo em um banco de dados e utilização de SQL para procurar a palavra que você precisa. Se houver um monte de palavras em seu dicionário, ela será muito mais rápido e eficiente.

Python tem milhares de DB API para ajudar você a fazer o trabalho; -)

Answer 12

Você pode usar str.startswith(). gravação para os documentos oficiais:

str.startswith (prefixo [, iniciar [, final]])

retornar TRUE se string começa com o prefixo, caso contrário retorna False. prefixo também pode ser uma tupla de prefixos que procurar. Com início opcional, corda teste começando nessa posição. Com o fim opcional, parar de comparar corda nessa posição.

como abaixo:

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

Answer 13

Se o seu dicionário é muito grande, eu sugiro indexação com um índice de texto python (PyLucene - note que eu nunca usei a extensão python para Lucene) A busca seria eficiente e você poderia até mesmo retornar uma pesquisa pontuação' '.

Além disso, se o dicionário é relativamente estática que você não vai mesmo ter a sobrecarga de re-indexação muito frequentemente.

Answer 14

Não use uma bazuca para matar uma mosca. Use algo simples como SQLite. Há todas as ferramentas que você precisa para todas as línguas modernas e você pode apenas fazer:

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

rápido, é um raio e um bebê poderia fazê-lo. O que é mais é portátil, persistente e tão fácil de manter.

Python tuto:

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

Answer 15

Um linear varredura é lento, mas uma árvore prefixo é provavelmente um exagero. Manter as palavras classificado e usando uma pesquisa binária é um rápido e simples compromisso.

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 você armazenar as palavras em um arquivo .csv, você pode usar pandas para resolver este sim nitidamente, e depois de ter lido uma vez que você pode reutilizar o quadro de dados já carregado se o usuário deve ser capaz de executar mais de uma procurar por sessão.

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