Help me find the algorithm name - quantify difference between two words

Question

I know there is an algorithm for seeing how "close" two words are together. The idea is that this algorithm adds 1 point to the score for every single letter addition or subtraction that is necessary to transform one word into the other. The lower this score, the "closer" the two words are together.

For example, if we take the word "word" and "sword", their distance is 1. To go from "word" to "sword" all you have to do as add an "s" in the beginning.

For "week" and "welk" the distance is 2. You need to subtract the "e" and add an "l".

I remember this algorithm is used for sorting the suggestion list in spell-checkers. I cannot recall the name of this algo.

What is this algorithm called?

Lefthand

haha, look at all the parrots! (me included) :) – Groundmass

upvote everyone :) I think the most correct answers are the assertive ones... so the ones that say 'this is it' rather than 'i think you mean...', since it clearly is the correct answer the others must know more... right? :) – Groundmass

At least when you see 5 different people give the same answer that it must be correct. – Walloon

I wish I could accept all these answers :) Thank you for the quick answers. Next time I'll make it tougher. – Lefthand

oh, and it appears I answered first hehe – Groundmass

+1 @ ChaosPandion... too true. – Groundmass

@ChaosPandion: I am not sure Galileo Galilei would have agreed... but it somehow seems to work on SO. – Tennyson

Answer 1

Levenshtein Distance

Is it just me or is this simple algorithm great?

Walloon

Answer 2

This sounds a lot like the Levenshtein distance algorithm

Spellman

Answer 3

Levenshtein distance.

Unsettled

Answer 4

Levenshtein distance

http://en.wikipedia.org/wiki/Levenshtein_distance

Groundmass

Answer 5

Do you mean Levenshtein distance?

Bade

Heh, that didn't take long! :) – Bade