Super Fast and Accurate string distance algorithm: Sift3 24 comments

Update: the Sift algorithm is now on Codeplex.

A while ago I wrote an entry here about Sift2, an improvement of Sift, the original and silly string distance algorithm. Now I am publishing Sift3, which is way more accurate and even simpler as an algorithm.

I found out that my algorithm is part of a class of algorithms that solve the Longest Common Substring problem, therefore I calculated the LCS, not the distance, then the distance from the LCS. The result is way more robust, easy to understand and closer to the Levenshtein algorithm both on random strings and user databases. Not to mention that there is no goto in this one.

BTW, if you are looking for an algorithm that detects switched words, this is not it :) This just looks for typos and small regional differences between the strings. I mean, you could normalize the strings, so that words are ordered by some mechanism, then it would work because the words wouldn't be switched :)

I promise to work on a word switching algorithm, but not in the near future.
Without further due, here is the code:

The C# code is a method in an object that has a private member maxOffset. As in Sift2 maxOffset should be around 5 and it represents the range in which to try to find a missing character.

        public float Distance(string s1, string s2, int maxOffset)

        {

            if (String.IsNullOrEmpty(s1))

                return

                    String.IsNullOrEmpty(s2) ? 0 : s2.Length;

            if (String.IsNullOrEmpty(s2))

                return s1.Length;

            int c = 0;

            int offset1 = 0;

            int offset2 = 0;

            int lcs = 0;

            while ((c + offset1 < s1.Length)

                   && (c + offset2 < s2.Length))

            {

                if (s1[c + offset1] == s2[c + offset2]) lcs++;

                else

                {

                    offset1 = 0;

                    offset2 = 0;

                    for (int i = 0; i < maxOffset; i++)

                    {

                        if ((c + i < s1.Length)

                            && (s1[c + i] == s2[c]))

                        {

                            offset1 = i;

                            break;

                        }

                        if ((c + i < s2.Length)

                            && (s1[c] == s2[c + i]))

                        {

                            offset2 = i;

                            break;

                        }

                    }

                }

                c++;

            }

            return (s1.Length + s2.Length)/2 - lcs;

        }

And here is the T-Sql code. This version is actually an improvement of my original source, gracefully provided by Todd Wolf:

CREATE FUNCTION [DBO].[SIFT3DISTANCE2] 
    (@s1      NVARCHAR(3999), 
       @s2      NVARCHAR(3999), 
       @maxOffset INT) 
RETURNS FLOAT 
AS 
    BEGIN 
     
   DECLARE    @s1LEN INT, 
     @s2LEN INT 
      
   SELECT @s1LEN = LEN(ISNULL(@s1,'')), 
      @s2LEN = LEN(ISNULL(@s2,'')) 
      
   IF @s1LEN = 0 
       RETURN @s2LEN 
   ELSE 
       IF @s2LEN = 0 
      RETURN @s1LEN 
       
   IF ISNULL(@maxOffset,0) = 0 
       SET @maxOffset = 5 
   
   DECLARE    @currPos    INT, 
     @matchCnt INT, 
     @wrkPos     INT, 
   
     @s1Offset INT, 
     @s1Char     VARCHAR, 
     @s1Pos   INT, 
     @s1Dist     INT, 
   
     @s2Offset INT, 
     @s2Char     VARCHAR, 
     @s2Pos   INT, 
     @s2Dist     INT 
   
   SELECT @s1Offset = 0, 
      @s2Offset = 0, 
      @matchCnt = 0, 
      @currPos = 0 
     
   WHILE (@currPos + @s1Offset < @s1LEN 
      AND @currPos + @s2Offset < @s2LEN) 
       BEGIN 
      SET @wrkPos = @currPos + 1 
       
      IF (SUBSTRING(@s1,@wrkPos + @s1Offset,1) =
          SUBSTRING(@s2,@wrkPos + @s2Offset,1)) 
     SET @matchCnt = @matchCnt + 1 
      ELSE 
     BEGIN 
    SET @s1Offset = 0 
     
    SET @s2Offset = 0 
       
    SELECT @s1Char = SUBSTRING(@s1,@wrkPos,1), 
       @s2Char = SUBSTRING(@s2,@wrkPos,1) 
     
    SELECT @s1Pos = CHARINDEX(@s2Char,@s1,@wrkPos) - 1, 
       @s2Pos = CHARINDEX(@s1Char,@s2,@wrkPos) - 1 
    
    SELECT @s1Dist = @s1Pos - @currPos, 
       @s2Dist = @s2Pos - @currPos 
       
    IF (@s1Pos > 0 
       AND (@s1Dist <= @s2Dist 
    OR @s2Pos < 1) 
       AND @s1Dist < @MaxOffset) 
   SET @s1Offset = (@s1Pos - @wrkPos) + 1 
    ELSE 
   IF (@s2Pos > 0 
      AND (@s2Dist < @s1Dist 
   OR @s1Pos < 1) 
      AND @s2Dist < @MaxOffset) 
       SET @s2Offset = (@s2Pos - @wrkPos) + 1 
     END 
      
      SET @currPos = @currPos + 1 
       END 
   
   RETURN (@s1LEN + @s2LEN) / 2.0 - @matchCnt 
    END 
 
 

It doesn't give the same exact results as my own code, yet the result is close enough and the speed is about 20% higher.

Thanks all for your comments and I look forward to more. Just tell me it worked or not and, most important, why. Good luck!