類似テキストが類似度を計算する場合の正規化に関する質問

2 つの文字列の長さを計算していたとき、この関数が正規化中に異なるアプローチをとっているように見えることがわかりました。
初めて、長さの異なる 2 つの文字列を試し、編集距離を計算しました。
echo "levenshtein Calculation: n";echo levenshtein("seller_id","selr_id");echo "n"; 結果は次のとおりです。 : 2

同じ 2 つの文字列を再度使用し、PHP の類似テキスト関数を使用して類似度を見つけます。類似度は: 87.5
2 の距離を正規化すると、次の式に正確に適合します: 1-(編集距離/(2 つの文字列の長さの合計))

2 回目は、同じ長さの 2 つの文字列を試しました編集距離と類似度をそれぞれ計算しました
minimum_text("abcd","1234",$percent);echo $percent;echo "n";
echo levenshtein("abcd", "1234");それぞれ: 4 と 0
式とまったく同じです: 1-(編集距離/(任意の文字列の長さ))

私の質問は次のとおりです: なぜ 2 つの長さが異なるのですか 文字列間の類似性を見つけるとき、分母が2つの文字列の長さの合計は?
オンラインでいくつかの PDF ドキュメントを見つけたところ、編集距離を正規化する場合、分母は最長の文字列の長さであることがわかりました。






ディスカッション (解決策) への返信

2 回目の結果は 0,4 で、逆に投稿して世間を誤解させました。

2 番目の結果は 0,4 です。あなたはそれを逆に投稿し、世間を誤解させました。

あはは、はい、逆に書いてしまいました、ご指摘ありがとうございます

タイプミス、正規化についてまだ疑問があります~~

あなたの結論は普遍的ですか?
長さが違う

$str1	= "esca";$str2	= "bca";echo	levenshtein($str1,$str2), "\n";similar_text($str1,$str2,$percent);echo	$percent;/*257.142857142857*/

同じ長さ

$str1	= "esca";$str2	= "sbca";echo	levenshtein($str1,$str2), "\n";similar_text($str1,$str2,$percent);echo	$percent;/*275*/

うーん、similar_textのアルゴリズムも理論も違うし、重み付けされているようです
誰がわざわざソースコード見つけて載せるのかな
マニュアルには実装されていると書いてありますrecursion を使用すると、コードが長すぎてはいけません

#define LEVENSHTEIN_MAX_LENGTH 255/* {{{ reference_levdist * reference implementation, only optimized for memory usage, not speed */static int reference_levdist(const char *s1, int l1, const char *s2, int l2, int cost_ins, int cost_rep, int cost_del ){	int *p1, *p2, *tmp;	int i1, i2, c0, c1, c2;	if (l1 == 0) {		return l2 * cost_ins;	}	if (l2 == 0) {		return l1 * cost_del;	}	if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {		return -1;	}	p1 = safe_emalloc((l2 + 1), sizeof(int), 0);	p2 = safe_emalloc((l2 + 1), sizeof(int), 0);	for (i2 = 0; i2 <= l2; i2++) {		p1[i2] = i2 * cost_ins;	}	for (i1 = 0; i1 < l1 ; i1++) {		p2[0] = p1[0] + cost_del;		for (i2 = 0; i2 < l2; i2++) {			c0 = p1[i2] + ((s1[i1] == s2[i2]) ? 0 : cost_rep);			c1 = p1[i2 + 1] + cost_del;			if (c1 < c0) {				c0 = c1;			}			c2 = p2[i2] + cost_ins;			if (c2 < c0) {				c0 = c2;			}			p2[i2 + 1] = c0;		}		tmp = p1;		p1 = p2;		p2 = tmp;	}	c0 = p1[l2];	efree(p1);	efree(p2);	return c0;}/* }}} *//* {{{ custom_levdist */static int custom_levdist(char *str1, char *str2, char *callback_name TSRMLS_DC){	php_error_docref(NULL TSRMLS_CC, E_WARNING, "The general Levenshtein support is not there yet");	/* not there yet */	return -1;}/* }}} *//* {{{ proto int levenshtein(string str1, string str2[, int cost_ins, int cost_rep, int cost_del])   Calculate Levenshtein distance between two strings */PHP_FUNCTION(levenshtein){	int argc = ZEND_NUM_ARGS();	char *str1, *str2;	char *callback_name;	int str1_len, str2_len, callback_len;	long cost_ins, cost_rep, cost_del;	int distance = -1;	switch (argc) {		case 2: /* just two strings: use maximum performance version */			if (zend_parse_parameters(2 TSRMLS_CC, "ss", &str1, &str1_len, &str2, &str2_len) == FAILURE) {				return;			}			distance = reference_levdist(str1, str1_len, str2, str2_len, 1, 1, 1);			break;		case 5: /* more general version: calc cost by ins/rep/del weights */			if (zend_parse_parameters(5 TSRMLS_CC, "sslll", &str1, &str1_len, &str2, &str2_len, &cost_ins, &cost_rep, &cost_del) == FAILURE) {				return;			}			distance = reference_levdist(str1, str1_len, str2, str2_len, cost_ins, cost_rep, cost_del);			break;		case 3: /* most general version: calc cost by user-supplied function */			if (zend_parse_parameters(3 TSRMLS_CC, "sss", &str1, &str1_len, &str2, &str2_len, &callback_name, &callback_len) == FAILURE) {				return;			}			distance = custom_levdist(str1, str2, callback_name TSRMLS_CC);			break;		default:			WRONG_PARAM_COUNT;	}	if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {		php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument string(s) too long");	}	RETURN_LONG(distance);}/* }}} */

