對于 i 等于 由 0 至 lenStr1
d[i, 0] := i
對于 j 等于 由 0 至 lenStr2
d[0, j] := j
對于 i 等于 由 1 至 lenStr1
對于 j 等于 由 1 至 lenStr2
若 str1[i] = str2[j] 則 cost := 0
否則 cost := 1
d[i, j] := 最小值(
d[i-1, j　　] + 1,　　　　 // 刪除
d[i　　, j-1] + 1,　　　　 // 插入
d[i-1, j-1] + cost　　 // 替換
)
返回 d[lenStr1, lenStr2]

double Minimum(double a, double b, double c) 
{ 
double mi; 

　mi = a; 
if (b < mi) { 
mi = b; 
} 
if (c < mi) { 
mi = c; 
} 
return mi; 
} 

int* GetCellPointer(int *pOrigin, int col, int row, int nCols) 
{ 
return pOrigin + col + (row * (nCols + 1)); 
} 

int GetAt(int *pOrigin, int col, int row, int nCols) 
{ 
int *pCell; 

　pCell = GetCellPointer (pOrigin, col, row, nCols); 
return *pCell; 
} 

void PutAt(int *pOrigin, int col, int row, int nCols, double x) 
{ 
int *pCell; 
pCell = GetCellPointer (pOrigin, col, row, nCols); 
*pCell = x; 
} 

//編輯距離
LD(const char *s, const char *t)
{
int *d; // pointer to matrix
int n; // length of s
int m; // length of t
int i; // iterates through s
int j; // iterates through t
char s_i1; // ith character of s
char s_i2; // ith character of s
char t_j1; // jth character of t
char t_j2; // jth character of t
int *cost; // cost代價矩陣
int result; // result
int cell; // contents of target cell
int above; // contents of cell immediately above
int left; // contents of cell immediately to left
int diag; // contents of cell immediately above and to left
int sz; // number of cells in matrix

　// Step 1 

　n = strlen (s);
m = strlen (t);
if (n == 0) 
{
return m;
}
if (m == 0) 
{
return n;
}
sz = (n+1) * (m+1) * sizeof (int);
d = (int *) malloc (sz);
cost = (int *) malloc (sz);

　// Step 2

　for (i = 0; i <= n; i++) 
{
PutAt (d, i, 0, n, i);
}

　for (j = 0; j <= m; j++)
{
PutAt (d, 0, j, n, j);
}
for (int g=0;g<=m;g++)//把代價距離矩陣全部初始化為同一個值，以后可根據此值判斷相應的方格是否被賦過值
{
for(int h=0;h<=n;h++)
{
PutAt(cost,h,g,n,2);
}
}
// Step 3

　for (i = 1; i <= n; i++) 
{

　　s_i1 = s[i-1];
s_i2 = s[i];
bool sbd=false;
bool tbd=false;
if(s_i1>=' '&&s_i1<='@'||s_i1>='A'&&s_i1<='~')
{//s為標點符號或其他非中文符號和數字
sbd=true;
}
// Step 4

　　for (j = 1; j <= m; j++) 
{

　　 tbd=false;
t_j1 = t[j-1];
t_j2 = t[j];
// Step 5
if(t_j1>=' '&&t_j1<='@'||t_j1>='A'&&t_j1<='~')
{//t也為標點符號
tbd=true;
}
if(!sbd)
{//s為漢字
if(!tbd)
{//t也為漢字
if (s_i1 == t_j1&&s_i2 == t_j2) 
{
bool tt=false;
int temp=GetAt(cost,i,j,n);
if(temp==2)
{
PutAt(cost,i,j,n,0);
tt=true;
}
if(tt)
{//因為st全市漢字，所以把代價矩陣他相鄰的未賦過值的三個格賦值
int temp1=GetAt(cost,i+1,j,n);
if(temp1==2)
{
PutAt(cost,i+1,j,n,0);
}
int temp2=GetAt(cost,i,j+1,n);
if(temp2==2)
{
PutAt(cost,i,j+1,n,0);
}
int temp3=GetAt(cost,i+1,j+1,n);
if(temp3==2)
{
PutAt(cost,i+1,j+1,n,0);
}
}
}
else 
{
bool tt=false;
int temp=GetAt(cost,i,j,n);
if(temp==2)
{
PutAt(cost,i,j,n,1);
tt=true;
}
if(tt)
{
int temp1=GetAt(cost,i+1,j,n);
if(temp1==2)
{
PutAt(cost,i+1,j,n,1);
}
int temp2=GetAt(cost,i,j+1,n);
if(temp2==2)
{
PutAt(cost,i,j+1,n,1);
}
int temp3=GetAt(cost,i+1,j+1,n);
if(temp3==2)
{
PutAt(cost,i+1,j+1,n,1);
}
}
}
}
else
{//t為符號
bool tt=false;
int temp=GetAt(cost,i,j,n);
if(temp==2)
{
PutAt(cost,i,j,n,1);
tt=true;
}
if(tt)
{
int temp1=GetAt(cost,i+1,j,n);
if(temp1==2)
{
PutAt(cost,i+1,j,n,1);
}
}

　　　　}

　　 }
else
{//s為符號
if(!tbd)
{//t為漢字 
bool tt=false;
int temp=GetAt(cost,i,j,n);
if(temp==2)
{
PutAt(cost,i,j,n,1);
tt=true;
}
if(tt)
{
int temp1=GetAt(cost,i,j+1,n);
if(temp1==2)
{
PutAt(cost,i,j+1,n,1);
}
}
}
else
{
if(s_i1==t_j1)
{
int temp=GetAt(cost,i,j,n);
if(temp==2)
{
PutAt(cost,i,j,n,0);
}
}
else
{
int temp=GetAt(cost,i,j,n);
if(temp==2)
{
PutAt(cost,i,j,n,1);
}
}
}

　　 }

　　　　// Step 6 

　　 above = GetAt (d,i-1,j, n);
left = GetAt (d,i, j-1, n);
diag = GetAt (d, i-1,j-1, n);
int curcost=GetAt(cost,i,j,n);
cell = Minimum (above + 1, left + 1, diag + curcost);
PutAt (d, i, j, n, cell);
}
}

　　// Step 7

　　result = GetAt (d, n, m, n);
free (d);
return result;

}

