字符编辑的字符串匹配算法的实现+编辑距离算法+JARO算法
基于字符编辑的字符串匹配算法的实现
摘 要
随着信息技术的迅猛发展，各种数据生成以及数据采集设备的广泛使用，人们获取到的数据量指数级增长，但是人们从海量数据中获取信息的方便性并没有得到有效的改善，究其原因，其一就是数据质量大大下降，不足以满足应用的需求。原文请找腾讯752018766辣'文.论,文.网
http://www.751com.cn本文介绍了对数据质量研究的必要性以及目前数据质量研究的热点，并着重介绍通过记录连接来改善数据质量问题。通过匹配技术中的编辑距离算法、Jaro-Winkler算法达到进行记录连接的目的，并对算法的原理及其实现作了阐述，通过计算两个记录的相似度来解决基于字符编辑的字符串匹配问题，实现对重复相似记录的检测以达到数据连接的目的，最后对匹配技术对数据质量研究的展望。
关键词：数据质量； 记录连接； 匹配； 编辑距离； Levenshtein算法； Jaro-Winkler算法
第二章 编辑距离 (Edit distance)
我们在拼写字符串时，难免会不小心漏写、多写或误写几个字符，比如出现表2-1几种情况：
表2-1 拼写字符串时出现的错误情况
正确的拼写 Record
漏写 Rec rd
多写 Recorrd
误写 Recond
对于漏写、多写、错写情况我们可以通过插入、删除、替换几个操作来解决，这就是我们提出的编辑距离算法。在信息论和计算机科学中，所谓的编辑距离，是指将两个不同的字符串变成相同的字符串所需要的最小操作（插入、删除和替换）的次数。编辑距离是基于编辑距离方法中的最基础的算法，可以用来检测字符编辑过程中的拼写错误。[4]
我们常将编辑距离一词用来特指Levenshtein距离。
2.1 Levenshtein算法思想
对于书写和录入时的编辑错误统称为排版错误(Typographical issues)。对于排版错误，我们令误写的记录为s，而正确的记录为t 。由于排版错误，一般只有几个字符之间差异，如漏写、多写、误写N个字符，则s与t的编辑距离则会一个较小的值。
另一方面，对于记录R1和R2，若R1与R2的编辑距离很小，则某种程度上可以说明R1与R2所要表述的为同一记录，只是由于录入时一些微小错误而导致其产生表示上的差异。
于是可以通过计算两个记录的编辑距离来推断这两个记录是否表述为同一实体而发生的冗余。当然这样的判定不会是100%正确，但其错误率仍是可以接受的，尤其在一些特定的应用背景之下，比如对记录客户的姓名和地址信息的数据集，则难有两个实体的正确表述有较低编辑距离，它们的差异总是较大。
2.2 Levenshtein算法原理
通过计算编辑距离来判断两记录是否为同一实体的不同表述。记编辑距离为d，d=0时表示两个字符串完全匹配，d>0时，d与给定的阈值p做比较，d小于阈值p时认为在语义上两个字符串是一致的，d大于阈值p时认为两字符串在语义上不一致。[5]
2.3 算法的实现
2.3.1 Levenshtein算法
基于距离编辑匹配的算法[6]是先输入两个字符串，通过插入、删除和替换的最少操作使得两个字符串相同，计算得到最少操作数。
计算Levenshtein距离使用自下而上的动态规划方法。采用基于矩阵的方法，假设m，n为字符串source与target的长度，建立(n + 1)× (m + 1)的矩阵，结构如表2-2：
表2-2
T A R G E T
0 1 2 3 4 5 6
S 1
O 2
U 3
R 4 d[i][j]
C 5
E 6 d[m][n]
令d[0][0]=0，d[i][0]=i，d[0][j]=j，矩阵结构中d[i][j]表示source前i位与target前j位字符所需要的最少编辑次数，即编辑距离。我们可以使用最少的d[i][j]操作将s[1..i]转换为t[1..j]，最后矩阵右下方的元素d[m][n]就是计算结果。
上一页 [1] [2] [3] [4] [5] [6] 下一页
java字符编辑的字符串匹配算法的实现+编辑距离算法+JARO算法 第2页下载如图片无法显示或论文不完整，请联系qq752018766
