Natural Language Processing · 免费预览
用动态规划求最小编辑距离
插入、删除、替换代价；带示例表格的动态规划递推；回溯对齐及加权变体。
1. Minimum Edit Distance by Dynamic Programming
Minimum Edit Distance by Dynamic Programming
2. The dynamic programming recurrence
The dynamic programming recurrence
3. Computing distance and alignment with NumPy
Computing distance and alignment with NumPy
4. Distance by pure insertion
What is the minimum edit distance between "fog" and "fbog" (insert, delete, substitute all cost 1)?
5. Levenshtein distance
Compute the minimum edit distance between "reef" and "crane" (insertions, deletions, substitutions each cost 1).
6. Substitution cost two
Compute the minimum edit distance between "reef" and "crane" when insertions and deletions cost 1 and substitutions cost 2.
7. Asymmetric edit costs
Compute the minimum edit cost between "reef" and "crane" with deletion cost 1, insertion cost 2, and substitution cost 1.5. Round your answer to one decimal place.
8. Bounds on the distance
For arbitrary strings of lengths 4 and 5 (such as "reef" and "crane"), which statement about their minimum edit distance (all costs 1) is always true?