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

 Submitted by: Mike Miller Submitted on: 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

You are not logged in

Discussion

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

> string distances in an old version of odepkg that was based
> on Levenshtein metric
>

That's on the strings package too, named edit_distance

CarnĂ« Draug <carandraug>
Tue 18 Oct 2016 10:16:38 AM UTC, comment #5:

Sorry, the link to levenshtein.m was incorrect,

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

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

Hi,

string distances in an old version of odepkg that was based
on Levenshtein metric

The code can be recovered from the repository here:

or here

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>
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>
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);
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>
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>
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

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

>> pkg install -forge signa

>> pkg install -forge signals

>> pkg install -forge communication

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

>> pkg install -forge sizzzz

Mike Miller <mtmiller>

Attached Files

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

Attach Files:

Comment:

No files currently attached

Dependencies

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)
•

Do you think this task is very important?
This task has 0 encouragements so far.

Only project members can vote.