I’m not what you would cosider an algorithm guy, but after needing to use a bit of spell checking in some code, I became fascinated with the Levenshtein distance. I found plenty of resources explaining what it did, I also found plenty of resources with example implementations. What I couldn’t find were any really simple explanations for exactly HOW it worked.

I’m a big believer in conference driven development, so I signed up to give some talks on the algorithm and then got to work dissecting it. To help I kept distance measurement notes and wrote scripts that visualized different distance measurement methods. The talk was a huge successs, I ended up giving it in RubyKaigi in Japan, Rails Pacific in Taiwan and RubyConf in San Diego.

I could tell you all about it, but I would rather you watched the video.

Video

Note: While there are 3 versions of me giving this talk, this is the only time I made the audience do the CanCan.

Slides

You can also review the slides:

Notes and Scripts

Download and Run my scripts.

Fin

I learned a ton presenting this unique and useful algorithm, I highly encourage you to not only use these resources but to also explore the algorithm world.

If you like algorithms, distance measurements, or Ruby things follow @schneems