字符串發生計數算法

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行代碼進行編碼，沒有預處理時間，對於普通文本字符串（大量文本很少匹配）可以很快找到所有匹配。

希望這會有所幫助！