编辑距离（Edit Distance）是指将一个字符串转化成另一个字符串所需要的最少操作次数，该操作包括插入一个字符、删除一个字符、替换一个字符。在自然语言处理领域，有时需要根据两个文本之间的差异程度进行比较，此时就可以采用编辑距离作为衡量依据。
例如：字符串A为‘kitten’，字符串B为‘sitting’，将A转化成B需要3步：将k替换成s、删除第二个t、在最后插入g。因此，字符串A和字符串B的编辑距离为3。
引入概念后，接下来我们用Python实现编辑距离算法。
Python代码：
# EDIT TABLE
# +-------+...+-------+
# | 0 | k | i | t | t | e | n |
# +-------+...+-------+
# | k | 0 | 1 | 2 | 3 | 4 | 5 |
# +-------+...+-------+
# | s | 1 | 1 | 2 | 3 | 4 | 5 |
# | +-------+...+-------+
# | i | 2 | 2 | 1 | 2 | 3 | 4 |
# +-------+...+-------+
# | t | 3 | 3 | 2 | 1 | 2 | 3 |
# +-------+...+-------+
# | t | 4 | 4 | 3 | 2 | 1 | 2 |
# | +-------+...+-------+
# | i | 5 | 5 | 4 | 3 | 2 | 3 |
# +-------+...+-------+
# | n | 6 | 6 | 5 | 4 | 3 | 2 |
# +-------+...+-------+
如上图，可以看到当字符串A为‘kitten’，字符串B为‘sitting’时，对应的编辑距离矩阵的过程。因此字符串A和字符串B的编辑距离为3。
