Problem with Fuzzy Substring Matching (brainteaser)
3 views (last 30 days)
Show older comments
Hello,
I implemented the Levenshtein algorithm in Matlab and modified it that that it can search for substrings within a longer string. (Setting the insertion costs at the beginning to zero).
Example:
original_levenshtein('Hello Tim','Tim') = 6
modified_levenshtein('Hello Tim','Tim') = 0
Where 0 is a perfect match and every additional point means 1 modification is necessary to change the second string to match the first one exactly.
So this works very well, but unfortunately I have to compare huge amounts of strings and not all of them are that clean and nice. For example, I have this string1 ('Hello Tim') on the one hand and a bunch of strings on the other and I want to know which of these is closest to string 1. With Levenshtein I can now rank the scores and that's it.
The problem is that shorter strings always get a better score and ruin my rankings.
Example:
modified_levenshtein('Hello Tim','Tim') = 0
modified_levenshtein('Hello Tim','i') = 0
So although 'Tim' is 3 times longer than 'i' and achieves a perfect match, both get the same score and are 'indistinguishable' with regard to the best matching for 'Hello Tim'. But of course the second one is nonsense. So my question is how can I link the score to the length of the string to compensate for that?
0 Comments
See Also
Categories
Find more on Fuzzy Logic Toolbox in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!