String-to-string correction algorithm

Question

I'm not sure I've titled this post correctly, but I'm wondering if there's a name for this type of algorithm:

What I'm trying to accomplish is to create a minimal set of instructions to go from one string to its permutation, so for example:

    STACKOVERFLOW -> STAKCOVERFLOW

would require a minimum of one operation, which is to

    shift K before C.

Are there any good online examples of

Finding the minimum instruction set (I believe this is also often called the edit distance), and
Listing the instruction set

Thanks!

what language? Please provide a complete description of your problem, if you want to get a helpful answer — Thomas Berger
– Thomas Berger, Commented Aug 19, 2011 at 22:48
Take a look at this link: norvig.com/spell-correct.html It's pretty good. — Jacob Eggers
– Jacob Eggers, Commented Aug 19, 2011 at 22:52
I'm happy with any language that has string manipulation abilities. I'm personally trying to use ActionScript 3, but the problem itself is not language-specific. — Edward H
– Edward H, Commented Aug 19, 2011 at 22:52
@Edward K Huang but languages are OS dependent. I could tell you to use perl p.a. but under windows, it may work not exactly the same way and would be a huge overhead. Thats why i'm asking for the language =) — Thomas Berger
– Thomas Berger, Commented Aug 19, 2011 at 23:20

Russ Clarke · Accepted Answer · 2011-08-19 23:01:36Z

3

There is something known as the Levenshtein distance that tells you how many changes are needed to go from one string to another and there are many C# implementations, many other languages too.

Here's the wiki:

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

Edit: As TheHorse has indicated, the Levenshtein distance doesn't understand Shift changes, but there is an improved algorithm:

Damerau-Levenshtein distance

edited Aug 19, 2011 at 23:01

answered Aug 19, 2011 at 22:47

Russ Clarke

17.9k4 gold badges44 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

TheHorse Over a year ago

Levenshtein distance have no SHIFT operation.

Russ Clarke Over a year ago

Sure it does, well, it understands substitution anyway ... and that's the example Edward has represented. An improved algorith is Damerau Levenshtein which supports transposition as well as addition, deletion and substitution: en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

Russ Clarke Over a year ago

Actually, sorry you're correct, substitution isn't the same as transposition. I'll update my answer.

Collectives™ on Stack Overflow

String-to-string correction algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related