CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    Dec 2014
    Posts
    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)

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: Damerau–Levenshtein Distance modification (Edit Distance for Strings)

    Quote Originally Posted by JrPtn View Post
    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.

  3. #3
    Join Date
    Jul 2013
    Posts
    576

    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
  •  





Click Here to Expand Forum to Full Width

Featured