Levenshteinフレーズの距離/文字列マッチングアルゴリズム

Question

私は自分の作品のネットワーク上で動作する多数のアプリケーションに関する情報をそれぞれ与える2つのスプレッドシートを持っています。彼らは決して対応していなかった2人の別々の人々によって作られました。

結果として、アプリケーションに与えた名前はシート間で一定ではありません。しかし、彼らは似ています。たとえば、アプリケーション「Office 2010」、その他の「MS Office 10」などを呼び出すことができます。

私はLevenshteinアルゴリズムを調べましたが、これは単語の順序が一定で、スペルのみが異なる単一の単語またはフレーズにのみ適用されるようです。 （私はコンピュータ科学者ではなく、これで私を修正してください）。

したがって、私はあるシートの各名前について、他のシートのすべての名前を繰り返して、最も近いものを見つけるアルゴリズムを探しています。完璧である必要はありませんが、何かが助けになります。

アイデア？助けることができるすべての人に感謝します。

Answer 1

Levenshtein Distanceは編集距離の一般化された形式で、編集、つまり挿入、削除、および置換の回数をカウントします.1つの文字列を別の文字列に変換するのに要します。あなたは転位をとてもうまく扱えないのは間違いありませんが、あなたの必要に応じて、それでも仕事をするかもしれません。

ファジーストリングマッチングはヒューリスティックな領域なので、あなたの特定の目的を達成しようとするのが最善の方法です。たとえば、大文字小文字を入れてテキストを前処理した後、編集距離を取る前に辞書を辞書順にソートすると、多くの場合転置に役立ちます。ある文字列が他の文字列のおおよその部分文字列であれば、2つの文字列の長さの絶対差を引いて、距離が小さくなるようにすることもできます。

一般に、特異性と感度の間には常にトレードオフがあるため、この手法は、ヒューリスティックをあなたが快適な方法で実行するようにチューニングするだけです。