1.一种基于LSH的过滤验证字符串相似性连接方法，其特征在于，包括如下步骤：

1)获取字符串数据集S；

2)数据预处理：对字符串数据集S进行预处理，生成一个有序的字符串集合A，并初始化哈希表

3)空间映射：利用CGK-嵌入方法对字符串集合A中的字符串进行编辑空间到汉明空间的映射，得到汉明空间的字符串集合S'；

4)过滤：使用LSH函数对字符串集合S'中的每个字符串进行计算哈希值，将每个字符串分别映射到每个哈希函数对应的哈希表中，依据字符串长度进行初步过滤得到初始候选集合，对初始候选集合进行k次相似的过滤，得到最终候选集合，过滤过程如下：(1)基于长度的初步过滤：利用LSH函数依次对字符串集合S'中的每个字符串计算哈希值，当一个字符串被哈希到其中一个哈希表中时，该字符串并不会与哈希表中其它的字符串组成候选对，而是依据字符串长度进行初步过滤得到初始候选集合，当任意一个新的字符串sj被映射到哈希表中后，根据预先设定的编辑距离阈值τ作为过滤半径，字符串sj与哈希表中已有的字符串si进行长度对比，若|sj|-|si|<＝τ，则将作为候选对加入初始候选集合，若|sj|-|si|>τ，则将过滤掉；

(2)基于k次相似的过滤：

①首先对字符串数据集S’每个字符串都使用z个LSH函数，分别对应z个哈希表；

②然后对经过基于长度的初步过滤得到的初始候选集合中的字符串并对该字符串在对应的初始候选集合中出现的次数进行计数和判断：若一组字符串对在初始候选集合中出现的次数超过k次，则加入最终候选集合；否则，该字符串对将被过滤掉；

5)验证：对最终候选集合中的字符串对进行编辑距离的验证，得到最终相似的对，相似的对即为相似性连接。

2.根据权利要求1所述的基于LSH的过滤验证字符串相似性连接方法，其特征在于，步骤1)中所述的字符串数据集S来自公开的现实数据集TREC，TREC是一个在线医疗信息数据库的参考数据集，由270种医学期刊的标题和摘要组成，主要提取了数据集中的标题、作者以及摘要的内容，并将其中的标点转化为空格以及对所有字母进行了大写转换，其中数据集TREC在网址https://trec.nist.gov/data/t9_filtering.html获取。

3.根据权利要求1所述的基于LSH的过滤验证字符串相似性连接方法，其特征在于，步骤2)中所述的预处理，包括如下步骤：(1)先将字符串数据集S中所有字符串按照长度递增的顺序进行排序，对于长度相同的字符串再按照字母表的顺序进行排序，生成一个有序的字符串集合A；

(2)基于哈希函数族H(m)产生一组哈希函数，并创建与哈希函数对应的哈希表，即通过对哈希函数 进行随机抽样来生成r×z的初始哈希表 其中r表示对于每个字符串进行CGK-嵌入的次数，z表示在LSH过程中，对CGK-嵌入生成的每个字符串使用哈希函数的个数。

4.根据权利要求1所述的基于LSH的过滤验证字符串相似性连接方法，其特征在于，步骤4)中所述的验证需要计算出所有候选字符串对的相似度，并将相似度大于等于给定阈值τ的字符串对找出来作为最终结果，验证步骤所采用的是传统的相似度计算方法——使用动态方法计算编辑距离，即使用一个|si|+1行、|sj|+1列的矩阵M，递归求得最终M(|si|,|sj|)的值，即为字符串对的编辑距离。