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/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中的源代码,我只能在下面的行中找到差异,但我不是程序员.对于差异的一些见解,将不胜感激.

在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的文本端口

Answer 1

看起来这个函数确实使用不同的逻辑,具体取决于参数顺序.我认为有两件事在起作用.

首先,看看这个例子:

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

似乎它正在测试"在param2中找到param1上任何不同的char多少次",因此如果你交换params,结果会有所不同.它已被报道为一个错误,尚未得到任何人的证实.

现在,上面的PHP和javascript实现都是一样的 - paremeter命令有影响,所以说JS代码不会这样做是错误的.我认为有可能认为这是预期的行为.不确定是不是.

第二 - 看起来不正确的是MYSQL/PHP单词示例.有了它,javascript版本给出3与params的顺序无关,而PHP给出2和3(并且由于这个,百分比是同样不同的).现在,短语"PHP IS GREAT"和"WITH 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

因此可以看出,在第一次比较时,函数找到'H',''和'S',但不是'T',得到了结果3.第二次比较发现'我'和'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'的顺序相同,而在第二次比较中发现'H',''和'S'相同 - 所以在这种情况下,参数的顺序无关紧要.

我认为javascript版本是更正确的做法,但这是猜测.在任何情况下,由于javascript意味着复制PHP函数的代码,它需要表现相同 - 这就是为什么我提交了基于@Khez分析和修复的错误报告.感谢那里.

Answer 2

这实际上是一个非常有趣的问题,谢谢你给我一个谜题,结果证明是非常有益的.

让我首先解释一下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爱好者或其他文学专家对这个特定情况的看法.

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

您根据输入顺序遇到的不同结果是由于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 

我们只有一次迭代,因为空/空字符串在递归时返回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)

注意:在以前的提交中,eis修复了JavaScript代码.谢谢@eis

揭秘!

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