excellent_text는 어떻게 작동하는가?

excellent_text는 어떻게 작동하는가?

방금 비슷한_text 함수를 찾아서 가지고 놀고 있었는데, 그 백분율 출력이 항상 나를 놀라게 한다.아래 예제를 참조하십시오.

php: :에 언급된 바와 같이 사용되는 알고리즘에 대한 정보를 찾으려고 했다.

<?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 + lengght 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의 출처: Javascript와 유사한 텍스트 포트

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

먼저 유사_텍스트의 실제 작동 방식을 설명하겠다.

---

유사한 텍스트:알고리즘

그것은 분업과 정복 알고리즘을 기반으로 한 재귀적인 것이다.먼저 두 입력 사이의 가장 긴 공통 문자열을 찾아 문제를 해당 문자열을 중심으로 하위 집합으로 나누는 방식으로 작동한다.

질문에서 사용한 예시, 실제로 모두 알고리즘의 반복을 한 번만 수행하십시오.한 번 반복해서 사용하지 않는 것과 다른 결과를 주는 것은 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

첫 번째 경우, Iteration은 단 한 가지뿐입니다.

test
wert

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

빈 문자열/null 문자열은 반복 시 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 Edition

짧은 대답은 다음과 같다.Javascript 코드가 올바른 알고리즘을 구현하지 않는 경우

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

분명히 그래야 한다.first.substr(0,pos1)

참고: 자바스크립트 코드는 이전 커밋에서 아이스에 의해 수정되었다.고마워 @eis

반신반의!

함수는 매개변수 순서에 따라 다른 논리를 사용하는 것처럼 보인다.내 생각에 두 가지 일이 있는 것 같아.

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

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

파라메터1의 구별되는 문자가 파라메터2에 몇 배나 있는지 테스트하고 있는 것 같아 파라메터를 바꾸면 결과가 달라진다.'예상대로 작동한다'고 폐쇄된 버그로 보고됐다.

이제 위의 내용은 PHP와 Javascript 구현 둘 다 동일하다. - 파레미터 주문은 영향을 미치기 때문에 JS 코드가 이것을 하지 않을 것이라고 말하는 것은 잘못된 것이다.이것은 의도된 행동으로서 버그 입력에서 논증된다.

두 번째 - 올바르지 않은 것으로 보이는 것은 MYSQL/PHP 단어 예입니다.그것과 함께, 자바스크립트 버전은 3을 매개 변수의 순서와 무관하게 주는 반면, PHP는 2와 3을 준다(그리고 그것 때문에, 백분율은 동등하게 다르다).이제, "PHP IS GREAT"와 "WITH MYSQL"은 공통적으로 5개의 문자를 가져야 하는데, 어떤 식으로 비교하든 상관없다: H, I, S, T, 각 1개씩, 그리고 빈 공간에 1개씩 더하면 된다.순서는 'H', '', 'S'의 3자를 가지기 때문에 순서를 보면 정답은 양방향 모두 3자가 되어야 한다.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의 결과를 얻었다는 것을 알 수 있다.두 번째 비교에서는 '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

Javascript 버전이 다른 방식으로 작동한다는 것을 보여준다.자바스크립트 버전이 하는 것은 첫 번째 비교에서 'H', 'S', 'S'가 같은 순서에 있고, 두 번째 비교에서도 같은 'H', '', 'S'가 있다는 것을 발견하기 때문에, 이 경우, 파라람의 순서는 중요하지 않다.

Javascript는 PHP함수의 코드를 복제하기 위한 것이기 때문에 동일한 동작이 필요하기 때문에 @Khez와 현재 병합된 fix의 분석을 바탕으로 버그리포트를 제출하였다.

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

in screased_text(현황 $1차, 문자열 $2차 [, float &$% ] )에 대한 설명

이것은 올리버 [1993]에서 설명한 바와 같이 두 문자열 사이의 유사성을 계산한다.이 구현은 올리버의 유사 코드에서처럼 스택을 사용하는 것이 아니라 전체 프로세스의 속도를 높일 수도 있고 아닐 수도 있는 재귀적 호출을 사용한다는 점에 유의한다.또한 이 알고리즘의 복잡성은 O(N**3)이며 여기서 N은 가장 긴 문자열의 길이입니다.매개변수

첫째로

The first string.

둘째

The second string.

백분율

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

참조URL: https://stackoverflow.com/questions/14136349/how-does-similar-text-work