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

标签 python algorithm search complexity-theory

我想在列表中搜索与给定词相匹配的词(如下例)。但是,假设有一个包含数百万个单词的列表。执行此搜索的最有效方法是什么?我正在考虑标记每个列表并将单词放入哈希表中。然后执行单词搜索/匹配并检索包含该单词的单词列表。据我所见,此操作将进行 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库或者第三方包可以进行高效的搜索?

最佳答案

这里的“匹配”的意思并不完全清楚,但如果您可以将其简化为身份比较,问题就简化为集合查找,即 O(1) 时间。

例如,如果“匹配”意味着“具有完全相同的字符集”:

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

然后,查找单词:

frozenset(word) in words_set

或者,如果它意味着“具有完全相同的多组字符”(即计算重复项但忽略顺序):

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),这听起来像是您关心的。


如果你需要找回匹配的词而不是只知道有一个,你仍然可以用一个集合来做这件事,但它更容易(如果你能负担得起浪费一点空间)用字典:

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

如果你想不使用哈希表来做到这一点(为什么?),你可以使用搜索树或其他对数数据结构:

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 树变体而不是哈希表。虽然这是 O(log N) 时间而不是 O(1),但在某些情况下它实际上比 dict 更快。

关于python - 提取匹配字符串的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50080414/

相关文章:

python - 夹层中的页面区域

python - 将记忆化应用于硬币兑换问题

java - 基于坐标的搜索

python - 使用 Python 抓取 Javascript 创建的动态内容

python - 通过网页共享脚本输出(不同服务器)

Python:如何检查unicode字符串是否包含大小写字符?

c - 在树型数据结构中,逐级显示树节点

c++ - 这个从后缀数组获取 LCP 的代码是如何工作的?

ios - 使用未指定的索引。考虑添加 ".indexOn": "phone" at/use_frameworks_beta_2/searchIndex to your security rules for better performance

使用 Applescript 搜索 Mail.app 的邮箱