搜索
首页后端开发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无尽的。

热工具

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)