文字列メトリック

数学とコンピュータサイエンスにおいて、文字列メトリック（文字列類似度メトリックまたは文字列距離関数とも呼ばれる）は、近似文字列マッチングや比較、およびあいまい文字列検索のために2つのテキスト文字列間の距離（「逆類似度」）を測定するメトリックです。文字列メトリックの要件（例えば、文字列マッチングとは対照的に）は、三角不等式を満たすことです。たとえば、文字列「Sam」と「Samuel」は近いと見なすことができます。^{[ 1 ]}文字列メトリックは、アルゴリズム固有の距離の指標を示す数値を提供します。

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

文字列メトリクスは情報統合において多用されており、現在では不正検出、指紋分析、盗作検出、オントロジーマージ、DNA分析、RNA分析、画像分析、証拠に基づく機械学習、データベースデータ重複排除、データマイニング、増分検索、データ統合、マルウェア検出、^{[ 3 ]}および意味知識統合などの分野で使用されています。

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

• レーベンシュタイン距離、またはその一般化編集距離
• ダメラウ・レーベンシュタイン距離
• ソレンセン・ダイス係数
• ブロック距離またはL1距離または都市ブロック距離
• ハミング距離
• 単純マッチング係数（SMC）
• ジャカード類似度、ジャカード係数、タニモト係数
• トヴェルスキー指数
• 重複係数
• 変分距離^{[ 4 ]}
• ヘリンガー距離またはバタチャリヤ距離
• 情報半径（ジェンセン・シャノン情報量）
• 歪んだ発散^{[ 4 ]}
• 混同確率^{[ 4 ]}
• タウ計量、カルバック・ライブラー距離の近似
• フェレギとスンターズメトリック（SFS）^{[ 4 ]}
• 最大一致^{[ 4 ]}
• 文法ベースの距離^{[ 5 ]}
• TFIDF距離メトリック^{[ 6 ]}

文字列間の類似度を測定する関数も存在しますが、必ずしも三角不等式を満たさず、数学的な意味での計量ではありません。そのような関数の例として、ヤロ・ウィンクラー距離が挙げられます。

選択された弦楽器の小節の例

名前	説明	例
ハミング距離	同じ長さの文字列のみ。変更された文字数。	「ka rol in」と「ka thr in」は3です。
レーベンシュタイン距離とダメラウ・レーベンシュタイン距離	異なる長さの文字列と（Damerau と）転置を考慮したハミング距離の一般化	k itt e nとsitt i n gの距離は 3 です。 k itten → s itten（「k」を「s」に置き換える） sitt e n → sitt i n (「e」を「i」に置き換え) sittin → sittin g（語尾に「g」が挿入されます）。
ヤロ・ウィンクラー距離		JaroWinklerDist("MARTHA","MARHTA") = ${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {mt}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-{\frac {2}{2}}}{6}}\right)=0.944}$ ${\displaystyle m}$ 一致する文字の数です。 ${\displaystyle t}$ 転置回数の半分（"MARTHA"[3]!=H, "MARHTA"[3]!=T）です。
最も頻繁に使用されるk文字		MostFreqKeySimilarity(' r e s e a r ch', 's ee king', 2) = 2

参考文献

1. Lu, Jiaheng; et al. (2013). 「文字列類似度測定と同義語との結合」 . 2013 ACM SIGMOD 国際データ管理会議議事録. pp.  373– 384. doi : 10.1145/2463676.2465313 . ISBN 9781450320375. S2CID  2091942 .
2. Navarro, Gonzalo (2001). 「近似文字列マッチングのガイドツアー」. ACM Computing Surveys . 33 (1): 31– 88. doi : 10.1145/375360.375365 . hdl : 10533/172862 . S2CID 207551224 . 
3. Shlomi Dolev、Mohammad, Ghanayim、Alexander, Binun、Sergey, Frenkel、Yeali, S. Sun (2017). 「マルウェアのクラスタリングとオンライン識別におけるJaccard距離と編集距離の関係」第16回IEEE国際ネットワークコンピューティング・アプリケーションシンポジウム、369–373ページ。
4. サムの文字列メトリクス - 計算言語学と音声学
5. Russell, David J., et al.「文法ベースの距離メトリックにより、16S配列の大規模セットの高速かつ正確なクラスタリングが可能になる。」 BMCバイオインフォマティクス11.1 (2010): 1-14.
6. Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (2003-08-01). 「名前照合タスクにおける文字列距離指標の比較」 : 73–78 .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

外部リンク

• 情報統合のための文字列類似性メトリクス かなり包括的な概要Wayback Machineのアーカイブインデックス
• カーネギーメロン大学のオープンソースライブラリ
• StringMetric プロジェクトは、文字列メトリックと音声アルゴリズムのScalaライブラリです。
• Naturalプロジェクトは、一般的な文字列メトリックの実装を含むJavaScriptの自然言語処理ライブラリです。