Write a program to implement the “Edit Distance” problem using top-down dynamic

Question

Write a program to implement the “Edit Distance” problem using top-down dynamic programming as discussed in class. Your program should read from an input file that looks like the following:

String1           // First string. Max length 20 chars.

String2           // First string. Max length 20 chars.

Your program should output the value of the edit distance between the two input strings.

your program should print the character positions at which the operators are applied (insert, delete, substitute).

Example output:

            CAVITATES

CAPTIVATE

     Edit distance was 4.

Insert P at position 3.

     Replace V with T at position 4.

     Replace T with V at position 6.

Delete S at position 10.

Submit your program with the results for the following input files:

IMPLICATED

INEXPLICABLE

SPRING

SUMMER

ABABABA

AABABAABA

Explanation / Answer

Pythan Code:

def edit_dist_matrix(a, b):

    """Generate the edit distance matrix for transforming string a into string b."""

    Create an empty len(a)+1 x len(b)+1 matrix ("d" below)

    Fill the matrix with the base case values

    Loop though each INDUCTIVE case row (sub-strings of a)

       Loop through each INDUCTIVE case column (sub-strings of b)

           if the corresponding characters of a & b are the same (watch the indexing here!), d[i][j] = d[i-1][j-1]

           else d[i][j] = 1 + the minimum of d[i, j-1], d[i-1][j], d[i-1][j-1]

    return the matrix

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.