qwidjib0

levenshtein distance (advanced))

Dec 8th, 2011
42
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. * Levenshtein comparison from 0 to 100: 0 being the most similar, 100 being the least (from php.net)
  3. */
  4. function levenshteinDistance2($str1, $str2) {
  5.     $len1 = mb_strlen($str1);
  6.     $len2 = mb_strlen($str2);
  7.    
  8.     // strip common prefix
  9.     $i = 0;
  10.     do {
  11.         if(mb_substr($str1, $i, 1) != mb_substr($str2, $i, 1))
  12.             break;
  13.         $i++;
  14.         $len1--;
  15.         $len2--;
  16.     } while($len1 > 0 && $len2 > 0);
  17.     if($i > 0) {
  18.         $str1 = mb_substr($str1, $i);
  19.         $str2 = mb_substr($str2, $i);
  20.     }
  21.    
  22.     // strip common suffix
  23.     $i = 0;
  24.     do {
  25.         if(mb_substr($str1, $len1-1, 1) != mb_substr($str2, $len2-1, 1))
  26.             break;
  27.         $i++;
  28.         $len1--;
  29.         $len2--;
  30.     } while($len1 > 0 && $len2 > 0);
  31.     if($i > 0) {
  32.         $str1 = mb_substr($str1, 0, $len1);
  33.         $str2 = mb_substr($str2, 0, $len2);
  34.     }
  35.    
  36.     if ($len1 == 0)
  37.         return $len2;    
  38.     if ($len2 == 0)
  39.         return $len1;
  40.    
  41.     $v0 = range(0, $len1);
  42.     $v1 = array();
  43.    
  44.     for ($i = 1; $i <= $len2; $i++) {
  45.         $v1[0] = $i;
  46.         $str2j = mb_substr($str2, $i - 1, 1);
  47.        
  48.         for ($j = 1; $j <= $len1; $j++) {
  49.             $cost = (mb_substr($str1, $j - 1, 1) == $str2j) ? 0 : 1;
  50.            
  51.             $m_min = $v0[$j] + 1;
  52.             $b = $v1[$j - 1] + 1;
  53.             $c = $v0[$j - 1] + $cost;
  54.            
  55.             if ($b < $m_min)
  56.                 $m_min = $b;
  57.             if ($c < $m_min)
  58.                 $m_min = $c;
  59.            
  60.             $v1[$j] = $m_min;
  61.         }
  62.        
  63.         $vTmp = $v0;
  64.         $v0 = $v1;
  65.         $v1 = $vTmp;
  66.     }
  67.    
  68.     return $v0[$len1];
  69. }
  70.  
RAW Paste Data