1. 什么是“编辑距离” ?
“编辑距离”又称 Leveinshtein 距离,是由俄罗斯科学家 Vladimir Levenshtein 在 1965 年提出。
“编辑距离”是计算两个文本相似度的算法之一,字符串 X 和字符串 Y 的编辑距离是将 X 转换成 Y 的最小操作次数,这里的操作包括三种:
例如:
kitten 和 sitting 的编辑距离是3。
至少要做3次操作。
图文无关:从入门到放弃
2. 基本策略 ?
... 当然还是传说中的 ...
线性规划
图文无关
递推公式如下
3. 程序代码 ?
4. 特性分析