From: Axel Etzold Date: 2009-09-30T06:24:52+09:00 Subject: Re: Match a long string in Ruby despite a few typing errors -------- Original-Nachricht -------- > Datum: Wed, 30 Sep 2009 05:23:15 +0900 > Von: Ehsanul Hoque > An: ruby-talk@ruby-lang.org > Betreff: Match a long string in Ruby despite a few typing errors > > I'd like to match a string to another, and recognize the match even if > there are a few typing errors. These errors could include omission of a > letter/space/punctuation mark, an extra letter or a mistyped letter. I don't > require it to detect multiple errors in a row, or in a single word. The string > would be comparable to the length of this paragraph, a little shorter, in > case that matters > > I could come up with some basic implementation for this, but it seems > like a little too much to do for something like this. I was wondering if there > was a simple way to do this, a gem perhaps? Dear Ehsan, you could use Levenstein distance - there's an implementation in Ruby here: http://raa.ruby-lang.org/project/levenshtein/ An even more informative alternative would be using the McIlroy-Hunt longest common subsequence algorithm, of which you get an implementation in the diff-lcs gem. Both algorithms can be implemented with complexity O(m*n), so this might take some time, if your string lengths m,n are big. Maybe you can check beforehand that the lengths of string a and b differ by e.g., 5, so their Levenstein distance is certainly greater than e.g., 3, which you'd fix as the maximum tolerable error number ... Also, some tweaking allows to bring down the complexity to O(m+n), as is stated e.g., here : ttp://www.ime.usp.br/~is/papir/sctp/node2.html . Best regards, Axel -- Neu: GMX Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate f�r nur 19,99 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02