Jaro Winkler algoritması yazım hatası olsa bile doğru sonuca erişme

• Rıza Güngör
• Tarih : 2023-07-22
• Kategori : Web Programlama

Arama motorları bizi nasıl anlıyor yanlış yazsak da doğru sonuca nasıl erişebiliyor? Bir programcının mutlaka ihtiyaç duyacağı bir algoritma. Bu algoritma yazım hatalarına rağman doğru sonuca erişmenizi sağlıyor. Söz konusu algoritmanın adı Jaro Winkler. Algoritma 1990 da William E. Winkler tarafından Jaro mesafe metriği kullanılarak geliştirildi.

Ben bunu ilk olarak formlara isimlerini yanlış kodlayan öğrencileri tespit etmek için kullanmıştım. Bir zamanlar lys de açık uçlu sorular vardı bunun tespitinde de kullanmıştım. Genel kullanımda nasıl işinize yarar? Varsayalım Birçok müşteriniz var ve bunların bir kısmı yabancı uyruklu. Veri tabanından veriyi tam eşleşme ile aradağınız için bunu bulmanız çok zor olabilir. Örneğin Mpabpe olarak aramanız gereken veri futbolcu isminden yanılarak Mbappe olarak arıyorsunuz. ve bulamıyorsunuz. Bu çok normal çünkü daha 2. harfte patladınız. Ama bunu Jaro Winkler algoritmasından geçirdiğinizde size binlerce kişi ismi arasından 0.96 eşleşme ile bunu bulacaktır. 1e 1 eşleşmeye ne kadar yakın bir sonuç öyle değil mi? Bu arama yapan kullanıcıyı fazlasıyla tatmin edecektir

Algoritmanın php fonksiyon hali aşağıdadır.

$hedef="Mpabpe"; $kaynak="Mbappe";

Jaro($hedef, $kaynak); 

// Şeklinde kullanabilirsiniz.

 

function getCommonCharacters( $string1, $string2, $allowedDistance ){

$str1_len = strlen($string1);
$str2_len = strlen($string2);
$temp_string2 = $string2;

$commonCharacters='';

for( $i=0; $i < $str1_len; $i++){

$noMatch = True;

// compare if char does match inside given allowedDistance
// and if it does add it to commonCharacters
for( $j= max( 0, $i-$allowedDistance ); $noMatch && $j < min( $i + $allowedDistance + 1, $str2_len ); $j++){
if( $temp_string2[$j] == $string1[$i] ){
$noMatch = False;

$commonCharacters .= $string1[$i];

$temp_string2[$j] = '';
}
}
}

return $commonCharacters;
}

function Jaro( $string1, $string2 ){

$str1_len = strlen( $string1 );
$str2_len = strlen( $string2 );

// theoretical distance
$distance = (int) floor(min( $str1_len, $str2_len ) / 2.0);

// get common characters
$commons1 = getCommonCharacters( $string1, $string2, $distance );
$commons2 = getCommonCharacters( $string2, $string1, $distance );

if( ($commons1_len = strlen( $commons1 )) == 0) return 0;
if( ($commons2_len = strlen( $commons2 )) == 0) return 0;

// calculate transpositions
$transpositions = 0;
$upperBound = min( $commons1_len, $commons2_len );
for( $i = 0; $i < $upperBound; $i++){
if( $commons1[$i] != $commons2[$i] ) $transpositions++;
}
$transpositions /= 2.0;

// return the Jaro distance
return ($commons1_len/($str1_len) + $commons2_len/($str2_len) + ($commons1_len - $transpositions)/($commons1_len)) / 3.0;

}

function getPrefixLength( $string1, $string2, $MINPREFIXLENGTH = 4 ){

$n = min( array( $MINPREFIXLENGTH, strlen($string1), strlen($string2) ) );

for($i = 0; $i < $n; $i++){
if( $string1[$i] != $string2[$i] ){
// return index of first occurrence of different characters
return $i;
}
}

// first n characters are the same
return $n;
}

function JaroWinkler($string1, $string2, $PREFIXSCALE = 0.1 ){

$JaroDistance = Jaro( $string1, $string2 );

$prefixLength = getPrefixLength( $string1, $string2 );

return $JaroDistance + $prefixLength * $PREFIXSCALE * (1.0 - $JaroDistance);
}