Problem with Fuzzy Substring Matching (brainteaser)

1 次查看（过去 30 天）
Léon
Léon 2011-12-15
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?

请先登录，再回答此问题。

回答（2 个）

Jan
Jan 2011-12-16
What about a simple scaling:
score = (modified_levenshtein(S1, S2) + 1) / length(S2)
Léon
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.
Like:
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
Jan 2011-12-16
The choice depends on the needs. If you look in the string "Tim", should "Xim" or "im" be preferred?

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Characters and Strings 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by