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!

Read More

I killed my first person tonight

It was going to be an easy job. Get in, do something, get out. It wasn't much, the reasons for doing it were rather more intellectual than financial. I was making a point, kind of like Robin Hood. But she was there. The thing was done, she could see it. She wasn't in a position to stop me. She looked at me, sized me up, found me lacking. Something was terribly ugly on her face when she howled and threw herself at me, shouting all the time. It was like I have offended her on a personal level, like she wouldn't take defeat, one that was obvious at the time we've met.

So I did it. In fear, panic more likely, with all my power, I stabbed her with the screwdriver I've used to get in. I did it once, twice, three times. I didn't believe that it was so easy to stick something that long in a human being so easily, through clothes, skin, meat... She looked at me, with annoyed surprize, my screwdriver dripping blood, her official looking shirt dirtied by three horrible red dots, she looked at me for the longest of moments, her face showing angry disaproval, hateful disgust.

Then she attacked again, with renewed force, in silence, which actually made her even scarier, like a demon from hell. Her face contorted by unmistakeable hate, she pushed me with all her strength, trying to claw at my eyes. All I could do is let me be pushed, holding her arms, trying to defend myself, until I reached a stair rail with my back. We couldn't go any further and starting from a mischievous thing, the simplest of things, I was fighting for my life with a witch which I've just stabbed, but didn't die. So I tried to throw her down the stair case, three floors down, which I am sure would have killed her.

But she clang to me, she knew she would fall, but instead of thinking of saving her life, she pulled at me, trying to make me fall with her. She wanted me hurt, dead, she wanted to avenge something terribly ugly from her own life, which, I am sure now, had nothing to do with me personally. She was scarred, long before I got there, with my bloody Johnson screwdriver. But right then, the only thing I could think about was I was going to die. But I didn't. Somehow I landed safely on a stair underneath, while the hag took the plunge.

She didn't die, though. Clinging to me has slowed her fall, so now she was sprawled on the floor downstairs, mumbling something, her legs in an awkard position. I went to her, partly because I wanted to get out, and I had to use the stairs, partly because I wanted to see her, to see what I have done, my brain in shock, yet sickly curios about the bloody mess I have caused.

She was clearly dying, her face wasn't wrinkled in hate anymore, she looked... peaceful. But she was alive and she looked at me with something resembling love or something similar. All her scars were gone in that moment and her thoughts, or what had remained of them after hitting the floor with her head, weren't evil anymore. There was no anger on her face and that made her look, well, beautiful. She was about 50, maybe more, but she looked like someone good at heart, like an innocent child.

So I did the only thing I could have. I kneeled next to her, I took her head in my hands, conforted her for a moment, telling her it will not hurt for long, then I snapped her neck. It isn't so easy as in the movies, I had to try several times, making this more of a mess than it already was. When I heard the snap, like in a chicken's neck, I turned her head in the other way, just to make sure that she was dead, not paralysed or feeling pain in any way.

Of course, That wouldn't have made it all better, I have done all of that, and I knew it, and my soul was crying and a huge depression engulfed me, like I had killed a part of me. And I also knew that no one would have waited for her home. She was this spiteful angry hateful person that no one liked, that stayed at the work place during the night because there was nothing waiting for her outside. I was sure that the members of her family would feel partly relieved that she was dead. And the only person that saw her beautiful, the only person that saw, even for the briefest moments, beyond that wall of negative emotions, was the man that had killed her.

At the time, struggling with all my strength to break that woman's neck, I had wished that I was more efficient in stabbing her, less panicked, maybe sticking her in the heart, killing her instantly, but now I know I was meant to see that beautiful face, that it couldn't go any other way, that I was meant to see that face looking at me, with an innocent sadness, for the rest of my life.

Read More

What is love funny animation!

I've stumbled upon this dugg link that shows a very cool animation. I am reproducing it here, because of annoying commercials on that site.

Also, if you have an iPad or some other device that doesn't support Flash, you're out of luck.

I am reproducing here two larger collections of What is Love thematic song remakes :) They're kind of funny.

