使用部分关键字搜索Python字典的最快方法

Question

如何快速确定字典中是否包含以特定字符串开头的键？我们能否比线性更好？当我们只知道键的开头时，怎样才能实现O(1)操作？

以下是当前的解决方案：

for key in dict.keys():
    if key.start_with(str):
        return True
return False

- Yuming Cao

---

我怀疑你无法做得更好，因为你无法从密钥的一部分推断出其哈希值。此外，如果两个密钥以相同的前缀开头，这也会留下歧义的余地。 - Hyperboreus

有一些数据结构可以做到这一点，但它们不在Python标准库中提供。例如，Tries或二叉搜索树。 - user395760

由于问题涉及速度，我觉得有必要指出for key in dict_:比for key in dict_.keys():更快，因为后者会构建一个键列表。 - Chris Barker

@ChrisBarker：对于Python 2.7来说，你说得很好；对于不可变操作的键，可以使用dict.viewkeys()。 - Jakub M.

我想知道是否可以通过子类化str来在字典键中本地获取此行为... - 2rs2ts

使用像arshajii回答中提到的trie。基本上，每个前缀字符串中的每个字符只需要进行1次字典查找。 - nmclean

Answer 1

不对字典进行预处理，O(n) 是你能做到的最好结果。但这并不一定要复杂：

any(key.startswith(mystr) for key in mydict)

不要使用 dict 和 str 作为变量名，因为它们已经是两个内置函数的名称。

如果您可以预处理字典，请考虑将键放入前缀树中（也称为trie）。甚至在维基百科文章中还有一个Python实现。

- arshajii

---

一棵Trie树的时间复杂度是O(log N)，而不是O(1)。但它几乎肯定是你在这里想要的。这几乎是数据结构的典型案例。 - abarnert

@abarnert 不，除非你做出奇怪的假设，即最大字符串长度是字符串数量的对数。在trie中查找是与键的长度成线性关系的，因此与trie中的字符串数量无关。 - user395760

@delnan：N 不是字符串的数量，而是不同符号的数量。如果您有一小部分且静态的符号（例如 ASCII 字符串），则可以忽略它。如果您有大量符号（例如任意 Unicode），则无法忽略。要么在每个 trie 级别上进行线性搜索，要么进行对数 N 次搜索。（是的，它也与字符串长度成线性关系，我忽略了这一点...） - abarnert

@abarnert 字母表大小几乎总是恒定的。此外，我熟悉并倾向于假设的表示（虽然还有其他方法）使用数组来进行符号的子节点的常数时间查找。这甚至适用于非常大的Unicode字母表，通过使用UTF-8代码单元而不是代码点作为节点，而不会浪费太多空间。或者，使用一个像样的哈希表以获得O(1)平均时间。 - user395760

如果你需要返回键本身（默认情况下，在没有匹配项时为“None”）：next((key for key in mydict if key.startswith(mystr)), None)。请注意，这将在迭代字典键无特定顺序时返回第一个匹配项，并停止匹配。 - Mr. Llama

维基百科文章不再有Python实现，但是如果你搜索一下，你可以很容易地找到一些。 - John Y

Answer 2

你可以将插入的键的所有前缀放入字典中，因此对于键foo，您将插入f，fo和foo。您将拥有O(1)的查找，但是您将花费时间进行预处理（O(k)，其中k是键长度），并浪费大量内存：

def insert_with_prefixes(key, value, dict_):
  prefixes = (key[:i+1] for i in xrange(len(key)))
  dict_.update((prefix, value) for prefix in prefixes)

对于日常使用，我会选择（并且我正在选择）arshajii答案中的方法。当然，要注意短前缀（这里是"h"）可能会有多个冲突：

>>> a = {}
>>> insert_with_prefixes('hello', 'world', a)
>>> insert_with_prefixes('homo', 'sapiens', a)
>>> a
{'h': 'sapiens', 'hom': 'sapiens', 'homo': 'sapiens', 'ho': 'sapiens', 
 'hel': 'world', 'hell': 'world', 'hello': 'world', 'he': 'world'}

- Jakub M.