一种基于PowerBuilder环境字符串相似度算法.doc

一种基于PowerBuilder环境字符串相似度算法

摘要:最小编辑距离能直接反映两个字符串的相似程度,而字符串的相似度比较在数据挖掘和数据查询方面多有应用。通过相似度比对,可更自动化地整理、规范文本,提高信息模糊查询的命中率。本文详细介绍了“LD”算法的原理,并完成了PowerBuilder环境下的具体编码。
中国论文网/8/view-
关键词:LD算法;字符串相似度;PowerBuilder;源码
中图分类号: 文献标识码: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