大规模字符串连接的并行化研究与应用

发布时间：2016-06-13 05:40

第 1 章  绪论

1.1 课题背景及意义
在这样一个科技不断进步的时代里，信息量无时无刻不在增加，数据量急剧膨胀。面对这样一种情况，数据处理工作变得越来越困难，如何快速地从互联网的信息库中寻找我们需要的信息正成为一个亟需解决的问题。 当今社会信息交互日益频繁，随着社会的发展、科技的进步，不难发现：传统的基于关键字的查询已经无法满足信息交流的需求。可以看这样一个例子，某用户想要找到关于“windows  XP 操作系统”相关信息，但因为用户记忆不清或输入马虎错误，在向数据库中输入信息时却输入成“windo XP 操作系统”。那么数据库最终可能无法返回给用户所需要的信息。如果使用字符串相似连接技术，当用户记忆不清或输入马虎错误，在向数据库中输入信息时却输入成“windo XP操作系统”。那么最终也是可以返回给用户所需要“windows XP 操作系统”相关信息。因此，如何以最快的速度从海量的数据库中找到用户所需及其相似的结果，是本文努力研究方向。 早期关于字符串相似连接问题的研究主要用于解决信息检索、生物信息学、数据集成等方面的相似连接问题。直到目前，以上几个问题依旧是字符串相似连接能够不断向前发展的驱动力。 随着计算机的普及，互联网技术的的广泛应用，信息已经实现了全球共享。文本成为信息存储和传播的主要形式。在面对大量的文本信息时，人们通常不知所措。通过信息检索，能从海量的文本中快速地、准确地找到所需要的信息。但想要在浩瀚如海的信息中甚至包含错误信息的数据库中找出与给定文本相似的信息，这就需要依靠字符串的相似连接的方法。 在当今社会，学术论文抄袭问题十分严重。如何有效地展开防止抄袭学术成果越来越受到社会的重视，在这种情况下出现了许多学术不端检测系统。在这些检测系统中，字符串的相似连接是根本[1]。 
........

1.2 国内外研究现状
国内在字符串相似性连接的研究主要包括英文字符串的相似度连接，中英文结合的相似字符串的连接以及中文字符串相似性连接，而国外的研究主要集中在英文字符串的相似度连接。中文字符串相似性连接主要被应用在中文信息检索、过滤、OCR 辨认、以及中文文本比较等领域。现有的字符串相似相似性连接方法根据处理特征的不同，大致可以分成两类：基于语法的相似性连接、基于语义相似性连接[4-9]。 基于语法的相似性连接实际上也就是基于字符串的相似性连接，这类研究在国内外也较多。基于特征的相似性连接首先需要提取字符串特征，然后根据相似度的度量方法，计算出两个字符串间的相似度并给出评价标准。目前，字符串的特征提取方法主要有基于字符的 q-gram 等和基于 token 的方法。衡量字符串相似度的方法主要有 Jaccard 相似度，Cosine 相似度，编辑距离（Edit Distance），混淆字符集，混淆字符矩阵或是 n 元相似度算法，在以上相似度的计算方法的基础上，提出了许多用于完成两个字符串相似度连接的算法，如 Part-Enum，All-Pairs-Ed，Ed-Join 以及基于 Trie 树的算法等。这些算法根据其处理策略可以分为两类：(1)先过滤后提炼的方法，如 Part-Enum，All-Pairs-Ed 以及 Ed-Join 算法；(2)基于 Trie 树的处理方法，如 Trie-Traverse，Trie-Dynamic，Trie-PathStack等[10-18]。 两个不同的句子不同词可能表述着相同的意思（比如同义词），这是基于语法的相似性连接无法解决的问题。基于语义的相似性连接在基于语法的相似性连接的基础上增加了语义相似性连接部分。它是基于语法的相似性的一种延续和扩展，在信息的表示和检索中的极为重要。基于语义的相似性连接首先需要明确语义相似度的概念，找到衡量语义相似度的方法以及计算过程中需要考虑的因素。
.......

第 2 章  字符串相似性连接技术研究 

本章主要研究字符串相似性连接技术，首先详细分析字符串相似性连接的过程，介绍了相关定义及概念；然后给出了字符串相似性连接中常用的相似度的度量方法以及相似性连接技术；最后分析了近年来研究最多的方法技术及现状，找出不足和解决大规模字符串连接的关键。 

2.1 相关定义及概念
在使用中，由于 Hamming  Distance 针对两个等长的字符串，而在实际计算字符串相似度的过程中，给定的两个字符串通常是不等长的，所以在应用Hamming  distance 时一般需要对给定的字符串做一些预处理。例如，先应用n-gram 将给定的字符串转换成一些长度为 n 的子串集合，然后再结合一些基于集合的相似度算法进而计算出两个字符串间的相似度。但是在实际的应用中，找到一种将两个字符串转化成等长且保留原语义的有效的方法十分困难。 
.......

2.2 字符串相似度的度量方法

字符串的相似度是用于判断两个字符串是否相似的基础，所以在字符串的相似性连接过程中，计算字符串间的相似度是至关重要的步骤。目前已经存在众多计算的字符串相似度的方法，大致可分为两类：基于特征的字符串相似度的度量方法和基于集合的字符串相似度的度量方法[25]。 编辑距离是指两个字串之间，从一个转变为另一个所需经过的最少编辑次数。许可的编辑操作包括将将一个字符替换成另一个字符，在字符串中插入一个字符，从字符串中删除一个字符。此算法首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance。编辑距离算法的匹配过程是有序的，对顺序的匹配十分有效。常用被应用于拼写检查、语音识别以及 DNA 比对和自动评分系统中。本文后续部分如无特殊说明默认为使用编辑距离衡量两个字符串间的相似度[26]。 

