2つの文字列の類似度を比較するアルゴリズムにはどのようなものがあるか？

質問

文字列を比較して、それらが同じものを表しているかどうかを判断する必要があります。 これは、人間が入力した案件のタイトルに関するもので、略称やその他の細かい点が異なる場合があります。 たとえば、次の2つのタイトルを考えてみましょう。

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";

とは対照的です。

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";

人間は、これらが同じものである可能性が高いとすぐに判断することができます。 私が取った現在のアプローチは、すべての文字を小文字にし、すべての句読点とスペースを削除して、文字列を正規化することです。

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";

そして

std::string secondNormalized = "harpervthelawofficesofhueylueyllp";

この場合、一方は他方の部分配列ですが、必ずしもそうではなく、重要な部分配列が共通している、より複雑なバリエーションを想像することができます。 また、文字の入れ替わりやスペルミスなど、人為的な入力ミスが時々発生する可能性もあります。

おそらく、ある種の文字の差分プログラムが役に立つのではないでしょうか。 チェックインするコードの違いを比較するための優れた行間差分プログラムを見たことがありますが、文字ベースで、おそらく boost でそのようなものがあるでしょうか。 共通する連続した文字の数をカウントし、共有されていない文字との比率を取ることができれば、おそらくそれは良いヒューリスティックになるでしょうか。

結局、同じとみなすかどうかのブール判定が必要なんです。 それは完璧である必要はありませんが、理想的にはほとんど間違っていないはずです。

2 つの文字列が互いにどの程度類似しているかについて、何らかの定量化を与えてくれる、どのようなアルゴリズムを使用することができますか。

どのように解決するのですか?

あなたが探しているものは 文字列メトリック というアルゴリズムがあります。そこには 重要な があり、その多くは似たような特徴を持っています。より人気のあるものの中で

• レーベンシュタイン距離 : ある単語を別の単語に変えるために必要な一文字の編集の最小回数。文字列は同じ長さである必要はありません。
• ハミング距離 : 同じ長さの2つの文字列で異なる文字の数。
• スミス-ウォーターマン : 可変長部分配列の類似性を計算するためのアルゴリズム群。
• Sørensen-Dice 係数 : 隣接する文字ペアの差分係数を計算する類似性アルゴリズム。

これらと同様に ウィキのページ をご覧ください。