Optimal way to find similar value from a large table

Question

I have a database where i am storing more than 1000000 names in mysql. Now the task of my application is a bit typical. I not only searches for names in the database,but also finds similar names. Suppose the name is entered as christian, then the application will show suggested names like christine, chris etc. What is the optimal way to do this, without using the like clause. The suggestions will be only on the changes in the last part of the name.

Answer 1

If you want also similar names (by sound) something like SOUNDEX() could help: http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

Otherwise … LIKE 'chri%' seems for me not a bad idea?

If you really want just the first characters without LIKE you can use SUBSTRING().

Answer 2

You could use php's metaphone() function to generate the metaphone-code for each name and store them along with the names.

<?php
print "chris" . "\t" . metaphone("chris") . "\n";
print "christian" . "\t" . metaphone("christian") . "\n";
print "christine" . "\t" . metaphone("christine") . "\n";

# prints:
# chris      XRS
# christine  XRSTN
# christian  XRSXN

You can then use a levenshtein distance algorithm (either in php [http://php.net/manual/en/function.levenshtein.php] or mysql [http://www.artfulsoftware.com/infotree/queries.php#552]) to calculate the distance between the metacodes. In my test below a distance of 2 or less seemed to indicate the level of similarity that you are seeking.

<?php
$names = array(
        array('mike',metaphone('mike')),
        array('chris',metaphone('chris')),
        array('chrstian',metaphone('christian')),
        array('christine',metaphone('christine')),
        array('michelle',metaphone('chris')),
        array('mick',metaphone('mick')),
        array('john',metaphone('john')),
        array('joseph',metaphone('joseph'))
);

foreach ($names as $name) {
        _compare($name);
}

function _compare($n) {
        global $names;
        $name = $n[0];
        $meta = $n[1];

        foreach ($names as $cname) {
                printf("The distance between $name and {$cname[0]} is %d\n",                          
                  levenshtein($meta, $cname[1]));
        }
}