一种基于PowerBuilder环境字符串相似度算法
2017-05-17刘永海
刘永海
摘要：最小编辑距离能直接反映两个字符串的相似程度，而字符串的相似度比较在数据挖掘和数据查询方面多有应用。通过相似度比对，可更自动化地整理、规范文本，提高信息模糊查询的命中率。本文详细介绍了“LD”算法的原理，并完成了PowerBuilder环境下的具体编码。
关键词：LD算法；字符串相似度；PowerBuilder；源码
中图分类号：TP311.52 文献标识码：A 文章编号：1007-9416（2017）03-0140-02
引言
在数据挖掘中，经常需要分类整理相似字符串；在模糊检索、文本智能纠错等方面也要进行字符串相似度比对。常见的算法包括编辑距离、最长公共子串、RKR-GST等算法。本文介绍了最小编辑距离算法（下称LD算法）在PowerBuilder环境中的实现。
1 算法分析
最小编辑距离算法最早是由俄罗斯科学家Levenshtein提出，因此也称“LD”算法。该算法是计算两个字符串之间，将一个字符串通过替换、插入、删除等方式转变为另一个字符串所需要的最少步骤数。如将“青岛市卫计委”转变为“青岛卫生局”的编辑距离是3。本文中，字符串S、T的最小编辑距离用表示。（见表1）
编辑距离与最大字符串长度的比值同字符串的相似度成负相关。字符串的相似度定义为。
字符串S，T相似度越高，LD就越小，当完全相同时值最小：，相似度为100%；当完全不同时值最大，
，相似度为0%。因此，。
根据LD的原理，存在如下公式：
公式1：当一个字符串为空时，LD等于不为空字符串的长度，即；
公式2：两个字符串位置对调不影响LD的值，即
；
公式3：同时在两个字符串的“头”或“尾”部连接相同的字符串，其LD不变，即
；
设S由组成，T由组成，长度分别为n和m。当S或T某一个为空时，根据公式1可计算LD值。当S和T都不为空时，引入i和k做为S和T的下标变量，取值范围是。子字符串。若字符元素，依据公式3，子字符串；若，取增加、删除和修改三种方式的最小LD值加1，由此得出：
公式4：时，；时，。
运用公式4，将i和k从1分别计算至n和m后，即可求出。
2 算法实现
根据上述分析，应构造矩阵进行计算。举例说明，设S=“青岛市卫计委”，T=“青岛卫生局”，构造矩阵如下：
上图将S和T字符串分别作为矩阵的列和行。其中，第一行是T为空时，的值；第一列是S为空时，的值。按照算法，首先计算，由于“青”字相同，因此
，将值填入对应位置；再计算，可以看到，，在图中可以看出，分别是的“上侧”、“左侧”和“左上侧”的值。这时最小值是0，因此，将值填入矩阵…；以此类推，计算完成整个矩阵后最右下角的数据即为的值。
上例。字符串的相似度为。
3 源代码
构建计算矩阵一般使用数组实现。在PB中选用了特有的DataStore对象来实现。DataStore是PB中特有的数据容器，它数据操控方便，代码维护量小，又是非可视对象，占用资源少，效率更高。具体算法如下：
//切分字符串为字符元素
Int li_1，mALen，mBLen
String ls_tmp，S，T//目標字符串S，T
Char mCharA[]，mCharB[]
If Len（S） ls_tmp=S；S=T；T=ls_tmp； End If For li_1=1 TomALen mCharA[li_1]=Mid（S，li_1，1） Next For li_1=1 TomBLen mCharB[li_1]=Mid（T，li_1，1） Next //动态创建数据存储 Intli_ret=0 String ls_sql，err_syn，err_crt，new_syn Datasore ds_1 ds_1=Create Datasore //创建实例 For li_1=1 To mBLen+1//组成SQL语句 ls_tmp=ls_tmp+0 as col+String（li_1）+， Next ls_tmp=Left（ls_tmp，Len（ls_tmp）-1）//去掉最后的逗号 ls_sql=Select + ls_tmp+From dual//Oracle用法 new_syn=sqlca.SyntaxFromSQL（ls_sql，style（type=grid），err_syn） ds_1.Create（new_syn，err_crt）//创建实例 //在DataStore中进行LD计算 Long ll_row Integer li_2，li_zs，li_left，ls_top，li_tmp Dec ld_ret ds_1.InsertRow（0）//新增第一行，填充0，1，2… For li_1=1 TomBLen+1 ds_1.SetItem（1，li_1，li_1-1） Next For li_1=1 to mALen
ll_row=ds_1.InsertRow（0）//填充第一列数据
ds_1.SetItem（ll_row，1，li_1）
Next
//計算LD
For li_1=1 TomBLen
For li_2=1 TomALen
li_zs=ds_1.GetItemNumber（li_2，li_1）
If mCharB[li_1]<>mCharA[li_2] Thenli_zs++
li_left=ds_1.GetItemNumber（li_2+1，li_1）+1
li_top=ds_1.GetItemNumber（li_2，li_1+1）+1
li_tmp=Min（li_zs，li_left）//Min只能两两比较
li_tmp=Min（li_tmp，li_top）
ds_1.SetItem（li_2+1，li_1+1，li_tmp）//设置单元的值
Next
Next
ld_ret=1-li_tmp*1.0/mALen//得到相似度
4 总结
基于LD的字符串相似度算法实现比较简单。在对比短长度的字符串时，其空间复杂度低，具有良好的实时性。测试表明，在普通PC机中PowerBuilder编写的LD算法执行速度达到200～300对/秒（字符串长度在5～20之间）。在进行中文机构名称和简称模糊匹配时，命中率接近80%。
但该算法也有明显缺陷，它无语义关联。例如进行“青岛市卫计委”、“青岛卫生局”、“青岛市统计局”机构名称匹配时，就得不到正确结果。因此，后期改进时，应考虑加入语义解析，比如用“分词”技术先拆分成词组，再用分词字典对词进行标准化转换后再计算相似度时就可以得到正确结果。
参考文献
[1]杜军强，杨波.云计算中加密数据的模糊关键字搜索方法.计算机工程与应用，2015，51（5）：146-152.
[2]黄林晟，邓志鸿，唐世渭，王文清，陈凌.基于编辑距离的中文组织机构名简称-全称匹配算法.山东大学学报（理学版），2012，47（5）：46-51.
[3]米琳.基于q-gram的字符串相似性查询研究.现代计算机，2014（4）：12-16.
