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

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

like_text('aaaa', 'aaaa', $percent);

var_dump($percent);

//float(100)

類似テキスト('aaaa', 'aaaabbbb', $percent);

var_dump($percent);

//float(66.666666666667)

類似テキスト('abcdef', 'aabcdefg', $percent);

var_dump($percent);

//float(85.714285714286)

この機能を使用すると、あいまい検索機能や、あいまい一致が必要なその他の機能を実行することができます。最近、私はこの機能を検証コード認識の研究における特徴照合ステップに組み込みました。

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

(1) 2つの文字列の同じ部分を持つ最長のセグメントを見つけます;

(2) 同じ方法を使用して、残りの 2 つの段落で同じ部分を持つ最長のセグメントを見つけます。これを、同一の部分がなくなるまで繰り返します。

(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 *) txt1 + len1;

char *end2 = (char *) txt2 + len2;

int l;

*max = 0;

//最初の文字列に基づいてトラバースを開始します

for (p = (char *) txt1; p < end1; p++) {

// 2 番目の文字列をトラバースします

for (q = (char *) txt2; q

//同じ文字がある場合はループを続けて検索、lは同じ部分の長さです

for (l = 0; (p + l

//最長の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 つの文字列に同じ文字がないことを意味し、if

if ((sum = max)) {

//前半を再帰し、同じセグメントの長さを累積します

if (pos1 && pos2) {

sum += php_similar_char(txt1, pos1,

txt2、pos2);

}

//セグメントの後半を再帰し、同じセグメントの長さが累積されます

if ((pos1 + max

sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,

txt2 + pos2 + max, len2 - pos2 - max);

}

}

返金額;

}

//PHP関数定義

PHP_FUNCTION(similar_text)

{

char *t1, *t2;

zval **パーセント = NULL;

int ac = ZEND_NUM_ARGS();

int sim;

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(パーセント);

}

//両方の文字列の長さが 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(パーセント) = sim * 200.0 / (t1_len + t2_len);

}

RETURN_LONG(シム);

}

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