Compute Similarity of Two Strings

[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

[Gerald Hernandez]

"Charles Law" <bl***@nowhere.com> wrote in message
news:Oq**************@TK2MSFTNGP12.phx.gbl...

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

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

[Charles Law]

"Gerald Hernandez" <Cablewizard@sp*********@Yahoo.com> wrote in message
news:u5**************@TK2MSFTNGP14.phx.gbl...

"Charles Law" <bl***@nowhere.com> wrote in message
news:Oq**************@TK2MSFTNGP12.phx.gbl...

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

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

[Charles Law]

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
"Gerald Hernandez" <Cablewizard@sp*********@Yahoo.com> wrote in message
news:u5**************@TK2MSFTNGP14.phx.gbl...

"Charles Law" <bl***@nowhere.com> wrote in message
news:Oq**************@TK2MSFTNGP12.phx.gbl...

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

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]

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

"Charles Law" <bl***@nowhere.com> wrote in message
news:%2***************@TK2MSFTNGP09.phx.gbl...

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
"Gerald Hernandez" <Cablewizard@sp*********@Yahoo.com> wrote in message
news:u5**************@TK2MSFTNGP14.phx.gbl...

"Charles Law" <bl***@nowhere.com> wrote in message
news:Oq**************@TK2MSFTNGP12.phx.gbl...

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

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

[Charles Law]

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
"Gerald Hernandez" <Cablewizard@sp*********@Yahoo.com> wrote in message
news:eB**************@TK2MSFTNGP12.phx.gbl...

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

"Charles Law" <bl***@nowhere.com> wrote in message
news:%2***************@TK2MSFTNGP09.phx.gbl...

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
"Gerald Hernandez" <Cablewizard@sp*********@Yahoo.com> wrote in message
news:u5**************@TK2MSFTNGP14.phx.gbl...

>
> "Charles Law" <bl***@nowhere.com> wrote in message
> news:Oq**************@TK2MSFTNGP12.phx.gbl...
>> 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
>
> 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
>
>