编辑距离求解算法分析

编辑距离是一种衡量两个相似字符串相似性的度量方法。距离越大相似度越小。具体地，两个字符串的编辑距离是其中一个字符串要变换为另一个字符串所需要的最小编辑次数。其中编辑操作包含3种：增加一个字符，删除一个字符，更改一个字符。

使用编辑距离可以用来进行用户输入纠错。比如sql语句有select insert update insert等合法命令，若用户输入selet，则可以计算selet与合法命令的编辑距离，找到距离最近的命令(select)提示用户进行更正。当然，编辑距离不止于此。

计算编辑距离的源码如下

    public static int editDist(String a, String b, int i, int j) {
        if (i == -1 || j == -1) {
            return Math.max(i+1, j+1);
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(editDist(a, b, i - 1, j) + 1);
        list.add(editDist(a, b, i, j - 1) + 1);
        list.add(editDist(a, b, i - 1, j - 1) + (a.charAt(i) == b.charAt(j) ? 0 : 1));
        return Collections.min(list);
    }

计算编辑距离的程序虽然简短，但并不简单。其并不是企图将其中一个字符串通过编辑变为另外一个，而是利用了编辑距离的如下性质:

假设字符串s1，s2经过编辑操作变换后变为t1，t2。则若s1，s2都应用了相同的编辑操作，则s1与s2的编辑距离应该等于t1与t2的编辑距离，否则s1，s2的编辑距离为t1与t2编辑距离加上不同的编辑操作次数。

利用如上性质，我们可以设计一些操作将两个字符串s1，s2经过最小次编辑后都变为空串。由于t1，t2变为空，编辑距离为0，则最小的不同编辑次数就是所求的编辑距离。

于是算法设计了三种编辑操作，目的是将两个字符串分别约简为空串。涉及的操作有两种

1. 删除第一个字符串的末尾字符
2. 删除第二个字符串的末尾字符
3. 同时删除两个字符串的末尾字符

很显然操作1,2会增加原始字符串的编辑距离，而操作3若删除的字符相同则不增加编辑距离，否则也增加编辑距离。

经过如上定义，求编辑距离的问题就转化为如何用最小的编辑距离距离增量将两个字符串都约简为空串。

算法用动态规划来解决这个转化后的问题，故而得到如上算法。

通过编辑距离分析编辑距离的求解方法，我们可以得到启示，有时候可以利用定义本身的性质来将原问题转化为更易解决的问题，再去变成实现。