2．最長公共子串 (LCS)

　　LCS問題就是求兩個字符串最長公共子串的問題。解法就是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對角線最長的1序列，其對應的位置就是最長匹配子串的位置。

　　下面是字符串21232523311324和字符串312123223445的匹配矩陣，前者為X方向的，后者為Y方向的。不難找到，紅色部分是最長的匹配子串。通過查找位置我們得到最長的匹配子串為：21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

　　但是在0和1的矩陣中找最長的1對角線序列又要花去一定的時間。通過改進矩陣的生成方式和設置標記變量，可以省去這部分時間。下面是新的矩陣生成方式：

　　　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

　　當字符匹配的時候，我們并不是簡單的給相應元素賦上1，而是賦上其左上角元素的值加一。我們用兩個標記變量來標記矩陣中值最大的元素的位置，在 矩陣生成的過程中來判斷當前生成的元素的值是不是最大的，據此來改變標記變量的值，那么到矩陣完成的時候，最長匹配子串的位置和長度就已經出來了。

//最長公共子串
char* LCS(char*left,char* right){
int lenLeft,lenRight;
lenLeft = strlen(left);
lenRight = strlen(right);
int *c = new int[lenRight];
int start,end,len;
end = len = 0;
for(int i = 0; i < lenLeft; i++){
for(int j = lenRight-1; j >= 0; j--){
if(left[i] == right[j]){
if(i == 0 || j == 0)
c[j] = 1;
else
c[j] = c[j-1]+1;
}
else
c[j] = 0;
if(c[j] > len){
len = c[j];
end = j;
}
}
}
char *p = new char[len+1];
start = end - len + 1;
for(i = start; i <= end; i++)
p[i - start] = right[i];
p[len] = '\0';
return p;
}

