When I wrote "Soundex - Experiments with SQLCLR" the resulting forum posts drew my attention to a number of weaknesses with the Soundex algorithm.

Soundex as implemented in SQL Server has around 7,000 possible values where as the English language has over 1 million words.  Clearly there is huge scope for false matches as many words can generate the same Soundex code.  In addition it makes no concessions to the fact that combinations of letters can make different sounds so will miss occurrences such as "Philip" and "Fillip".

Clearly something better than Soundex is required and fortunately there are quite a few good resources to look at.

• Nikita's blog lists a number of alternative phonetic algorithms
• The Apache Commons library contains actual Java implementations of the algorithms and adds ColognePhonetic
• Utilitymill.com allows you to test words against Soundex and NYSIIS and also take a look at the source code.
• Rosettacode.org provides many programming language implementations of common algorithms.

I decided to see if I could extend my "SoundexLong" function to take these into account.  I also wanted to see if continuing the Test Driven Development approach helped or hindered further development.

The first step in doing so was to perform some basic analysis into the way that these algorithms work in order to understand the scope of the changes that would have to be made.

Basic analysis of the algorithms

A good starting point is to understand what algorithms are available and what they are used for.  Those of interest are shown in the table below:-

I also characterised the types of transformations that each algorithm supported.  Again these are summarised in the table below:-

The right-most column indicates that the number of substituted characters can exceed the number of characters being replaced.  This is important as in my original article I looked to use a single character array iterating through deciding whether to ignore or overwrite characters as appropriate.  An example of which is shown below.

Daitch-Mokotoff, ColognePhonetic and the Metaphone algorithms can replace a single 'X' with two characters.  If we were to use a single character array then we would risk prematurely overwriting characters rather than considering them appropriately.

This means that we are certainly going to need to have a separate input array from an output array.

Design Decisions

The original function from my "Soundex - Experiments with SQLCLR" article had the following characteristics:

• Accepted a single argument, a string
• Converted the input argument to upper case effectively making the function case insensitive
• Returned a single string value
• Named the function SoundexLong

If I want to cater for a range of phonetic algorithms then I face a number of choices.

• Do I refactor my original code or build a new function that duplicates the functionality of the existing algorithm?
• Do I produce multiple separate functions thereby duplicating code or a single function with a parameter to indicate what I want the function to do?

All the decisions have undesirable implications either from a code complexity, code duplication or alteration of established code perspective.  I am going to do the following:

• My original SoundexLong will remain as an immutable set of code
• I will have a single "LongPhonetic" function rather than multiple functions as I have learnt that end users lean towards simplicity and ease of use.
• I am going to duplicate my SoundexLong code to form the starting point for LongPhonetic and refactor it to achieve the desired result

It is quite possible that these decisions will return to haunt me, however, we have to start somewhere.   Attempt a course of action but do so in such a way that identifies as quickly as possible if it is a dead end. This is the principle of "failing fast" and allows us to develop a strategy for failure that removes fear and doubt.  Such a strategy gives us a number of advantages:

• Failure has to be viewed as a learning experience.  A success is great but we learn more from our failures.
• Avoids analysis paralysis.  Fear and doubt can lead to analysis paralysis in an attempt to avoid failure
• Allows us to take less timid steps and therefore open up potentially greater rewards.

Step One - Addressing some technical debt

jimbobmcgee gave constructive feedback to my original article pointing out that my implementation of an IsLetter() function was unnecessary as a char object has an inbuilt IsLetter() function. To correct this I simply changed both occurences of IsLetter in my code with char.IsLetter

        if(!char.IsLetter(inputArray[0]))

        if (char.IsLetter(inputArray[currentCharacterPosition]))

Step Two - Refactoring for an outputArray