/* {{{ proto int similar_text(string str1, string str2 [, float percent])   Calculates the similarity between two strings */PHP_FUNCTION(similar_text){	char *t1, *t2;	zval **percent = 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) {		return;	}	if (ac > 2) {		convert_to_double_ex(percent);	}	if (t1_len + t2_len == 0) {		if (ac > 2) {			Z_DVAL_PP(percent) = 0;		}		RETURN_LONG(0);	}	sim = php_similar_char(t1, t1_len, t2, t2_len);	if (ac > 2) {		Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);	}	RETURN_LONG(sim);}static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2){	int sum;	int pos1, pos2, max;	php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);	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;}

1 つ減ります

static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, inと * pos 2, int *max)
{ char *p, *q;

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

* max = 0;
for (p = (char *) txt1; p for (q = (char *) txt2; q for (l = 0; ( p + l if (l > *max) {
*max = l; *pos1 = p


Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len); // 類似度
と
の合計を計算します。 // 2 つの文字列の一致する文字の数を返します

は実際には少し異なります
sim * 200.0 / (t1_len + t2_len)
意味は、一致した文字数がソース文字列の平均長の割合を占めるということです。これは、1 編集距離/最大長とあまり変わりません。


まだ違いが 1 つあります

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 *)...
説明書によると、この関数のようです。ですよね？
では、php_similar_char の再帰は計算量では計算されないのでしょうか？

渡された 2 つの文字列の長さが同じ場合、計算された類似度は理論と何ら変わりません。類似性は理論ほど急峻ではありません。つまり、一致する確率が高くなります。もちろん、これを望まない場合は、文字列を自分で計算することもできます。また、一致する数も返します。計算するのは難しくありません

複雑さの問題については、このように考えて良いでしょうか？

php_similar_char の複雑さは、理想的には logN ですが、最悪は N です

そして、php_similar_str 関数の
については、 (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); ステートメント

このステートメントはループですが、前の php_similar_char に関連しています。最も長い同一の文字列がここで「削除」されるため

最長の文字列が見つかるたびに +1、外側再帰、最悪の複雑さは -1 になります



さらに、これらは 2 つの異なるアルゴリズムです。 lz がなぜこのパターンを探しているのかわかりませんが、無駄になると思います。アルゴリズムの意味を理解してください。


PHP_FUNCTION(similar_text)

sim = php_similar_char(t1, t1_len, t2, t2_len);

Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2 _len);/ /calculation 類似度
と
return sum; // 2 つの文字列内の一致する文字の数を返します

確かに少し異なります
sim * 200...

ここでの sim の計算がわかりません、方法一致する文字を取得します。
seller_id と selr_id を例にとると、それらの sim 値は類似度から逆算され、7 になります。比較により 7 はどのように得られるのでしょうか?これについて詳しく教えていただけますか？

like_text 関数の設計者は非常に思慮深いと言わなければなりません
渡された 2 つの文字列の長さが同じ場合、計算される類似度は理論と何ら変わりません。渡された値が異なる場合、得られる類似度は理論ほど急峻ではありません。つまり、一致する確率が高くなります。もちろん、これを望まない場合は、文字列を自分で計算することもできます。また、一致する数も返します。計算するのは難しくありません

「2 つの入力文字列の長さが異なる場合、得られる類似性は理論ほど急峻ではありません」 ここでの理論は 1-(編集距離/(最長文字列の長さ)) を指します。 ?

$str1 = "esca";
$str2 = "sbca";
1-(編集距離/(最長の文字列の長さ)) に従って計算すると、それは 50、similar_text を計算すると、それは 75 になります。確かに大きくなります。しかし、なぜこのようになっているのでしょうか? 多くの場合、入力された一致条件がエラーだらけで効果がなくなるからです。

根拠は何ですか? 実践
理論は実践に基づいており、理論を使用して実践を制約することはできません


一致する確率は大きくなります
多くの場合、入力された一致条件は満たされています。 厳密なフィルタリング条件は非効率的な作業になるだけです

根拠は何ですか? 実践に基づくものであり、理論は実践を制限するために使用することはできません

はは、つまり、実践では、ということです。一般に、ソース文字列の 1 編集距離/最大長などで計算された値よりも大きいと人々は直感的に感じます。また、この再帰コードは実際には役に立たないことを理解していますか?例として selr_id を使用した場合、sim 値は 7 です。 7 がどのように取得されるかを示していただけますか? ありがとうございます
類似テキストの計算方法は、
2 つの文字列の長さの合計の半分に対する長い類似性の長さの比率です

$max_similar_len = 0;

$percent = 0;
$max_similar_len = 類似テキスト($string1, $string2, $percent);
$perc = $max_similar_len * 2 / (strlen($string1) + strlen($string2)) ;
この時点では、$perc と $percent は等しいです