搜尋
首頁後端開發php教程similar_text算相似性时归一化时的疑问

我在算两个字符串的长度时,发现归一化时好像此函数采取的方式不一样。
第一次,我试了两个不一样长的字符串,算其编辑距离:
    echo "levenshtein计算:\n";echo levenshtein("seller_id","selr_id");echo "\n";
    得到的结果是:2

   再用同样的两个字符串,用PHP的similar_text函数来求其相似性
   echo "similar_text计算:\n";similar_text("seller_id","selr_id",$percent);
      echo $percent;
   出现在相似性是:87.5
把2这个距离归一化时,正好符合公式: 1-(编辑距离/(两个字符串的长度之和))

第二次,我试了两个一样长度的字符串,分别算其编辑距离和相似性
similar_text("abcd","1234",$percent);echo $percent;echo "\n";
echo levenshtein("abcd","1234");
得到的值分别为:4和0
正好符合公式: 1-(编辑距离/(任一个字符串的长度))

我的问题是:为什么对两个不一样长的字符串求相似性时,分母是两个字符串的长度之和呢?
我在网上找了些pdf文档看,对编辑距离归一化时,其分母是最长的那个字符串的长度呢。


回复讨论(解决方案)

第二次结果是0,4,你贴反了,误导群众。

第二次结果是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 的算法与理论是不一样的,似乎是加权了
不知哪位能费神找一下源码贴出
手册上说是用递归实现的,代码应该不太长

#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;}

还差一个

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  for (q = (char *) txt2; q  for (l = 0; (p + l  if (l > *max) {
*max = l;
*pos1 = p - txt1;
*pos2 = q - txt2;
}
}
}
}

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);//计算相似度

return sum; //返回两个字符串的匹配字符的数目

的确有点不一样
sim * 200.0 / (t1_len + t2_len)
的含义是 匹配的字符数占源串平均长度的百分比
与 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 *)……

手册上说复杂度是 O(N**3) 似乎这个函数就是了吧?
那 php_similar_char 的递归就不计算在复杂度中吗?

应该说 similar_text 函数的设计者,考虑的还是蛮周到的
当传入的两个串长度相同时,计算的相似度与理论上并无差异
当传入的两个串长度不同时,得到的相似度不像理论上的那么陡峭。也就是说被匹配的概率变大
当然如果你不希望这样的话可以自行计算,串都是你的,他也返回了已匹配的数量。计算一下并不困难

复杂度问题,是不是可以这样考虑?

php_similar_char的复杂度,理想的情况是logN,但最差是N


而对于,php_similar_str函数里的
for (l = 0; (p + l 
这语句虽然是个循环,但是和前面的php_similar_char是有关系的。因为此处会“剔除”最长相同字符串

每找出最长字符串+1,则外层递归,最差的复杂度会-1



另外,这是两种不同的算法,不知道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);//计算相似度

return sum; //返回两个字符串的匹配字符的数目

的确有点不一样
sim * 200……


算sim的这里我有点看不懂,是如何得到匹配的字符数的?
以seller_id和selr_id为例,其sim值通过相似度倒推过来,是7,7是如何比较得到的呢?能不能麻烦您详细说下?

应该说 similar_text 函数的设计者,考虑的还是蛮周到的
当传入的两个串长度相同时,计算的相似度与理论上并无差异
当传入的两个串长度不同时,得到的相似度不像理论上的那么陡峭。也就是说被匹配的概率变大
当然如果你不希望这样的话可以自行计算,串都是你的,他也返回了已匹配的数量。计算一下并不困难


“当传入的两个串长度不同时,得到的相似度不像理论上的那么陡峭”这里的理论是指1-(编辑距离/(最长的字符串的长度))这个吗?
$str1    = "esca";
$str2    = "sbca";
如果按照1-(编辑距离/(最长的字符串的长度)来算,是50,similar_text算出来,是75
确实变大了。不过为什么要这么处理呢,依据是什么

不是说了吗:匹配的概率变大
在很多情况下,输入的匹配条件就是误差多多的
多分严格的过滤条件,只能是无效劳动

依据是什么?实践
理论是建立在实践基础上的,不能用理论去约束实践。

不是说了吗:匹配的概率变大
在很多情况下,输入的匹配条件就是误差多多的
多分严格的过滤条件,只能是无效劳动

依据是什么?实践
理论是建立在实践基础上的,不能用理论去约束实践。


呵呵,那你的意思就是说,在实践中,人直觉感觉到的相似性一般要大于 1-编辑距离/源串的最大长度 这样算出来的值了~~~
另外,那个sim值是在算什么呢,那一段递归代码,实在木有看懂。。以seller_id和selr_id为例,其sim值是7,能否演示下7是如何得到的呢?谢谢啦

similar_text计算与编辑距离无关
similar_text计算方法是
两个字符的最长相似长度 与 两个字符串长度和的一半 的比值

$max_similar_len = 0;
$percent = 0;
$max_similar_len = similar_text($string1, $string2, $percent);
$perc = $max_similar_len * 2 / (strlen($string1) + strlen($string2));
这时$perc与$percent是相等的

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
繼續使用PHP:耐力的原因繼續使用PHP:耐力的原因Apr 19, 2025 am 12:23 AM

PHP仍然流行的原因是其易用性、靈活性和強大的生態系統。 1)易用性和簡單語法使其成為初學者的首選。 2)與web開發緊密結合,處理HTTP請求和數據庫交互出色。 3)龐大的生態系統提供了豐富的工具和庫。 4)活躍的社區和開源性質使其適應新需求和技術趨勢。

