2 つの文字列間の差の割合を見つけるために、2 つのシーケンス間の差の量を測定するための文字列メトリックであるレーベンシュタイン距離を使用しています。文字列内の単語を使用して、文字列が類似していることを宣言するためのより良い方法を使用したいと思います。
例: 2 つの段落を含む文字列があり、2 番目の文字列には最初の文字列の 2 番目の段落のみが含まれているとします。
各文字列の最初の単語と 2 番目の単語などを比較できることはわかっていますが、最後に提示した例のようなケースが発生した場合、それは効果的ではありません。
最初の文字列の最初の単語を 2 番目の文字列のすべての単語と比較するかもしれないと考えていましたが、これによりプロセスが非常に遅くなるのではないかと心配しています。
最初の文字列の各単語を 2 番目の文字列のすべての単語と比較すると、レーベンシュタイン距離よりわずかに優れたパフォーマンスが得られますが、大きさは同じです。レーベンスタイン距離は O(m*n) で、アルゴリズムは O(m^2) になります (m と n は文字列の長さです)。
一致する単語のみに関心があり (たとえば、"color" と "colour" は 2 つのまったく異なる文字列として扱われます) 、単語の順序は無視します(たとえば、"red color" と "color red" は 2 つの同じ文字列として扱われます)。アルゴリズムのスペースの複雑さは気にしません。最初の文字列の単語のインデックス (ハッシュテーブルなど) を作成し、2 番目の文字列の各単語をこのインデックスと比較できます。これにより、インデックスに一定時間の挿入と削除を伴うデータ構造を使用する場合、複雑さ O(m+n) のアルゴリズムが生成されます。