基于字符编辑的字符串匹配算法的实现
摘 要
随着信息技术的迅猛发展，各种数据生成以及数据采集设备的广泛使用，人们获取到的数据量指数级增长，但是人们从海量数据中获取信息的方便性并没有得到有效的改善，究其原因，其一就是数据质量大大下降，不足以满足应用的需求。
本文介绍了对数据质量研究的必要性以及目前数据质量研究的热点，并着重介绍通过记录连接来改善数据质量问题。通过匹配技术中的编辑距离算法、Jaro-Winkler算法达到进行记录连接的目的，并对算法的原理及其实现作了阐述，通过计算两个记录的相似度来解决基于字符编辑的字符串匹配问题，实现对重复相似记录的检测以达到数据连接的目的，最后对匹配技术对数据质量研究的展望。
关键词：数据质量； 记录连接； 匹配； 编辑距离； Levenshtein算法； Jaro-Winkler算法
目 录
摘 要 i
ABSTRACT ii
第一章 绪论 - 1 -
第二章 编辑距离 (Edit distance) - 3 -
2.1 Levenshtein算法思想 - 3 -
2.2 Levenshtein算法原理 - 3 -
2.3 算法的实现 - 4 -
2.3.1 Levenshtein算法 - 4 -
2.3.2 Levenshtein算法实现 - 5 -
2.4 正确性说明 - 6 -
2.5 Levenshtein算法补充说明 - 6 -
第三章 Jaro-Winkler距离(Jaro-Winkler Distance) - 7 -
3.1 Jaro算法 - 7 -
3.1.1 Jaro算法原理 - 7 -
3.1.2 Jaro算法实现 - 7 -
3.2 Jaro-winkler算法 - 10 -
3.2.1 Jaro-winkler原理 - 10 -
3.2.2 Jaro-winkler实现 - 10 -
3.2.3 算法相关补充说明 - 12 -
结束语 - 13 -
致谢 - 14 -
参考文献 - 15 -
附录 - 16 -
