如何制作一个用户输入字符串的程序，然后程序会生成一个以该字符串开头的单词列表？
例如：
用户：“abd”
程序：abdicate，腹部，绑架......
谢谢！
编辑：我正在使用 python，但我认为这是一个相当独立于语言的问题。
stalepretzel
问问题
6852 次
16 回答
11
使用trie。
将您的单词列表添加到 trie 中。从根到叶的每条路径都是一个有效词。从根到中间节点的路径表示前缀，中间节点的子节点是前缀的有效补全。
于 2008-09-21T23:35:48.210 回答
8
最好的方法之一是使用有向图来存储您的字典。这需要一些设置，但是一旦完成，就可以很容易地进行您正在谈论的搜索类型。
图中的节点对应于单词中的一个字母，因此每个节点将有一个传入链接和最多 26 个（英文）传出链接。
您还可以使用混合方法，在其中维护包含字典的排序列表，并使用有向图作为字典的索引。然后，您只需在有向图中查找您的前缀，然后转到字典中的那个点并吐出所有符合您的搜索条件的单词。
于 2008-09-21T23:35:09.600 回答
6
如果你在 debian[-like] 机器上，
#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words
在我的 P200 上占用所有 0.040 秒。
于 2008-09-21T23:37:53.133 回答
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]
于 2008-09-21T23:50:59.810 回答
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。
于 2008-09-21T23:57:05.740 回答
2
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)
于 2008-09-21T23:35:07.493 回答
1
var words = from word in dictionary
where word.key.StartsWith("bla-bla-bla");
select word;
于 2008-09-21T23:29:51.063 回答
1
尝试使用正则表达式搜索您的单词列表，例如 /^word/ 并报告所有匹配项。
于 2008-09-21T23:30:13.777 回答
1
如果您需要非常快，请使用树：
构建一个数组并根据第一个字母将单词分成 26 个集合，然后根据第二个字母将每个项目分成 26 个，然后再一次。
因此，如果您的用户键入“abd”，您将查找 Array[0][1][3] 并获取所有以这样开头的单词的列表。此时，您的列表应该足够小，可以传递给客户端并使用 javascript 进行过滤。
于 2008-09-21T23:37:19.033 回答
1
大多数 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
请记住，生成器只能使用一次，因此将其转换为列表（使用 list(word_generator)）或使用 itertools.tee 函数，如果您希望多次使用它。
最好的方法：
将其存储到数据库中并使用 SQL 查找您需要的单词。如果您的字典中有很多单词，它会更快更高效。
Python 有数千个 DB API 来帮助你完成这项工作 ;-)
于 2008-11-21T11:11:41.757 回答
1
您可以使用str.startswith(). 录制到官方文档：
str.startswith(prefix[, start[, end]])
如果字符串以前缀开头，则返回 True，否则返回 False。prefix 也可以是要查找的前缀元组。使用可选开始，测试从该位置开始的字符串。使用可选结束，停止在该位置比较字符串。
如下所示：
user_input = input('Enter something: ')
for word in dictionary:
if str.startswith(user_input):
return word
于 2018-12-20T11:50:42.647 回答
0
如果您的字典真的很大，我建议使用 python 文本索引进行索引（PyLucene - 请注意，我从未使用过 lucene 的 python 扩展）搜索会很有效，您甚至可以返回搜索“分数”。
此外，如果您的字典是相对静态的，您甚至不会经常重新索引的开销。
于 2008-09-22T02:05:02.517 回答
0
不要用火箭筒杀死苍蝇。使用一些简单的东西，比如 SQLite。每种现代语言都有您需要的所有工具，您可以这样做：
"SELECT word FROM dict WHERE word LIKE "user_entry%"
闪电般的速度，一个婴儿可以做到。更重要的是，它便携、持久且易于维护。
Python教程：
http://www.initd.org/pub/software/pysqlite/doc/usage-guide.html
于 2008-09-22T09:39:15.467 回答
0
线性扫描很慢，但前缀树可能是矫枉过正。保持单词排序并使用二进制搜索是一种快速而简单的折衷方案。
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']
于 2008-11-20T19:04:05.080 回答
0
如果您将单词存储在 .csv 文件中，您可以使用 pandas 相当巧妙地解决此问题，并且在您阅读过一次之后，如果用户应该能够在每个会话中执行多个搜索，则可以重用已加载的数据框.
df = pd.read_csv('dictionary.csv')
matching_words = df[0].loc[df[0].str.startswith(user_entry)]
于 2018-12-20T08:15:25.103 回答