提取匹配字符串的最快方法

Question

我想搜索与列表中给定词相匹配的词（如下例）。但是，假设有一个包含数百万个单词的列表。执行此搜索的最有效方法是什么？我正在考虑标记每个列表并将单词放入哈希表中。然后执行单词搜索/匹配并检索包含该单词的单词列表。据我所见，此操作将进行 O(n) 操作。还有别的办法吗？可能不使用哈希表？

words_list = ['yek', 'lion', 'opt'];
# e.g. if we were to search or match the word "key" with the words in the list we should get the word "yek" or a list of words if there many that match

此外，是否有 python 库或第三方包可以执行高效搜索？

Answer 1

这里的 "match" 的意思还不是很清楚，但是如果可以将其简化为身份比较，问题就简化为集合查找，即 O(1) 时间。

例如，如果"match"表示"has exactly the same set of characters"：

words_set = {frozenset(word) for word in words_list}

然后，查一个字：

frozenset(word) in words_set

或者，如果它意味着 "has exactly the same multiset of characters"（即计算重复项但忽略顺序）：

words_set = {sorted(word) for word in words_list}

sorted(word) in words_set

... 或者，如果您愿意：

words_set = {collections.Counter(word) for word in words_list}

collections.Counter(word) in words_set

无论哪种方式，这里的关键（不是双关语……但也许应该是）的想法是提出一个转换，将您的值（字符串）转换为相同的值，前提是它们匹配（一组字符、字符的多集、已排序字符的有序列表等）。然后，集合的全部意义在于它可以在恒定时间内寻找与您的值相等的值。

当然，转换列表需要 O(N) 时间（除非你只是首先构建转换后的集合，而不是构建列表然后转换它），但你可以反复使用它，并且每次都需要 O(1) 时间而不是 O(N)，这听起来像是你关心的。

如果你需要找回匹配的词而不是只知道有一个，你仍然可以用一组来做，但它更容易（如果你能负担得起浪费一点 space ) 用字典：

words_dict = {frozenset(word): word for word in words_list}

words_dict[frozenset(word)] # KeyError if no match

如果可以有多个匹配项，只需将 dict 更改为 multidict:

words_dict = collections.defaultdict(set)
for word in words_list:
    words_dict[frozenset(word)].add(word)

words_dict[frozenset(word)] # empty set if no match

或者，如果您明确希望它是一个列表而不是一个集合：

words_dict = collections.defaultdict(list)
for word in words_list:
    words_dict[frozenset(word)].append(word)

words_dict[frozenset(word)] # empty list if no match

如果你想不使用散列tables（为什么？），你可以使用搜索树或其他对数数据结构：

import blist # pip install blist to get it

words_dict = blist.sorteddict()
for word in words_list:
    words_dict.setdefault(word, set()).add(word)

words_dict[frozenset(word)] # KeyError if no match

这看起来几乎相同，除了将 defaultdict 包裹在 blist.sorteddict 周围并不是很简单的事实——但这只需要几行代码。（也许你真的想要一个 KeyError 而不是一个空集，所以我认为值得在某处显示带有 setdefault 的 defaultdict 和普通字典，这样你就可以选择了。）

但在幕后，它使用的是混合 B 树变体而不是散列 table。尽管这是 O(log N) 时间而不是 O(1)，但在某些情况下它实际上比 dict 更快。

提取匹配字符串的最快方法

Fastest way to extract matching strings

python

algorithm

complexity-theory

search