From: Erik Veenstra <erikveen@...>
Date: 2008-05-15T20:24:42+09:00
Subject: Re: 40 million levenshtein distances for two long strings

> I have to do a lot of comparisons, about 40 million.

40 million or 400 million?... :}

I've once written a Levenshtein implementation in C, because of
this speed issue. It compares 2 20 KB files in 3 seconds. And
it does come with a threshold.

Interested?

gegroet,
Erik V. - http://www.erikveen.dds.nl/

----------------------------------------------------------------

 $ ll lev[12]
 -rw-r--r-- 1 erik erik 19275 May 15 12:10 lev1
 -rw-r--r-- 1 erik erik 19275 May 15 12:12 lev2

 $ cat lev.rb
 require "ev/levenshtein"

 s1 = File.read("lev1")
 s2 = File.read("lev2")

 p EV.levenshtein(s1, s2)

 $ time ruby lev.rb
 12

 real    0m3.105s
 user    0m2.843s
 sys     0m0.281s

----------------------------------------------------------------