similar_text算相似性时归一化时的疑问

原创: 2016-06-23 13:35:12 796浏览

我在算两个字符串的长度时，发现归一化时好像此函数采取的方式不一样。
第一次，我试了两个不一样长的字符串，算其编辑距离：
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，你贴反了，误导群众。

呵呵，是的，写反了，谢谢指出来

笔误，对于归一化的疑问仍在~~

你的结论有普遍性吗？

不一样长

$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   



/* {{{ 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     还差一个  

 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是相等的