私は200,000の文字列を持っています。そのセットの中から類似の文字列を見つける必要があります。セット内の同様の文字列の数は非常に少ないと思います。効率的なデータ構造を手伝ってください。
完全に一致する文字列を探している場合は、単純なハッシュを使用できます。しかし、私の場合、「類似性」はカスタム定義されています。2 つの文字列は、それらの文字の 80% が同じであれば同様に扱われ、順序は関係ありません。
「類似性」を見つける関数を〜（200k * 100k）回呼び出したくありません。文字列を前処理する手法、効率的なデータ構造などの提案は大歓迎です。ありがとう。
2つの弦の弦の長さの差が<=3の場合にのみ、>=0.85の距離比が可能であることを学びました。つまり、長さの差が3未満の文字列をグループ化できます。
これにより、各グループの文字列の数が大幅に減少しました。したがって、全体的な比較の数は、私のデータセットでは50％弱（200k * 100k）に減少します。さらに、データセットを複数の小さなセットに分割すると、並列処理を実行するのに役立ち、全体の実行時間がさらに短縮されます。
削減率はサンプルデータセットによって異なる場合があります。つまり、すべての文字列の長さの差が3未満の場合に最悪のケースが発生します。
[この考えを刺激してくれたInbarRoseに感謝します]
私の場合、ヒストグラムは次のようになりました。
