大規模な配列から大量の部分一致文字列を取り除く

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スピードをチェックする価値があります。

---

もう1つの問題 - martrecordtoremoveはどのように実装されていますか？効果的に削除するには、複数のメモリの再割り当てをなくす必要があります。

Answer 2

バイナリ検索はできますが、インデックスは非常に大きくなります（災害ではなく約50百万のエントリ）。 sphinxsearch索引を作成するための最も簡単な試みは、Word内の単語を設定するためのparamを持っているの内側（内部的には、屋形船のスフィンクスの検索のためにそれがインデックスだにこれらのキーワードを追加することを意味しています）：検索から

houseboat 
     at 
     oat 
    boat 
etc.. 

戻りますすぐにインデックスの作成はかなり速くなるはずです

Answer 3

私は、問題の一部はあなたが2.5M * 4.5M回ループしているということです。配列の代わりにTStringListを使ってみましたか？あなたの配列は（SA1、SA2を言う）の代わりにTStringListにした場合、あなたはこのようなコードを書くことができます：

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のアイテムリストを1回だけ実行し、2.5Mアレイからアイテムを削除します（つまり、ループ中にSA1が縮小されます）。ループの最後に、SA1には必要な文字列（SA2には存在しない文字列）のみが含まれます。おそらくあなたはこれを試してみて、それがあなたのために働くかどうかを見てみるべきです（そしてうまくいけば、パフォーマンスが向上するでしょう）？

これが役に立ちます。

UPDATE 20170221：削除する前にFindを使用して（SA1のSA2の）文字列インデックスを検索するようにコードを更新しました。またSA1でSA2文字列が複数回現れる可能性があるようにコードを更新しました。StringList操作の大文字と小文字を区別しないようにコードを更新しました。