HardNLPnlp-188

Substitution Insertion Deletion Counts

Problem

Return [substitutions, insertions, deletions] for the optimal Levenshtein alignment between reference and hypothesis.

Backtrack from the bottom-right cell and prefer, in order: an equal diagonal match, a diagonal substitution, an upward deletion, then a leftward insertion. Deletions are reference tokens missing from the hypothesis; insertions are extra hypothesis tokens.

Hint

The backtracking tie-breaking rule makes the counts deterministic.

Test cases

case 1

in: ["abc","abc"]

expected: [0,0,0]

case 2

in: ["abc","axc"]

expected: [1,0,0]

case 3

in: ["abc","ab"]

expected: [0,0,1]

case 4

in: ["ab","abc"]

expected: [0,1,0]

case 5

in: ["kitten","sitting"]

expected: [2,1,0]

Starter codePython

def sub_ins_del_counts(reference, hypothesis):
    # Your code here
    pass

5 test cases · run your code against them in the editor