Easy Fuzzy matching using PHP

Posted on 2011-06-16 10:19:03
by Geert Vandeweyer

Loading Content

Easy Fuzzy matching using PHP

Posted on 2011-06-16 10:19:03
by Geert Vandeweyer

Fuzzy matching is a very powerfull way of correcting for user input, for example if you need to match a user provided keyword against options in a database. In this particular case you can use the SOUNDEX functions of mysql, but they do have significant shortcomings like the inability to discriminate long strings. 

Another way is to use levenshtein distance. This builtin function estimates the minimal number of substitutions needed to go from string A to string B.  Although not very fast, it can be used as an easy way to allow fuzzy matching, without installing third-party plugins or packages. 

Code: 

include the following code in your php program: 

function fuzzy_match($query,$target,$distance) {
         ##  set max substitution steps if set to 0
         if ($distance == 0) {
                 $length = strlen($query);
                 if ($length > 10) {
                     $distance = 4;
                 }
                 elseif ($length > 6) {
                     $distance = 3;
                 }
                 else {
                     $distance = 2;
                 }
         }
         $lev = levenshtein(strtolower($query), strtolower($target));
         if ($lev <= $distance) {
            return array('match' => 1, 'distance' => $lev, 'max_distance' => $distance);
         }
         else {
            return array('match' => 0, 'distance' => $lev, 'max_distance' => $distance);
         }
}

Usage:

The function returns an array containing the result, distance and max_allowed_distance:

<?php

## value to test against database
$provided = $_POST['provided'];

## check against database
$match = '';
$query = mysql_query("SELECT names FROM exampletable");
while ($row = mysql_fetch_array($query))
     $dbname = $row['names'];
     ## test with maximal distance of 3
     $result = fuzzy_match($provided,$dbname,3);
     if ($result['match'] == 1) {
           $match = $dbname;
           break;
     }
}
if ($match == '') {
   echo "$provided does not match a name from the database";
}

?>

fuzzy match, levenshtein, PHP, Searching