43

文字列類似関数を使用して、データベース内の破損したデータを見つけたいと考えています。

私はそれらのいくつかに出くわしました：

  • ジャロ、
  • ジャロ・ウィンクラー
  • レーベンシュタイン、
  • ユークリッドと
  • Qグラム、

それらの違いと、どのような状況で最も効果的かを知りたかったのです。

4

2 に答える 2

42

正誤表での私のwikiウォークのコメントを拡張し、同様の問題空間に適用されるアルゴリズムの比較可能性に関する1階の文献のいくつかに注目して、数値的に比較可能かどうかを判断する前に、これらのアルゴリズムの適用可能性を調べてみましょう。

ウィキペディアから、ジャロ・ウィンクラー：

コンピュータサイエンスと統計では、ジャロウィンクラー距離（Winkler、1990）は、2つの文字列間の類似性の尺度です。これは、Jaro距離メトリック（Jaro、1989、1995）の変形であり、主に[要出典]レコードリンケージ（重複検出）の領域で使用されます。2つの弦のジャロ・ウィンクラー距離が長いほど、弦は類似しています。ジャロ・ウィンクラー距離計量は、人の名前などの短い文字列に最適に設計されています。スコアは、0が類似性なしに等しく、1が完全一致になるように正規化されます。

レーベンシュタイン距離：

情報理論とコンピュータサイエンスでは、レーベンシュタイン距離は2つのシーケンス間の差の量を測定するための文字列メトリックです。編集距離という用語は、レーベンシュタイン距離を具体的に指すためによく使用されます。

2つの文字列間のレーベンシュタイン距離は、1つの文字列を別の文字列に変換するために必要な編集の最小数として定義され、許容される編集操作は1つの文字の挿入、削除、または置換です。1965年にこの距離を考慮したウラジミールレベンシュテインにちなんで名付けられました。

ユークリッド距離：

数学では、ユークリッド距離またはユークリッド距離は、定規で測定する2点間の「通常の」距離であり、ピタゴラスの公式で与えられます。この式を距離として使用することにより、ユークリッド空間（または内積空間）が距離空間になります。関連するノルムはユークリッドノルムと呼ばれます。古い文献では、このメトリックをピタゴラスメトリックと呼んでいます。

そしてQ-またはn-gramエンコーディング：

計算言語学と確率の分野では、n-gramは、テキストまたは音声の特定のシーケンスからのn個のアイテムの連続したシーケンスです。問題のアイテムは、アプリケーションに応じて、音素、音節、文字、単語、または塩基対にすることができます。n-gramは、テキストまたは音声コーパスから収集されます。

n-gramモデル（およびそれらを使用するアルゴリズム）の2つの主要な利点は、比較的単純であり、スケールアップできることです。naモデルを増やすだけで、よく理解されている時空間のトレードオフでより多くのコンテキストを格納でき、非常に効率的にスケールアップするための実験。

問題は、これらのアルゴリズムが、データ内またはその使用可能なメトリックを移植する際に、最長共通部分列問題を解決するために、すべての可能なアルゴリズムの空間内で異なる適用性を持つさまざまな問題を解決することです。実際、これらのすべてが三角不等式を満たさないため、すべてがメトリックであるとは限りません。

データの破損を検出するための疑わしいスキームを定義するのではなく、データにチェックサムとパリティビットを使用して、これを適切に実行します。より単純な解決策で解決できる場合は、はるかに難しい問題を解決しようとしないでください。

于 2012-03-29T21:48:21.763 に答える
4

文字列の類似性は、さまざまな点で役立ちます。例えば

  • グーグルは、文字列の類似性を使用して結果が計算されることを意味しましたか。
  • 文字列の類似性は、OCR エラーを修正するために使用されます。
  • 文字列の類似性は、キーボード入力エラーを修正するために使用されます。
  • 文字列の類似性は、バイオインフォマティクスで 2 つの DNA の最も一致する配列を見つけるために使用されます。

ただし、1 つのサイズですべてに対応できるわけではありません。すべての文字列類似アルゴリズムは特定の用途向けに設計されていますが、それらのほとんどは似ています。たとえば、Levenshtein_distanceは、2 つの文字列を等しくするために変更する文字数に関するものです。

kitten → sitten

ここでの距離は 1 文字の変更です。削除、追加、および置換に異なる重みを与えることができます。たとえば、OCR エラーとキーボード エラーは、一部の変更の重要度を下げます。OCR (一部の文字は他の文字と非常に似ています)、キーボードの一部の文字は互いに非常に近いです。生物情報学的文字列の類似性により、多くの挿入が可能になります。

「 Jaro-Winkler距離メトリックは設計されており、人名などの短い文字列に最適です」の 2 番目の例

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

文字列類似関数を使用して、データベース内の破損したデータを見つけたいと考えています。

データはどのように破損していますか? キーボード入力エラーのようなユーザー エラーですか? それともOCRエラーに似ていますか？それともまったく別のものですか？

于 2012-03-29T20:36:55.170 に答える