iframe-proxy | Sunbelt Computer Software

History

76 lines (60 loc) · 2.19 KB

Raw

"""

This is a Python implementation of the levenshtein distance.

Levenshtein distance is a string metric for measuring the

difference between two sequences.

For doctests run following command:

python -m doctest -v levenshtein-distance.py

python3 -m doctest -v levenshtein-distance.py

For manual testing run:

python levenshtein-distance.py

"""

def levenshtein_distance(first_word, second_word):

"""Implementation of the levenshtein distance in Python.

:param first_word: the first word to measure the difference.

:param second_word: the second word to measure the difference.

:return: the levenshtein distance between the two words.

Examples:

>>> levenshtein_distance("planet", "planetary")

>>> levenshtein_distance("", "test")

>>> levenshtein_distance("book", "back")

>>> levenshtein_distance("book", "book")

>>> levenshtein_distance("test", "")

>>> levenshtein_distance("", "")

>>> levenshtein_distance("orchestration", "container")

"""

# The longer word should come first

if len(first_word) < len(second_word):

return levenshtein_distance(second_word, first_word)

if len(second_word) == 0:

return len(first_word)

previous_row = range(len(second_word) + 1)

for i, c1 in enumerate(first_word):

current_row = [i + 1]

for j, c2 in enumerate(second_word):

# Calculate insertions, deletions and substitutions

insertions = previous_row[j + 1] + 1

deletions = current_row[j] + 1

substitutions = previous_row[j] + (c1 != c2)

# Get the minimum to append to the current row

current_row.append(min(insertions, deletions, substitutions))

# Store the previous row

previous_row = current_row

# Returns the last element (distance)

return previous_row[-1]

if __name__ == "__main__":

first_word = input("Enter the first word:\n").strip()

second_word = input("Enter the second word:\n").strip()

result = levenshtein_distance(first_word, second_word)

print(

"Levenshtein distance between {} and {} is {}".format(

first_word, second_word, result

)

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

levenshtein_distance.py

Latest commit

History

levenshtein_distance.py

File metadata and controls