私は、この質問が何度も聞かれたことを知っています。どのアルゴリズムが近似文字列マッチングに適しているかについての提案が必要です。
アプリケーションは、特に会社名の照合のみを目的としており、他には何もありません。
最大の課題は、おそらく会社の末尾の部分と短い名前の部分です。例: 1. companyA pty ltd と companyA pty. 株式会社 vs companyA 2. WES Engineering vs WES Engineering (ごく稀に)
レーベンシュタイン編集距離は適切だと思いますか?
私はC＃を使用しています
よろしく、マックス
使用できるさまざまな文字列距離メトリックがあります。
私はJaro-Winklerをお勧めします。比較の結果が個別の編集単位である edit-distance とは異なり、JW は 0-1 のスコアを提供します。特に固有名詞に適しています。この素敵なチュートリアルと このSOの質問も見てください。
私は C# を使用したことはありませんが、オンラインで見つけた JW の実装を次に示します。
Impl 1 (ファイルリストを見ると、DOT NET バージョンもあります)
もう少し洗練されたマッチングを行いたい場合はltd/limited, inc/incorporated, corp/corporation、大文字と小文字を区別しない、略語などを考慮するなど、会社名で一般的に使用される単語形式のカスタム正規化を試みることができます。
distance (normalize("foo corp."), normalize("FOO CORPORATION") )
結果は 14 ではなく 0 になるはずです (これは、レーベンシュタイン編集距離を計算した場合に得られるものです)。
はい、レーベンシュタイン距離がこれに適しています。少なくともリストしたすべての人に対して機能します。
Soundexを使用することもできますが、必要ないと思います。
これらの単純な例では、英数字以外のすべての文字を削除するだけで一致が得られます。これは、両側のデータを事前に計算できるため、最も簡単です。交差乗算と編集距離の計算。
別の質問ですでに回答を提供しています。
https://stackoverflow.com/a/30120166/2282794
私は、あなたが話したのと同様の名前一致要件を持つ非常に大規模なシステムに取り組んできました。名前の一致はそれほど単純ではなく、姓と名の順序が異なる場合があります。このようなシナリオでは、単純なあいまいな名前一致アルゴリズムは惨めに失敗します。
近似文字列マッチング アルゴリズムについて話したいだけなら、たくさんあります。それらのいくつかは、Jaro-Winkler、Edit distance(Levenshtein)、Jaccard 類似性、Soundex/Phonetics ベースのアルゴリズムなどです。単純なグーグル検索ですべての詳細が得られます。それらすべてをC#で実装できます
皮肉なことに、指定された 2 つの入力文字列を照合しようとしているときに機能します。理論的には申し分なく、あいまいまたは近似文字列マッチングが機能する方法を示します。
ただし、非常に控えめな点は、生産設定で同じものをどのように使用するかです。おおよその文字列マッチング アルゴリズムを探していた私が知っている全員が、運用環境で同じ問題を解決する方法を知っていたわけではありません。
Java 固有の Lucene について話したばかりかもしれませんが、.Net 用の Lucene もあります。