使用Python字典实现类似自动完成的功能

Question

在PHP中，我有这样一行代码 matches = preg_grep('/^for/', array_keys($hash));。这行代码的作用是从$hash中找出以“for”开头的单词，比如“fork”、“form”等。

在Python中，我有一个包含40万个单词的字典。这个字典的键是我想要在自动补全功能中展示的单词（而这些单词对应的值在这里没有意义）。我该如何返回与输入匹配的字典键呢？

举个例子，如果我有

my_dic = t{"fork" : True, "form" : True, "fold" : True, "fame" : True}

当我输入 "for" 时，它会返回一个包含 "fork" 和 "form" 的列表。

Answer 1

如果你想要一种特定的查找方式（比如上面提到的“以3个字符开头”），你可以通过围绕这个想法创建一个专门的查找字典，来快速解决问题。

q = {"fork":1, "form":2, "fold":3, "fame":4}
from collections import defaultdict
q1 = defaultdict(dict)
for k,v in q.items():
    q1[k[:3]][k]=v

这样你就可以在一个更小的集合中进行类似于 .startswith 的查找。

def getChoices(frag):
    d = q1.get(frag[:3])
    if d is None:
        return []
    return [ k for k in d.keys() if k.startswith(frag) ]

希望这样会比处理整整40万个键要快很多。

Answer 2

这不是直接回答你问题的内容，不过……

看起来你其实不想要一个字典来处理这个问题，你想要的是一种树状结构，对吧？

这样的话，你可以在每次输入字母时遍历这棵树（这个过程是恒定时间），然后从树的那个部分返回叶子节点，作为与那个前缀匹配的单词。

Answer 3

>>> mydict={"fork" : True, "form" : True, "fold" : True, "fame" : True}
>>> [k for k in mydict if k.startswith("for")]
['fork', 'form']

这样做应该比用普通的正则表达式快，而且如果你只是想找单词的开头，这个方法就足够了。