Sounds Like a Duck

I’ve been doing a lot of reading lately about soundex and other algorithms for matching words. In my iOS application, I have a simple alliteration function, basically just looking for matching starting characters. in the next version, I want to expand the alliteration and have a sounds like function.

Soundex is a nice simple function, primarily designed to work with surnames, that converts a name to a starting consonant sound and digits representing the remaining sounds. It’s a coding system that’s been around since the early 1900’s. It works, and it’s easy to use, but it is limited to english.

So, I setup a simple php test script to look at soundex results. The script creates a soundex code of the input, takes the first three characters of the soudex code and returns the results of an sql call:

$soundex = soundex($soundslike);
<pre><code>$soundex = soundex($soundslike);
$soundexPrefix = substr($soundex, 0, 3);
$sql = "SELECT name from names WHERE SOUNDEX(name) LIKE '$soundexPrefix%' order by rand() limit 10";

This works ok. Here are a couple of examples:

input      name            sybcount   soundex
<pre><code>input      name            sybcount   soundex
Bill       Bloi            1          B400
Bill       Biley           2          B400
Bill       Ballou          2          B400
Bill       Boele           1          B400
Bill       Balow           2          B400
Bill       Builly          3          B400
Bill       Billiou         2          B400
Bill       Bayol           2          B400
Bill       Bella           2          B400
Bill       Ballie          2          B400

input      name            sybcount   soundex
Louis      Laux            1          L200
Louis      Laske           1          L200
Louis      Leigha          2          L200
Louis      Luis            2          L200
Louis      Lasse           1          L200
Louis      Lucija          3          L220
Louis      Lezo            2          L200
Louis      Laessig         2          L220
Louis      Luiz            2          L200
Louis      Lucek           2          L220

Without prefixing the soundex return, the results are more narrow, for example:

input      name            sybcount   soundex
<pre><code>input      name            sybcount   soundex
William    Willaim         2          W450
William    Wollin          2          W450
William    Willman         2          W455
William    Wallin          2          W450
William    Wahlman         2          W455
William    Whelan          2          W450
William    Wallman         2          W455
William    William*        3          W450
William    Woolen          2          W450
William    Willam          2          W450

sybcount is a rough function I’m working on to count syllables in the name returned. Since I’m looking to do sounds like for full names, I’m going to expand the script a bit to get given and surnames and return full name. For sounds like, I want the user to have the flexibility of options like:

    • Bob Newhart
    • % New%
    • Bob New%

In this case, using % as a wild card. The first choice, the first name would sound like Bob, the last would sound like Newhart.

Looking at option 1, if I set no prefix for the soundex, meaning use the full soundex code, Bob returns nothing. If I set the prefix to 1, then it returns anything that starts with B or N. The results are not impressive:

soundslike: Bob, Newhart
<pre><code>soundslike: Bob, Newhart
soundex, B, N
SELECT name from names WHERE givenname = 1 and SOUNDEX(name) LIKE 'B%' order by rand() limit 10
SELECT name from names WHERE surname = 1 and SOUNDEX(name) LIKE 'N%' order by rand() limit 10

inputs               name                      sybcount
Bob Newhart          Babette Nicolette         6
Bob Newhart          Bibi Nowland              4
Bob Newhart          Bijan Nuffer              4
Bob Newhart          Breanne Nasri             4
Bob Newhart          Bahnbeamter Nedina        6
Bob Newhart          Baldassare Nagengast      7
Bob Newhart          Beggue Nolette            4
Bob Newhart          Baptiste Nabavian         7
Bob Newhart          Byron Najera              5
Bob Newhart          Barnardus Nickless        5

No prefix works with some names, but still, the results are not great:

soundslike: Jimmy, Carter
<pre><code>soundslike: Jimmy, Carter
soundex, J500, C636
SELECT name from names WHERE givenname = 1 and SOUNDEX(name) LIKE 'J500%' order by rand() limit 10
 SELECT name from names WHERE surname = 1 and SOUNDEX(name) LIKE 'C636%' order by rand() limit 10

inputs               name                      sybcount
Jimmy Carter         Joannah Cryder            4
Jimmy Carter         Jenna Courtright          4
Jimmy Carter         Jemina Carrethers         6
Jimmy Carter         Jamey Caruthers           5
Jimmy Carter         Jana Carrothers           5
Jimmy Carter         Jannie Crowther           4
Jimmy Carter         Jane Cordeiro             5
Jimmy Carter         Janie Carruthers          5
Jimmy Carter         Jesenia Cardeiro          7
Jimmy Carter         Jasna Cardera             5

Metaphone is a popular sounds like alternative. So, again, I want to convert the incoming sounds like names into metaphone code, the restrict the result set to names that match part of the code.

$metaphonef = metaphone($soundslikef, $prefix);

Metaphone with an unlimited phonemes returned better results for the Bob Newhart use case:

soundslike: Bob, Newhart
<pre><code>soundslike: Bob, Newhart
metaphone: BB, NHRT

inputs               name                      sybcount
Bob Newhart          Bibi Neuhart              4
Bob Newhart          Baby Neyhart              4
Bob Newhart          Bebe Newhard              4
Bob Newhart          Bobbie Nihart             4
Bob Newhart          Bobbi Newhart             4
Bob Newhart           Neihart                  2
Bob Newhart                                    0
Bob Newhart                                    0
Bob Newhart                                    0
Bob Newhart                                    0

