|
Dynamic Programming DPalign.pl (5.682 Kb) Figure 5.05 (23.617 Kb) (chapter 5): Dynamic programming is a technique to, eg., align characters (and speech). DPalign.pl is a small program that can give you the best alignment between two strings. See "perl DPalign.pl --help" for help. See section 5.6, pages 153-156 + figure 5.6, of Jurafsky & Martin. Implement the edit distance algorithm from figure 5.05 (see link) in your favorit programming/scripting language, but include back-pointers to allow tracing the best alignment (use 'S', 'I', 'D' to indicate Substitution, Insertion, and Deletion). Test it on a few examples. NOTE: there are errors in the pseudo-code, e.g., the iterations should start at 1, not 0, and you should initialize the 0 column and row of the distance matrix Submit the "core" of the program with ample comments plus some example outputs. Compare your implementation with DPalign.pl and discuss any differences. |