Modify Damerau-Levenshtein algorithm to track transformations (insertions, deletions, etc)

Question

I'm wondering how to modify the Damerau-Levenshtein algorithm to track the specific character transformations required to change a source string to a target string. This question has been answered for the Levenshtein distance, but I couldn't find any answers for DL distance.

I looked at the py-Levenshtein module: it provides exactly what I need, but for Levenshtein distance:

Levenshtein.editops("FBBDE", "BCDASD")
[('delete', 0, 0), ('replace', 2, 1), ('insert', 4, 3), ('insert', 4, 
4), ('replace', 4, 5)]

The code for editops was difficult to decipher since it's written in C. I wonder how tracking transformations the can be done efficiently: I imagine it is possible from the distance matrix, which looks something like:

      r  e  p  u  b  l  i  c  a  n
   0  1  2  3  4  5  6  7  8  9  10
d  1  1  2  3  4  5  6  7  8  9  10
e  2  2  1  2  3  4  5  6  7  8  9
m  3  3  2  2  3  4  5  6  7  8  9
o  4  4  3  3  3  4  5  6  7  8  9
c  5  5  4  4  4  4  5  6  6  7  8
r  6  5  5  5  5  5  5  6  7  7  8
a  7  6  6  6  6  6  6  6  7  7  8
t  8  7  7  7  7  7  7  7  7  8  8

Answer 1

import numpy as np

def levenshtein_distance(string1, string2):
    n1 = len(string1)
    n2 = len(string2)
    return _levenshtein_distance_matrix(string1, string2)[n1, n2]

def damerau_levenshtein_distance(string1, string2):
    n1 = len(string1)
    n2 = len(string2)
    return _levenshtein_distance_matrix(string1, string2, True)[n1, n2]

def get_ops(string1, string2, is_damerau=False):
    i, j = _levenshtein_distance_matrix(string1, string2, is_damerau).shape
    i -= 1
    j -= 1
    ops = list()
    while i != -1 and j != -1:
        if is_damerau:
            if i > 1 and j > 1 and string1[i-1] == string2[j-2] and string1[i-2] == string2[j-1]:
                if dist_matrix[i-2, j-2] < dist_matrix[i, j]:
                    ops.insert(0, ('transpose', i - 1, i - 2))
                    i -= 2
                    j -= 2
                    continue
        index = np.argmin([dist_matrix[i-1, j-1], dist_matrix[i, j-1], dist_matrix[i-1, j]])
        if index == 0:
            if dist_matrix[i, j] > dist_matrix[i-1, j-1]:
                ops.insert(0, ('replace', i - 1, j - 1))
            i -= 1
            j -= 1
        elif index == 1:
            ops.insert(0, ('insert', i - 1, j - 1))
            j -= 1
        elif index == 2:
            ops.insert(0, ('delete', i - 1, i - 1))
            i -= 1
    return ops

def execute_ops(ops, string1, string2):
    strings = [string1]
    string = list(string1)
    shift = 0
    for op in ops:
        i, j = op[1], op[2]
        if op[0] == 'delete':
            del string[i + shift]
            shift -= 1
        elif op[0] == 'insert':
            string.insert(i + shift + 1, string2[j])
            shift += 1
        elif op[0] == 'replace':
            string[i + shift] = string2[j]
        elif op[0] == 'transpose':
            string[i + shift], string[j + shift] = string[j + shift], string[i + shift]
        strings.append(''.join(string))
    return strings

def _levenshtein_distance_matrix(string1, string2, is_damerau=False):
    n1 = len(string1)
    n2 = len(string2)
    d = np.zeros((n1 + 1, n2 + 1), dtype=int)
    for i in range(n1 + 1):
        d[i, 0] = i
    for j in range(n2 + 1):
        d[0, j] = j
    for i in range(n1):
        for j in range(n2):
            if string1[i] == string2[j]:
                cost = 0
            else:
                cost = 1
            d[i+1, j+1] = min(d[i, j+1] + 1, # insert
                              d[i+1, j] + 1, # delete
                              d[i, j] + cost) # replace
            if is_damerau:
                if i > 0 and j > 0 and string1[i] == string2[j-1] and string1[i-1] == string2[j]:
                    d[i+1, j+1] = min(d[i+1, j+1], d[i-1, j-1] + cost) # transpose
    return d

if __name__ == "__main__":
    # GIFTS PROFIT
    # FBBDE BCDASD
    # SPARTAN PART
    # PLASMA ALTRUISM
    # REPUBLICAN DEMOCRAT
    # PLASMA PLASMA
    # FISH IFSH
    # STAES STATES
    string1 = 'FISH'
    string2 = 'IFSH'
    for is_damerau in [True, False]:
        if is_damerau:
            print('=== damerau_levenshtein_distance ===')
        else:
            print('=== levenshtein_distance ===')
        dist_matrix = _levenshtein_distance_matrix(string1, string2, is_damerau=is_damerau)
        print(dist_matrix)
        ops = get_ops(string1, string2, is_damerau=is_damerau)
        print(ops)
        res = execute_ops(ops, string1, string2)
        print(res)

Output:

=== damerau_levenshtein_distance ===
[[0 1 2 3 4]
 [1 1 1 2 3]
 [2 1 1 2 3]
 [3 2 2 1 2]
 [4 3 3 2 1]]
[('transpose', 1, 0)]
['FISH', 'IFSH']
=== levenshtein_distance ===
[[0 1 2 3 4]
 [1 1 1 2 3]
 [2 1 2 2 3]
 [3 2 2 2 3]
 [4 3 3 3 2]]
[('replace', 0, 0), ('replace', 1, 1)]
['FISH', 'IISH', 'IFSH']