查找字符串中最常見的子字符串的算法

Question

是否有任何算法可用於查找字符串中最常用的短語（或子字符串）？例如，下面的字符串將有「世界你好」作爲其最常見的兩個字母的詞組：

"hello world this is hello world. hello world repeats three times in this string!"

在上面的字符串，最常見的字符串（空字符串的字符後，其重複無限次數）將是空格字符。

有沒有什麼辦法可以從最常見到最不常見的字符串中生成常見子字符串列表？

Answer 1

這是類似於Nussinov算法的任務，實際上甚至更簡單，因爲我們不允許任何間隙，插入或對齊中的不匹配。

對於串A具有長度N，定義一個F[-1 .. N, -1 .. N]表，並在使用以下規則填寫：

for i = 0 to N 
    for j = 0 to N 
     if i != j 
     { 
      if A[i] == A[j] 
      F[i,j] = F [i-1,j-1] + 1; 
      else 
      F[i,j] = 0; 
     } 

例如，對於BAöBA B：

這運行在O(n^2)時間。表中最大的值現在指向最長的自匹配子序列的結束位置（i - 一個發生的結束，j - 另一個）。在開始時，陣列被假定爲零初始化。我添加了條件來排除最長但可能不是有趣的自我匹配的對角線。

思考更多，此表是在對角線上對稱的，因此僅計算它的一半就足夠了。此外，數組初始化爲零，因此分配零是多餘的。這仍然

for i = 0 to N 
    for j = i + 1 to N 
     if A[i] == A[j] 
     F[i,j] = F [i-1,j-1] + 1; 

更短，但可能更難以理解。計算表包含所有短和長的匹配。您可以根據需要添加進一步的過濾。

在接下來的步驟中，您需要恢復字符串，然後從非零單元格向上並向左對角線。在這個步驟中，使用一些hashmap來計算同一個字符串的自相似匹配的數量也是微不足道的。使用正常的字符串和正常的最小長度，只有少量的表格單元格將通過此地圖進行處理。

我認爲直接使用hashmap實際上需要O（n^3），因爲訪問結束時的關鍵字符串必須以某種方式進行比較以實現相等性。這個比較可能是O（n）。

Answer 2

Python。這有點快而骯髒，數據結構完成大部分的提升。

from collections import Counter 
accumulator = Counter() 
text = 'hello world this is hello world.' 
for length in range(1,len(text)+1): 
    for start in range(len(text) - length): 
     accumulator[text[start:start+length]] += 1 

計數器結構是一個散列支持的字典，用於計算你已經看到了什麼東西。添加到不存在的鍵將創建它，而檢索不存在的鍵會給你零而不是錯誤。所以你所要做的就是迭代所有的子字符串。

Answer 3

Perl中，O(n²)溶液

my $str = "hello world this is hello world. hello world repeats three times in this string!"; 

my @words = split(/[^a-z]+/i, $str); 
my ($display,$ix,$i,%ocur) = 10; 

# calculate 

for ($ix=0 ; $ix<=$#words ; $ix++) { 
    for ($i=$ix ; $i<=$#words ; $i++) { 
    $ocur{ join(':', @words[$ix .. $i]) }++; 
    } 
} 

# display 

foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) { 
    print "$_: $ocur{$_}\n"; 
    last if !--$display; 
} 

顯示器最常用的子串的10個最佳得分（在相同的情況下，首先顯示的字的最長鏈）。將$display更改爲1僅具有結果。
有n(n+1)/2迭代。

Answer 4

只是僞代碼，也許這不是最漂亮的解決方案，但我想解決這樣的：

function separateWords(String incomingString) returns StringArray{ 
    //Code 
} 

function findMax(Map map) returns String{ 
    //Code 
} 

function mainAlgorithm(String incomingString) returns String{ 
    StringArray sArr = separateWords(incomingString); 
    Map<String, Integer> map; //init with no content 
    for(word: sArr){ 
     Integer count = map.get(word); 
     if(count == null){ 
      map.put(word,1); 
     } else { 
      //remove if neccessary 
      map.put(word,count++); 
     } 
    } 
    return findMax(map); 
} 

凡地圖可以包含一個鍵，值對像Java中的HashMap。

Answer 5

由於對長度的字符串的每個子> = 2的文本包含長度爲2的至少一個子至少很多時候，我們只需要調查的長度的字符串2.

val s = "hello world this is hello world. hello world repeats three times in this string!" 

val li = s.sliding (2, 1).toList 
// li: List[String] = List(he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " t", th, hi, is, "s ", " i", is, "s ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, d., ". ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " r", re, ep, pe, ea, at, ts, "s ", " t", th, hr, re, ee, "e ", " t", ti, im, me, es, "s ", " i", in, "n ", " t", th, hi, is, "s ", " s", st, tr, ri, in, ng, g!) 

val uniques = li.toSet 
uniques.toList.map (u => li.count (_ == u)) 
// res18: List[Int] = List(1, 2, 1, 1, 3, 1, 5, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 1, 3, 3, 2, 4, 1, 2, 2, 1) 

uniques.toList(6) 
res19: String = "s "