PHP में स्ट्रिंग समानता: लंबे तारों के लिए फ़ंक्शन की तरह लेवेनशेटिन

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 एल्गोरिथ्म O(n*m), जहां n और m दो इनपुट तार की लंबाई की एक समय जटिलता है: क्या मुझे नीचे की तरह समान वाक्य का पता लगाने के लिए सबसे आसान तरीका है। यह बहुत महंगा है और लंबे तारों के लिए ऐसी दूरी की गणना करने में काफी समय लगेगा।

पूरे वाक्य के लिए, आप के बजाय एक diff एल्गोरिथ्म का उपयोग करने, उदाहरण के लिए देखें चाह सकते हैं: Highlight the difference between two strings in PHP

कहा करने के बाद यह, पीएचपी भी similar_text समारोह है जो एक भी बदतर जटिलता (O(max(n,m)**3)) है प्रदान करता है, लेकिन काम करने के लिए लगता है लंबे तारों पर।

Answer 2

आप similar_text का उपयोग करने का प्रयास कर सकते हैं।
यह 20,000+ वर्णों (3-5 सेकेंड) के साथ काफी धीमा हो सकता है लेकिन आपका उदाहरण आप केवल वाक्यों का उपयोग करके उल्लेख करते हैं, यह उस उपयोग के लिए ठीक काम करेगा।

ध्यान देने योग्य एक बात यह है कि विभिन्न आकारों की स्ट्रिंग की तुलना करते समय आपको 100% नहीं मिलेगा। उदाहरण के लिए यदि आप "हे" के साथ "हे" की तुलना करते हैं तो आपको केवल 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);