Dynamic Programming on Two Sequences
Longest common subsequence and edit distance both fill a grid where each cell asks one question about the last character of each string. The table gives the answer, and walking back through it gives the alignment that produced it.
What a learner can do afterwards
- Fill an edit distance table for two short words and read the answer off the corner
- Trace back through the table to recover the actual edits
- Explain deletion, insertion and diagonal pairing in the edit-distance recurrence, and distinguish its minimum from the LCS maximum
1 · Read
As in earlier dynamic programming, first name the subproblem. Put source string S down the rows and target string T across the columns. D(i,j) is the minimum edit cost from the first i source characters to the first j target characters. Row 0 and column 0 represent empty prefixes. For lengths m and n, D(m,n) answers the full problem.
Use unit costs: insertion, deletion and substitution each cost 1; matching characters costs 0. Initialize D(i,0)=i because removing i characters takes i deletions. Initialize D(0,j)=j because building j characters from empty takes j insertions. D(0,0)=0. The displayed cells show the start of row 0.
For i,j above 0, compare three costs. Delete the last source character: D(i-1,j)+1. Insert the last target character: D(i,j-1)+1. Pair the last characters: D(i-1,j-1)+a, where a is 0 for a match and 1 for a substitution. D(i,j) is their minimum. Fill from shorter prefixes so these neighbors are already known.
For MAP to MOP, rows use empty, M, MA, MAP and columns use empty, M, MO, MOP. The displayed row lists give the completed table. Its final entry is 1. A traceback pairs M with M, substitutes O for A, and pairs P with P. Only the substitution has a cost.
Trace back from D(m,n). Move only to a predecessor whose value plus its move cost equals the current value. Up records a deletion, left an insertion, and diagonal a match or substitution. Reverse the recorded moves to perform them from the start. Tied predecessors can give different edit sequences with the same minimum cost.
Longest common subsequence, or LCS, keeps character order but allows gaps. L(i,j) is the longest shared subsequence length for the two prefixes. Empty-prefix values are 0. Matching last characters give L(i-1,j-1)+1. On a mismatch use max(L(i-1,j),L(i,j-1)). For AX and AY the length is 1, from A. LCS maximizes length; edit distance minimizes cost.
To recover an LCS, start at L(m,n). When the last characters match, record that character and move diagonally. Otherwise move up or left to a cell with the same value as the current cell. A tie allows either move. Stop when a prefix is empty, then reverse the recorded characters. For AX and AY, skip X and Y, then record the matching A.
Define prefix states and boundaries. Minimize edit costs or maximize LCS length. Trace back through transitions that preserve the final value.
Original lesson, questions, worked solutions and flashcards written for this dataset.
2 · Watch
به انگلیسیTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.