Read More

Oh no! Saddam again?

Well, I just had to say something about the video of Saddam Hussein's execution. But I'll try to be brief and focus on only two things: the censorship applied to the official video and the US comments.
First, the big row shouldn't be about Saddam at all. Whatever he did, why he did it and how harsh a punishment he deserves is an internal Iraqi affair, and their... democratic history... leaves to be desired. It's not like they know how to behave in a dignified manner, anyway. No, the problem is the censorship on the official video. Somehow, they realised that how they did the whole thing was wrong. They got it! It was wrong. But, in their typical governmental greed, they removed the sound, clipped the video, and spun the story as they could to actually make them look good.
The second issue, the US government made a statement that said they would have done everything in a different way and that it all boils down to the inexperience of the Iraqi government. But they were referring to the leaked video! So what they actually said, publicly, is that they had more experience in limiting media access and manipulating public opinion. Which, of course, they do, but that's besides the point.
Both these situations show only one thing: shamelessness, the lack of shame, on the part of any government. It's beyond 'power corrupts', it's all about the corrupted seeking power and getting it, wrapped in a nice 'democratic' package.

There is no statistic that I know of that calculates the percentage of "media leaks" in situations like this or Abu Ghraib, etc. In other words, a formula that could estimate the actual number of cases based on the number that were recorded on tape and made it to the public. But my guess is it's similar to fossiles. Only a small fraction of dead animals fossilise in order for archeologists to find them. Such leaks show a trend, rather than exceptions. They also help "them" to become more "experienced".

Read More

Here is a nice piece of writing

Randomly browsing the net I've found a very nicely written article, deceptively titled The dumbing-down of programming , which I just had to blog about. It tells about the onion structure in computers, layers upon layers of stuff you didn't even think it's there and that you never use. It's about archeology in your own computer. Cute.

Read More

The Embedding, by Ian Watson

Ian Watson
Reviews

I've first started reading this book with aprehension, it seemed to involve weird and useless experiments, a heavy language or writing style, socialist concepts and a lot of bull. After a while, however, it started to become interesting. The concepts were refined, the gray areas explained, aliens appeared... it seemed to gather pace. After reading 90% of it I was looking forward for the grand finale. Which was nothing but a big and sloppy hiss.

The whole idea of the book revolves around the nature of reality and our perception of it. It starts from three different points of view and it seems to have a very good foundation to build on. It does present some concepts that might have value, but in the end, it fails miserably. I guess the author was unable to carry everything through or he just got bored with it.

But do bear in mind that it's his first novel, written in 1973, and he won the Apollo Prix in 1975 with it.

Read More

So you want to be a... anything!

I've spent my last two days watching popular science shows. I've started with the very bad and time wasting "What we still don't know" and ended up with the marvelous "Stephen Hawking's Universe". I've always had this fantasy of doing something that matters, maybe become proficient in the things I really like, but rarely do, like writing, or science. And, in the good old trandition of Sierra games, I've thought of a "So you want to be a ..." series, where average everyday people like myself could be shown how to become something they always wanted, in the shortest time possible. Something like a career guide on speed.

Well, I am certainly not the only one to have come up with this idea: Dr. Michio Kaku wrote an article about becoming a physicist. Well, he basically tells you you cannot become a physicist if you've already lost the train. But I disagree. If you really want something, you can achieve it, at any age, only you can't do it with support from others.

So, what do I want to become? I've written in my todo list to check out calculus, topology and noncommutative geometry. That is almost certain not to go well, but at least I plan to try (trying). Damn, I like to think of stuff and never do anything about it. I only like whinning more! But the question is: what do you want to become? Don't waste your time. And I am not talking about carrers, I am talking about the things that makes one define himself on. Like for me, I am a C# programmer. That defines me at this moment. I certainly am glad there is more to add to that, like other achievements or "I am a good person" or "I have felt true love", but I still wish I could add more. Maybe being a part time garage cosmologist wouldn't hurt. Dreams ARE important and they are surely unachievable only when you don't even try to achieve them.

Read More