PHP: using levenshtein distance to match words

I been reading and testing some examples in php levenshtein. Comparing $input to $words outputs comparing

$input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato','hw are you');

outputs

Input word: hw r u my dear angel
Did you mean: hw are you?

comparing, remove hw are you in the array.

$input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato');

in the second removing hw are you in the array outputs

Input word: hw r u my dear angel
Did you mean: orange?

where in similar_text()

 echo '<br/>how are you:'.similar_text($input,'how are you');
    echo '<br/>orange:'.similar_text($input,'orange');
    echo '<br/>hw are you:'.similar_text($input,'hw are you');

how are you:6
orange:5
hw are you:6

on second compare why does it output orange when how are you has also 6 similar text like hw are you? Is there any way to improve or better method about this?ALso im saving all the posible input on the database. should i query it and store in array then use foreach to get levenshtein distance? but that would be slow if a have millions.

CODE

  <?php
    // input misspelled word
    $input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato','hw are you');


    // no shortest distance found, yet
    $shortest = -1;

    $closest = closest($input,$words,$shortest);


    echo "Input word: $input<br/>";
    if ($shortest == 0) {
        echo "Exact match found: $closest\n";
    } else {
        echo "Did you mean: $closest?\n";
    }
    echo '<br/><br/>';

    $shortest = -1;
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato');
    $closest = closest($input,$words,$shortest);
    echo "Input word: $input<br/>";
    if ($shortest == 0) {
        echo "Exact match found: $closest\n";
    } else {
        echo "Did you mean: $closest?\n";
    }

    echo '<br/><br/>';
    echo 'Similar text';
    echo '<br/>how are you:'.similar_text($input,'how are you');
    echo '<br/>orange:'.similar_text($input,'orange');
    echo '<br/>hw are you:'.similar_text($input,'hw are you');



    function closest($input,$words,&$shortest){
        // loop through words to find the closest
    foreach ($words as $word) {

        // calculate the distance between the input word,
        // and the current word
        $lev = levenshtein($input, $word);

        // check for an exact match
        if ($lev == 0) {

            // closest word is this one (exact match)
            $closest = $word;
            $shortest = 0;

            // break out of the loop; we've found an exact match
            break;
        }

        // if this distance is less than the next found shortest
        // distance, OR if a next shortest word has not yet been found
        if ($lev <= $shortest || $shortest < 0) {
            // set the closest match, and shortest distance
            $closest  = $word;
            $shortest = $lev;
        }


    }
    return $closest;
    }
    ?>

Solution

First of all it doesn't matter what outputs similar_text(), because it uses another algorithm to calculate similarity between strings.

Lets try to understand why levenstein() thinks, that hw r u my dear ange is closer to orange than to 'how are you. Wikipedia has a good definition of what Levenstein distance is.

Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other.

Now lets count how many edits we have to do to change hw r u my dear angel into orange.

hw r u my dear angel → hw r u my dear ange (deletion of last character)
hw r u my dear ange → hw r u my dearange (deletion of last space)
hw r u my dearange → arange (deletion of first 12 characters)
arange → orange (substitution of a with o)

So it takes 1 + 1 + 12 + 1 = 15 edits total to change hw r u my dear angel into orange.

And here is transformation of hw r u my dear angel into how are you.

hw r u my dear angel → how r u my dear angel (insertion of o character)
how r u my dear angel → how dear angel (deletion of 7 characters)
how dear angel → how ar angel (deletion of 2 characters)
how ar angel → how are angel (insertion of e character)
how are angel → how are ang (deletion of last 2 characters)
how are ang → how are you (substition of last 3 characters)

Total 1 + 7 + 2 + 1 + 5 = 16 edits. So as you can see in terms of Levinstein distance orange is closer to hw r u my dear angel ;-)