如何找到具有最多常用詞的兩個句子？

Question

給定一個句子列表，找到兩個句子，它們的常用詞數量最多。 常用單詞不需要在句子中位於同一位置（順序無關緊要）。

謝謝！

更新：

是否存在針對此問題的非成對算法？因爲pairwise非常簡單。

我的想法是使用倒排索引來存儲這個詞出現在哪裏。這需要遍歷每個句子中的每個單詞。然後創建一個n * n二維數組，用於計算兩個句子在倒排索引中出現在同一個桶中的次數。

Answer 1

首先，您需要一種方法，將採取兩個句子，並確定他們共同有多少單詞。這可以通過將兩個句子作爲輸入來工作，並從中創建兩個包含按字母順序排列的單詞的數組。然後，您可以檢查兩個數組，向前推進，無論哪個數組按字母順序提前（因此，如果當前匹配是「算盤」和「書籍」，則可以將「算盤」移動到下一個單詞）。如果你有一個匹配（「書」和「書」），然後你增加一個匹配的單詞的計數，並將兩個數組移動到下一個單詞。你繼續這樣做直到你到達其中一個數組的末尾（因爲另一個數組中的剩餘單詞不會有任何匹配）。

一旦有了這種算法來實現，需要一個循環，將如下所示：

for (i = 0; i < sentenceCount - 1; i++) { 
    for (j = i+1; j < sentenceCount; j++) { 
    } 
} 

循環，你會調用你的函數計算的話在共同使用的句子在指標數內i和j。你會記錄到目前爲止共同看到的最多的單詞，以及發現它的兩個句子。如果一個新句子的共同詞數較多，則會存儲該計數和產生該計數的兩個句子。最後，你會得到你想要的兩個句子。

Answer 2

假設你有句子的數組：

String[] sentences 

創建包含默認值的一些變量來跟蹤這兩個句子的最常見的詞

sentence1Index = -1 
sentence2Index = -1 
maxCount = -1 

請在嵌套循環句子陣列

for i : 0 -> sentences.length 
    for j : 0 -> sentences.length 

請確保您沒有檢查相同的先知NCE

if i != j 

斯普利特字符串由空的空間（這通常會給你每個字假設你指望一些符號字）

String[] words1 = sentences[i].splitAt(" ") 
    String[] words2 = sentences[j].splitAt(" ") 

就該運行而言，

tempCount = 0 

創建一個臨時的計數值

兩個字組之間的循環（從您正在比較的兩個句子中獲得）

for a : 0 -> words1 .length 
     for b : 0 -> words2.length 

如果字是相同的，然後增加溫度數

  if words[a] equal-to-ignore-case words[b] 
       tempCount++ 

整理比較的話後，如果tempCount比目前MAXCOUNT更大，更新跟蹤你的所有值都在尋找

if tempCount > maxCount 
     sentence1Index = i 
     sentence2Index = j 
     maxCount = tempCount 

返回新創建的數組，其中兩個句子

if sentence1Index != -1 and sentence2Index != -1 
    String[] retArray = sentences[sentence1Index], sentences[sentence2Index ] 
    return retArray 

return null 

所有的僞代碼：

String[] sentences 
sentence1Index = -1 
sentence2Index = -1 
maxCount = -1 

for i : 0 -> sentences.length 
    for j : 0 -> sentences.length 
     if i != j 
      String[] words1 = sentences[i].splitAt(" ") 
      String[] words2 = sentences[j].splitAt(" ") 
      tempCount = 0 
      for a : 0 -> words1 .length 
       for b : 0 -> words2.length 
        if words[a] equal-to-ignore-case words[b] 
         tempCount++ 
      if tempCount > maxCount 
       sentence1Index = i 
       sentence2Index = j 
       maxCount = tempCount 

if sentence1Index != -1 and sentence2Index != -1 
    String[] retArray = sentences[sentence1Index], sentences[sentence2Index ] 
    return retArray 

return null