7
\$\begingroup\$

I had to implement a function for getting the Levenshtein distance of two strings for a problem. It linked to the Wikipedia Article for Levenshtein distance and mentioned I can use the dynamic programming solution. Following is my implementation.

def levenshtein_distance(s, t):
    m, n = len(s) + 1, len(t) + 1
    d = [[0] * n for _ in range(m)]

    for i in range(1, m):
        d[i][0] = i

    for j in range(1, n):
        d[0][j] = j

    for j in range(1, n):
        for i in range(1, m):
            substitution_cost = 0 if s[i - 1] == t[j - 1] else 1
            d[i][j] = min(d[i - 1][j] + 1,
                          d[i][j - 1] + 1,
                          d[i - 1][j - 1] + substitution_cost)

    return d[m - 1][n - 1]

This function did work and my code passed the test case but I'm not sure if this is the most optimum solution.

Any pointers or suggestions will be appreciated.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ You don't actually need such a big array (d) because you're only ever accessing two consecutive rows at a time. Hence a 2 x m array is sufficient, while accessing the two rows in an alternating fashion (à la j % 2). However, sometimes you're interested not just in the smallest distance but also what is the actual "path" through the array (as in: which operations do you have to apply to transform s into t), in which case you do need the full array. \$\endgroup\$
    – Thomas
    Oct 19 at 12:48
  • 1
    \$\begingroup\$ Correction, you don't even need the full array then - you could simply store the best "path" that lead to d[i][j%2] in a separate data structure -- which, however, would then take up the same size as storing the full d as you're currently doing. \$\endgroup\$
    – Thomas
    Oct 19 at 12:57
  • 1
    \$\begingroup\$ I personally would find it easier to read without the blank lines between the for loops. But PEP8 leaves that up to the author's judgment, using blank lines to separate logical sections is apparently fine. I'd be interested to hear a more experienced opinion on blank lines in short functions. \$\endgroup\$ Oct 19 at 22:51
13
\$\begingroup\$

Documentation

Add a docstring for levenshtein_distance which explains what Levenshtein distance is. Explain the algorithm (or give a link to some existing explanation) if easy. I count about 5 sections in the algorithm--put a comment above each to explain what it's doing. Not all code needs a lot of comments, but algorithms do.

Variable names

Your names here are: d, s, t, i, j, m, and substitution_cost. One of these is not like the others. Make all of them have descriptive names like substitution_cost.

Tests

You're worried your algorithm is not correct. So add some explicit tests and test cases.

Optimality

Time how long your function takes on various lengths of string. Measure the runtime experimentally to make sure it's what you expect.

\$\endgroup\$
1
\$\begingroup\$

Kill two birds with one stone, documented examples and testing, by using doctests:

def levenshtein_distance(s, t):
    """Return the Levenshtein edit distance between t and s.
    
    >>> levenshtein_distance('kitten', 'sitting')
    3
    >>> levenshtein_distance('flaw', 'lawn')
    2
    """

Test the that your code produces these expected results with

python -mdoctest levenshtein.py

Take the chance to write a good docstring too.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Do note that doctests aren't a substitute for tests nor a substitute for documentation: they serve a number of adjacent purposes, but primarily they supplement (and verify the correctness of) documentation. Ideally, every bug you encounter gets a test once fixed (or potentially prior to fixing in TDD), but you don't want that in your documentation! \$\endgroup\$
    – CtrlAltF2
    Oct 20 at 2:47
0
\$\begingroup\$

Just in case you might be interested in a memoized version. (Maybe somewhat cleaner, but slower by a constant factor.)

#!/usr/bin/env python3

from functools import cache


def levenshtein_distance(s, t):
    '''
    >>> levenshtein_distance("snowy", "sunny")
    3
    '''

    @cache
    def d(i, j):
        return (
            i if j == 0 else
            j if i == 0 else
            d(i - 1, j - 1) if s[i - 1] == t[j - 1] else
            min(
                d(i - 1, j) + 1,
                d(i, j - 1) + 1,
                d(i - 1, j - 1) + 1
            )
        )

    return d(len(s), len(t))

if __name__ == "__main__":
    import doctest
    doctest.testmod()
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why are you including #!/usr/bin/env python3 this is not neccecary for Python 3. Why are you using lru_cache? From Python 3.9 the standard is @cache docs.python.org/3/library/functools.html. Not super happy with your formating either, this is what black gives: pastebin.com/EShFq31D. Assert should only be used for testing, not production code. It would be clearer using docs.python.org/3/library/doctest.html. \$\endgroup\$ Oct 19 at 22:15
  • \$\begingroup\$ Good points, thanks. For this purpose I don't like the way black formats the if .. else construct. Should use doctest, no doubt, but didn't know it. Mainly just wanted to show how a memoized version can avoid the explicit array management. \$\endgroup\$
    – Neal Young
    Oct 20 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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