php - similar_text 是如何工作的？

Question

我刚刚找到了similar_text 函数并正在使用它，但是百分比输出总是让我感到惊讶。请参阅下面的示例。

我试图找到关于 php: 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 个，结果是 10，所以我可以使用。

similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>"; 
//10
//5 out of 95 = 5 * 200 / (5 + 95) = 10

但我仍然无法弄清楚为什么 PHP 在翻转字符串时会返回不同的结果。 dfsq 提供的 JS 代码不这样做。查看PHP中的源代码我只能在以下行中找到不同之处，但我不是c程序员。了解其中的区别，将不胜感激。

在 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 源代码:similar text port to javascript

Answer 1

这实际上是一个非常有趣的问题，谢谢你给我一个谜题，结果非常有收获。

让我首先解释 similar_text 的实际工作原理。

---

类似文本:算法

这是一个基于递归的 divide and conquer algorithm .它的工作原理是首先找到两个输入之间的最长公共(public)字符串，然后将问题分解为围绕该字符串的子集。

您在问题中使用的示例实际上都执行算法的一次迭代。唯一不使用一次迭代和给出不同结果的来自 php.net comments .

这是一个简单的例子，可以帮助您理解 simple_text 背后的主要问题，并希望对它的工作原理有所了解。

---

类似文字:缺陷

eeeefaaaaafddddd
ddddgaaaaagbeeee

Iteration 1:
Max    = 5
String = aaaaa
Left : eeeef and ddddg
Right: fddddd and geeeee

我希望这个缺陷已经很明显了。它只会在两个输入字符串中直接检查最长匹配字符串的左侧和右侧。这个例子

$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

说实话，我不确定应该如何处理这种情况。可以看出，字符串中只有2个字符不同。但是 eeee 和 dddd 都在两个字符串的两端，不确定是什么 NLP爱好者或other literary专家们不得不对这种具体情况发表看法。

---

类似文本:参数交换的结果不一致

您遇到的基于输入顺序的不同结果是由于算法的实际行为方式(如上所述)。我将对发生的事情进行最后的解释。

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 

我们只有一次迭代，因为空/空字符串在递归时返回 0。所以这结束了算法，我们得到了我们的结果:1

然而，在第二种情况下，我们面临着多次迭代:

wert
test

Iteration 1:
Max    = 1
String = e
Left : w and t
Right: rt and st

我们已经有一个长度为 1 的公共(public)字符串。左边子集的算法将以 0 个匹配结束，但在右边:

rt
st

Iteration 1:
Max    = 1
String = t
Left : r and s
Right:  and 

这将导致我们新的最终结果:2

感谢您提出的这个内容丰富的问题​​以及再次涉足 C++ 的机会。

---

类似文字:JavaScript Edition

简短的回答是:javascript 代码没有实现正确的算法

sum += this.similar_text(first.substr(0, pos2), second.substr(0, pos2));

显然应该是first.substr(0,pos1)

注意: JavaScript 代码已由 eis 修复在 previous commit .谢谢 @eis

揭秘!