文字列メトリック

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

数学およびコンピュータサイエンスは、文字列メトリック(文字列類似性メトリックまたは文字列距離関数とも呼ばれます)は、 2つのテキスト文字列間の距離(「逆類似性」)を測定して近似文字列の照合または比較を行い、ファジー文字列検索を行うメトリックです。文字列メトリックの要件(たとえば、文字列照合とは対照的に)は、三角不等式の実現です。たとえば、文字列「Sam」と「Samuel」は近いと見なすことができます。[1]文字列メトリックは、アルゴリズム固有の距離の表示を示す数値を提供します。

最も広く知られている文字列メトリックは、レーベンシュタイン距離(編集距離とも呼ばれます)と呼ばれる基本的なメトリックです。[2] 2つの入力文字列間で動作し、1つの入力文字列を別の入力文字列に変換するために必要な置換と削除の数に相当する数を返します。レーベンシュタイン距離などの単純な文字列メトリックは、音声、トークン、文法、および文字ベースの統計的比較方法 を含むように拡張されました。

文字列メトリックは情報統合で頻繁に使用され、現在、不正検出指紋分析盗聴検出オントロジーマージDNA分析、RNA分析、画像分析、証拠ベースの機械学習データベース データ重複排除データマイニングインクリメンタルなどの分野で使用されています検索データ統合、マルウェア検出、[3]およびセマンティック知識統合

文字列メトリックのリスト

選択した文字列測定例

名前
ハミング距離 karolin」と「kathrin 3です
レーベンシュタイン距離ダメラウ・レーベンシュタイン距離 k ittensitting距離3です _
  1. kイッテンシッテン(「k」の代わりに「s」を使用
  2. sittensittin (「 e 」の代わりに「i」を使用
  3. sittinsitting(末尾に「g」を挿入)
ジャロ・ウィンクラー距離 JaroWinklerDist( "MARTHA"、 "MARHTA")=
  • 一致する文字の数です;
  • 転置の数の半分です"MARTHA"[3]!=H, "MARHTA"[3]!=T)。
最も頻繁なk文字 MostFreqKeySimilarity(' r e s e a r ch'、's ee king'、2)= 2


参照

  1. ^ Lu、Jiaheng; etal。(2013)。「文字列の類似性を測定し、同義語と結合します」データ管理に関する2013ACMSIGMOD国際会議の議事録:373–384。土井10.1145/2463676.2465313ISBN 9781450320375
  2. ^ Navarro、ゴンザロ(2001)。「文字列マッチングを概算するためのガイド付きツアー」。ACMコンピューティング調査33(1):31–88。土井10.1145/375360.375365hdl10533/172862
  3. ^ Shlomi Dolev ; モハマド、ガーナイム; アレクサンダー、ビヌン; セルゲイ、フレンケル; Yeali、S. Sun(2017)。「マルウェアクラスタリングとオンライン識別におけるJaccardと編集距離の関係」。ネットワークコンピューティングとアプリケーションに関する第16回IEEE国際シンポジウム:369–373。
  4. ^ コーエン、ウィリアム; ラヴィクマール、プラディープ; フィエンバーグ、スティーブン(2003-08-01)。「名前照合タスクの文字列距離メトリックの比較」:73–78。 {{cite journal}}引用ジャーナルには|journal=ヘルプ)が必要です


外部リンク