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
5  1770 
"Charles Law" <bl***@nowhere. com> wrote in message
news:Oq******** ******@TK2MSFTN GP12.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" <Cablewizard@sp *********@Yahoo .com> wrote in message
news:u5******** ******@TK2MSFTN GP14.phx.gbl...
"Charles Law" <bl***@nowhere. com> wrote in message
news:Oq******** ******@TK2MSFTN GP12.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
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******** ******@TK2MSFTN GP14.phx.gbl...
"Charles Law" <bl***@nowhere. com> wrote in message
news:Oq******** ******@TK2MSFTN GP12.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
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******** *******@TK2MSFT NGP09.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******** ******@TK2MSFTN GP14.phx.gbl...
"Charles Law" <bl***@nowhere. com> wrote in message
news:Oq******** ******@TK2MSFTN GP12.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
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******** ******@TK2MSFTN GP12.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******** *******@TK2MSFT NGP09.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******** ******@TK2MSFTN GP14.phx.gbl... >
> "Charles Law" <bl***@nowhere. com> wrote in message
> news:Oq******** ******@TK2MSFTN GP12.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
>
>
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Bosconian |
last post by:
I'm looking for a method to compare two strings and grade them for
similarity.
My idea is to strip out common words and punctuation and create a checksum
of each remaining string. I would then compare the checksums and if they are
close then there's a potential match (to be judged by user interaction.)
Can someone suggest an existing function or class to perform such a task?
Thanks!
|
by: Achim Domma |
last post by:
Hi,
I have a list of lets say 100-1000 strings and want to know which one is
most similar to a reference string. Does somebody know such a library for
Python? I don't need complicated scientific stuff, I think the most simple
ones will do it for my data.
regards,
Achim
|
by: Dick Moores |
last post by:
I need to figure out how to compute pi to base 12, to as many digits as
possible. I found this reference,
<http://mathworld.wolfram.com/Base.html>, but I really don't understand
it well enough. Could someone show me how to do what I need?
Thanks,
Dick Moores
rdm@rcblue.com
|
by: Anibal Acosta |
last post by:
Somebody know an algorithm for determine the similarity between two string
for example:
string 1: "Hello what is your name?, where are you from?"
string 2: "Hello man, where are you from?"
In this case I think that this two string has 75% of similarity.
However, if you know an algorithm that do that I'll appreciate very very
|
by: Charles Law |
last post by:
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
| | |
by: himoundary |
last post by:
hi all
i am using microsoft speech sdk (sapi 5.1).
i have the following requirements:
1) i need to compare current input sound (through mic) with recorded
sound file (say .wav). based of this, i need a measure of similarity or
correlation between the two sounds (live input from mic and recorded
..wav sound). a score indicating the degree of similarity would be
perfect, but even a boolean response (match / no match) would do.
|
by: Ralf Goertz |
last post by:
Hi,
is there some c++ library that helps me assess the similarity of two
strings? In particular, I want to match strings that describe names of
institutions. For instance, one string could be a proper substring of
the other or one string contains abbreviations whereas the other does
not. Typos in one of the strings is another possibility.
Thanks in advance,
|
by: IanWright |
last post by:
I'm trying to come up with an effective assignment algorithm to allocate nodes to a nearest outlet, where each node should be have a time slot checked against the already allocated nodes for similarity (or even sequentiality to allow effective journey planning throughout a day).
I've currently looked at something called SPA - Simple Parallel Assigning which works out the cost of assigning each node to its nearest and next nearest outlet, and...
|
by: Jeff |
last post by:
I've got a series of data like this:
Long Sleeve White P/C Sm 32/33
Long Sleeve White P/C Med 32/33
....
What I'd like to do is extract the differences and the similarity. In
this case:
similar: Long Sleeve White P/C
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| | |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| | |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
