Перечислите все слова в словаре, которые начинаются с <user input>

Question

Как можно создать программу, в которой пользователь вводит строку, а программа генерирует список слов, начинающихся с этой строки?

Пример:
Пользователь: "abd"
Программа: отречься от престола, живот, похитить ...

Спасибо!

---

Edit: я использую python, но я предполагаю, что это довольно независимая от языка проблема.

Answer 1

Используйте Три .

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

Answer 2

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

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

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

Answer 3

Если вы работаете на машине, подобной Debian,

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

Принимает все 0,040 с на моем P200.

Answer 4

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

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 (log (m)), а затем O (n) относительно количества строк, которые фактически начинаются с префикс, в то время как полное сканирование - O (m), с n << m. </p>

Answer 5

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

о, я не видел редактирование 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 6

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

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

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

Вы можете использовать str.startswith(). запись в официальные документы:

str.startswith (префикс [, начало [, конец]])

Вернуть True, если строка начинается с префикса, в противном случае вернуть False. Префикс также может быть набором префиксов для поиска. При необязательном запуске, тестовая строка начинается с этой позиции. При необязательном завершении прекратите сравнение строки в этой позиции.

как показано ниже:

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

Answer 9

Самое питоновское решение

# 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

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

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

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

Python получил тысячи API БД, чтобы помочь вам в работе; -)

Answer 10

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

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

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