similar_text是如何工作的？
我刚刚find了similar_text函数，并且正在玩弄它，但是百分比输出总是令我惊讶。 看下面的例子。
我试图find在php上提到的algorithm使用的相关信息： similar_text() Docs ：
<?php $p = 0; similar_text('aaaaaaaaaa', 'aaaaa', $p); echo $p . "<hr>"; //66.666666666667 //Since 5 out of 10 chars match, I would expect a 50% match similar_text('aaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p); echo $p . "<hr>"; //40 //5 out of 20 > not 25% ? similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p); echo $p . "<hr>"; //9.5238095238095 //5 out of 100 > not 5% ? //Example from PHP.net //Why is turning the strings around changing the result? similar_text('PHP IS GREAT', 'WITH MYSQL', $p); echo $p . "<hr>"; //27.272727272727 similar_text('WITH MYSQL', 'PHP IS GREAT', $p); echo $p . "<hr>"; //18.181818181818 ?>
有人可以解释这实际上是如何工作的？
更新：
感谢意见，我发现，百分比实际上是使用类似的字符数* 200 / length1 + lenght 2
Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
所以这就解释了为什么人们的期望高于预期。 用95中的5个string表示10，以便我可以使用。
similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p); echo $p . "<hr>"; //10 //5 out of 95 = 5 * 200 / (5 + 95) = 10
但是我仍然无法弄清楚为什么PHP在转换string时返回不同的结果。 由dfsq提供的JS代码不会这样做。 看看PHP中的源代码，我只能find以下行中的差异，但我不是ac程序员。 有一些洞察，在不同的是，将不胜感激。
在JS中：
for (l = 0;(p + l < firstLength) && (q + l < secondLength) && (first.charAt(p + l) === second.charAt(q + l)); l++);
在PHP中:( php_similar_str函数）
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
资源：
/* {{{ 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); } /* }}} */ /* {{{ php_similar_str */ 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_similar_char */ 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; } /* }}} */
在Javascript中的源代码： 相似的文本端口到JavaScript
这确实看起来function使用不同的逻辑取决于参数顺序。 我认为有两件事情在发挥。
首先看这个例子：
echo similar_text('test','wert'); // 1 echo similar_text('wert','test'); // 2
它似乎是testing“在param2中发现param1上的任何不同的字符多less次”，因此如果您交换参数，结果将会不同。 据报道，这是一个没有得到任何人证实的错误 。
现在，上面的PHP和JavaScript实现都是一样的 – 文件sorting有一个影响，所以说JS代码不会这样做是错误的。 我认为有可能根据预期的行为来争辩。 不知道是否。
其次 – 看起来不正确的是MYSQL / PHP的例子。 有了这个，javascript版本给出了3个与params顺序无关的参数，而PHP给出了2个和3个（因为这个百分比也是不同的）。 现在，“PHP是伟大的”和“与MYSQL”短语应该有5个字符是共同的，与你比较的方式无关：H，I，S和T，每一个，加上一个空的空间。 为了让他们有3个字符，'H'，''和'S'，所以如果你看看这个顺序，正确的答案应该是三种。 我将C代码修改为可运行版本，并添加了一些输出，以便可以看到发生了什么（ 键盘链接 ）：
#include<stdio.h> /* {{{ php_similar_str */ 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_similar_char */ 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) { printf("txt here %s,%s\n", txt1, txt2); sum += php_similar_char(txt1, pos1, txt2, pos2); } if ((pos1 + max < len1) && (pos2 + max < len2)) { printf("txt here %s,%s\n", txt1+ pos1 + max, txt2+ pos2 + max); sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max, txt2 + pos2 + max, len2 - pos2 - max); } } return sum; } /* }}} */ int main(void) { printf("Found %d similar chars\n", php_similar_char("PHP IS GREAT", 12, "WITH MYSQL", 10)); printf("Found %d similar chars\n", php_similar_char("WITH MYSQL", 10,"PHP IS GREAT", 12)); return 0; }
结果是输出：
txt here PHP IS GREAT,WITH MYSQL txt here P IS GREAT, MYSQL txt here IS GREAT,MYSQL txt here IS GREAT,MYSQL txt here GREAT,QL Found 3 similar chars txt here WITH MYSQL,PHP IS GREAT txt here TH MYSQL,S GREAT Found 2 similar chars
所以我们可以看到，在第一个比较中，函数find了'H'，''和'S'，而不是'T'，得到了3的结果。第二个比较发现'I'和'T' 'H'，''或'S'，从而得到2的结果。
这些结果的原因可以从输出中看出：algorithm采用第二个string包含的第一个string中的第一个字母，对其进行计数，并在第二个string之前丢弃之前的字符 。 这就是为什么它错过了中间的字符，这就是改变字符顺序的原因。
发生什么事情可能是故意的，也可能不是。 但是，这不是如何JavaScript版本的作品。 如果你在javascript版本中打印出相同的东西，你会得到这个：
txt here: PHP, WIT txt here: P IS GREAT, MYSQL txt here: IS GREAT, MYSQL txt here: IS, MY txt here: GREAT, QL Found 3 similar chars txt here: WITH, PHP txt here: W, P txt here: TH MYSQL, S GREAT Found 3 similar chars
显示javascript版本以不同的方式。 JavaScript版本所做的是在第一次比较中发现“H”，“S”和“S”是相同的顺序，第二次比较中也是一样的“H”，“S”和“S”，所以在这种情况下params的顺序并不重要。
我认为，JavaScript版本是更正确的做法，但这是炒作。 在任何情况下，因为javascript是为了复制PHP函数的代码，所以它需要performance一致 – 这就是为什么我根据@Khez的分析和修复提交错误报告的原因。 荣誉那里。
这实际上是一个非常有趣的问题，谢谢你给我一个谜题，结果是非常有益的。
我首先解释一下similar_text是如何工作的。
类似文本：algorithm
这是一个基于recursion的分而治之algorithm 。 它首先find两个input之间最长的公共string，并将问题分解成该string的子集。
你在问题中使用的例子，实际上只执行algorithm的一次迭代 。 唯一没有使用一个迭代和给出不同结果的是从php.net的评论 。
下面是一个简单的例子来理解simple_text背后的主要问题，并希望对它的工作方式有所了解。
类似的文本：缺陷
eeeefaaaaafddddd ddddgaaaaagbeeee Iteration 1: Max = 5 String = aaaaa Left : eeeef and ddddg Right: fddddd and geeeee
我希望这个缺陷已经很明显了。 它只会直接检查两个inputstring中最长匹配string的左侧和右侧 。 这个例子
$s1='eeeefaaaaafddddd'; $s2='ddddgaaaaagbeeee'; echo similar_text($s1, $s2).'|'.similar_text($s2, $s1); // outputs 5|5, this is due to Iteration 2 of the algorithm // it will fail to find a matching string in both left and right subsets
说实话，我不确定这种情况应该如何处理。 可以看出，string中只有2个字符不同。 但是eeee和dddd是两个string的两端，不确定NLP爱好者或其他文学专家对这个具体情况的说法。
类似的文本：参数交换的结果不一致
根据input顺序，您所经历的不同结果是由于alogirthm的实际行为方式（如上所述）。 我将对最新进展进行最后的探讨。
echo similar_text('test','wert'); // 1 echo similar_text('wert','test'); // 2
在第一种情况下，只有一个迭代：
test wert Iteration 1: Max = 1 String = t Left : and wer Right: est and
我们只有一个迭代，因为空/空string在recursion时返回0。 所以这结束了algorithm，我们得到了我们的结果：1
但在第二种情况下，我们面临着多重迭代：
wert test Iteration 1: Max = 1 String = e Left : w and t Right: rt and st
我们已经有了一个长度为1的公共string。左侧子集的algorithm将以0个匹配结束，但是在右侧：
rt st Iteration 1: Max = 1 String = t Left : r and s Right: and
这将导致我们的新的和最终的结果：2
我感谢你提供这个非常丰富的问题，并再次涉足C ++。
类似的文本： JavaScript版本
简短的回答是： JavaScript代码没有实现正确的algorithm
sum += this.similar_text(first.substr(0, pos2), second.substr(0, pos2));
显然它应该是first.substr(0,pos1)
注意：在之前的提交中 ， eis已经修复了JavaScript代码。 谢谢@eis
揭秘！
first String = aaaaaaaaaa = 10 letters second String = aaaaa = 5 letters first five letters are similar a+a a+a a+a a+a a+a a a a a a ( <similar_letters> * 200 ) / (<letter_count_first_string> + <letter_count_second_string>) ( 5 * 200 ) / (10 + 5); = 66.6666666667
描述int similar_text（string $ first，string $ second [，float＆$ percent]）
如Oliver [1993]所述，计算两个string之间的相似度。 请注意，这个实现不像Oliver的伪代码那样使用堆栈，而是recursion调用，这可能会或可能不会加速整个过程。 还要注意，这个algorithm的复杂性是O（N ** 3），其中N是最长string的长度。 参数
第一
The first string.
第二
The second string.
百分
By passing a reference as third argument, similar_text() will calculate the similarity in percent for you.
