Re: ADT.Heap performance poorer than just sorting and slicing

On Wed, 24 Feb 2016, Martin Nilsson (Coppermist) @ Pike (-) importm?te f?r mailinglistan wrote:

>> String.fuzzymatch will examine two strings and give a score out of 100
>> for their similarity. I'd like to employ this to create a simple
>> spelling suggestion engine, by feeding it a test word and an array of
>> known words, and getting back an array of the 5 nearest matches. So
>> far, so good.
>
> As a side note I think using levenstein_distance() is better. At least
> it is twice as fast. We should possibly change fuzzymatch to something
> like the following, if people or OK with the actual numbers not being
> exactly the same.
>
> int fuzzymatch(stirng a, string b)
> {
>  return (int)round(1-levenstein_distance()/max(sizeof(a),sizeof(b)));
> }

The above looks severely broken:

   * The division needs a cast to float.

   * It has the wrong range (will only return 0 or 1 (mostly 1)).

Something like the following might work better:

   int(0..100) fuzzymatch(string a, string b)
   {
     int m = max(sizeof(a), sizeof(b));
     return (int(0..100))round((100.0 * (m - levenshtein_distance(a, b))) /
                               m);
   }

-- 
Henrik Grubbström					[email protected]
Roxen Internet Software AB