python-3.x - O(n) 字符串中单词列表的出现次数
问题描述
我已经看到了类似问题的答案: https ://stackoverflow.com/a/44311921/5881884
ahocorasick 算法用于显示列表中的每个单词是否存在于字符串中,时间为 O(n)。但我想获取字符串列表中每个单词的频率。
例如,如果
my_string = "some text yes text text some"
my_list = ["some", "text", "yes", "not"]
我想要结果:
[2, 3, 1, 0]
我在文档中没有找到一个确切的例子,知道如何做到这一点吗?
除了使用 ahocorasick 之外的其他 O(n) 解决方案也将不胜感激。
解决方案
执行:
这是一个 Aho-Corasick 频率计数器:
import ahocorasick
def ac_frequency(needles, haystack):
frequencies = [0] * len(needles)
# Make a searcher
searcher = ahocorasick.Automaton()
for i, needle in enumerate(needles):
searcher.add_word(needle, i)
searcher.make_automaton()
# Add up all frequencies
for _, i in searcher.iter(haystack):
frequencies[i] += 1
return frequencies
(对于您的示例,您会调用ac_frequency(my_list, my_string)
以获取计数列表)
对于中大型输入,这将比其他方法快得多。
笔记:
对于真实数据,此方法可能会产生与发布的其他解决方案不同的结果,因为 Aho-Corasick 会查找目标单词的所有出现,包括子字符串。
如果您只想查找完整的单词,您可以searcher.add_word
使用原始字符串的空格/标点符号填充版本进行调用:
...
padding_start = [" ", "\n", "\t"]
padding_end = [" ", ".", ";", ",", "-", "–", "—", "?", "!", "\n"]
for i, needle in enumerate(needles):
for s, e in [(s,e) for s in padding_start for e in padding_end]:
searcher.add_word(s + needle + e, i)
searcher.make_automaton()
# Add up all frequencies
for _, i in searcher.iter(" " + haystack + " "):
...
推荐阅读
- javascript - 在for循环中调用服务时出现角度异步问题
- c++ - OpenGL 4.1 和更低的黑色纹理,Mac 和 Windows
- javascript - JavaScript 随机词(来自列表)生成器
- python - 使用熊猫样式时如何不转义字符
- c++ - 创建没有 new/delete 的模板类型
- javascript - 访问对象
- ios - 如何在 SwiftUI 中基于绑定枚举更改 View 的样式?
- python-3.x - 为什么 librosa.load() 会产生内存问题?
- python - Keras 预测精度与训练精度不匹配
- powershell - Powershell - 仅显示 CSV 中运行脚本后 15 分钟内的行