NLP: Edit distance with custom costs

Compute edit distance when insertions, deletions and substitutions have different costs.

What to build

A program that computes weighted edit distances with dynamic programming.

Requirements

  • Line 1 gives the costs of an insertion, a deletion and a substitution. Turning a into b, a deletion removes a character of a and an insertion adds a character of b; matching characters cost 0.
  • For each pair print a -> b: D, the minimum total cost.

Input

Line 1: three integer costs. Line 2: n. Then n lines with two words.

Output

n lines.

Constraints

Costs from 1 to 10; words have at most 100 characters.

Example

Input:

1 1 1
2
kitten sitting
flaw lawn

Output:

kitten -> sitting: 3
flaw -> lawn: 2

Why it works

The cheapest way to turn a prefix of a into a prefix of b must end with a deletion, an insertion or a substitution (or a free match), so each cell is the best of those three options built on smaller prefixes.

Examples

Example 1 · Input
1 1 1
2
kitten sitting
flaw lawn
Expected output
kitten -> sitting: 3
flaw -> lawn: 2
Example 2 · Input
1 1 2
2
intention execution
cat cut
Expected output
intention -> execution: 8
cat -> cut: 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

The first row is `[j * ins for j in range(len(b) + 1)]` and each new row starts with `i * dele`.

Hint 2

Each cell is the minimum of the cell above + delete, the cell to the left + insert, and the diagonal + (0 or the substitution cost).

Solution

Show one correct solution (try it yourself first)
ins, dele, sub = map(int, input().split())
for _ in range(int(input())):
    a, b = input().split()
    prev = [j * ins for j in range(len(b) + 1)]
    for i in range(1, len(a) + 1):
        cur = [i * dele]
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else sub
            cur.append(min(prev[j] + dele, cur[j - 1] + ins, prev[j - 1] + cost))
        prev = cur
    print(f"{a} -> {b}: {prev[-1]}")

Lesson: Edit distance and spelling correction →