Given that Daitch-Mokotoff and Metaphone necessitate a 2nd array the next step was to change my code to read from the inputArray[] and write to the outputArray[]. At this stage I don't need to know how long I to make the outputArray as I am simply refactoring my code.  Making it the same length as the inputArray[] will suffice.

          char[] inputArray = InputString.ToUpper().ToCharArray();
          char[] outputArray = new String(' ', inputArray.Length).ToCharArray();

        return new string(inputArray).Trim();

        return new string(outputArray).Trim();

It turns out we need a bit of code to cater for the first character of the input argument being a letter.

        if (!char.IsLetter(inputArray[0]))
        {
            inputArray[0] = ' ';
        }
        else
        {
            outputArray[0] = inputArray[0];
        }

Valid criticism of Test Driven Development

• Answer the question "What is the acceptance criteria that would demonstrate that this piece of functionality will deliver what it should"?  
• Develop a test that expresses that acceptance criteria and will only pass if your code meets that criteria.  
• Write the code to pass the test
• Refactor mercilessly

Frameworks such as Cucumber with its Gherkin language address these points because the common language in which tests are defined is separate from the implementation of the items that for which the tests apply.  By having the separation between the language defining the tests and the language implementing the tests it means that if you took the decision to replatform your application from one language to another all your tests would remain valid for your new application.

Step Three - Refactoring my function to accept an additional argument

So far my LongPhonetic() function (refactored from SoundexLong in my original article) accepts a single string argument.  All I am going to do at this stage is change the signature of my function and refactor all the tests so they are proven to work.  I am NOT going to implement the selection of phonetic algorithms at this stage.  

    [Microsoft.SqlServer.Server.SqlFunction (IsDeterministic=true,IsPrecise=true)]
    public static SqlString LongPhonetic(short PhoneticType,String InputString)

        #region LongPhonetic() tests
        [TestMethod]
        public void StartUpTest()
        {
            Assert.AreEqual("D", Phonetics.LongPhonetic(0, "D"));
       }
        [TestMethod]
        ..... 
       #endregion

using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
delegate Char PhoneticAlgorithm(Char a);
public partial class Phonetics
{
    [Microsoft.SqlServer.Server.SqlFunction(IsDeterministic=true,IsPrecise=true)]

