たとえば、文字列の長いリストがあり、各文字列は約 30 ～ 50 文字であり、そのリスト内の他の文字列に似ている文字列を削除したい (重複のファミリから 1 つだけを残す)。
さまざまな文字列類似度アルゴリズムを調べました。たとえば、レーベンスタイン距離や、この記事で紹介した方法です。それらは機能しますが、非常に遅いです-私が思いついた最良のアルゴリズムは、O(n^2) の複雑さを示し、3000 文字列のリストを処理するのに約 1.5 秒かかります。
これらのリストを重複排除する簡単な方法はありますか?
類似性の尺度が強い場合 (例: レーベンシュタイン距離 1)、文字列リストを順番に処理して、現在の文字列に「近い」文字列をすべて生成し、ハッシュテーブルでその近い文字列を検索できます。そこにある場合は、元の文字列をスキップします。そうでない場合は、出力してハッシュテーブルに追加します。
このアルゴリズムは、文字列に近いすべての文字列を生成できるかどうか、およびそれらが多すぎないかどうかに依存します。（これが、上記の「強い」という意味です。）
考えられる最適化として、元の文字列以外のものをハッシュテーブルに格納できます。たとえば、レーベンシュタイン距離 3 が必要な場合は、出力された文字列から距離 1 のすべての文字列をハッシュテーブルに格納し、新しい文字列をチェックするときに距離 2 の文字列を検索できます。