文字列メトリック

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

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

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

文字列間の相違度を測定する関数も存在しますが、必ずしも三角不等式を満たすわけではなく、数学的な意味での測定基準ではありません。そのような関数の例としては、Jaro–Winkler 距離があります。

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