similar_text는 어떻게 작동합니까?

similar_text는 어떻게 작동합니까?

---

방금 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 / 길이 1 + 길이 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의 소스 코드를 보면 다음 줄에서만 차이점을 찾을 수 있지만 저는 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;
}
/* }}} */

자바 스크립트 소스 : 자바 스크립트 와 유사한 텍스트 포트

---

실제로 함수는 매개 변수 순서에 따라 다른 논리를 사용하는 것처럼 보입니다. 두 가지가 있다고 생각합니다.

먼저 다음 예를 참조하십시오.

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

"param2에서 param1의 고유 문자가 몇 번이나 발견되는지"테스트하는 것 같습니다. 따라서 매개 변수를 바꾸면 결과가 달라집니다. 버그 로보고 되었으며 "예상대로 작동"하는 것으로 종료되었습니다.

이제 위의 내용은 PHP와 자바 스크립트 구현 모두 동일 합니다. 매개 변수 순서가 영향을 미치므로 JS 코드가이를 수행하지 않는다는 것은 잘못된 것입니다. 이것은 의도 된 동작으로 버그 항목에서 주장됩니다.

둘째-정확하지 않은 것은 MYSQL / PHP 단어 예제입니다. 이를 통해 자바 스크립트 버전은 매개 변수 순서와 무관 한 3 개를 제공하는 반면 PHP는 2 개와 3 개를 제공합니다 (이로 인해 백분율이 동일하게 다릅니다). 이제 "PHP IS GREAT"및 "WITH MYSQL"이라는 구는 5 개의 공통 문자를 가져야합니다. 비교하는 방법과는 무관합니다. H, I, S 및 T, 각각 하나씩, 빈 공간에 대해 하나씩 추가합니다. 'H', '', 'S'의 3 글자로되어 있으므로 순서를 보시면 정답은 양방향 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입니다.

이러한 결과의 이유는 출력에서 ​​확인할 수 있습니다. 알고리즘은 두 번째 문자열에 포함 된 첫 번째 문자열의 첫 번째 문자를 가져 와서 세고 두 번째 문자열에서 그 앞의 문자를 버립니다 . 그렇기 때문에 중간에있는 문자를 놓치는 이유가 바로 문자 순서를 변경할 때 차이를 일으키는 원인입니다.

의도적 일 수도 있고 아닐 수도 있습니다. 그러나 그것은 자바 스크립트 버전이 작동하는 방식이 아닙니다. 자바 스크립트 버전에서 동일한 내용을 인쇄하면 다음과 같은 결과가 나타납니다.

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

자바 스크립트 버전이 다른 방식으로 작동 함을 보여줍니다. 자바 스크립트 버전이하는 일은 첫 번째 비교에서 'H', ''및 'S'가 동일한 순서이고 두 번째 비교에서도 동일한 'H', ''및 'S'를 찾는 것입니다. 이 경우 매개 변수의 순서는 중요하지 않습니다.

자바 스크립트는 PHP 함수의 코드를 복제하기위한 것이므로 동일하게 동작해야하므로 @Khez 분석을 기반으로 버그 보고서를 제출하고 현재 병합 된 수정 사항을 제출했습니다.

---

이것은 실제로 매우 흥미로운 질문이었습니다. 매우 보람있는 것으로 밝혀진 퍼즐을 제게 주셔서 감사합니다.

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

To be honest, I'm uncertain how this case should be treated. It can be seen that only 2 characters are different in the string. But both eeee and dddd are on opposite ends of the two strings, uncertain what NLP enthusiasts or other literary experts have to say about this specific situation.

---

Similar Text: Inconsistent results on argument swapping

The different results you were experiencing based on input order was due to the way the alogirthm actually behaves (as mentioned above). I'll give a final explination on what's going on.

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

On the first case, there's only one Iteration:

test
wert

Iteration 1:
Max    = 1
String = t
Left :  and wer
Right: est and 

We only have one iteration because empty/null strings return 0 on recursion. So this ends the algorithm and we have our result: 1

On the second case, however, we are faced with multiple Iterations:

wert
test

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

We already have a common string of length 1. The algorithm on the left subset will end in 0 matches, but on the right:

rt
st

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

This will lead to our new and final result: 2

I thank you for this very informative question and the opportunity to dabble in C++ again.

---

Similar Text: JavaScript Edition

The short answer is: The javascript code is not implementing the correct algorithm

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

Obviously it should be first.substr(0,pos1)

Note: The JavaScript code has been fixed by eis in a previous commit. Thanks @eis

Demystified!

---

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

---

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

This calculates the similarity between two strings as described in Oliver [1993]. Note that this implementation does not use a stack as in Oliver's pseudo code, but recursive calls which may or may not speed up the whole process. Note also that the complexity of this algorithm is O(N**3) where N is the length of the longest string. Parameters

first

The first string.

second

The second string.

percent

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

ReferenceURL : https://stackoverflow.com/questions/14136349/how-does-similar-text-work