2
$\begingroup$

I am looking for an algorithm that checks if the Levenshtein distance between two strings $s_1$ and $s_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating the Levenshtein distance, but I expect a possible efficiency gain in scenarios where $B$ << $Levenshtein(s_1, s_2)$, because an algorithm not aiming to determine the actual distance, but just aiming to answer the question whether the distance is below $B$ or not, can terminate earlier, as soon as it becomes clear that the distance must surpass $B$.

For such an algorithm, I have the idea of using a recursive function which takes the parameters $s_1$, $s_2$ and $B$ checks if the first character of $s_1$ and $s_2$ are equal, and recursively calls itself (with a potentially decremented $B$ and accordingly adapted $s_1$ and $s_2$). The function would sort out all scenarios where $B$ falls below 0. (And of course, the function will make use of the trivial lower bounds of $Levenshtein(s_1, s_2)$.) If no recursion branch is left, the algorithm would terminate, asserting $Levenshtein(s_1, s_2) \geq B$.

But before reinventing the wheel, I wanted to ask if there are already existing solutions for my problem. I googled this and didn't find any, but maybe my google results were just polluted with the Levenshtein Distance Algorithms. If there is no such algorithm yet, is my approach a good idea, or are there more efficient ways which I oversee?

$\endgroup$
6
  • $\begingroup$ (The insight exceedin a distance limit should be possible early on is vary valid.) I googled this and didn't find any try with Levenshtein|Левенште́йн - you should find, amongst others, Ukkonen. $\endgroup$
    – greybeard
    Commented Sep 28, 2020 at 9:58
  • $\begingroup$ @greybeard Thanks! I think, Ukkonen was the keyword I was missing. $\endgroup$ Commented Sep 28, 2020 at 10:14
  • $\begingroup$ (My suggestion isn't to add Ukkonen as a keyword, but look for his papers on the subject(/implementations) to appear as a check whether the search was formulated in a promising way.) $\endgroup$
    – greybeard
    Commented Sep 28, 2020 at 10:32
  • $\begingroup$ @greybeard Yes I got it. Withour your comment, I just didn't even know of the existing of Ukkonen's algorithm. $\endgroup$ Commented Sep 28, 2020 at 10:33
  • $\begingroup$ cs.stackexchange.com/q/27539/755 $\endgroup$
    – D.W.
    Commented Oct 1, 2020 at 23:58

1 Answer 1

1
$\begingroup$

You may be interested in this implementation: https://github.com/fujimotos/polyleven

$\endgroup$
2
  • 2
    $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. $\endgroup$
    – xskxzr
    Commented Sep 4, 2021 at 5:27
  • 1
    $\begingroup$ Polyleven is a fast Levenshtein distance library for Python. $\endgroup$ Commented Sep 5, 2021 at 7:45

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.