If I cut the phonemes down to 2, the results are more promising:

soundslike: Bob, Newhart
<pre><code>soundslike: Bob, Newhart
metaphone: BB, NH

inputs               name                      sybcount
Bob Newhart          Babette Nyhan             5
Bob Newhart          Bobbye Nihart             4
Bob Newhart          Bobbie Nyhus              4
Bob Newhart          Babatunde Neihart         6
Bob Newhart          Bibi Nhep                 3
Bob Newhart          Bebe Newhook              4
Bob Newhart          Bobak Newhall             4
Bob Newhart          Bobbi Neehouse            4
Bob Newhart          Boban Nohe                3
Bob Newhart          Babak Newham              4

Many folks suggest a combination of Metaphone and Levenshtein distance calculations. Use the Levenshtein distance to set an error margin. Levenshtein distance calculates the variance between two strings. So two strings with a distance of 1, there is one variance between the two. So, the idea is to calculate the Metaphone code for the input variable, and each name, then determine a percent difference to look for matches. This is an interesting idea, and probably more useful for narrowing searches, or fuzzy input matches, but it is not yielding good results in this case.

Looks like the Metaphone search with no limit is giving me the best results. Here are a couple of name examples:

soundslike: Jimmy, Carter
<pre><code>soundslike: Jimmy, Carter
Metaphone
metaphone: JM, KRTR

inputs               name                      sybcount
Jimmy Carter         Jaimee Grider             4
Jimmy Carter         Gema Graeter              4
Jimmy Carter         Jomo Kreider              4
Jimmy Carter         Jaymie Gorter             4
Jimmy Carter         Jem Greider               3
Jimmy Carter         Jamee Cardeiro            5
Jimmy Carter         Jimmie Cordrey            4
Jimmy Carter         Jammie Credeur            4
Jimmy Carter         Jamey Cartier             4
Jimmy Carter         Jimmy Crader              4

Metaphone Levenshtein Distance
metaphone: JM, KRTR

inputs               name                      sybcount
Jimmy Carter         Gentien Grentmesnil       5
Jimmy Carter         Shaunta Aristizabal       7
Jimmy Carter         Ivarson Brightharp        5
Jimmy Carter         Ersan Hilderbrandt        5
Jimmy Carter         Thiphaine Macnaughton     6
Jimmy Carter         Katheleen Policastri      7
Jimmy Carter         Dorothee Vonderhaar       7
Jimmy Carter         Rebeccah                  3
Jimmy Carter         Ederson                   3
Jimmy Carter         Svaer                     1

Soundex
soundex, J500, C636

inputs               name                      sybcount
Jimmy Carter         Jazmine Cryderman         6
Jimmy Carter         Jaymie Czartoryski        6
Jimmy Carter         Jonn Cardero              4
Jimmy Carter         Jón Cordray              2
Jimmy Carter         Jannine Charter           5
Jimmy Carter         Jane Crouter              4
Jimmy Carter         Jesenia Cruthird          6
Jimmy Carter         Joon-ho Cortright         4
Jimmy Carter         Jimmy Courter             4
Jimmy Carter         Joannin Carrethers        5

soundslike: Mary, Sue
Metaphone
metaphone: MR, S

inputs               name                      sybcount
Mary Sue             Meir Sooy                 3
Mary Sue             Meri Zou                  3
Mary Sue             Miri Sy                   3
Mary Sue             Mr Sey                    1
Mary Sue             Mary Hsu                  3
Mary Sue             Maura Zeh                 3
Mary Sue             Merri Su                  3
Mary Sue             Maihri Hsieh              3
Mary Sue             Mairi Sou                 3
Mary Sue             Mária Sea                3

Metaphone Levenshtein Distance
metaphone: MR, S

inputs               name                      sybcount
Mary Sue             Jerimas Gabrielsen        6
Mary Sue             Evariste Nett             5
Mary Sue             Norfolkeast Patsula       6
Mary Sue             Rebecka Suggs             4
Mary Sue             Denisha Klemetz           5
Mary Sue             Tressie Halgas            4
Mary Sue             Carita Robida             6
Mary Sue             Wesley Mish               3
Mary Sue             Cezary Gosson             5
Mary Sue             Hupert Puelo              4

Soundex
soundex, M600, S000

inputs               name                      sybcount
Mary Sue             Muammer Saka              5
Mary Sue             Munir Shyu                3
Mary Sue             Marya Secky               4
Mary Sue             Maira Schuh               3
Mary Sue             Mireya Saia               5
Mary Sue             Meri Sheeks               3
Mary Sue             Mara Sow                  3
Mary Sue             Mhairi Schewe             3
Mary Sue             Munira Schei              4
Mary Sue             Maria Sockey              5

Ok. Decision made. I’m going with the simple Metaphone approach. On the server side of the application, this should be pretty easy, php has a built in metaphone() function. However, Object-c will be a little more challenging. The algorithm for the metaphone and double metaphone are publicly available, so I’ll probably just end up writing my own function.

One thing I need to sleep on, should I pre calculate all of the metaphone codes and make a data structure change to accommodate the new column. This would allow me to greatly reduce the time to find matches. Before making the data structure change, I will probably mock it up and see if it will work as expected.

That should be enough nerd talk for today.

Enjoy!

Similar Posts

Return to blog