Help with string matching algorythm

Ruby
1

Hello,

I would be so gratefull to ANYONE who can help me!

I’m writting a program in C++.
A part of my program is to compare two strings and as a result I have to
get a number (range:0-1) which represents a similarity beetwen those two
strings.

Which algorythm to use?
I searched Web, but there’s a million of them, and I don’t know which to
use.
I don’t need a solution in C++, just a hint which algorythm to use to
implement this concept.

Thanx!

2

Tomislav K. wrote:

I’m writting a program in C++.
A part of my program is to compare two strings and as a result I have to
get a number (range:0-1) which represents a similarity beetwen those two
strings.

Which algorythm to use?
I searched Web, but there’s a million of them, and I don’t know which to
use.
I don’t need a solution in C++, just a hint which algorythm to use to
implement this concept.

Thanx!

strcmp()

Todd

3

2007/8/9, Tomislav K. [email protected]:

I searched Web, but there’s a million of them, and I don’t know which to
use.
I don’t need a solution in C++, just a hint which algorythm to use to
implement this concept.

There is no general answer to your question. It depends on what you
want to do with the result. There must be some requirements or at
least more information about the nature of your problem. There is no
general definition of the term “similarity” for text strings - it
really depends on the application case.

Kind regards

robert

4

On Aug 9, 6:28 am, Tomislav K. [email protected] wrote:

A part of my program is to compare two strings and as a result I have to
get a number (range:0-1) which represents a similarity beetwen those two
strings.

You might want to google for string “correlation” algorithms.
(Depending on what sort of similarity you want.)

5

Tomislav K. wrote:

I searched Web, but there’s a million of them, and I don’t know which to
use.
I don’t need a solution in C++, just a hint which algorythm to use to
implement this concept.

Thanx!

That sounds like a fun problem. As someone already said in a reply, the
algorithm depends on your requirements, and what type of similarity you
want. For example, if you wanted to use this information to attempt a
new type of sorting, the algorithm I’m about to suggest would be
useless.

That being said, here’s what I would do–it’s conceptually very simple:

  1. Find the “longest common subsequence”. What distinguishes this from
    “longest common substring” (and makes it harder) is that the matching
    letters don’t need to be adjacent. For example, the longest common
    subsequence of “aaaacccceeee” and “aaaabbbbccc” is “aaaacccc”. This is
    best calculated with dynamic programming, but you can probably find
    guidance on that on the internet.

  2. Compare the length of this substring with the lengths of the two
    original strings. Perhaps something simple like “Percent similarity =
    (length of common subsequence) / (average length of two original
    strings)”.

Hope this helps,
Dan

6

n 8/9/07, Robert K. [email protected] wrote:

The problem description made me think of bioinformatics - especially
comparing genetic distances. You can measure similarity as the number
of changes needed to transform one string into another. If that
sounds like the type of similarity you need, look up Levenshtein
Distance: Levenshtein distance - Wikipedia

In fact, there was a Ruby Q. dealing with a similar problem: Word
Chains - Ruby Quiz - Word Chains (#44). The difference was that
the quiz only allowed changes that resulted in valid dictionary words.

-Adam

7

Tomislav K. a écrit :

I searched Web, but there’s a million of them, and I don’t know which to
use.
I don’t need a solution in C++, just a hint which algorythm to use to
implement this concept.

Thanx!

You problem is similar to finding the edit distance between two strings.
Have a look at Edit distance - Wikipedia and
String metric - Wikipedia.
I don’t know which one could give a result in the range [0,1], however.

8

Phrogz pisze:

On Aug 9, 6:28 am, Tomislav K. [email protected] wrote:

A part of my program is to compare two strings and as a result I have to
get a number (range:0-1) which represents a similarity beetwen those two
strings.

You might want to google for string “correlation” algorithms.
(Depending on what sort of similarity you want.)

You might try: http://amatch.rubyforge.org/

lopex

9

Olivier R. a écrit :

Which algorythm to use?
I don’t know which one could give a result in the range [0,1], however.

I think using the levenshtein distance this way should do the trick :
levenshtein_distance(a, b) / max(a.size, b.size)

since the result of the levenshtein distance is at most the length of
the longer string.

10

As others already said, it depends on your needs.
But nobody mentioned soundex yet:
http://raa.ruby-lang.org/project/soundex/
which may or may not, be what you want.

Han H.