Problem with Fuzzy Substring Matching (brainteaser)

조회 수: 3 (최근 30일)
Léon . 2011년 12월 15일
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).
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.
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?

답변 (2개)

Jan 2011년 12월 16일
What about a simple scaling:
score = (modified_levenshtein(S1, S2) + 1) / length(S2)

Léon 2011년 12월 16일
Hello Jan,
I actually didn't think of that.
My actual approach is to examine the shortest string on the list and subtract the difference between that and the actual string to the score.
string1 = ' Hello Tim';
candidates = ('Tim' ; 'i');
mlength = min(length(candidates)); % I know that the real code must be slightly different
score = (modified_levenshtein(string1,candidates(1)) - (length(candidates(1) - mlength);
Which one serves best?
  댓글 수: 1
Jan 2011년 12월 16일
The choice depends on the needs. If you look in the string "Tim", should "Xim" or "im" be preferred?

댓글을 달려면 로그인하십시오.


Help CenterFile Exchange에서 Prepare Model Inputs and Outputs에 대해 자세히 알아보기

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by