4

我很好奇在一段文本中计算字符串出现次数的最有效算法（或常用算法）是什么。

根据我的阅读，Boyer–Moore 字符串搜索算法是字符串搜索的标准，但我不确定以有效方式计算出现次数是否与搜索字符串相同。

在 Python 中，这就是我想要的：

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

编辑：似乎 pythonstr.count就是这样一种方法；但是，我无法找到它使用的算法。

4

3 回答 3

3

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

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

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

最后，如果您正在寻找可以轻松编码且麻烦最少的东西，您可能需要考虑研究Rabin-Karp算法，该算法使用滚动散列函数来查找字符串。这可以用大约 10 到 15 行代码进行编码，没有预处理时间，并且对于普通文本字符串（大量文本很少匹配）可以非常快速地找到所有匹配项。

希望这可以帮助！

于 2011-08-26T17:38:15.933 回答
1

Boyer-Moore 将是计数出现次数的好选择，因为它有一些您只需要做一次的开销。模式字符串越长效果越好，因此对于“one”来说，这不是一个好的选择。

如果要计算重叠，请在上一个匹配后一个字符开始下一个搜索。如果要忽略重叠，请在上一次匹配之后开始下一次搜索完整模式字符串长度。

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

于 2010-05-04T19:04:21.603 回答
-1

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。请记住，此算法计算字符在字符串中出现的次数，这对字谜很有用。

于 2011-08-26T17:23:22.497 回答