java字符编辑的字符串匹配算法的实现+编辑距离算法+JARO算法
随着信息化的迅猛发展，人们使用的数据按指数级的速度增长，然而人们并没有从产出的数据得到更好的利用价值，原因之一为数据质量不足以满足应用的需求。质量管理大师约瑟夫•朱兰(Joseph M.Juran)认为数据质量是用来衡量数据能否满足指定应用的要求。数据是现实世界中客体在计算机中的抽象表示，是信息的载体。而随着数据量的增加使得数据管理和数据处理的技术复杂度加大，使得数据异构性增加，同时人们提高了对有用数据的期望。根据“垃圾进，垃圾出”的原理，要从大量有用的数据中获取有用的信息，对数据质量的研究是有必要的。
近年来，数据质量研究课题主要包括四个方面：[1]
(1)数据连接(Date Linkage)。由于数据源不同和数据质量问题(如拼写错误，非标准缩写，时间性变化等)，这些关于同一实体的信息描述没有统一标准的标识符。数据连接的目的就是为了在大量数据中找到关于现实世界中同一实体的信息。近些年来，数据连接的研究重点在以不同情况的记录相似性以及在上百万记录中快速找到最相似记录的算法。原文请找腾讯752018766辣'文.论,文.网http://www.751com.cn
(2)数据约束(Date Constraints)。数据的完整性是保证数据库中数据正确性的必要条件，而数据约束是关系数据库中对数据正确性的支持。现代数据管理中存在来源不同的数据，而这些数据没有统一的关系模式。用户可以在数据库关系层上定义函数依赖及各种约束，保证数据的正确性。最近提出了一种基于记录的条件函数依赖，而不是基于关系模式的函数依赖，对现代数据库中的数据质量的描述和保证起着重要意义。
(3)数据溯源(Date Provenance)。基于大规模的数据整合的应用中，数据来源复杂，质量参差不齐，处理过程繁多时，数据溯源功能显得很重要。数据溯源分为数据级溯源和过程级溯源。数据库领域总体上对数据溯源研究不多，虽然目前主要侧重于数据级溯源的研究，但还仍不能有效支持对大规模数据下的数据溯源。
(4)数据非确定性。传统的关系数据库系统中认为，系统应避免数据的不一致性，而现实生活中，可能存在对某个事物的不确定描述，如记录交通事故的数据库中，目击证人对看到的车的颜色是不确定的，这样颜色会有多个值。将数据的不确定性引入到数据库系统中，在理论和工程上的研究都有着重大的挑战性。
以上四个方面的研究中，可能会由于数据来源不同或其他原因造成多个记录不同，却都指的是同一现实实体，这样的记录称为相似重复记录(duplicate record)，其容易造成系统数据冗余，降低了数据质量。为了解决这类问题，研究人员提出了记录连接这个概念。将确定数据记录的描述是否指同一现实实体的这样一个操作性过程称为记录连接(Record Linkage)，即查找共同指涉的记录对，而实体一般可以是人、或组织等，数据记录可以是姓名、地址、出生日期等。记录连接主要应用在联接异构关系和从单一的关系中删除重复数据。记录连接也被称为对象识别、数据清洗、模糊匹配等。[2]
对于数据库管理，重复记录的匹配和合并也被称为对象识别和重复记录清除。通常情况下,指向同一个现实实体的两条记录信息部分冗余,数据互为补充，为了能够更准确地反映该实体，需要将相似重复记录合并。相似重复记录清除是先识别出同一个现实实体的相似重复记录，随后将其合并成一个包含该实体的更多属性,同时从数据集中删除多余的记录。有一些数据记录总能够惟一标识一个实体，这时,只要对两个记录集在该属性集上作等值连接,就完成了记录匹配。对于单个记录集的情形,先对属性集进行排序,然后通过检查相邻的记录,判断出它们是否为相似重复记录。有些不存在这样的属性集，而且数据中可能还存在错误，那么以上排序方法就不适用了。这时可以通过引入匹配规则来完成模糊匹配，比如有这样的规则:如果stuname 字段相同, stuaddress 字段相似度也很大,那么认为这两条记录是重复记录。我们一般用[0,1]数值来表示字段之间的相似度，根据相似度与阈值比较，来判断两条记录是否是相似重复记录。作为记录连接研究的一部分，本文的主要工作主要是使用算法实现判断两个记录的相似度。[3]
现实生活中存在某类情况，如”NanJing University”和”NJU”都是表示“南京大学”， 或者拼写错误的”NanJing Univesity”语义上也是指“南京大学”，只是形式不一致。在字符编辑过程中产生了这些重复相似记录，为了检测出这些记录，现多采用匹配技术来解决以达到记录连接的目的。
前面介绍的”NanJing Univesity” ，在书写上漏写了一个字母’r’造成了拼写错误，为数据匹配中的排版错误。本文主要介绍了使用匹配技术的编辑距离算法、Jaro及其变体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 -
String Matching Algorithm and its Realization
Based on Character Editor
ABSTRACT
With the rapid development of information technology and various data generation and data acquisition equipment widely used ,the amount of data which people get is increasing by exponential,however, the huge amounts of data which people get in the convenience of access to information has not been effective improvement, one of reseaons is that data quality significantly decreased and insufficient to meet the application requirements.
This paper introduces the necessarity of researching data quality and describes the current hot topic of data quality ,then puts an emphasis on introducing through the records to improve data quality problems. Through the matching technology in the edit distance, Jaro-Winkler algorithm to achieve the purpose of record linkage,then describe the Principles and implementation of the algorithm .Through Introduces the useage of the edit distance algorithm, Jaro-Winkler algorithm of matching technology and how to realize them ,through calculating the similarity of two records to solve the character-based string matching editor to achieve detection of duplicate records ,finally looks forward to the research on matching technology for data quality.
Keywords：Data Quality; Record Linkage; Matching; Edit distance; Levenshtein Algorithm; Jaro-Winkler Algorithm1645