Super fast string distance algorithm: Sift2

Update!! Read the Sift3 post. It is an even better algorithm.


A while ago I wrote a little algorithm that tried to cope with the large amount of time that the Levenshtein edit-distance algorithm took to compare two strings. It was a really funny algorithm, but it was fast enough to show me the similarity between strings that, after all, should have been either very similar or different.

Meanwhile I started thinking if I could improve on it. I was sure I could, because it wasn't very scientific, it was empirical. And finally I did it. This is the Sift2 algorithm, along with an SQL server function that can make one million string comparisons in 2.5 minutes. Compared with Levenshtein, Sift2 performs 10 to 25 times faster and it is four times faster than Sift.

The concept:

• Starting from the beginning of both words, compare the letters on the same position.
• If the same, move forward, else search the letter from the first word in the next maxOffset letters in the second word and viceversa.
• Offset the words according to the closest found letter, add 1 to distance
• Repeat until one of the words ends
• Add to the calculated distance half of the length of string remained unparsed from the other word

That's it! Here is the code:

C# Code (double click to show/hide)

public class StringSift2

{

 private int maxOffset;

 public StringSift2() : this(5) { }

 public StringSift2(int maxOffset)

 {

 this.maxOffset = maxOffset;

 }

 public float Distance(string s1, string s2)

 {

 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 dist = 0;

 while ((c + offset1 < s1.Length) 

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

 {

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

 {

 offset1 = 0;

 offset2 = 0;

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

 {

 if ((c + i < s1.Length) 

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

 {

 if (i > 0)

 {

 dist++;

 offset1 = i;

 }

 goto ender;

 }

 if ((c + i < s2.Length) 

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

 {

 if (i > 0)

 {

 dist++;

 offset2 = i;

 }

 goto ender;

 }

 }

 dist++;

 }

 ender:

 c++;

 }

 return dist + (s1.Length - offset1

 + s2.Length - offset2)/2 - c;

 }

 public float Similarity(string s1, string s2)

 {

 float dis = Distance(s1, s2);

 int maxLen = Math.Max(s1.Length, s2.Length);

 if (maxLen == 0) return 1;

 else

 return 1 - dis / maxLen;

 }

}

T-SQL code (double click to show/hide)

CREATE FUNCTION Sift2Distance(@s1 nvarchar(3999), @s2 nvarchar(3999),@maxOffset int)

RETURNS int

AS

BEGIN

IF ISNULL(@s1,'')='' RETURN LEN(isnull(@s2,''))

IF ISNULL(@s2,'')='' RETURN LEN(isnull(@s1,''))

IF isnull(@maxOffset,0)=0 SET @maxOffset=5

 DECLARE @c int,@offset1 int, @offset2 int, @dist int,@i int

 SET @offset1=0

 SET @offset2=0

 SET @dist=0

 SET @c=0

WHILE (@c+@offset1<len(@s1) AND @c+@offset2<len(@s2))

BEGIN

 IF (SUBSTRING(@s1,@c+@offset1+1,1)!=SUBSTRING(@s2,@c+@offset2+1,1))

 BEGIN

 SET @offset1=0

 SET @offset2=0

 SET @i=0

 WHILE (@i<@maxOffset)

 BEGIN

 IF (@c+@i<len(@s1) AND SUBSTRING(@s1,@c+@i+1,1)=SUBSTRING(@s2,@c+1,1))

 BEGIN

 IF (@i>0)

 BEGIN

 SET @dist=@dist+1

 SET @offset1=@i

 END

 GOTO ENDER

 END

 IF (@c+@i<len(@s2) AND SUBSTRING(@s1,@c+1,1)=SUBSTRING(@s2,@c+@i+1,1))

 BEGIN

 IF (@i>0)

 BEGIN

 SET @dist=@dist+1

 SET @offset2=@i

 END

 GOTO ENDER

 END

 SET @i=@i+1

 END

 SET @dist=@dist+1

 END

 ENDER:

 SET @c=@c+1

END

RETURN @dist+(len(@s1)-@offset1+len(@s2)-@offset2)/2-@c

END

CREATE function Sift2Similarity (@s1 nvarchar(3999), @s2 nvarchar(3999),@replaceCost int) returns float

as

BEGIN

 DECLARE @distance int

 SELECT @distance=dbo.Sift2Distance(@s1,@s2,2)

 DECLARE @maxLen int

 SET @maxLen=case when len(@s1)>len(@s2) then len(@s1) else len(@s2) end

 return case when @maxLen=0 then 1 else 1-cast(@distance as float)/@maxLen end

END

You can find a nice OOP Javascript implementation at IT BASE.

Performance:
The algorithm seems to be working fine for letter insertions, typos, letter inversions and such. It gives slightly different values than Levenshtein when big words are inverted. When a lot of letters are inverted, the difference from Levenshtein increases. Example: abcdefghijkl vs. badcfehgjilk (every two letters inverted) results in 0.42 similarity in Levenshtein and 0.08 in Sift2. But let's face it, the two words are really different.

Update:
I've optimised the algorithm a little and also changed the formula so that it matches the Levenshtein distance as close as possible. The basic idea remains the same, but now the average error from Levenshtein (calculated or real company name and address data) is only 3%.
Some people saw the goto line and immediately laughed. Well, I tried replacing it with a break and a subtraction and even removed the subtraction altogether (thus maiming the algorithm) and the goto implementation was still the fastest. So I will continue to use goto, as it is more efficient.

Request:
I have seen a lot of people actually searched on Google and got here. I would really really really like some comments, links to implementations or whatever... It's my baby after all. Thanks!