【作者】 王燕；

【导师】 周军锋；

【作者基本信息】 燕山大学 ， 计算机应用技术， 2013， 硕士

【摘要】 对于给定的字符串集合，基于相似度的连接操作可用于从中找出相似的字符串对，该操作是数据清洗，数据集成以及协同过滤等应用的核心操作之一，其执行效率直接影响系统的整体性能。本文针对不同的字符串集合，结合编辑距离对称性原则，对字符串集合间的相似度连接操作展开深入研究：首先，现有的基于trie树的字符串相似度连接操作的处理方法重点关注如何提高单一字符串集合内部相似对的处理效率。然而，如何快速处理不同字符串集合间的相似对操作也并非轻而易举的事。针对此问题，本文分析和总结了现有算法在处理不同字符串集合间相似对效率低下的原因。其次，针对现有方法因重复计算编辑距离而导致的冗余计算问题，本文提出Trie-TS以及Trie-TSS两种算法，这两种方法的特点是基于trie树结构，结合编辑距离对称性原则，减少了编辑距离计算次数，从而达到提升系统性能的目的。进而提出一种旨在减少冗余编辑距离计算次数的PP优化技术来提升系统性能。最后，搭建开发平台，并在不同的数据集上，通过查询时间对所做的算法的高效性进行验证，实验结果表明我们提出的Trie-TSS算法效率优于现有算法。当字符串集合中字符串数目足够大时Trie-TS算法的优势也得以显现。通过编辑距离计算次数以及查询时间验证了PP优化技术的高效性与有效性。更多还原

【Abstract】 A string similarity join finds similar pairs between collections of strings. It is anessential operation in many applications, such as data integration and cleaning andcollaborative filtering, and it had attracted significant attention recently. The paper focuseson the research of finding similar pairs between two different collections of strings whichjoins with the edit distance, the main research is as follow:Firstly, existing trie_based string similarity join research methods focus on improvingthe string similarity join calculation of the same collections of strings. But, how to quicklycompute the string similarity join of the different collections of strings is not an easy job.For this problem, in this paper we analyze and summarize existing algorithms, and findthe inefficient reason.Secondly, for the problem of inefficiency in the existing methods, We propose twonovel algorithms, named Trie-TS and Trie-TSS, which use the symmetry of edit distanceto reduce redundant computation. Moreover, we propose a new optimization technique tofurther reduce the unnecessary computation to improve the overall performance.Finally, we development environment, and verify the efficiency of our algorithms inthe different data sources. The experimental results show that Trie-TSS algorithm is betterthan existing trie_based algorithms.When the number of the string collection is big enough,Trie-TS algorithm is also better. And we implement the new optimization techniquetowards the number of computation and query time to further reduce the unnecessarycomputation to improve the overall performance.更多还原