python - 有效地检查字符串列表中的字符串中的单词

Question

我有一个很长的字符串，让我们说 astr = "我是一个很长的字符串，我可以包含很多文本，所以在这里考虑效率"。我还有一个list alist = ["I", "am a", "list", "of strings", "and each string", "可以由很多词组成", "所以想效率这里"]。现在，我的字符串列表也有一个对应的整数列表 alist_ofints = [1, 2, 3, 4, 5, 6, 7] 表示每个字符串有多少个点此列表中的字符串等于。

我应该创建一个函数来查找 astr 中有多少单词出现在列表 alist 中，并使用相应的点列表创建一个“点数”计数器alist_ofints。所以，在这个例子中，“我”、“是一个”、“所以在这里考虑效率”这些词分别出现了两次、一次和一次。这将为我们提供 1*2 + 2*1 + 7*1 = 11 点。

我提出了两个简单的解决方案。第一个是创建一个函数来查看此字符串列表 alist 并检查每个项目是否在 astr 中，如果是，则应用明显的以下内容逻辑。这是低效的，因为我将查看 astr len(alist) 次。那是一种浪费，不是吗？它干净利落，但效率低下。

第二个解决方案是让 astr 成为一个单词列表，我会检查索引 i 到索引 j 的每个单词，其中 i 是我在列表中的位置，j 是我要查找的 alist 中短语的长度。所以，“am a”是一个长度为 2 的短语(因为它有两个词)，所以我会看 i = 一些数字，j = 一些数字 + 1。如果我正在寻找短语 “和每个字符串”，i = 一些数字，j = 一些数字 + 3。因此，在测试这个短语时，我正在查看三个词。现在，我认为这也具有相同的时间复杂度。虽然我没有遍历 astr 列表一次，但我正在遍历我的单词列表 alist len(list(astr)) 次。此外，我必须创建一个 astr 列表，我想这会增加一些复杂性。

所以，到目前为止，我更喜欢第一个解决方案，因为它最简单、最简单、最干净。有一个更好的方法吗？如果您能找到列表理解方式，则加分...

谢谢

注意:我知道 list(astr) 不会返回单词列表。想象一下，对于这个例子，它确实如此。

TLDR:我有两个列表。我需要检查列表中的每个元素是否等于另一个列表中的元素，并计算它们出现的次数。有没有比检查列表 1 中的每个元素与列表 2 中的每个其他元素(我认为这是 O(n^2))更有效的方法？

Answer 1

更高效的算法可以使用字符串索引(例如 Suffix Array )对长字符串 astr 进行索引。然后搜索索引列表中的每个条目，并在找到结果时相应地增加点数。

索引 astr 的运行时间是 O(n)，其中 n 是 astr 的长度。

从索引中长度为 m 的列表中搜索条目的时间复杂度为 O(log n)

总的来说，你应该摆脱 O(p log n)，其中 p 是 alist 中的条目数。

示例

让我们将长字符串 astr 视为

I am a very long string

则对应的后缀数组(全部小写)为

SA = [1 4 6 11 16 5 2 8 22 15 0 20 12 3 21 14 13 19 9 17 18 7 10]

这些都是按词典顺序排序的astr(由它们的起始索引表示)的后缀。例如 SA[9] = 15 表示 astr 中从位置 15 开始的字符串(“g string”)。

现在让我们假设您的短语列表

alist = ["I am", "very long",...]

然后对于您要搜索后缀数组中出现的每个条目。这是通过对后缀数组使用二进制搜索来完成的。对于“我是”，这将如下所示:

首先，您查看后缀数组的中间条目 (SA[11] = 20)。然后您查看由该索引(“ing”)表示的后缀。由于此后缀大于您的搜索短语“我是”，因此您想查看后缀数组的左半部分。继续进行二分查找，直到找到该短语或确定它不在其中。