2
$\begingroup$

I need to implement simple search on Python package names and I'm struggling with ranking the results. Considered Levenshtein distance, but it would give too low ranking for matches which contain the search term exactly but have a long extra prefix or suffix.

I was thinking of applying Levenshtein to each substring of the same length as the search term and then using the best result, but I'm hoping there is a more elegant solution.

Is there a well known algorithm, which considers both the length and the similarity of the match?

$\endgroup$
2
  • 3
    $\begingroup$ In Levenshtein, you can assign different costs to deletions, insertions and substitutions. You can also craft your own measure by combining the number of matches, insertions, deletions and substitutions. $\endgroup$
    – user16034
    Aug 21, 2023 at 7:23
  • 1
    $\begingroup$ General matching, with Levenshtein distance but parameters for deletions and substitutions, is called alignment in the context of computational biology. Global alignment matches full strings, but local alignment looks for local optimal matches. It is basically the same algorithm, but resets negative values. en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm $\endgroup$ Aug 22, 2023 at 1:22

2 Answers 2

3
$\begingroup$

It seems that in your context there can be prefixes or suffixes added to the substrings you care about, so for example you want the strings $w$ and $\alpha v \beta$ to be similar if $v$ and $w$ are themselves similar, with some penalty that depends on the length of the extra characters in $\alpha$ and $\beta$. This can be achieved in several ways:

  1. As Yves Daoust commented, if you're defining a variation of Levenshtein's distance you are free to assign different weights to deletions, insertions and substitutions. Moreover, the weight can also depend specifically on the characters; for example, you could consider that using 'n' instead of 'm' is a common typo, and thus will penalize an 'n'-'m' substitution less than a 'a'-'z' substitution.

  2. As suggested by Hendrik Jan's comment, the field of computational biology is extremely into the problem of (sub)-string similarity, and therefore their literature might be a great place to start. Here are some surveys found upon a quick Google search. String Similarity Search and Join : A Survey, A guided tour to approximate string matching, A Comparative Study on String Matching Algorithm of Biological Sequences

In order for anyone to be able to help you more precisely about defining a good similarity measure you'd need to provide the context of your application; there's not silver bullet here, and the best solution will depend on the specific constraints and goals of your context.

$\endgroup$
0
$\begingroup$

Jaro-Winkler distance could be what I need, as it has a performant implementation with permissive license (https://pypi.org/project/jarowinkler/)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.