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

 
 

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

Submitted by:  Mike Miller <mtmiller>
Submitted on:  Mon 17 Oct 2016 07:56:07 PM UTC  
 
Category: Octave FunctionSeverity: 2 - Minor
Priority: 3 - LowItem Group: Incorrect Result
Status: ConfirmedAssigned to: None
Originator Name: Open/Closed: Open
Release: devOperating System: Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project 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>
Project 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>
Project 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?

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>
Project 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.

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>
Project 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>
Project Administrator
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:

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:

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

Mike Miller <mtmiller>
Project Administrator

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 18 Oct 2016 09:53:10 AM UTCcdfCarbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added -unavailable-
    Mon 17 Oct 2016 09:47:06 PM UTCrik5StatusNone=>Confirmed
    Mon 17 Oct 2016 08:20:06 PM UTCmtmillerPriority5 - Normal=>3 - Low

    Back to the top


    Powered by Savane 3.1-cleanup1