減少從二次到更快的重複字符串搜索

Question

如果標題的描述不夠準確，道歉。

我有一個程序，搜索元音字符串，但它通過滑動整個字符串的特定大小的窗口。我想計算元音的密度。假裝我不在乎有空白和符號;它只是留在那裏。我已經編碼爲明顯的解決方法如下：

s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit ... consequat." 
# assume s continues after the "..." 
v = "aeiou" 
v_dict = {} 
max_win_size = 100 
if max_win_size > len(s): max_win_size = len(s) 

for i in range(1, max_win_size): 
    v_dict[i] = {} 
    for j in range(0, i+1): 
     v_dict[i][j] = 0 # set counts to zero 
    for j in range(1, len(s)-i+1): 
     s_slice = s[j:j+i].lower() 
     v_count = sum([s_slice.count(c) for c in v]) 
     v_dict[i][v_count] += 1 

這使最終讓我元音的頻率在1到字符串的大小不同的滑動窗口。這個程序按我想要的方式工作，但問題在於它非常緩慢。它顯然是二次的，我想提高效率，因爲隨着文本越來越大，程序需要花費更多的時間。問題是我不確定如何將問題空間轉換爲更高效的算法。

有沒有人有任何想法，如何做到這一點，比如說，線性？

編輯：

我試圖通過本福格特由cr1msonB1ade實現了答案。它像廣告一樣工作。另外，我認爲我會將經驗證據包含在速度聲明中。

首先是增加字符串大小的運行時間。兩個函數都是線性執行的，但是使用純python實現它的開銷會導致線性運行時間的係數更大。

其次是增加窗口大小的運行時間。我修正了窗口大小，並且運行了更大和更大的窗口大小。這一次，我的函數的二次函數顯示了它本身，而numpy累加和函數保持線性。

Answer 1

在理論運行時間方面你計算max_win_size * (len(s)-max_win_size+1)值，所以沒有辦法讓下面o(max_win_size*len(s))運行時間。

就實際計算運行時間而言，您當前的代碼存在一些問題。首先沒有理由對每個字符串進行字母匹配。您應該先將您的字符串轉換爲TRUEFALSE列表，然後查詢。

其次，您可以在移動滑動窗口時動態更新總和。換句話說，你只需要查詢你正在丟棄的字母和正在添加的字母，以獲得下一個子字符串中的元音數量。

另外，您並不需要爲數據結構的第二級設置字典。您確切知道列表的長度，您將使用整數值進行索引，因此只需使用列表。

我敢肯定，有可能是可以添加一些其他的效率，但把這些在一起，我們有：

s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit ... consequat." 
# assume s continues after the "..." 
v = list("aeiou") 
isVowel = [l in v for l in s] 
v_dict = {} 
max_win_size = 100 
if max_win_size > len(s): max_win_size = len(s) 

for i in range(1, max_win_size): 
    v_dict[i] = [0,] * (i+1) 
    curr_vowels = sum(isVowel[:i]) 
    v_dict[i][curr_vowels] += 1 
    for curr_pos in range(1, len(s)-i): 
     # add next letter position and subtract letter falling out of window 
     curr_vowels += isVowel[curr_pos + i] - isVowel[curr_pos - 1] 
     v_dict[i][curr_vowels] += 1 

編輯：使用累積方法，@Ben建議：

import numpy as np 
s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit ... consequat." 
# assume s continues after the "..." 
v = list("aeiou") 
cumVowels = [0,] + np.cumsum([l in v for l in s]) 
v_dict = {} 
max_win_size = 100 
if max_win_size > len(s): max_win_size = len(s) 

for i in range(1, max_win_size): 
    v_dict[i] = [0,] * (i+1) 
    for pos in range(0, len(s)-i): 
     v_dict[i][cumVowels[pos + i] - cumVowels[pos]] += 1 

Answer 2

根據累計計數重寫算法。

位置i和j（含）之間發生的次數僅爲cumul_count(j) - cumul_count(i-1)，所需計算量不隨窗口大小而增加。