时间：2021-07-01 10:21:17 帮助过：34人阅读
第二次结果是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 < end1; p++) {
for (q = (char *) txt2; q < end2; q++) {
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); 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 *)……
应该说 similar_text 函数的设计者，考虑的还是蛮周到的
当传入的两个串长度相同时，计算的相似度与理论上并无差异
当传入的两个串长度不同时，得到的相似度不像理论上的那么陡峭。也就是说被匹配的概率变大
当然如果你不希望这样的话可以自行计算，串都是你的，他也返回了已匹配的数量。计算一下并不困难
复杂度问题，是不是可以这样考虑？
php_similar_char的复杂度，理想的情况是logN,但最差是N
而对于，php_similar_str函数里的
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); 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……
应该说 similar_text 函数的设计者，考虑的还是蛮周到的
当传入的两个串长度相同时，计算的相似度与理论上并无差异
当传入的两个串长度不同时，得到的相似度不像理论上的那么陡峭。也就是说被匹配的概率变大
当然如果你不希望这样的话可以自行计算，串都是你的，他也返回了已匹配的数量。计算一下并不困难
不是说了吗：匹配的概率变大
在很多情况下，输入的匹配条件就是误差多多的
多分严格的过滤条件，只能是无效劳动
依据是什么？实践
理论是建立在实践基础上的，不能用理论去约束实践。
不是说了吗：匹配的概率变大
在很多情况下，输入的匹配条件就是误差多多的
多分严格的过滤条件，只能是无效劳动
依据是什么？实践
理论是建立在实践基础上的，不能用理论去约束实践。
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是相等的