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

Question

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

Бывший:
Пользователь:"abd"
Программа: отречься, живот, отведение...

Спасибо!

---

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

Answer 1

Если вы используете [похожую на debian] машину,

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

На моем P200 уходит всего 0,040 секунды.

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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]

Answer 5

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

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

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

Answer 8

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

Answer 9

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

Answer 10

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

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

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

Answer 11

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

# 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 есть тысячи DB API, которые помогут вам выполнить эту работу ;-)

Answer 12

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

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

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

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

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

Answer 13

Если ваш словарь действительно большой, я бы предложил индексировать с помощью текстового индекса python (PyLucene - обратите внимание, что я никогда не использовал расширение python для lucene) Поиск был бы эффективным, и вы даже могли бы вернуть результат поиска "оценка".

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

Answer 14

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

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

Это происходит молниеносно, и ребенок мог бы это сделать.Более того, он портативный, стойкий и очень прост в обслуживании.

Python tuto :

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

Answer 15

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

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

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

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