Перечислите все слова в словаре, которые запускаются с <ввода данных пользователем>

Линейное сканирование является медленным, но дерево префикса является, вероятно, излишеством. Хранение отсортированных слов и использование двоичного поиска являются быстрым и простым компромиссом.

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

Если бы Ваш словарь является действительно большим, я предложил бы индексировать с текстовым индексом Python (PyLucene - отмечают, что я никогда не использовал расширение Python для lucene), поиск был бы эффективен, и Вы могли даже возвратить поисковый 'счет'.

Кроме того, если Ваш словарь будет относительно статичен, то у Вас даже не будет издержек переиндексации очень часто.

Не используйте симметрирующее устройство для уничтожения мухи. Используйте что-то простое точно так же, как SQLite. Существуют все инструменты, Вам нужны для каждого современные языки, и можно просто сделать:

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

Это - молния быстро, и ребенок мог сделать это. Что больше, это является портативным, персистентным и настолько легким поддержать.

Python tuto:

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

Большая часть решения 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

Помните, что генераторы могут только использоваться однажды, так поверните его к списку (использующий список (word_generator)) или используйте функцию itertools.tee, если Вы ожидаете использовать его несколько раз.

Лучший способ сделать это:

Сохраните его в базу данных и используйте SQL для поиска слова, в котором Вы нуждаетесь. Если будет много слов в Вашем словаре, то это будет намного быстрее и эффективным.

Python заставил тысячу DB API помогать Вам сделать задание ;-)

Попытайтесь использовать regex, чтобы перерыть Ваш список слов, например,/^word/и сообщить обо всех соответствиях.

Если необходимо быть действительно быстрыми, используйте дерево:

создайте массив и разделите слова в 26 наборах на основе первой буквы, затем разделите каждый объект в 26 на основе второй буквы с другой стороны.

Таким образом, если бы Ваш пользователь вводит "abd", Вы искали бы Массив [0] [1] [3] и получили бы список всех слов, запускающихся как этот. В той точке Ваш список должен быть достаточно маленьким, чтобы передать клиенту и использовать JavaScript для фильтрации.

Если Вы действительно хотите быть эффективными - используют суффиксные деревья или суффиксные массивы - статья Википедии.

Ваша проблема - то, что суффиксные деревья были разработаны для обработки. Существует даже реализация для Python - здесь

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)

Если Вы действительно хотите скорость, используйте trie/automaton. Однако что-то, что будет быстрее, чем простое сканирование целого списка, учитывая, что список слов отсортирован:

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

Обратите внимание, что автомат является O (1) относительно размера Вашего словаря, в то время как этот алгоритм является O (журнал (m)) и затем O (n) относительно количества строк, которые на самом деле запускаются с префикса, в то время как полное сканирование является O (m) с n <<m.

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

о, я не видел редактирование Python, вот то же самое в 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]

Один из лучших способов сделать это должно использовать ориентированного графа для хранения словаря. Это занимается определенной установкой, но когда-то сделанный довольно легко затем сделать тип поисков, о которых Вы говорите.

Узлы в графике соответствуют букве в Вашем слове, таким образом, каждый узел будет иметь одну входящую ссылку и до 26 (на английском языке) исходящими ссылками.

Вы могли также использовать гибридный подход, где Вы ведете отсортированный список, содержащий Ваш словарь, и используете ориентированного графа в качестве индекса в Ваш словарь. Затем Вы просто ищете свой префикс в Вашем ориентированном графе и затем переходите к той точке в Вашем словаре и выкладываете все слова, соответствующие Вашим критериям поиска.

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

Используйте trie.

Добавьте свой список слов к trie. Каждый путь от корня до листа является допустимым словом. Путь от корня до промежуточного узла представляет префикс, и дети промежуточного узла являются допустимыми завершениями для префикса.