algorithm - 名前のスペルミスを特定するための最も効率的な編集距離？

Question

編集距離のアルゴリズムは、2つの文字列間の距離の尺度を提供します。

質問：実際に同じである2人の異なる人物の名前を検出するために、これらの測定値のどれが最も関連性がありますか？（スペルミスのために異なります）。秘訣は、誤検知を最小限に抑える必要があるということです。例：

オバマオバマ=>おそらくマージする必要があります

オバマイバマ=>マージしないでください。

これは単純すぎる例です。この問題をより詳細に解決したプログラマーやコンピューター科学者はいますか？

score 5 · Accepted Answer

そうするための情報検索手法を提案することはできますが、正しく機能するためには大量のドキュメントのコレクションが必要です。

標準のIR技術を使用して、データにインデックスを付けます。Luceneは、それを支援できる優れたオープンソースライブラリです。

名前を取得したら（たとえば、Obaama）：Obaamaという単語が含まれるコレクションのセットを取得します。このセットを。としますD1。
ここで、wD1 ¹ の各単語について、（IRシステムを使用して）を検索します。Obaama AND wセットをD2。

スコア|D2|/|D1|wは、に接続されている量の推定値であり、 ²Obaamaの場合は1に近い可能性があります。一連の例に手動でラベルを付けて、単語が期待される値を見つけることができます。w=Obama

標準の辞書式類似性手法を使用して、スペルミスではない単語を除外することを選択できます（Like Barack）。

よく使用される別の解決策には、クエリログが必要です。検索された単語間の相関関係を見つけます。クエリログでオバマと相関関係がある場合は、それらが接続されます。

1：最初に2番目のフィルターを実行し、辞書式順序で「十分に類似している」候補のみをチェックすることで、パフォーマンスを向上させることができます。

2：通常、正規化も使用されます。これは、関連しているかどうかに関係なく、より頻繁な単語が他の単語と同じドキュメントに含まれる可能性が高いためです。

score 2 · Accepted Answer

SecondStringも使用しているNerSim（デモ）を確認できます。対応する論文を見つけるか、この論文を検討してください：名前付きエンティティのマッチングのためのロバストな類似性測度。

2 に答える 2