最小編輯距離通常作為一種相似度計算函式被用於多種實際套用中，詳細如下： （特別的，對於中文自然語言處理，一般以詞為基本處理單元）
全局序列比對嘗試找到兩個完整的序列 和 之間的最佳比對。以下面兩個 DNA 序列為例：
= GCCCTAGCG
= GCGCAATG
如果為每個匹配字元一分，一個空格扣兩分，一個不匹配字元扣一分，那么下面的比對就是全局最優比對：
= GCCCTAGCG
= GCGC-AATG
套用,算法,pascal代碼,
套用
最小編輯距離通常作為一種相似度計算函式被用於多種實際套用中，詳細如下： （特別的，對於中文自然語言處理，一般以詞為基本處理單元）
全局序列比對嘗試找到兩個完整的序列 和 之間的最佳比對。以下面兩個 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）都與詞典中的詞條計算最小編輯距離，時間複雜度是不是太高了？的確，所以一般需要加一些剪枝策略，如：
具體的，可以將候選文本串與詞典中的每個實體名進行編輯距離計算，當發現文本中的某一字元串的編輯距離值小於給定閾值時，將其作為實體名候選詞；獲取實體名候選詞後，根據所處上下文使用啟發式規則或者分類的方法判定候選詞是否的確為實體名。
算法
動態規劃經常被用來作為這個問題的解決手段之一。
整數 Levenshtein距離(字元串 str1[1..m], 字元串 str2[1..n])
//聲明變數， d[i , j]用於記錄str1[1...i]與str2[1..j]的Levenshtein距離
int d[0..m, 0..n]
//初始化
for i from 0 to m
d[i, 0] := i
for j from 0 to n
d[0, j] := j
//用動態規劃方法計算Levenshtein距離
for i from 1 to m
for j from 1 to n
{
//計算替換操作的代價，如果兩個字元相同，則替換操作代價為0，否則為1
if str1[i]== str2[j] then cost := 0
else cost := 1
//d[i,j]的Levenshtein距離，可以有
d[i, j] := minimum(
d[i-1, j] + 1, //在str1上i位置刪除字元（或者在str2上j-1位置插入字元）
d[i, j-1] + 1, //在str1上i-1位置插入字元（或者在str2上j位置刪除字元）
d[i-1, j-1] + cost // 替換操作
)
}
//返回d[m, n]
return d[m, n]
wikisource上有不同的程式語言的版本。
pascal代碼
procedure levenshtein;
var
st1,st2:string;
d:array[0..1000000] of integer;
i,j,m,n,cost:integer;
begin
m:=length(st1);
n:=length(st2);
for i:=0 to m do
d[i,0]:=i;
for j:= 0 to n do
d[0,j]:=j;
for i:= 1 to m do
for j:= 1 to n do
begin
if st1[i]=st2[j] then
cost:=0
else cost:=1;
if cost=0 then
begin
if (d[i-1,j]
then d[i,j]:=d[i-1,j]+1
else if d[i,j-1]+1< d[i-1,j-1]+cost
then d[i,j]:=d[i,j-1]+1
else d[i,j]:=d[i-1,j-1]+cost;
end;
end;
