PHP関数similar_text()の原理分析_PHPチュートリアル-PHPチュートリアル-php.cn

PHP関数similar_text()の原理分析_PHPチュートリアル

WBOY

リリース： 2016-07-21 14:58:27

オリジナル

896 人が閲覧しました

PHP には、2 つの文字列の類似性を計算する関数類似テキスト() があり、2 つの文字列の類似性を表すパーセンテージを取得できます。効果は以下の通りです

similar_text('aaaa', 'aaaa', $percent);
var_dump($percent)
//float(100)
similar_text('aaaa', 'aaaabbb', $percent); ; //フロート（66.666666667）ファジーマッチングが必要です。最近、私はこの機能を検証コード認識の研究における特徴照合ステップに組み込みました。

しかし、この関数はどのようなアルゴリズムを使用しているのでしょうか?私は彼の基礎となる実装を研究し、それを 3 つのステップにまとめました:

(1) 2 つの文字列内の同じ部分を持つ最長のセグメントを検索します。
(2) 同じ方法を使用して、残りの 2 つのセグメント内の同じ部分を持つ最長のセグメントを見つけます。これを、Any がなくなるまで繰り返します。同一部分;
(3) 類似度 = すべての同一部分の長さの合計 * 2 / 2 つの文字列の長さの合計

私が調査したソースコードのバージョンは PHP 5.4.6 で、関連するコードは次の場所にあります。ファイル php - -5.4.6/ext/standard/string.c の 2951 ～ 3031 行目。以下はコメントを追加した後のソースコードです。

//2 つの文字列内の同じ部分を持つ最長のセグメントを検索します
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
char *p, *q;
char *end1 = (char *) txt2 + len2;

*max = 0;最初の文字列に基づいて走査
for (p = (char *) txt1; p < end1; p++) {
//2 番目の文字列を走査
for (q = (char *) txt2; q //同じ文字がある場合は、ループを続けて検索します。l は同じ部分の長さです
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]);
//Bubble メソッドは最長の l を見つけ、同じ部分の開始位置を記憶します
if (l > *max) {
* max = l;
*pos1 = p - txt1;
*pos2 = q - txt2;
}
}
}
}

//2 つの文字列の同じ部分の合計の長さを計算します
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
int sum;
int pos1, pos2, max;

//2 つの文字列の同じ部分の最長のセグメントを見つけます
php_similar_str(txt1, len1 , txt2, len2, &pos1, &pos2, &max);
//これは合計への最初の代入と最大値の判定です
//max が 0 の場合、2 つの文字列に同一の文字がないことを意味します。 is if から飛び出します
if ((sum = max)) {
//前半は再帰、同じセグメントの長さが累積されます
if (pos1 && pos2) {
sum += php_similar_char(txt1, pos1) ,
txt2, pos2);
}
//セグメントの後半を再帰し、同じセグメントの長さが累積されます
if ((pos1 + max < len1) && (pos2 + max < len2) ) {
sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
txt2 + pos2 + max, len2 - pos2 - max);

return sum

//PHP関数定義
PHP_FUNCTION(similar_text)
{
char *t1, *t2 ;
int ac = ZEND_NUM_ARGS();
int t1_len, t2_len;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z" , &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {
}

//3 番目のパラメーターがある場合
if (ac > 2) {
convert_to_double_ex(percent);
}

//両方の文字列の長さが 0 の場合、0 を返します
if (t1_len + t2_len == 0) {
if (ac > 2) {
Z_DVAL_PP (パーセント) = 0;
}

RETURN_LONG(0) ;
}

//上記の関数を呼び出して 2 つの文字列の類似性ライブラリを計算します
sim = php_similar_char(t1, t1_len, t2, t2_len); /3番目のパラメータパーセントの計算式がわかります
if (ac > 2) {
Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len)
}

RETURN_LONG(sim);
さらに、PHP は文字列の類似性を計算するための別の関数 levenshtein() も提供します。これは 2 つの文字列の編集距離を計算することで文字列の類似性を表現します。これも非常に一般的なアルゴリズムです。 levenshtein() のパフォーマンスは、similar_text() よりも優れています。これは、前のコード分析から、similar_text() の複雑さは O(n^3) であり、n は最長の文字列の長さを表し、levenshtein( ) 複雑さは O(m*n) で、m と n はそれぞれ 2 つの文字列の長さです。