類似のアルゴリズムを比較する

Question

データベース内の破損したデータを見つけるために文字列類似機能を使用したいと思います。

• JARO、
• JARO-ウィンクラー、
• レーベンシュタイン、
• ユークリッドと
• Q-グラム、

I：

は、私はそれらのいくつかに出くわしました何が彼らの違いで、どのような状況で彼らが一番うまくいくのかを知りたがっていましたか？

Answer 1

正誤表のwiki-walkのコメントを拡大し、noting some of the ground-floor literature on the comparability of algorithms that apply to similar problem spaces,は数値的に比較できるかどうかを判断する前にこれらのアルゴリズムの適用性を調べてみましょう。ウィキペディア、Jaro-Winklerから

：コンピュータサイエンスと統計で

、JARO-ウィンクラーの距離 （ウィンクラー、1990）は二つの文字列間の類似性の尺度です。Jaro距離メトリック（Jaro、1989,1995）および の亜種である であり、主にレコードリンケージの領域で使用されています（複製 検出）。 2つのストリングのJaro-Winkler距離が高いほど、 ほどストリングが似ています。 Jaro-Winklerの距離メトリックは であり、人名などの短い文字列に最適です。 スコアは、0が類似性なしに等しく、1が 完全一致であるように正規化される。情報理論、コンピュータサイエンスの

Levenshtein distance:

、レーベンシュタイン距離は、二つの 配列間の差の量を測定するためのメトリックの文字列です。編集距離という用語は、具体的には をLevenshtein距離と呼ぶのによく使われます。

2つの文字列の間のレーベンシュタイン距離は 許容編集操作は、単一の文字の挿入、削除、または 置換された状態で、他に1つの文字列を変換するために必要な編集の最小 数として定義されます。これは数学で

Euclidean distance:

1965年にこの距離を考慮さウラジミール レーベンシュタイン、にちなんで命名され、ユークリッド距離またはユークリッドメトリックは、2つのポイント間の 「普通」の距離はある1つのだろう 定規で測定し、ピタゴラス式によって与えられる。この式を距離として使用することによって、ユークリッド空間（または任意の内積空間）がメトリック空間である になります。関連するノルムはユークリッド標準と呼ばれます。 古い文献は、ピタゴラスのメトリックとしてのメトリックを指します。

、計算言語学及び確率の分野で

Q- or n-gram encoding:は、nグラム は、テキストまたは 音声の所与の配列からN個のアイテムの連続配列です。問題の項目は、アプリケーションに応じて、音素、音節、文字、 単語または塩基対であり得る。 nグラムは、テキストまたは音声コーパスから収集された です。

（ それらを使用し、アルゴリズム）nグラムモデルの2つのコア 利点は、比較的簡単であり、スケールアップする能力 - モデルNAを増加単に によっては よくてよりコンテキストを格納するために使用することができます狭い実験を可能にして に非常に効率的にスケールアップすることができます。

トラブルは、これらのアルゴリズムは、データまたはその利用可能metricを移植して、longest common subsequence問題を解決するために、すべての可能なアルゴリズムのスペース内で異なる適用可能性を持っているさまざまな問題を解決するためです。実際には、これらのすべてがメトリックであっても、その一部がtriangle inequalityを満たしていないためです。

データの破損を検出するために迷惑なスキームを定義するのではなく、を適切に実行します。checksumsとparity bitsをデータに使用します。より簡単な解決策があれば、はるかに難しい問題を解決しようとしないでください。

Answer 2

文字列の類似性は、さまざまな方法で役立ちます。たとえば、

• googleの結果は、文字列の類似性を使用して計算されたことを意味しましたか？
• 文字列の類似性を使用してOCRエラーを修正します。
• キーボードの入力エラーを修正するために、文字列の類似性が使用されます。
• 生物情報学における2つのDNAの最も一致する配列を見出すために、類似性が用いられる。

しかし、1つのサイズがすべてに適合しないため。すべての文字列類似アルゴリズムは、特定の用途に合わせて設計されていますが、大半は類似しています。たとえば、Levenshtein_distanceは、2つの文字列を同じにするために変更する文字の数です。

kitten → sitten 

ここで、距離は1文字の変更です。削除、追加、置換に異なる重みを付けることができます。例えば、OCRエラーやキーボードエラーは、いくつかの変更に対してより軽い重みを与えます。 OCR（いくつかの文字は他の文字と非常によく似ています）、キーボードの文字はお互いに非常に近いです。 Bioinformaticの文字列の類似性は、多くの挿入を可能にします。

のあなたの第二の例「Jaro–Winkler距離メトリックは、このような人物名などの短い文字列のために設計されており、最も適している」

したがって、あなたはあなたの問題についてのあなたの心に留めておく必要があります。

文字列類似機能を使用して、データベース内の壊れたデータを検索したいと考えています。

データが壊れていますか？キーボード入力エラーに似たユーザーエラーですか？それとも、OCRエラーに似ていますか？それとも全く別のもの？