-
December 1st, 2014, 10:28 PM
#1
Damerau–Levenshtein Distance modification (Edit Distance for Strings)
Is there a way to modify the Damerau–Levenshtein distance algorithm to allow the transposition of substrings? By this I mean that instead of simply turning "ba" to "ab" you could calculate "worra" to "arrow" and have that cost only be 1. An example might help:
If you had a target of timeflieslikeanarrow and a staring string of tfemiliilzejeworrbna, you would have the following operations for a minimum of 6.
tfemiliilzejeworrbna (the target)
tfemiliilzejeanbrrow (transpose)
tfemiliezlijeanbrrow (transpose)
timefliezlijeanbrrow (transpose)
timefliezlijeanarrow (a substitution)
timefliezlikeanarrow (a substitution)
timeflieslikeanarrow (a substitution)
-
December 5th, 2014, 05:46 PM
#2
Re: Damerau–Levenshtein Distance modification (Edit Distance for Strings)
Originally Posted by JrPtn
Is there a way to modify the Damerau–Levenshtein distance algorithm to allow the transposition of substrings?
Is this an unresolved research proposition?
Are you asking for an unassuming genious to help you get a doctorate?
Last edited by razzle; December 5th, 2014 at 05:51 PM.
-
December 12th, 2014, 04:28 PM
#3
Re: Damerau–Levenshtein Distance modification (Edit Distance for Strings)
I guess you'll have to do it the hard way then, by your own deep thinking.
This is the kind of cheating I dislike the most. Posting hard unsolved problems all over the place in the slim chance someone gifted is struck by genious coming up with a solution you can copycat as your own.
Earn your own Ph.D.
Last edited by razzle; December 12th, 2014 at 05:06 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|