Skip to content

Instantly share code, notes, and snippets.

@joaoceron

joaoceron/levenshtein

Created July 14, 2020 08:25
Show Gist options
  • Save joaoceron/f9938257179575e1e408af566ddff214 to your computer and use it in GitHub Desktop.
Save joaoceron/f9938257179575e1e408af566ddff214 to your computer and use it in GitHub Desktop.
Download ZIP
levenshtein
Raw
levenshtein
def levenshtein(seq1, seq2):
size_x = len(seq1) + 1
size_y = len(seq2) + 1
matrix = np.zeros ((size_x, size_y))
for x in range(size_x):
matrix [x, 0] = x
for y in range(size_y):
matrix [0, y] = y
for x in range(1, size_x):
for y in range(1, size_y):
if seq1[x-1] == seq2[y-1]:
matrix [x,y] = min(
matrix[x-1, y] + 1,
matrix[x-1, y-1],
matrix[x, y-1] + 1
)
else:
matrix [x,y] = min(
matrix[x-1,y] + 1,
matrix[x-1,y-1] + 1,
matrix[x,y-1] + 1
)
print (matrix)
return (matrix[size_x - 1, size_y - 1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment