ジャロ・ウィンクラー距離

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンス統計ではジャロウィンクラー距離2つのシーケンス間の編集距離を測定する文字列メトリックです。これは、1990年にジャロ距離計量のウィリアムE.ウィンクラーによって提案された変形です(1989年、マシューA.ジャロ)。

ジャロ・ウィンクラー距離は接頭辞スケールを使用しますこれにより、設定されたプレフィックス長に対して最初から一致する文字列により有利な評価が与えられます

2つの弦のジャロ・ウィンクラー距離が短いほど、弦は類似しています。スコアは、1が完全一致を意味し、0が類似性がないことを意味するように正規化されます。元の論文では、実際には類似性の観点からメトリックが定義されていたため、距離はその値の反転として定義されます(距離= 1-類似性)。

距離計量と呼ばれることもありますが、ジャロ・ウィンクラー距離は三角不等式に従わないため、数学的な意味での距離ではありません。

定義

ジャロの類似性

ジャロの類似性与えられた2つの文字列の

どこ:

  • 文字列の長さです;
  • 一致する文字の数です(以下を参照)。
  • 転置の数です(以下を参照)。

から2文字それぞれ、それらが同じであり、より遠くない場合にのみ一致すると見なされます文字を離して。

の各キャラクターで一致するすべての文字と比較されます一致する(ただしシーケンス順序が異なる)文字の数を2で割ると、転置の数が定義されます。たとえば、CRATEとTRACEを比較する場合、一致する文字は'R''A''E'のみです。つまり、m=3です。'C'、'T'は両方の文字列に表示されますが、1よりも離れています()。したがって、t=0です。DwAyNEとDuANEでは、一致する文字はすでにDANEと同じ順序になっているため、転置は必要ありません。

ジャロ・ウィンクラー類似性

ジャロ・ウィンクラー類似性はプレフィックススケールを使用しますこれにより、設定されたプレフィックス長に対して最初から一致する文字列により有利な評価が与えられます与えられた2つの文字列、ジャロ・ウィンクラー類似性は:

どこ:

  • 文字列のJaro類似性です
  • は、最大4文字までの文字列の先頭にある共通プレフィックスの長さです。
  • は、共通のプレフィックスを持つためにスコアが上方に調整される量の一定のスケーリング係数です。0.25を超えてはなりません(つまり、1/4、考慮されるプレフィックスの最大長は4です)。そうでない場合、類似性は1より大きくなる可能性があります。ウィンクラーの作業におけるこの定数の標準値は次のとおりです。

ジャロ・ウィンクラー距離と定義されている

距離計量と呼ばれることもありますが、ジャロ・ウィンクラー距離は三角不等式に従わないため、数学的な意味での距離ではありません。[1]ジャロ・ウィンクラー距離もアイデンティティ公理を満たしていません

他の編集距離メトリックとの関係

編集距離の一般的な測定値は他にもあります。これらは、許容される編集操作の異なるセットを使用して計算されます。例えば、

編集距離は通常、許可された編集操作の特定のセットで計算されたパラメーター化可能なメトリックとして定義され、各操作にはコスト(場合によっては無限)が割り当てられます。これは、 Smith–WatermanアルゴリズムなどのDNA配列アラインメントアルゴリズムによってさらに一般化されます。これにより、操作のコストは、適用される場所によって異なります。

も参照してください

脚注

  1. ^ 「ジャロウィンクラー«招待エピファニー」RichardMinerich.com 2017年6月12日取得

参照

外部リンク