3. 余弦定理 (向量空間算法)

　　余弦定理古老而廣泛的數學概念，在各個學科及實踐中都得到了大量的應用，這里簡單的介紹下其在判斷兩個字符串相似度的應用。在余弦定理中基本的公式為：

　　假如字符串s1與s2，比較兩個字符串的相似度，sim(s1,s2)，假設s1,s2中含有n個不同的字符，其分別為c1,c2,... cn，判斷字符串的相似度轉換為兩個字符串對應的向量v1,v2之間夾角大小的判斷，余弦值越大其向量之間的夾角越小，s1與S2的相似度越大。

向量空間算法的介紹：

　　在向量空間模型中，文本泛指各種機器可讀的記錄。用D（Document）表示，特征項（Term，用t表示）是指出現在文檔D中且能夠代表該 文檔內容的基本語言單位，主要是由詞或者短語構成，文本可以用特征項集表示為D(T1，T2，...，Tn)，其中Tk是特征項，1<=k< =N。例如一篇文檔中有a、b、c、d四個特征項，那么這篇文檔就可以表示為D(a，b，c，d)。對含有n個特征項的文本而言，通常會給每個特征項賦予 一定的權重表示其重要程度。即D＝D(T1，W1；T2，W2；...，Tn，Wn)，簡記為D＝D(W1，W2，...，Wn)，我們把它叫做文本D的 向量表示。其中Wk是Tk的權重，1<=k<=N。在上面那個例子中，假設a、b、c、d的權重分別為30，20，20，10，那么該文本的 向量表示為D(30，20，20，10)。在向量空間模型中，兩個文本D1和D2之間的內容相關度Sim(D1，D2)常用向量之間夾角的余弦值表示，公 式為：　　 

　　其中，W1k、W2k分別表示文本D1和D2第K個特征項的權值，1<=k<=N。我們可以利用類似的方法來計算兩個字符串的相關度。　　　　
這個算法網上沒找到，雖然我寫過，但是沒什么通用性，就不貼出來。很簡單的，有興趣的可以自己寫一個。
 由 胡文青 在 十月 10, 2007 10:08 發貼 | 永久鏈接 superdullwolf

比較單詞相似度，必須首先切詞，英文單詞切詞法，combine排列組合的"組合"數學算法是關鍵。

下面代碼給出原子的一種思路：比如輸入單詞"spide"，輸出所有可能用來和其他單詞比較的原子,由于單詞長度是5，匹配度小于60%的沒意義，所以原子最小長度是3。

代碼是從C語言算法改過來的，同樣代碼也可以修改成任何編程語言。

ide
pde
sde
pie
sie
spe
pid
sid
spd
spi
pide
side
spde
spie
spid
spide

這里用到了Combine 輸出全部組合，Combine 5,3就是得到在5個里選3個的全部可能選法。

<SCRIPT LANGUAGE="vbScript">

str="spide" 
''創建全局字典對象，用來存儲所有得到的原子結果
Set dict=CreateObject("Scripting.Dictionary")

Dim a(100)
strLength=Len(str)
''原子
atomyLength=round(strLength*0.6)

For x=atomyLength To strLength
a(0)=x 
''計算5選3，5選4，5選5組合
combine strLength,x 
next

sub combine(m, k) 
''計算組合在m里面選k個元素的全部組合情況，添加到字典對象里
i=0
j=0 
For i=m To k Step -1
a(k)=i 
if (k>1) then
combine i-1,k-1 
else 
tempStr=""
for j=1 To a(0) 
tempStr=tempStr & Mid(str,a(j),1) 
Next
''排除重復的，加到字典里
If Not dict. Exists(tempStr) then dict.add tempStr,Len(tempStr)
End if 
next 
End sub 

Main()

Sub Main
''輸出顯示結果
For i=0 To dict.count-1
Document.write dict.keys()(i) & "<br/>"
next
End sub
</SCRIPT>