    public static SqlString LongPhonetic(short PhoneticType,String InputString)
    {
        PhoneticAlgorithm phoneticAlgorithm;
        switch (PhoneticType)
        {
            case 0:
                phoneticAlgorithm = new PhoneticAlgorithm(SoundexChar);
                break;
            default:
                phoneticAlgorithm = new PhoneticAlgorithm(SoundexChar);
                PhoneticType = 0;
                break;
        }

        #region LongPhonetic() tests
        [TestMethod]
        public void StartUpTest()
        {
            Assert.AreEqual("D", Phonetics.LongPhonetic(0, "D"));
            Assert.AreEqual("D", Phonetics.LongPhonetic(99, "D"));
       }
        [TestMethod]
        ..... 
       #endregion

            // If not a double occurrence of either characters or phonetic codes
            if (!((outputArray[validCharacterPosition] == inputArray[currentCharacterPosition]) ||
                outputArray[validCharacterPosition] == SoundexChar(inputArray[currentCharacterPosition])))
            {
                // Only increment the validCharacterPosition if it is not a vowel
                if (outputArray[validCharacterPosition] != '0')
                {
                    validCharacterPosition++;
                }
                outputArray[validCharacterPosition] = SoundexChar(inputArray[currentCharacterPosition]);
            }

            // If not a double occurrence of either characters or phonetic codes
            if (!((outputArray[validCharacterPosition] == inputArray[currentCharacterPosition]) ||
                outputArray[validCharacterPosition] == phoneticAlgorithm(inputArray[currentCharacterPosition])))
            {
                // Only increment the validCharacterPosition if it is not a vowel
                if (outputArray[validCharacterPosition] != '0')
                {
                    validCharacterPosition++;
                }
                outputArray[validCharacterPosition] = phoneticAlgorithm(inputArray[currentCharacterPosition]);
            }

        [TestMethod]
        public void LlangollenHeritageRailwayTest()
        {
            Assert.AreEqual("L5245 H632 R4", Phonetics.LongPhonetic(0, "llangollen heritage railway"));
            Assert.AreEqual("L8478 H964 R7", Phonetics.LongPhonetic(1, "llangollen heritage railway"));
            Assert.AreEqual("L5245 H632 R4", Phonetics.LongPhonetic(99, "llangollen heritage railway"));
        }

   /// <summary>
    /// For a given character return the raw refined soundex value.  If the argument is not a letter then return a space.
    /// </summary>
    /// <remarks>Refined Soundex works in the same way as normal Soundex but assigns digits from 1 to 9 as opposed to 1-6.</remarks>
    /// <param name="a">The character to be evalutated.</param>
    /// <returns></returns>
    private static Char RefinedSoundexChar(Char a)
    {
        switch (a)
        {
            case 'A':
            case 'E':
            case 'I':
            case 'O':
            case 'U':
            case 'W':
            case 'H':
            case 'Y':
                a = '0';
                break;
            case 'B':
            case 'P':
                a = '1';
                break;
            case 'F':
            case 'V':
                a = '2';
                break;
            case 'C':
            case 'K':
            case 'S':
                a = '3';
                break;
            case 'G':
            case 'J':
                a = '4';
                break;
            case 'Q':
            case 'X':
            case 'Z':
                a = '5';
                break;
            case 'D':
            case 'T':
                a = '6';
                break;
            case 'L':
                a = '7';
                break;
            case 'N':
            case 'M':
                a = '8';
                break;
            case 'R':
                a = '9';
                break;
            default:
                a = ' ';
                break;
        }
        return a;
    }

        PhoneticAlgorithm phoneticAlgorithm;
        switch (PhoneticType)
        {
            case 0:
                phoneticAlgorithm = new PhoneticAlgorithm(SoundexChar);
                break;
            case 1:
                phoneticAlgorithm = new PhoneticAlgorithm(RefinedSoundexChar);
                break;
            default:
                phoneticAlgorithm = new PhoneticAlgorithm(SoundexChar);
                PhoneticType = 0;
                break;
        }

        while (validCharacterPosition < currentCharacterPosition)
        {
            outputArray[validCharacterPosition++] = ' ';
        }

Step Eight - Further refactoring

while (currentCharacterPosition < inputArray.Length)
{
  ...
}

• validCharacterPosition
• currentCharacterPosition
• inputArray
• outputArray
• phoneticAlgoritm

while (currentCharacterPosition < inputArray.Length)
{
  SimpleSoundex(ref validCharacterPosition,ref currentCharacterPosition,inputArray,outputArray,phoneticAlgorithm);
  currentCharacterPosition++;
}

 
private static void SimpleSoundex(ref int validCharacterPosition, ref int currentCharacterPosition, char[] inputArray, char[] outputArray,PhoneticAlgorithm phoneticAlgorithm)
    {
        // If start of word
        if (outputArray[validCharacterPosition] == ' ')
        {
           ......
        }
    }
 

New algorithms, new Challenges 

One challenge we have to face when implementing the more complex phonetic algorithms is that we have to consider more character relationships.

• We need to be capable of matching a contiguous occurrence
• We need to determine the location of the occurrence (beginning of word, end of word, after vowel, relative to other combinations
• We need to be capable of deciding appropriate encoding for that occurence
• We need to consider cases such as the letter 'X' which encodes to two characters

Problems with the current approach

Looking at the code I have written it is becoming apparent that the approach I have used up to now is not suitable to meet the challenges for the more complex phonetic algorithms.

It is clear that a number of functions and methods are needed.  As the functions are static methods of a static class we cannot maintain state for our validCharacterPosition and currentCharacterPosition variables.  Although we are addressing this by passing the variables between the various functions by reference it will make messy and convoluted code if we continue to do so.

Clearly a more radical rethink is needed and that will be a subject for the next article.