Compute Similarity of Two Strings

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

re: Compute Similarity of Two Strings

"Charles Law" <blank@nowhere.com> wrote in message
news:Oq6vDOekFHA.4000@TK2MSFTNGP12.phx.gbl...[color=blue]
> Hi folks
>
> Not really a .NET question, but I always think this is a good place to[/color]
ask.[color=blue]
>
> Does anyone have a favourite algorithm for determining the similarity of,[/color]
or[color=blue]
> 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[/color]
I[color=blue]
> am interested in people's practical experience and use of such algorithms[/color]
to[color=blue]
> help me choose a good'un.
>
> TIA
>
> Charles[/color]

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

re: Compute Similarity of Two Strings

"Gerald Hernandez" <Cablewizard@spam_remove@Yahoo.com> wrote in message
news:u53Cf9ekFHA.2152@TK2MSFTNGP14.phx.gbl...[color=blue]
>
> "Charles Law" <blank@nowhere.com> wrote in message
> news:Oq6vDOekFHA.4000@TK2MSFTNGP12.phx.gbl...[color=green]
>> Hi folks
>>
>> Not really a .NET question, but I always think this is a good place to[/color]
> ask.[color=green]
>>
>> Does anyone have a favourite algorithm for determining the similarity of,[/color]
> or[color=green]
>> 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[/color]
> I[color=green]
>> am interested in people's practical experience and use of such algorithms[/color]
> to[color=green]
>> help me choose a good'un.
>>
>> TIA
>>
>> Charles[/color]
>
> 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
>
>[/color]

re: Compute Similarity of Two Strings

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@spam_remove@Yahoo.com> wrote in message
news:u53Cf9ekFHA.2152@TK2MSFTNGP14.phx.gbl...[color=blue]
>
> "Charles Law" <blank@nowhere.com> wrote in message
> news:Oq6vDOekFHA.4000@TK2MSFTNGP12.phx.gbl...[color=green]
>> Hi folks
>>
>> Not really a .NET question, but I always think this is a good place to[/color]
> ask.[color=green]
>>
>> Does anyone have a favourite algorithm for determining the similarity of,[/color]
> or[color=green]
>> 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[/color]
> I[color=green]
>> am interested in people's practical experience and use of such algorithms[/color]
> to[color=green]
>> help me choose a good'un.
>>
>> TIA
>>
>> Charles[/color]
>
> 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
>
>[/color]

re: Compute Similarity of Two Strings

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" <blank@nowhere.com> wrote in message
news:%23Jj6qLfkFHA.320@TK2MSFTNGP09.phx.gbl...[color=blue]
> 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[/color]
range[color=blue]
> 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[/color]
whether[color=blue]
> 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@spam_remove@Yahoo.com> wrote in message
> news:u53Cf9ekFHA.2152@TK2MSFTNGP14.phx.gbl...[color=green]
> >
> > "Charles Law" <blank@nowhere.com> wrote in message
> > news:Oq6vDOekFHA.4000@TK2MSFTNGP12.phx.gbl...[color=darkred]
> >> Hi folks
> >>
> >> Not really a .NET question, but I always think this is a good place to[/color]
> > ask.[color=darkred]
> >>
> >> Does anyone have a favourite algorithm for determining the similarity[/color][/color][/color]
of,[color=blue][color=green]
> > or[color=darkred]
> >> 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,[/color][/color][/color]
but[color=blue][color=green]
> > I[color=darkred]
> >> am interested in people's practical experience and use of such[/color][/color][/color]
algorithms[color=blue][color=green]
> > to[color=darkred]
> >> help me choose a good'un.
> >>
> >> TIA
> >>
> >> Charles[/color]
> >
> > 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[/color][/color]
clearly[color=blue][color=green]
> > 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[/color][/color]
best,[color=blue][color=green]
> > you can present the user with a list of choices, and often times even a
> > short list will contain some simply absurd suggestions.
> >
> > Gerald
> >
> >[/color]
>
>[/color]

re: Compute Similarity of Two Strings

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@spam_remove@Yahoo.com> wrote in message
news:eBjHAzfkFHA.3144@TK2MSFTNGP12.phx.gbl...[color=blue]
> 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" <blank@nowhere.com> wrote in message
> news:%23Jj6qLfkFHA.320@TK2MSFTNGP09.phx.gbl...[color=green]
>> 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[/color]
> range[color=green]
>> 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[/color]
> whether[color=green]
>> 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@spam_remove@Yahoo.com> wrote in message
>> news:u53Cf9ekFHA.2152@TK2MSFTNGP14.phx.gbl...[color=darkred]
>> >
>> > "Charles Law" <blank@nowhere.com> wrote in message
>> > news:Oq6vDOekFHA.4000@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[/color][/color]
> of,[color=green][color=darkred]
>> > 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,[/color][/color]
> but[color=green][color=darkred]
>> > I
>> >> am interested in people's practical experience and use of such[/color][/color]
> algorithms[color=green][color=darkred]
>> > 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[/color][/color]
> clearly[color=green][color=darkred]
>> > 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[/color][/color]
> best,[color=green][color=darkred]
>> > you can present the user with a list of choices, and often times even a
>> > short list will contain some simply absurd suggestions.
>> >
>> > Gerald
>> >
>> >[/color]
>>
>>[/color]
>
>[/color]