Delphi從大型數組中刪除大量的部分匹配字符串

Question

我有2個字符串數組，數組＃1包含大約250萬個字符串，數組＃2大約450萬個字符串。我需要檢查數組＃2中的字符串是否在數組＃1的字符串內，然後刪除它們。

由於「字符串包含另一個字符串」的要求，我不能使用任何二進制搜索等，該過程需要在30個小時以上。

我的意思是「字符串包含另一個字符串」，例如，數組＃1包含一個字符串「houseboat」，數組＃2包含某處「house」，所以「house」位於「houseboat」，這意味着我會必須從陣列＃1中刪除「船屋」。

例（不實際，不工作要麼）代碼，以便更好地解釋：

for i:=0 to length(array1)-1 do 
begin 
    for j:=0 to length(array2)-1 do 
    begin 
    if ansicontainstext(array1[i],array2[j]) then 
    begin 
     martrecordtoremove; 
     break; 
    end; 
    end; 
end; 

這將需要約30小時的所有字符串。

所以我的問題是，有沒有辦法做得更快？

Answer 1

爲了避免天真的字符串搜索，您必須利用字符串搜索算法，旨在快速搜索文本(wiki)中的整組模式。

最簡單的實現是Rabin-Karp算法。
最壞的情況下最好的複雜性是Aho-Corasick之一。

兩種算法的平均情況都很接近，因此首先檢查R-K速度是否適合您的目的是值得的。

---

另一個可能的問題 - 如何實現martrecordtoremove？爲了有效地移除，你應該消除多次內存重新分配。

Answer 2

你可以做二分搜索，但是索引會很大（大約5000萬條目，而不是災難）。最容易嘗試創建一個sphinxsearch指數，在你裏面有一個參數去設置裏面的字字（在內部它意味着對於遊艇獅身人面像搜索將這些關鍵字添加到它的指數）：從搜索

houseboat 
     at 
     oat 
    boat 
etc.. 

回報將立即建立索引應該是相當快的

Answer 3

在我看來，問題的一部分是，你循環2.5M * 4.5M次。你有沒有嘗試過使用TStringList而不是數組？如果你的陣列是不是TStringList中（比如SA1，SA2），您可以編寫代碼，例如這樣的：

var 
    i, j: integer; 
begin 
    SA1.CaseSensitive:=false; 
    SA2.CaseSensitive:=false; 
    SA1.Sort; 
    SA2.Sort; 
    for i := 0 to SA2.Count-1 do 
    begin 
    while true do 
    begin 
     //if we delete all the SA1 items, no more processing is required 
     if SA1.Count=0 then 
     exit; 
     //find the occurrence of SA2[i] in SA1 
     SA1.Find(SA2[i], j); 
     //Check if the line at item j in SA1 contains the text of SA2[i] 
     if Pos (SA2[i], SA1[j]) > 0 then //yes, then we delete it 
     SA1.Delete(j) 
     else 
     if (j-1>=0) and (Pos (SA2[i], SA1[j-1]) > 0) then //else check the previous line to see if that has the text 
      SA1.Delete(j-1) 
     else 
      if (j+1<SA1.Count) and (Pos (SA2[i], SA1[j+1]) > 0) then //else check the next line 
      SA1.Delete(j+1) 
      else //otherwise break out of while loop 
      break; 
    end; 
    end; 
end; 

我們正在使用的情況下找到trings的不敏感（和排序）名單。它只運行一次4.5M項目列表 - 並在2.5M陣列中刪除項目（即SA1在循環中縮小）。在循環結束時，SA1將只包含您想要的字符串（SA2中不存在）。也許你應該嘗試一下，看看它是否適合你（並希望提高性能）？

希望這會有所幫助。

更新20170221：我更新了代碼，在刪除之前使用Find查找SA1中的SA2字符串索引。而且我還更新了代碼，以便SA1中的SA2字符串可能出現多次。我還更新了代碼以使Stringlist操作不區分大小寫。