PHP和Python:探索他們的相似性和差異PHP和Python:探索他們的相似性和差異Apr 19, 2025 am 12:21 AM

PHP和Python都是高層次的編程語言,廣泛應用於Web開發、數據處理和自動化任務。 1.PHP常用於構建動態網站和內容管理系統,而Python常用於構建Web框架和數據科學。 2.PHP使用echo輸出內容,Python使用print。 3.兩者都支持面向對象編程,但語法和關鍵字不同。 4.PHP支持弱類型轉換,Python則更嚴格。 5.PHP性能優化包括使用OPcache和異步編程,Python則使用cProfile和異步編程。

PHP和Python:解釋了不同的範例PHP和Python:解釋了不同的範例Apr 18, 2025 am 12:26 AM

PHP主要是過程式編程,但也支持面向對象編程(OOP);Python支持多種範式,包括OOP、函數式和過程式編程。 PHP適合web開發,Python適用於多種應用,如數據分析和機器學習。

PHP和Python:深入了解他們的歷史PHP和Python:深入了解他們的歷史Apr 18, 2025 am 12:25 AM

PHP起源於1994年,由RasmusLerdorf開發,最初用於跟踪網站訪問者,逐漸演變為服務器端腳本語言,廣泛應用於網頁開發。 Python由GuidovanRossum於1980年代末開發,1991年首次發布,強調代碼可讀性和簡潔性,適用於科學計算、數據分析等領域。

在PHP和Python之間進行選擇:指南在PHP和Python之間進行選擇:指南Apr 18, 2025 am 12:24 AM

PHP適合網頁開發和快速原型開發,Python適用於數據科學和機器學習。 1.PHP用於動態網頁開發,語法簡單,適合快速開發。 2.Python語法簡潔,適用於多領域,庫生態系統強大。

PHP和框架:現代化語言PHP和框架:現代化語言Apr 18, 2025 am 12:14 AM

PHP在現代化進程中仍然重要,因為它支持大量網站和應用,並通過框架適應開發需求。 1.PHP7提升了性能並引入了新功能。 2.現代框架如Laravel、Symfony和CodeIgniter簡化開發,提高代碼質量。 3.性能優化和最佳實踐進一步提升應用效率。

PHP的影響:網絡開發及以後PHP的影響:網絡開發及以後Apr 18, 2025 am 12:10 AM

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

PHP類型提示如何起作用,包括標量類型,返回類型,聯合類型和無效類型?PHP類型提示如何起作用,包括標量類型,返回類型,聯合類型和無效類型?Apr 17, 2025 am 12:25 AM

PHP類型提示提升代碼質量和可讀性。 1)標量類型提示:自PHP7.0起,允許在函數參數中指定基本數據類型,如int、float等。 2)返回類型提示:確保函數返回值類型的一致性。 3)聯合類型提示:自PHP8.0起,允許在函數參數或返回值中指定多個類型。 4)可空類型提示:允許包含null值,處理可能返回空值的函數。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱工具

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)