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

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

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

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

4)过滤：使用LSH函数对字符串集合S'中的每个字符串进行计算哈希值，将每个字符串分别映射到每个哈希函数对应的哈希表中，依据字符串长度进行初步过滤得到初始候选集合，对初始候选集合进行k次相似的过滤，得到最终候选集合；

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

2.根据权利要求1所述的基于LSH的过滤验证字符串相似性连接方法，其特征在于，步骤1)中所述的字符串数据集S来自公开的现实数据集TREC。

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

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

4.根据权利要求1所述的基于LSH的过滤验证字符串相似性连接方法，其特征在于，步骤3)中所述的空间映射，包括如下步骤：(1)设字符串集合A中所有输入字符串x长度的最大值为N，给定随机字符串R∈{0,1}3N|Σ|，利用R将输入字符串x∈A映射为输出字符串x'∈Σ3N；

(2)i为输入字符串x的个数，将i初始化为1，i初始化为1嵌入过程的步骤为j＝1，...,

3N，在第j步中，将x复制为x'；这时i有1/2的概率会加1，有1/2的概率保持不变；

(3)当i>|x|时，如果j<＝3N，则在x'后面加上任意字符“┴”来使得x'长度为3N，最终得到汉明空间的字符串集合S'。

5.根据权利要求1所述的基于LSH的过滤验证字符串相似性连接方法，其特征在于，步骤4)中所述的过滤包括如下步骤：(1)基于长度的初步过滤：利用LSH函数依次对字符串集合S'中的每个字符串计算哈希值，当一个字符串被哈希到其中一个哈希表中时，该字符串并不会与哈希表中其它的字符串组成候选对，而是依据字符串长度进行初步过滤得到初始候选集合，当任意一个新的字符串sj被映射到哈希表中后，根据预先设定的编辑距离阈值τ作为过滤半径，字符串sj与哈希表中已有的字符串si进行长度对比，若|sj|-|si|<＝τ，则将作为候选对加入初始候选集合，若|sj|-|si|>τ，则将过滤掉；

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

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

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

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