среда, 28 июля 2010 г.

Как узнать насколько две строки похожи?

Для того, что бы узнать на сколько похожи две строки, можно использовать алгоритм - "расстояние Левенштейна". О нем я сегодня узнал от Алены C++.

Я же хочу предложить вариант реализации на языке программирования php:

function levenshtein_distance($s, $t)
{
 $n = strlen($s); 
 $m = strlen($t); 
 
    /* if used russian or other UTF-8 characters 
    change above code with this 
 $n = mb_strlen($s, 'UTF-8'); 
 $m = mb_strlen($t, 'UTF-8');
 */
 
 if ($n == 0) 
  return $m;
 if ($m == 0) 
  return $n;
  
 $d = array();
 
 for ($i = 0; $i <= $n; $i++) {
  $d[$i][0] = $i;
 }
 
 for ($j = 0; $j <= $m; $j++) {
  $d[0][$j] = $j;
 }
 
 for ($i = 1; $i <= $n; $i++) {
  $sI = $s[$i - 1];
  for ($j = 1; $j <= $m; $j++) {
   $tJ = $t[$j - 1];
   $cost = ($tJ == $sI) ? 0 : 1;
   $d[$i][$j] = min(
    $d[$i - 1][$j] + 1, 
    $d[$i][$j - 1] + 1 , 
    $d[$i - 1][$j - 1] + $cost);
  }
 }

 return $d[$n][$m];
}

echo levenshtein_distance('gumbol', 'gambo');

В результате мы увидим "2", так как необходимо заменить u на a и удалить l.

Комментариев нет:

Отправить комментарий