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

Question

在PHP中，我有这一行代码matches = preg_grep('/^for/', array_keys($hash));它的功能是从$hash中获取以fork、form等开头的单词。

在Python中，我有一个包含400,000个单词的字典。它的键是我想要呈现在自动完成功能中的单词（在这种情况下，值是无意义的）。如何能够返回与输入匹配的字典键？

例如（如前面所用），如果我有：

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

如果我输入"for"，它会返回一个列表，其中包括"fork"和"form"。

- tipu

---

'fold' 不太像 'for'。 - SilentGhost

SilentGhost：你说得完全正确，已经编辑过了。 - tipu

Answer 1

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

这种方法比使用正则表达式更快（如果你只是查找单词开头的话，这种方法已经足够）。

- Tim Pietzcker

Answer 2

所以这并不是你所问的直接答案，但是...

看起来你并不想要一个这种类型的字典，你是在寻找一种树状结构，对吧？

然后你可以遍历每个被敲入的字母的树（常量时间），并从该子树返回作为与该前缀匹配的单词的叶节点。

- joshk0

---

这个特定的情况并不是我使用字典的唯一时刻。它是一个倒排索引，因此值是一组文档ID，对我正在做的事情非常重要。我使用字典的原因是查找速度比树快得多（内存很多，CPU周期不够）。 - tipu

尽管使用字典进行已知键查找比树结构更快，但是必须为每个键测试部分匹配时不会更快 - 因此，在您事先不知道键的情况下（例如上面所述），使用类似树的结构会更好。 - pycruft

FYI，此问题的完美数据结构称为Trie - 但Python的标准库没有。 - Jochen Ritzel

Answer 3

>>> my_dict = {"fork" : True, "form" : True, "fold" : True, "fame" : True}
>>> import re
>>> [s for s in my_dict if re.search('^for', s) is not None]
['fork', 'form']

正则表达式的使用更加通用，因为它可以提供更复杂的搜索模式。如果只是关于前缀的问题，你可以使用字符串方法：str.startwith，例如：

>>> [s for s in my_dict if s.startswith('for')]
['fork', 'form']

- SilentGhost

Answer 4

如果您想要一个特定的查找策略（例如上面概述的“startswith 3 chars”），那么您可能可以通过创建基于该想法的特定查找字典来获得快速胜利。

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

希望这比处理全部 400,000 个键要快得多。

- pycruft

Answer 5

你可以使用 my_dict.keys() 从 my_dict 中获取键。然后，你可以搜索每个键，看它是否与你的正则表达式匹配。

m = re.compile('^for')
keys = []
for key in my_dict.keys():
   if m.match(key) != None:
      keys.append(key)

- Donald Miner