字符串出现次数计算算法

Question

我很想知道在一段文本中计算字符串出现次数的最有效算法（或常用算法）是什么。根据我所读到的，Boyer-Moore字符串搜索算法是字符串搜索的标准算法，但我不确定高效计算出现次数是否与搜索字符串相同。在Python中，我想要这样做：

text_chunck = "one two three four one five six one"
occurance_count(text_chunck, "one") # gives 3.

编辑：看起来Python的str.count方法可以达到这样的效果；但是，我无法找到它使用了什么算法。

- Hellnar

---

如果你要搜索的字符串是“aa”，而你的文本是“aaaa”，这算作两个还是三个出现次数？ - tloflin

不，那不是一个是或否的问题：它是二还是三？ - tloflin

哦，抱歉，我将使用精确的关键词来计算人工输入内容中的出现次数，因此它并不重要，因为它的出现次数非常低，即使发生了，也不是关键问题。 - Hellnar

如果真的不重要，那么Boyer-Moore（或任何其他已发布的算法）就是杀鸡焉用牛刀了。你可以使用简单的滚动匹配算法在O(n)（其中n是文本长度）内完成；即检查当前文本字符是否与当前字符串字符匹配，如果匹配，则将两者都推进到下一个字符，否则只推进文本并将字符串重置为第一个字符。如果你到达字符串的末尾，请将其重置并增加出现次数。这只会给出一个粗略的估计（它不会找到许多边缘情况），但你说这不重要。 - tloflin

此外，几乎肯定已经有一个适用于您选择的语言的库可以为您完成此操作。您可能应该直接使用它。过早优化等等。 - tloflin

Answer 1

首先，使用Boyer-Moore算法可以非常高效地完成此任务。但是，根据您问题的其他一些参数，可能有更好的解决方案。

Aho-Corasick字符串匹配算法 可以在目标字符串中查找一组模式字符串的所有出现，并以O(m + n + z) 的时间完成匹配，其中m是要搜索的字符串的长度，n是要匹配的所有模式的总长度，z是生成的匹配总数。如果只需要匹配一个字符串，则这是与源字符串和目标字符串的大小成线性关系。它还将找到相同字符串的重叠出现次数。此外，如果您想检查一组字符串在某个源字符串中出现的次数，您只需要调用该算法一次即可。如果您要搜索的字符串集永远不会更改，您可以在预处理时间内进行O(n)工作，然后以O(m+z)的时间找到所有匹配项。

如果您有一个源字符串和一组快速变化的子字符串要搜索，您可能需要使用后缀树。在预处理时间为O(m)的字符串中进行搜索，在每个子字符串的O(n)时间内，可以检查特定长度为n的子字符串在字符串中出现的次数。

最后，如果您正在寻找一些易于编码且无需大量麻烦的东西，您可能需要考虑研究Rabin-Karp算法，该算法使用滚动哈希函数来查找字符串。这可以编写大约十到十五行的代码，没有预处理时间，并且对于正常文本字符串（大量文本但匹配较少）可以非常快速地找到所有匹配项。

希望这可以帮助您！

- templatetypedef

Answer 2

Boyer-Moore算法是计算出现次数的好选择，因为它有一些开销只需要执行一次。它对于模式字符串越长，表现得越好，所以对于"one"来说，它不是一个好的选择。

如果您想要计算重叠部分，下一次搜索应该从上一个匹配后的一个字符开始。如果您想忽略重叠部分，下一次搜索应该从上一个匹配后的整个模式字符串长度开始。

如果您的编程语言有indexOf或strpos方法用于在另一个字符串中查找一个字符串，您可以使用它。如果它被证明太慢了，那么选择更好的算法。

- drawnonward

Answer 3

Hellnar， 您可以使用简单的字典来计算字符串中出现的次数。这个算法是一个计数算法，下面是一个例子：

"""
The counting algorithm is used to count the occurences of a character
in a string. This allows you to compare anagrams and strings themselves.
ex. animal, lamina a=2,n=1,i=1,m=1
"""

def count_occurences(str):
  occurences = {}
  for char in str:
    if char in occurences:
      occurences[char] = occurences[char] + 1
    else:
      occurences[char] = 1
  return occurences

  def is_matched(s1,s2):
    matched = True
    s1_count_table = count_occurences(s1)

    for char in s2:
      if char in s1_count_table and s1_count_table[char]>0:
      s1_count_table[char] -= 1
    else:
      matched = False
      break
    return matched

  #counting.is_matched("animal","laminar")

这个例子只返回 True 或 False，如果字符串匹配。请记住，此算法计算字符在字符串中出现的次数，这对于排列词很好。

- newfront

---

这个方法对于这个问题并不正确。首先，它只报告真/假，而不是匹配数量，这正是 OP 所要求的。如果你要在一个大文本语料库（比如《纽约时报》）中搜索某个字符串的所有出现次数，那么你几乎肯定会得到任何字符串的误报，因为你的算法只是检查字符串的字母是否在源文本中出现过。 - templatetypedef