bugGNU Octave - Bugs: bug #49375, pkg name similarity measurement is...

 
 

bug #49375: pkg name similarity measurement is off / too simplistic

Submitter:  Mike Miller <mtmiller>
Submitted:  Mon 17 Oct 2016 07:56:07 PM UTC
   
 
Category:  Octave Function Severity:  2 - Minor
Priority:  3 - Low Item Group:  Incorrect Result
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 18 Oct 2016 12:59:39 PM UTC, comment #6: 


> We actually had a more advanced mechanism for computing
> string distances in an old version of odepkg that was based
> on Levenshtein metric
>


That's on the strings package too, named edit_distance

http://hg.code.sf.net/p/octave/strings/file/db1ee7036df0/inst/editdistance.m

Carnë Draug <carandraug>
Group Member
Tue 18 Oct 2016 10:16:38 AM UTC, comment #5: 

Sorry, the link to levenshtein.m was incorrect,
this is the correct link.

The code needs a few fixes here and there but it should be easy to get it to work.

Carlo de Falco <cdf>
Group Member
Tue 18 Oct 2016 09:52:17 AM UTC, comment #4: 

Hi,

We actually had a more advanced mechanism for computing
string distances in an old version of odepkg that was based
on Levenshtein metric

The code can be recovered from the repository here:

c++ version

or here

m-file

the function fuzzy_compare finds the best match of a given string within a set of allowed strings and would be useful in this context.


Carlo de Falco <cdf>
Group Member
Mon 17 Oct 2016 09:47:06 PM UTC, comment #3: 

Maybe a cost penalty based on 1 or 2 for each additional character?


    function d = fdist (x)
      len1 = length (name);
      len2 = length (x);
      if (len1 <= len2)
        #d = sum (abs (name(1:len1) - x(1:len1))) + sum (x(len1+1:end));
        d = sum (abs (name(1:len1) - x(1:len1))) + (len2 - len1);
      else
        #d = sum (abs (name(1:len2) - x(1:len2))) + sum (name(len2+1:end));
        d = sum (abs (name(1:len2) - x(1:len2))) + (len1 - len2);
      endif
    endfunction


This works for a single addition of a character.  But it still sucks if there has been a repetition or deletion within the body of the name since after the error all of the characters are mis-aligned.

Rik <rik5>
Group administrator
Mon 17 Oct 2016 09:39:30 PM UTC, comment #2: 

See the end of scripts/pkg/private/get_forge_pkg.m.  I'm pretty sure I wrote it and it is pretty dumb.


    ## Try a simplistic method to determine similar names.
    function d = fdist (x)
      len1 = length (name);
      len2 = length (x);
      if (len1 <= len2)
        d = sum (abs (name(1:len1) - x(1:len1))) + sum (x(len1+1:end));
      else
        d = sum (abs (name(1:len2) - x(1:len2))) + sum (name(len2+1:end));
      endif
    endfunction
    dist = cellfun ("fdist", t);
    [~, i] = min (dist);
    error ("get_forge_pkg: package not found: ""%s"".  Maybe you meant ""%s?""",
           name, t{i});


Additional characters add a cost penalty assuming a reference of 0.  This can easily overwhelm distances in the first half of the calculation.

Rik <rik5>
Group administrator
Mon 17 Oct 2016 08:20:06 PM UTC, comment #1: 

Ok, disregard the last bit, I can see that the total distance between "sizzzz" and "zeromq" is less than the distance between "sizzzz" and "signal" despite having two identical letters in the first two positions.

The rest still stands, the string distance measurement is way off when two strings are mostly identical except for a single addition, deletion, or repetition.

Mike Miller <mtmiller>
Group Member
Mon 17 Oct 2016 07:56:07 PM UTC, original submission:  

When a user tries to install a Forge package, but gets the name wrong, a single name suggestion is shown:


>> pkg install -forge springs
error: get_forge_pkg: package not found: "springs".  Maybe you meant "strings?"


This works very well when the string length matches exactly. But when a single character is added or omitted, the metric it is using for similarity falls apart as it seems to be assigning a higher cost to having a different string length than to having every single character being wrong:


>> pkg install -forge imagel
error: get_forge_pkg: package not found: "imagel".  Maybe you meant "signal?"

>> pkg install -forge signa
error: get_forge_pkg: package not found: "signa".  Maybe you meant "video?"

>> pkg install -forge signals
error: get_forge_pkg: package not found: "signals".  Maybe you meant "sockets?"

>> pkg install -forge communication
error: get_forge_pkg: package not found: "communication".  Maybe you meant "generate_html?"


Also not sure why this case returns "zeromq" instead of "signal":


>> pkg install -forge sizzzz
error: get_forge_pkg: package not found: "sizzzz".  Maybe you meant "zeromq?"


Mike Miller <mtmiller>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by cdf
  • -email is unavailable- added by cdf
  • -email is unavailable- added by cdf (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mtmiller (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-10-18 cdf Carbon-Copy- Added -email is unavailable-
        Carbon-Copy- Added -email is unavailable-
        Carbon-Copy- Added -email is unavailable-
    2016-10-17 rik5 StatusNone Confirmed
    2016-10-17 mtmiller Priority5 - Normal 3 - Low

    Back to the top

    Powered by Savane 3.13-3230.
    Corresponding source code