应用

最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中，详细如下： （特别的，对于中文自然语言处理，一般以词为基本处理单元）

全局序列比对尝试找到两个完整的序列 和 之间的最佳比对。以下面两个 DNA 序列为例：

= GCCCTAGCG

= GCGCAATG

如果为每个匹配字符一分，一个空格扣两分，一个不匹配字符扣一分，那么下面的比对就是全局最优比对：

= GCCCTAGCG

= GCGC-AATG

连字符（-）代表空格。在 中有五个匹配字符，一个空格（或者反过来说，在 中有一个插入项），有三个不匹配字符。这样得到的分数是 (5 * 1) + (1 * -2) + (3 * -1) = 0，这是能够实现的最佳结果。

使用局部序列比对，不必对两个完整的序列进行比对，可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 和 ，以及同样的得分方案，可以得到以下局部最优比对 和 ：

= GCCCTAGCG

= GCG

= GCG

= GCGCAATG

这个局部比对的得分是 (3 * 1) + (0 * -2) + (0 * -1) = 3。

这里肯定有人有疑问：对每个不在词典中的词（假如长度为len）都与词典中的词条计算最小编辑距离，时间复杂度是不是太高了？的确，所以一般需要加一些剪枝策略，如：

具体的，可以将候选文本串与词典中的每个实体名进行编辑距离计算，当发现文本中的某一字符串的编辑距离值小于给定阈值时，将其作为实体名候选词；获取实体名候选词后，根据所处上下文使用启发式规则或者分类的方法判定候选词是否的确为实体名。

算法

动态规划经常被用来作为这个问题的解决手段之一。