Compute Similarity of Two Strings

  • Thread starter Thread starter Charles Law
  • Start date Start date
C

Charles Law

Hi folks

Not really a .NET question, but I always think this is a good place to ask.

Does anyone have a favourite algorithm for determining the similarity of, or
difference between two strings? I'm looking for something that could be
considered to be quite reliable.

I have Googled quite extensively, and there is a lot on this subject, but I
am interested in people's practical experience and use of such algorithms to
help me choose a good'un.

TIA

Charles
 
Charles Law said:
Hi folks

Not really a .NET question, but I always think this is a good place to ask.

Does anyone have a favourite algorithm for determining the similarity of, or
difference between two strings? I'm looking for something that could be
considered to be quite reliable.

I have Googled quite extensively, and there is a lot on this subject, but I
am interested in people's practical experience and use of such algorithms to
help me choose a good'un.

TIA

Charles
Click to expand...

Well, it depends a great deal on what you are actually trying to accomplish.
The Levenshtein Edit Distance is fairly ubiquitous and a good starting
point, especially if you are looking to get results similar to other
applications.
For my needs, modifying it to handle transpositions, double chars, and other
things significantly improve the results. Additionally, applying a
tokenization algorithm, such as MetaPhone, and then comparing the tokenized
strings might be desirable. For example to compare words that might "sound"
alike.

Reliable? In this arena, that is a very subjective thing. It means clearly
defining your needs, and most likely altering the algorithm to specifically
meet those needs. If you are trying to write a spell checker and have it
always select the right word, that simply is not going to happen. At best,
you can present the user with a list of choices, and often times even a
short list will contain some simply absurd suggestions.

Gerald
 
Gerald Hernandez said:
Well, it depends a great deal on what you are actually trying to
accomplish.
The Levenshtein Edit Distance is fairly ubiquitous and a good starting
point, especially if you are looking to get results similar to other
applications.
For my needs, modifying it to handle transpositions, double chars, and
other
things significantly improve the results. Additionally, applying a
tokenization algorithm, such as MetaPhone, and then comparing the
tokenized
strings might be desirable. For example to compare words that might
"sound"
alike.

Reliable? In this arena, that is a very subjective thing. It means clearly
defining your needs, and most likely altering the algorithm to
specifically
meet those needs. If you are trying to write a spell checker and have it
always select the right word, that simply is not going to happen. At best,
you can present the user with a list of choices, and often times even a
short list will contain some simply absurd suggestions.

Gerald
Click to expand...
 
Hi Gerald

Thanks for the response. Please ignore the previous, empty reply; finger
trouble.

I have seen the Levenshtein Edit Distance algorithm, and have some code in
VB.NET for it.

It would be nice to have an algorithm that produced a % value, in the range
0 - 100%. Perhaps by taking

(Edit Distance / Length of longest string) * 100

but I don't know if that is the best formula to produce a percentage.

I am purely interested in character-by-character similarity, and not whether
the strings sound alike. For example, a test might be

ABC vs WXYZ = 0%
PR vs RP = 50%
JKL vs JKL = 100%

Charles
 
Hmm...
In this case, it would help to clarify the PR vs RP = 50%. How are you
coming up with that value? The obvious might be to treat this as one
transposition. If you get your hands on a Levenshtein algorithm that
implements transpositions as well, then you might be able to use something
like:
NumChars = Length of Longest String
Changes = Edit Distance
(NumChars - Changes) / NumChars = %

Gerald
 
Now that I look at it again I am not sure about the PR vs RP = 50%. I was
thinking in terms of one of the characters being in the right place and the
other not. The two strings could be lined up as

PR
RP

and now the R is correct and it is just the P that is wrong. I will give
that one more thought ...

Charles
 
Back
Top