Similar String algorithm

by

Levenshtein distance will not completely work, because you want to allow rearrangements. I think your best bet is going to be to find best rearrangement with levenstein distance as cost for each word.

To find the cost of rearrangement, kinda like the pancake sorting problem. So, you can permute every combination of words (filtering out exact matches), with every combination of other string, trying to minimize a combination of permute distance and Levenshtein distance on each word pair.

edit:
Now that I have a second I can post a quick example (all ‘best’ guesses are on inspection and not actually running the algorithms):

original strings             | best rearrangement w/ lev distance per word
Into the clear blue sky      |    Into the c_lear blue sky 
The color is sky blue        |    is__ the colo_r blue sky

R_dist = dist( 3 1 2 5 4 ) --> 3 1 2 *4 5* --> *2 1 3* 4 5 --> *1 2* 3 4 5 = 3  
L_dist = (2D+S) + (I+D+S) (Total Subsitutions: 2, deletions: 3, insertion: 1)

(notice all the flips include all elements in the range, and I use ranges where Xi – Xj = +/- 1)

Other example

original strings             | best rearrangement w/ lev distance per word
Into the clear blue sky      |   Into the clear blue sky 
In the blue clear sky        |   In__ the clear blue sky

R_dist = dist( 1 2 4 3 5 ) -->  1 2 *3 4* 5  = 1
L_dist = (2D) (Total Subsitutions: 0, deletions: 2, insertion: 0)

And to show all possible combinations of the three…

The color is sky blue         |    The colo_r is sky blue
In the blue clear sky         |    the c_lear in sky blue

R_dist = dist( 2 4 1 3 5 ) --> *2 3 1 4* 5 --> *1 3 2* 4 5 --> 1 *2 3* 4 5 = 3
L_dist = (D+I+S) + (S) (Total Subsitutions: 2, deletions: 1, insertion: 1)

Anyway you make the cost function the second choice will be lowest cost, which is what you expected!

More Related Contents:

  1. What is the difference between palindrome permutation and permutation? [closed]
  2. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  3. Splitting a string by a character
  4. C++ string::find complexity
  5. Are there any better methods to do permutation of string?
  6. How to find and replace all occurrences of a substring in a string?
  7. how to change to c code while using for loop and array
  8. C++ Convert string (or char*) to wstring (or wchar_t*)
  9. What are the mechanics of short string optimization in libc++?
  10. Why should one not derive from c++ std string class?
  11. How do I convert a double into a string in C++?
  12. Fastest way to get IPv4 address from string
  13. How I can print the wchar_t values to console?
  14. How can I get double quotes into a string literal?
  15. C++ string to enum
  16. How to read cin with whitespace up until a newline character?
  17. How to use string.substr() function?
  18. Is it reasonable to use std::basic_string as a contiguous buffer when targeting C++03?
  19. Reversible shuffle algorithm using a key
  20. How to pass a vector of strings to execv
  21. c++ sizeof( string )
  22. Issue with cin when spaces are inputted, using string class
  23. Why can’t the switch statement be applied to strings?
  24. Fast n choose k mod p for large n?
  25. Print 2-D Array in clockwise expanding spiral from center
  26. Convert char * to LPWSTR
  27. C++ Extract number from the middle of a string
  28. C++ Passing std::string by reference to function in dll
  29. Concatenate compile-time strings in a template at compile time?
  30. C++ most efficient way to convert string to int (faster than atoi)

Leave a Comment