From: Anton Bangratz Date: 2010-09-29T06:03:52+09:00 Subject: Re: levenshtein function issue --------------enigA3E82D9EF18A8F36264E9D4E Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On 09/28/2010 08:10 PM, Chris Hulan wrote: > On Sep 27, 3:37 pm, Joe Smith wrote: >> Chris Hulan wrote: >>> On Sep 26, 12:43 am, Joe Smith wrote: >>>> error... (that's why I had originally changed it) >>>> -- [...] >=20 Now, that bugged me too, and I had a go (using more idiomatic ruby ranges and Enumerable methods, and "enhancing" the String class): http://gist.github.com/601739 Notes: When first going through the matrix, I fill the initial values in the first column and row, and set the rest to nil. When traversing the matrix a second time, I start at index '1' and end at the index calculated from the size, but the strings actually use zero-based indexes. To illustrate that: S T R I N G <-- This is the string - spaced out f. visibility 0 1 2 3 4 5 <-- These are the corresponding index numbers ^ This is the last index, but the size is returned as 6. So, when I am traversing the matrix, I use 1..6, but the corresponding letters are at 0..5. That is the reason that I have to use cost =3D (self[s-1] =3D=3D other[t-1]) ? 0 : 1 so I really do compare the strings letter by letter. Hope that helps a bit, t. --=20 Anton Bangratz - Key ID 363474D1 - http://tony.twincode.net/ fortune(6): He who laughs last -- missed the punch line. --------------enigA3E82D9EF18A8F36264E9D4E Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.14 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJMolgoAAoJEAgZMsE2NHTRYpgH/1pHrU0C1sCtAy8GiNNU/d2Y sICEZGmeNQptC1bAmnnxE+dkrFr027wUjPM2Za0cxJcPlq9Xnie35GVFutePjr5/ ETHbDvEb7vLbz8Y1tenMDVhi0uOtDINFAwm9fPtRdJqtWqWCPtNAfNHtwvUtSRGu JgXmUnTEh7SbEb2ykUu4yKj0Noj7WUr2Zr3k9yHWhoyPDqi7ItMl7NYKosxilXAa GOjLd+N28675bYOoM1GfyuJLqXdLtWOLiS3gtSTnnLxpWxjgm5FQ/XYHByD+XBsM zf3L01oKtH0rsZPyWlcVCA0AEVr2onNEHevBWUR+SreJJ7UR6NdmEhHpbqMhBLQ= =GCpq -----END PGP SIGNATURE----- --------------enigA3E82D9EF18A8F36264E9D4E--