字符串发生计数算法

Question

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

从我read时，Boyer-Moore字符串搜索算法是什么字符串搜索的标准，但我不知道是否有效率的方式计算的出现将是等同于搜索的字符串。

在Python这就是我想要的：

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

编辑：它看起来像蟒蛇str.count作为这样的方法;但是，我无法找到它使用的算法。

Answer 1

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

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

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

Answer 2

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如果字符串匹配。请记住，该算法计算字符在字符串中出现的次数，这对字符串非常有用。

Answer 3

对于初学者来说，是的，你可以非常有效地用Boyer-Moore来完成。但是，根据问题的其他参数，可能会有更好的解决方案。

The Aho-Corasick string matching algorithm会发现一个的所有出现设定在目标串图案串的和在时间为O这样做（M + N + Z），其中m是串的长度，以搜寻中，n是要匹配的所有模式的总长度，z是产生的匹配总数。如果您只有一个字符串匹配，则这与源字符串和目标字符串的大小呈线性关系。它也会发现相同字符串的重叠事件。此外，如果您想检查某个源字符串中出现一组字符串的次数，则只需要对该算法进行一次调用即可。最重要的是，如果您想要搜索的字符串集合永不改变，您可以将O（n）工作作为预处理时间，然后查找O（m + z）中的所有匹配项。

如果，另一方面，你有一个源字符串和一组子搜索的快速变化，您可能需要使用suffix tree。对于要搜索的字符串，O（m）预处理时间可以在每个子字符串的O（n）时间内检查字符串中出现长度为n的特定子字符串的次数。

最后，如果你正在寻找的东西，你可以很容易地和以最小的麻烦的代码，你可能要考虑寻找到Rabin-Karp算法，它采用了罗林哈希函数查找字符串。这可以用大约10到15行代码进行编码，没有预处理时间，对于普通文本字符串（大量文本很少匹配）可以很快找到所有匹配。

希望这会有所帮助！