From: Olivier Renaud <o.renaud@...>
Date: 2007-08-14T18:20:28+09:00
Subject: Re: Help with string matching algorythm

Olivier Renaud a 辿crit :
> Tomislav Kralj a 辿crit :
>> 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!
>>   
> You problem is similar to finding the edit distance between two 
> strings. Have a look at http://en.wikipedia.org/wiki/Edit_distance and 
> http://en.wikipedia.org/wiki/String_metrics.
> 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.

--
Olivier Renaud