如何确定中文字符串的相似度

　最近有一项目要求对大量的药品名称和治疗项目进行模糊（相似度）比较，如果用 like %xxx% 之类的无法达到要求，如"奶奶的兄弟"和"奶妈的兄弟"，用like之类就无能为力了。网上也有一些国外的字符串相似度比较的算法，但几乎都是针对单字节字符串的比较，典型的例子是MS SQL中的字符串相似度比较函数就是此类，对于双字节的中文无效。数据挖掘实验室

　有没有一个什么算法可以知道两个中文字符串之间有哪些不同？如何通过程序判断某个句子和其他很多句子中的哪一个更相似呢？数据挖掘工具

starfish（海星）

如果仅仅是判断字符串相似，这就仅仅是一个模式识别问题，可以构造一个函数，将两个字符串映射到高维空间内，然后比较坐标矩阵的特征向量；如果是要判断句子的含义是否相似，那就难了，牵涉到语义识别和人工智能。数据挖掘研究院

g9yuayon（渡渡鸟）

hoho，语意识别当然难啦，但我猜ab问的是语法的近似匹配(不然问WinDiff干嘛？)。如果是的话，　
研究一下字串匹配就成了。一般简单的用动态规划就行，比如LCS(longest　common　subsequence)加上字串近似匹配(最简单的那种，用动态规划)。据说UNIX下的diff就是用的　
这种方法。LCS比较常见，就说说动态规划下的近似字串匹配吧(我也是菜鸟，只会动态规划　
的简单解法。其实匹配的算法足以写本书了。例如用后缀树(suffix　tree)做匹配，不论空间　
还是时间效率都很高)：　
To　be　more　precise,　let　P　be　a　pattern　string　and　T　a　text　string　over　 the　same　alphabet.　The　edit　distance　between　P　and　T　is　the　smallest　 number　of　changes　sufficient　to　transform　a　substring　of　T　into　P,　where 　the　changes　may　be:　数据挖掘工具

　先定义编辑距离：令P为一个字串模式，T为一个字串，且P和T来源于同一字符集，则编辑距离为　
把T的一子串转化为P所需的最小改动。改动有三种：　
1.　置换：两对应的字符不同，例如far和bar。　
2.　插入：将P所有的一字符插入T，例如fr,　bar。　
3.　删除：将T有但P没有阿字符去掉，例如faar和far　

　有了这个定义就好办了。按照动态规划的三斧头：先定义D[i,j]为T[i..j]转化到P的编辑距离，　
则:　
EditDistance(P,T)　数据挖掘工具

(initialization)　数据挖掘交友

For　i　=　0　to　n　do　D[i,0]　=　i　

For　i　=　0　to　m　do　D[0,i]　=　i　数据挖掘工具

(recurrence)　

For　i　=　1　to　n　do　数据挖掘工具

　For　j　=　1　to　m　do　

　　　D[i,j]　=　min{D[i-1,j-1]+matchcost(P Idea ,T[j]),D[i-1,j]+1,D[i,j-1]+1}　
其中matchcost(P Idea ,　T[j])为置换P Idea 和T[j]的开销，当P Idea 和P[j]一样时为0，不一样时为1。　数据挖掘工具

　睡午觉去了。数据挖掘实验室

由胡文青在十月 10, 2007 09:44 发贴 | 永久链接

字符串相似度算法介绍

dongle2001 数据挖掘工具

最近在做这方面的应用，把我找到的资料贴出来，有需要的人可以参考参考。

1．编辑距离（Levenshtein Distance）

　　编辑距离就是用来计算从原串（s）转换到目标串(t)所需要的最少的插入，删除和替换
的数目，在NLP中应用比较广泛，如一些评测方法中就用到了（wer,mWer等），同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。
Levenshtein Distance算法可以看作动态规划。它的思路就是从两个字符串的左边开始比较,记录已经比较过的子串相似度(实际上叫做距离),然后进一步得到下一个字符位置时的相似度。用下面的例子: GUMBO和GAMBOL。当算到矩阵D[3,3]位置时,也就是当比较到GUM和GAM时,要从已经比较过的3对子串GU-GAM, GUM-GA和GU-GA之中选一个差别最小的来当它的值. 所以要从左上到右下构造矩阵。
编辑距离的伪算法：
整数 Levenshtein距离(字符 str1[1..lenStr1], 字符 str2[1..lenStr2])
宣告 int d[0..lenStr1, 0..lenStr2]
宣告 int i, j, cost

　　对于 i 等于由 0 至 lenStr1
d[i, 0] := i
对于 j 等于由 0 至 lenStr2
d[0, j] := j
对于 i 等于由 1 至 lenStr1
对于 j 等于由 1 至 lenStr2
若 str1 Idea = 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 Idea ;
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 Idea == 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 Idea ;
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个的全部可能选法。

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> 数据挖掘交友

有了原子,就可以比较最长公共子串。