similar_text如何工作？

Question

我刚发现了 similar_text 函数，并且尝试使用它，但百分比输出总是让我感到惊讶。请看下面的例子。

我试图在 php: similar_text()^文档 中找到有关所使用算法的信息：

<?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 / (长度1 + 长度2)来计算的。

Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);

这就解释了为什么百分比高于预期。使用一个字符串中的5个字符，总数为95，则计算得出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++);

Source:

/* {{{ 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 的 Javascript 移植版

- Hugo Delsing

---

伊恩·奥利弗，《编程经典：实现世界最佳算法》（Ian Oliver, Programming classics: implementing the world's best algorithms）可在Google图书和亚马逊上购买。 - Gordon

请参见https://dev59.com/oXA75IYBdhLWcg3w0sp-。 - Nanne

你应该检查 PHP 源代码以获取原始实现。 - dfsq

@HugoDelsing想让我深入解释一下函数如何迭代以找到结果吗？我认为从答案的顶部向下进行解释已经很清楚了，如果我错了，我很抱歉。 - Khez

你的链接包含了&thanks=6，这已经显示了“感谢您的投票信息”。你的链接应该是https://bugs.php.net/bug.php?id=62648，这样你才能真正地投票。 - Hugo Delsing

Answer 1

这实际上是一个非常有趣的问题，感谢您给了我一个非常有益的难题。

让我先解释一下similar_text的工作原理。

---

相似文本：算法

这是一个基于递归的分治算法。它首先找到两个输入之间的最长公共字符串，并围绕该字符串将问题分解为子集。

您在问题中使用的示例实际上都执行了算法的一次迭代。唯一没有使用一次迭代并且给出不同结果的是php.net注释中的那些。

这里有一个简单的示例，以理解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爱好者或其他文学专家对这种特定情况有什么看法。

---

相似文本：关于参数交换的不一致结果

您在输入顺序上所遇到的不同结果是由算法实际行为（如上所述）导致的。接下来我将对发生的情况做出最终说明。

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的共同字符串。左子集算法将以0个匹配结束，但右子集算法：

rt
st

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

这将导致我们的新结果：2。

非常感谢您提供这个非常有启发性的问题和再次涉足C++的机会。

---

类似文本：JavaScript 版本

简短回答是：JavaScript 代码未正确实现算法

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

显然应该是first.substr(0,pos1) 注意：JavaScript代码已经由eis在之前的提交中修复。感谢@eis 揭秘！

- Khez

---

老实说，我不认为我们所经历的是一个漏洞。这只是它被设计成那样而已。参数交换只是掩盖了一个设计决策。考虑到这一点，一切都取决于你的需求以及你计划如何处理结果。你需要听起来相同的字符串吗？用 soundex。你需要让它们在英语中听起来相同吗？用 metaphone。你想要一个通用的相似性函数吗？用 levenshtein。奇怪的是，与 levenshtein 相比，similar_text 的复杂度更糟糕，并且可能会产生非常糟糕的结果，除非完全明白。 - Khez

@eis 尝试了使用 juggling test/wert，结果与 PHP 版本相同。你实际上发现了什么不同之处？ - Khez

@Khez 嗯？test/wert 在两个版本中的结果是相同的，就像我解释的那样：这是 MySQL-PHP 字符串引起差异的情况。 - eis

@eis 如果你的算法有错误，那就有所不同了！我更新了我的回答... - Khez

@Khez 没问题。我猜我也需要更新我的答案。很好，找到了问题所在。 - eis

Answer 2

“确实，根据参数顺序，该函数似乎使用不同的逻辑。我认为有两个因素在起作用。

首先，看这个例子：”

echo similar_text('test','wert'); // 1
echo similar_text('wert','test'); // 2

似乎它正在测试“在param2中找到param1上任何不同字符的次数”，因此如果交换参数，结果会有所不同。它已被报告为错误，但已被关闭为“按预期工作”。现在，以上内容对于PHP和JavaScript实现是相同的，参数顺序会产生影响，因此说JS代码不会这样做是错误的。这在错误条目中被认为是预期行为。

第二点 - 看起来不正确的是MYSQL / PHP单词示例。在此情况下，无论参数顺序如何，JavaScript版本都会给出3个不相关的结果，而PHP则会给出2和3（因此百分比也不同）。现在，“PHP IS GREAT”和“WITH MYSQL”这两个短语应该有5个共同字符，无论如何比较：H，I，S和T，各一个，加上一个空格。按顺序排列，它们有3个字符，'H'，' '和'S'，因此如果您查看排序，则正确答案应为两种方式都是3。我修改了C代码以使其可运行，并添加了一些输出，以便可以看到发生了什么（codepad link）：

#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

所以可以看到，在第一次比较中，函数找到了'H'、' '和'S'，但没有找到'T'，结果为3。第二次比较找到了'I'和'T'，但没有找到'H'、' '或'S'，因此得到2的结果。

从输出结果可以看出，这些结果的原因是：算法在第二个字符串中找到第一个字符，计数后将其从第二个字符串中删除。这就是它错过中间字符的原因，也是改变字符顺序时产生差异的原因。

这种情况可能是有意为之，也可能不是。然而，这并不是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'按相同顺序出现，第二次比较也是相同的，因此在这种情况下参数的顺序并不重要。

由于JavaScript旨在复制PHP函数的代码，它需要表现得完全相同，因此我基于@Khez的分析提交了错误报告和修复，现在已经合并。

- eis

---

这对我来说听起来是正确的。值得思考的是，“为什么我要使用similar_text()，而不是levenshtein()和/或metaphone()？”我编写了字符串去重代码和字符串相似搜索代码，使用levenshtein()和metaphone()取得了更好的结果，而不是similar_text()。一个相关的技术值得研究的是TFIDF（总频率与逆域频率），当尝试识别唯一字符串时。 - Apollo Clark

关于未经确认的错误，无论是在工单中还是在PHP.net上的评论中，都感觉算法就是应该这样工作的... - Khez

@Khez 是的，我同意。但实际确认它确切的操作仍然缺失，所以我们无法确定。 - eis

@Khez 我认为你应该注意到 OP 实际上有两个算法，一个是 PHP 的，另一个是 javascript 的。我认为 javascript 版本是他们试图拥有的东西，但是却失败了，转而使用了 PHP 实现。 :P - eis

@HugoDelsing我的回复没有帮到您吗？您还需要进一步的解释吗？ - Khez

Answer 3

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

- spinsch

---

哦，这个公式只是对（相似文本的发现/两个字符串的平均长度）进行操作，然后乘以100。 - Sanket Deshpande

Answer 4

描述

int similar_text ( string $first , string $second [, float &$percent ] )

此函数计算两个字符串的相似度，如 Oliver [1993] 所述。请注意，此实现不使用像 Oliver 伪代码中那样的堆栈，而是使用递归调用，这可能会加快整个过程的速度。还要注意，此算法的复杂度为 O(N**3)，其中 N 是最长字符串的长度。

参数：

first

The first string.

第二个

The second string.

百分比

By passing a reference as third argument, similar_text() will calculate the similarity in percent for you.

- Kamesh S