PHP의 문자열 유사성 : 긴 문자열의 함수처럼 levenshtein

Question

PHP의 함수 levenshtein은 최대 길이 255 인 문자열에서 작동합니다. PHP에서 문장의 유사도 점수를 계산하는 좋은 방법은 무엇입니까?

기본적으로 나는 문장의 데이터베이스를 가지고 있으며 대략적인 중복을 찾고 싶습니다. similar_text 기능이 예상 결과를 제공하지 않습니다.

$ss="Jack is a very nice boy, isn't he?"; 
$pp="jack is a very nice boy is he"; 

$ss=strtolower($ss); // convert to lower case as we dont care about case 
$pp=strtolower($pp); 

$score=similar_text($ss, $pp); 
echo "$score %\n"; // Outputs just 29 % 

$score=levenshtein ($ss, $pp); 
echo "$score\n"; // Outputs '5', which indicates they are very similar. But, it does not work for more than 255 chars :(

Answer 1

levenshtein 알고리즘은 n 및 m는 두 개의 입력 문자열의 길이입니다 O(n*m)의 시간 복잡도를 가지고 : 어떤 날 아래와 같이 유사한 문장을 감지 할 수있는 가장 쉬운 방법입니다. 이것은 꽤 비싸고 긴 문자열을위한 그런 거리 계산은 오랜 시간이 걸릴 것입니다. 전체 문장에 대한

, 당신은 대신 diff 알고리즘을 사용 예를 참조 할 수 있습니다 : Highlight the difference between two strings in PHP

이가, PHP는 훨씬 더 복잡 (O(max(n,m)**3))을 가지는 similar_text 기능을 제공하지만 작동하는 것 같다 미루어 긴 문자열에.

Answer 2

similar_text을 사용해보세요.
20,000+ 문자 (3-5 초)로 매우 느려질 수 있지만 문장 만 사용하면이 사용법에 문제가 없습니다.

한 가지주의 할 점은 다른 크기의 문자열을 비교할 때 100 %를 얻지 못한다는 것입니다. 예를 들어 "he"와 "head"를 비교하면 50 % 만 일치합니다.

Answer 3

저는 Smith Waterman Gotoh이 문장 비교를위한 최상의 알고리즘이라는 것을 알았습니다. 더 많은 정보 in this answer. 다음은 PHP 코드 예입니다.

class SmithWatermanGotoh 
{ 
    private $gapValue; 
    private $substitution; 

    /** 
    * Constructs a new Smith Waterman metric. 
    * 
    * @param gapValue 
    *   a non-positive gap penalty 
    * @param substitution 
    *   a substitution function 
    */ 
    public function __construct($gapValue=-0.5, 
       $substitution=null) 
    { 
     if($gapValue > 0.0) throw new Exception("gapValue must be <= 0"); 
     //if(empty($substitution)) throw new Exception("substitution is required"); 
     if (empty($substitution)) $this->substitution = new SmithWatermanMatchMismatch(1.0, -2.0); 
     else $this->substitution = $substitution; 
     $this->gapValue = $gapValue; 
    } 

    public function compare($a, $b) 
    { 
     if (empty($a) && empty($b)) { 
      return 1.0; 
     } 

     if (empty($a) || empty($b)) { 
      return 0.0; 
     } 

     $maxDistance = min(mb_strlen($a), mb_strlen($b)) 
       * max($this->substitution->max(), $this->gapValue); 
     return $this->smithWatermanGotoh($a, $b)/$maxDistance; 
    } 

    private function smithWatermanGotoh($s, $t) 
    { 
     $v0 = []; 
     $v1 = []; 
     $t_len = mb_strlen($t); 
     $max = $v0[0] = max(0, $this->gapValue, $this->substitution->compare($s, 0, $t, 0)); 

     for ($j = 1; $j < $t_len; $j++) { 
      $v0[$j] = max(0, $v0[$j - 1] + $this->gapValue, 
        $this->substitution->compare($s, 0, $t, $j)); 

      $max = max($max, $v0[$j]); 
     } 

     // Find max 
     for ($i = 1; $i < mb_strlen($s); $i++) { 
      $v1[0] = max(0, $v0[0] + $this->gapValue, $this->substitution->compare($s, $i, $t, 0)); 

      $max = max($max, $v1[0]); 

      for ($j = 1; $j < $t_len; $j++) { 
       $v1[$j] = max(0, $v0[$j] + $this->gapValue, $v1[$j - 1] + $this->gapValue, 
         $v0[$j - 1] + $this->substitution->compare($s, $i, $t, $j)); 

       $max = max($max, $v1[$j]); 
      } 

      for ($j = 0; $j < $t_len; $j++) { 
       $v0[$j] = $v1[$j]; 
      } 
     } 

     return $max; 
    } 
} 

class SmithWatermanMatchMismatch 
{ 
    private $matchValue; 
    private $mismatchValue; 

    /** 
    * Constructs a new match-mismatch substitution function. When two 
    * characters are equal a score of <code>matchValue</code> is assigned. In 
    * case of a mismatch a score of <code>mismatchValue</code>. The 
    * <code>matchValue</code> must be strictly greater then 
    * <code>mismatchValue</code> 
    * 
    * @param matchValue 
    *   value when characters are equal 
    * @param mismatchValue 
    *   value when characters are not equal 
    */ 
    public function __construct($matchValue, $mismatchValue) { 
     if($matchValue <= $mismatchValue) throw new Exception("matchValue must be > matchValue"); 

     $this->matchValue = $matchValue; 
     $this->mismatchValue = $mismatchValue; 
    } 

    public function compare($a, $aIndex, $b, $bIndex) { 
     return ($a[$aIndex] === $b[$bIndex] ? $this->matchValue 
       : $this->mismatchValue); 
    } 

    public function max() { 
     return $this->matchValue; 
    } 

    public function min() { 
     return $this->mismatchValue; 
    } 
} 

$str1 = "Jack is a very nice boy, isn't he?"; 
$str2 = "jack is a very nice boy is he"; 
$o = new SmithWatermanGotoh(); 
echo $o->compare($str1, $str2);