PHP - smart, error tolerating string comparison

Question

Hello,

I'm looking either for routine or way to look for error tolerating string comparison.

Let's say, we have test string Čakánka - yes, it contains CE characters.

Now, I want to accept any of following strings as OK:

• cakanka
• cákanká
• ČaKaNKA
• CAKANKA
• CAAKNKA
• CKAANKA
• cakakNa

The problem is, that I often switch letters in word, and I want to minimize user's frustration with not being able (i.e. you're in rush) to write one word right.

So, I know how to make ci comparison (just make it lowercase :]), I can delete CE characters, I just can't wrap my head around tolerating few switched characters.

Also, you often put one character not only in wrong place (character=>cahracter), but sometimes shift it by multiple places (character=>carahcter), just because one finger was lazy during writing.

Thank you :]

Answer 1

Spelling checkers do something like fuzzy string comparison. Perhaps you can adapt an algorithm based on that reference. Or grab the spell checker guessing code from an open source project like Firefox.

Answer 2

Not sure (especially about the accents / special characters stuff, which you might have to deal with first), but for characters that are in the wrong place or missing, the levenshtein function, that calculates Levenshtein distance between two strings, might help you (quoting) :

int levenshtein  ( string $str1  , string $str2  )
int levenshtein  ( string $str1  , string $str2  , int $cost_ins  , int $cost_rep  , int $cost_del  )

The Levenshtein distance is defined as the minimal number of characters you have to replace, insert or delete to transform str1 into str2

Other possibly useful functions could be soundex, similar_text, or metaphone.

And some of the user notes on the manual pages of those functions, especially the manual page of levenshtein might bring you some useful stuff too ;-)

Answer 3

You could transliterate the words to latin characters and use a phonetic algorithm like Soundex to get the essence from your word and compare it to the ones you have. In your case that would be C252 for all of your words except the last one that is C250.

---

Edit    The problem with comparative functions like levenshtein or similar_text is that you need to call them for each pair of input value and possible matching value. That means if you have a database with 1 million entries you will need to call these functions 1 million times.

But functions like soundex or metaphone, that calculate some kind of digest, can help to reduce the number of actual comparisons. If you store the soundex or metaphone value for each known word in your database, you can reduce the number of possible matches very quickly. Later, when the set of possible matching value is reduced, then you can use the comparative functions to get the best match.

Here’s an example:

// building the index that represents your database
$knownWords = array('Čakánka', 'Cakaka');
$index = array();
foreach ($knownWords as $key => $word) {
    $code = soundex(iconv('utf-8', 'us-ascii//TRANSLIT', $word));
    if (!isset($index[$code])) {
        $index[$code] = array();
    }
    $index[$code][] = $key;
}

// test words
$testWords = array('cakanka', 'cákanká', 'ČaKaNKA', 'CAKANKA', 'CAAKNKA', 'CKAANKA', 'cakakNa');
echo '<ul>';
foreach ($testWords as $word) {
    $code = soundex(iconv('utf-8', 'us-ascii//TRANSLIT', $word));
    if (isset($index[$code])) {
        echo '<li> '.$word.' is similar to: ';
        $matches = array();
        foreach ($index[$code] as $key) {
            similar_text(strtolower($word), strtolower($knownWords[$key]), $percentage);
            $matches[$knownWords[$key]] = $percentage;
        }
        arsort($matches);
        echo '<ul>';
        foreach ($matches as $match => $percentage) {
            echo '<li>'.$match.' ('.$percentage.'%)</li>';
        }
        echo '</ul></li>';
    } else {
        echo '<li>no match found for '.$word.'</li>';
    }
}
echo '</ul>';