........

第  3  章 基于内存的并行化连接方法........ 16 
3.1 相关符号定义 .... 16 
3.2 Para-Join 算法框架 .......... 17 
3.3 Para-Join 的数据划分及相似度计算 .......... 18 
3.3.1  数据划分.......... 18 
3.3.2  相似度计算...... 20 
3.4 Para-Join 的连接过程 ...... 21 
3.4.1 Para-Join 算法的实现 .... 21 
3.4.2 Para-RR 与 Para-RS 的实现 ........ 23 
3.5 实验结果与分析 ....... 25
3.6 本章小结 ..... 28 
第  4  章 基于 Spark 框架的 Spss-Join 算法 ...... 30 
4.1 常见的并行化处理框架 ......... 30 
4.2 MapReduce 在字符串相似度连接中的应用 ..... 33
4.3 基于 Spark 框架的 Spss-Join 算法实现 ...... 38
4.4 实验结果与分析 ....... 41
4.5 本章小结 ..... 43 
第  5  章 系统原型..... 44 
5.1 系统框架 ..... 44
5.2 运行结果 ..... 47 
5.3 本章小结 ..... 48 

第 5 章  系统原型

本章结合基于内存的 Para-Join 算法和基于 Spark 框架的 Spss-Join 算法，设计并给出了一个用于处理字符串相似度连接的系统原型。该系统主要分成五个模块：输入模块、token 集划分模块、数据过滤模块、数据验证模块、输出模块。本章首先将详细介绍这五个模块，并给出相应模块中的 API 接口，最后通过一个真实案例的应用来分析该系统。 

5.1 系统框架 
本节分别将从硬件架构和功能框架两方面来分析字符串相似度连接的系统的组成。如图 5-1 所示，系统的物理部署可以划分为 C/S 和 B/S 相结合的模式。对于主要的功能模块以 C/S 模式部署在服务器上，token 集划分模块、数据过滤模块和数据验证模块，从而能够快速的进行相似性连接工作，将输入数据集以及相似性连接的结果存储于 HDFS 中；需要与用户交互的输入输出模块则同时 B/S 和B/S 模式来构建，用户既可以通过 PC 客户端又可以通过浏览器来访问系统。 这两个模块主要用于与用户交互，用户可以同过输入模块上传需要进行处理的字符串集合，设置相关参数，例如相似度阈值。PC 客户端的用户界面如图 5-3所示。输入模块首先会对用户上传的数据集进行简单的预处理，例如将结构化的数据去结构化转换成简单的字符串，以方便之后的模块使用，接着将处理后的数据存入 HDFS 中。输出模块主要用于完成结果的查询，用户发出查询请求后，该模块将存储在 HDFS 中的相似性连接结果取出并返回给用户，该模块会将相似对数以及连接用时等结果直接返回给用户，对于相似对记录会以文本的形式返回给用户，需要用户下载后才能查看。表 5-1 给出了相应的 API 接口。 
.......

总结

在计算机应用方面，字符串相似性连接是被广泛研究的课题之一。它在众多领域方面都有着重要应用，如数据清洗和集成、附近重复文本检测、协同过滤、生物信息序列比较等。目前，已有大量的字符串相似性算法被提出。本文在这些算法的基础上，重点研究了并行化的字符串连接技术。下面给出本文的主要工作： 
(1) 提出了一种新的字符串相似度计算方法，它在过滤阶段结合了频率向量过滤和多匹配感知子串选择（Multi-match-aware Substring Selection）技术，提高了过滤的强度。在过滤阶段能够淘汰掉更多的不相似对，从而减少的计算量提高了算法效率。 
(2) 提出了一种新的基于内存的并行化字符串相似性连接算法——Para-Join，同时本文还提出了 Para-RR 和 Para-RS 算法，用于解决单个子集的自连接问题和不同子集间的连接问题。实验结果表明 Para-Join 算法在处理大量字符串相似性连接时比以往的算法更加高效，他拥有高可扩展性。由于算法完全在内存中运行，内存容量会限制对数据集的大小，同时对算法的效率产生较大的影响。另一方面，线程数量受到具体的应用环境的影响，用户无法在算法运行前给出一个最优的线程数。 
(3) 为了弥补 Para-Join 的不足，本文研究了当前流行的并行化处理框架Hadoop 和 Spark。重点研究了如何使用 MapReduce 编程模型解决大规模字符串相似度连接的问题。通过分析发现它拥有诸多优点，例如算法不再需要明确指出线程数量，数据集的大小不再受内存容量的限制。但让也同时带来了新的问题，由于 MapReduce 编程模型本身不支持迭代，使得在一次算法运行中不得不多次开启 map-reduce 任务，，另外由于其对编辑距离的支持较差，使得已有的大量高效的过滤验证策略不能被使用，降低了算法的效率。针对以上问题本文在Para-Join 的基础上，提出了基于 Spark 框架的 Spss-Join 算法，它有效的解决了上述所有问题。 
(4) 本文最后在 Spark 框架的基础上，设计并讨论了一个用于处理大规模字符串相似性连接的并行化系统原型。
.........
参考文献(略) 

本文编号：56661