I need a function that checks how different are two different strings. I chose the Levenshtein distance as a quick approach, and implemented this function:

from difflib import ndiff



def calculate_levenshtein_distance(str_1, str_2):

    """

        The Levenshtein distance is a string metric for measuring the difference between two sequences.

        It is calculated as the minimum number of single-character edits necessary to transform one string into another

    """

    distance = 0

    buffer_removed = buffer_added = 0

    for x in ndiff(str_1, str_2):

        code = x[0]

        # Code ? is ignored as it does not translate to any modification

        if code == ' ':

            distance += max(buffer_removed, buffer_added)

            buffer_removed = buffer_added = 0

        elif code == '-':

            buffer_removed += 1

        elif code == '+':

            buffer_added += 1

    distance += max(buffer_removed, buffer_added)

    return distance

Then calling it as:

similarity = 1 - calculate_levenshtein_distance(str_1, str_2) / max(len(str_1), len(str_2))

How sloppy/prone to errors is this code? How can it be improved?

There is a module available for exactly that calculation, python-Levenshtein. You can install it with pip install python-Levenshtein.

It is implemented in C, so is probably faster than anything you can come up with yourself.

from Levenshtein import distance as levenshtein_distance

According to the docstring conventions, your docstring should look like this, i.e. with the indentation aligned to the """ and the line length curtailed to 80 characters.

def calculate_levenshtein_distance(str_1, str_2):

    """

    The Levenshtein distance is a string metric for measuring the difference

    between two sequences.

    It is calculated as the minimum number of single-character edits necessary to

    transform one string into another.

    """

    ...

The code itself is rather clear. There are some smaller changes I would make

tuple unpacking

You can use tuple unpacking to do:

for code, *_ in ndiff(str1, str2):

instead of:

for x in ndiff(str_1, str_2):

    code = x[0]

dict results:

Instead of a counter for the additions and removals, I would keep it in 1 dict: counter = ({"+": 0, "-": 0})

def levenshtein_distance(str1, str2, ):

    counter = {"+": 0, "-": 0}

    distance = 0

    for edit_code, *_ in ndiff(str1, str2):

        if edit_code == " ":

            distance += max(counter.values())

            counter = {"+": 0, "-": 0}

        else: 

            counter[edit_code] += 1

    distance += max(counter.values())

    return distance

generators

A smaller, less useful variation, is to let this method be a generator, and use the builtin sum to do the summary. this saves 1 variable inside the function:

def levenshtein_distance_gen(str1, str2, ):

    counter = {"+": 0, "-": 0}

    for edit_code, *_ in ndiff(str1, str2):

        if edit_code == " ":

            yield max(counter.values())

            counter = {"+": 0, "-": 0}

        else: 

            counter[edit_code] += 1

    yield max(counter.values())



sum(levenshtein_distance_gen(str1, str2))

timings

The differences in timings between the original and both these variations are minimal, and within the variation of results. This is rather logical, since for simple strings (aaabbbc and abcabcabc) 90% of the time is spent in ndiff