一种基于结构和内容二级过滤的Web数据相似性检测方法

摘要

本发明公开了一种基于结构和内容二级过滤的Web数据相似性检测方法，在传统的通用相似性检测方法的基础上，发掘出Web数据结构和内容分布的特点，对检测的文档集进行两级过滤；两级过滤中的第一级过滤是结构相似性过滤，对每个Web文档建模为Tag树结构，从而剔除在结构上不相似的文档集，并对剩余的文档进行关键内容抽取，将其表示成元组向量的形式，将关键信息连接起来生成字符串集；两级过滤中的第二级过滤则对第一级过滤后生成的字符串集进行Trie树结构建模，并对相似字符串进行连接，得到最终的结果。经过多次实验证明，采用本发明提出的方法能够显著提高web领域数据相似性检测的效果。

说明书

技术领域

本发明属于Web数据结构和内容的相似性检测领域，尤其涉及一种基于结 构和内容二级过滤的Web数据相似性检测方法。

背景技术

Web数据通常是利用XML或者HTML等形式进行存储和交换的，数据通 过各种不同的标签组织在一起。由于Web数据传播速度快，且html网页的格式 比较灵活，传播较广的网页被转载或改动的几率比较大，且同属于某一相同主题 的数据组织形式可能相互不同，但相似度较高。因此对相似性数据进行检测和排 除，对数据的分类和聚类、数据挖掘、聚焦搜索引擎、模式识别和文章检测等领 域是非常有意义的。

传统的Web数据相似性检测方法主要集中在对Web数据的结构相似性检测 和对内容字符串相似性检测这两个领域中。对于结构相似性检测，主要首先基于 文档中包含的数据建立索引树。目前提出的基于索引树的K最邻近搜索算法如 R-tree(参见文献3)，K-D树(参见文献4)，SR树(参见文献5)返回准确的 结果，但是对于高维数据的时间效率并不高。文献2提出了位置敏感哈希函数 LSH的方法，基本的方法是使用一个位置敏感哈希函数族将高维空间中的对象 hash到邻近的桶中。执行相似性搜索时，这个索引方法将一个查询对象hash到 一个桶中，将hash到的桶中的值作为候选结果集，然后基于相似性距离测量对 候选结果集排序。

在候选数据集中Web文档可以模型化为有序带标签的根树(参见文献1、文 献2)。文档中的元素和属性可以看作是结构节点或者内部节点。将树编辑距离 作为衡量TAG树之间相似性的标准，其中树编辑距离是指使用删除、插入、重 命名标签等操作，将一棵树转化为另外一棵树所操作的最少节点。当两棵树的编 辑距离在一定的阈值范围内，认为它们是相似的。

最近的研究中，学者Panigrahy提出了一种基于熵的LSH方法(参见文献6)， 这种方法除了查询对象外随机对查询对象附近的对象求熵，然后将所有结果的交 集作为候选集。这个方法以时间换取空间。但是针对Web数据集较大的情况， 花费的时间不切实际，实用性不高。虽然存在着各种LSH的改进算法，但是由 于LSH算法本身存在例如很难找到一种随给定数据的规模和分布特点而改变的 哈希函数，且需要耗费大量的内存资源而不能及时释放等缺陷，使得求解的过程 效率不高，而且最终的结果也不可能是绝对近似的，仅仅靠对LSH算法的改进 很难取得预期的效果。

已有的算法对文档内容的字符串相似性检测通常采用一种先过滤后验证的 框架(见文献7)，过滤步骤中，通常对字符串集中的每个字符串生成一个签名， 并利用字符串见的签名之间的特征生成未经验证的近似对。然后在后续的验证过 程中，对近似对进行正确性验证。在满足给定的条件后，输出最终的相似结果， Binary branch(参见文献7)，Min-Hashing based LSH(参见文献8)和All-Pairs-ED (参见文献9)方法均是属于此框架中的相似性检测方法。虽然这些算法能够满 足部分字符串相似检测的需求，但是不能适应字符串集中平均字符串长度较小或 较大的情况，这样会导致生成的签名不准确，易导致相似性检测的范围过宽从而 生成大量的相似对，增加后续验证过程的压力，且暂无一种针对任何情况都是适 用的验证方法，最终使生成的结果过多且不准确。

现有的相似性检测方法通常都是在算法效率和结果精度其中一个方面中进 行改进，而没有对适用领域进行深入探究。例如对Web空间中的文档和数据而 言，如果按照通用的已有相似性检测方法进行相似性挖掘，因为没有充分利用 Web数据的结构特征和字符串内容的分布区域特点，从而很难高效地找出近似内 容块。

文献1：Andrea Tagarelli,Sergio Greco.Semantic clustering of XML documents. In TOIS,2010。

文献2：Giovanni Mella,Elena Ferrari,Elisa Bertino,Yunhua Koglin. Controlled and cooperative updates of XML documents in byzantine and  failure-prone distributed systems.In TISSEC,2006。

文献3：A.Guttman.R-trees:A dynamic index structure for spatial searching.In  SIGMOD,1984。

文献4：J.L.Bentley.K-D trees for semi-dynamic point sets.In SCG,1990。

文献5：N.Katayama and S.Satoh.The SR-tree:An index structure for  high-dimensional nearest neighbor queries.In SIGMOD,1997。

文献6：R.Panigrahy.Entropy based nearest neighbor search in high dimensions. In SODA,2006。

文献7：Rui Yang,Panos Kalnis,and Anthony K.H.Tung.Similarity evaluation  on tree-structured data.In SIGMOD Conference,2005。

文献8：R.Panigrahy.Entropy based nearest neighbor search in high dimensions. In SODA,2006。

文献9：R.J.Bayardo,Y.Ma,and R.Srikant.Scaling up all pairs similarity  search.In WWW,2007。

发明内容

针对上述已有算法存在的问题，本发明提出一种基于结构和内容二级过滤的 Web数据相似性检测方法。

本发明所采用的技术方案是：一种基于结构和内容二级过滤的Web数据相 似性检测方法，其特征在于：在传统的通用相似性检测方法的基础上，发掘出 Web数据结构和内容分布的特点，对检测的文档集进行两级过滤；两级过滤中 的第一级过滤是结构相似性过滤，对每个Web文档建模为Tag树结构，从而剔 除在结构上不相似的文档集，并对剩余的文档进行关键内容抽取，将其表示成元 组向量的形式，将关键信息连接起来生成字符串集；两级过滤中的第二级过滤则 对第一级过滤后生成的字符串集进行Trie树结构建模，并对相似字符串进行连 接，得到最终的结果。

作为优选，所述的第一级过滤具体实现包括以下步骤：

步骤A1：对输入的待检测Web文档集进行预处理，提取Web文档结构模 型Tag.tree，并建立有效节点索引；

步骤A2：结合MapReduce并行构造所有Tag.tree的二叉分支向量(Binary  Branch Vector)；

步骤A3：为Tag.tree的二叉分支向量建立多指针LSH索引；

步骤A4：查询给定查询q的结构相似性Web文档集S₁；

步骤A5：获取Web文档集S₁基于Tag树抽取的内容六元组向量集W，基 于W使用字符串连接算法，获取查询q的相似性结果集S₂。

作为优选，步骤A1的具体实现包括以下子步骤：

步骤A1.1：结合MapReduce，并行处理存放在分布式文档系统(HDFS)中 的Web文档数据集，使用基于路径标签的Tag树建模方式，提取Web文档结构 模型Tag.tree；

步骤A1.2：新建一个MapReduce任务，Map任务的输入key为文件名，value 为Tag.tree，reduce任务的key为文件名，value为Tag.tree对应转化的二叉树B 的二叉节点向量，将reduce的结果输入到HDFS中。

作为优选，步骤A2的具体实现包括以下子步骤：

步骤A2.1：新建一个MapReduce任务，计算所有Tag.tree的二叉节点向量 集合S，接着使用Hadoop的DistributedCatch功能，把全域集合S分发到系统中 的各个DataNode；

步骤A2.2：根据S和每一个Tag.tree的二叉节点向量，使用一个MapReduce 任务构建其二叉分支向量BBV；map任务的key为文件名，value为Tag.tree的 二叉节点向量；reduce任务的key为文件名，value为对应Tag.tree的BBV；

步骤A2.3：任务把每一个Tag.tree的BBV写入HDFS。

作为优选，步骤A3的具体实现包括以下子步骤：

步骤A3.1：为建立多指针LSH索引，初始化L个hash表，每个表中初始化 M个hash函数，r个哈希桶；使用一个MapReduce任务，计算所有Tag.tree的 BBV的索引；

步骤A3.2：假设某Web文档X的二叉分支向量为m，首先对m计算M次 哈希函数，设g_i(m)是查询m在第i张哈希表中的哈希值，即 g(m)＝(h₁(m),…,h_M(m))；

步骤A3.3：初始化L维扰动向量Δ，其中Δ＝(Δ₁,…,Δ_L)，g_i(m)+Δ₁是将 干扰向量Δ₁应用于g_i(m)得到的哈希桶的一阶指针，它指向哈希表中另外一组哈 希桶，每个扰动向量都映射到一组独特的哈希值，且指针指向一个hash桶至多 一次；

步骤A3.4：依次将Δ中的扰动向量应用于g_i(m)，得到i(i＝1,2,…,L)阶指 针，指向不同的哈希桶，建立多指针索引；

步骤A3.5：根据所有Tag.tree的指针构建情况，二阶以内的哈希桶给定组编 号BandID；MapReduce任务的key为组编号BandID和桶号BucketID，value为 对应的Web文件名。

作为优选，步骤A4的具体实现包括以下子步骤：

步骤A4.1：提取给定查询q的二叉分支向量，基于多指针LSH索引，快速 检索出q的top-k临近点，筛选出其中二叉分支距离BDist(T_i,T_q)满足条件 的T树集合S₁，作为二级索引输入；

步骤A4.2：基于索引s快速检索出q的top-k临近点；

计算查询q的M次哈希函数，设g(q)是查询q在第i张哈希表中的哈希值， 即其中g(q)＝(h₁(q),…,h_M(q))，g_i(q)+Δ₁是将干扰向量Δ₁应用于g_i(q)得到的哈 希桶的一阶指针，根据索引s，获取所有距离给定点q二阶以内的哈希桶，即为 查询q的top-k邻近点。

作为优选，步骤A5的具体实现包括以下子步骤：

步骤A5.1：基于步骤A1，获取Web文档集S₁的Tag.tree集合；

步骤A5.2：根据Web文档X的Tag.tree有效索引，获取所有有效节点的叶 子中的内容；

步骤A5.3：根据父节点标签，判断叶子节点类型后，加入X的六元组向量， 其中六元组向量是由X的编号(id)，标题(title)，内容(content)，关键词(KeyWord)， 链接(URL)，发布时间(PageTime)组成。

作为优选，所述的第二级过滤具体实现包括以下步骤：

步骤B1：从第一级过滤生成的六元组向量中提取出字符串集合U (u₁,u₂,u₃,…u_k)和V(v₁,v₂,v₃,…v_l)，两个字符串集合存在完全相同的可能性；其 中的每个字符串为每个元组向量中编号(id)，标题(title)，内容(content)，关 键词(KeyWord)，链接(URL)，发布时间(PageTime)进行串联的结果；根据 实际应用情形确定字符串编辑距离阈值τ；

步骤B2：对字符串集U和V中的字符串按照字典排序，形成有序集合，基 于此有序集合建立Trie树H_u∪v，Trie树由U和V中的每个字符对应的节点组成， Trie树节点保存着节点编号，节点与字符的映射关系，节点所属的字符串集以及 节点之间的结构关系；

例如，Trie树H_u∪v中，每个节点按照先序遍历编上号，基于节点所属的集合 对每个节点进行标注(只属于U，或者只属于V，或者属于U∪V)。同时，节 点需要存储与其他节点之间的父子，兄弟等位置关系，以便于遍历查找。

步骤B3：创建“已访问节点栈”数据结构，用以存储已经访问过的Trie树 节点；栈初始化为只有根节点和其对应的活跃节点集；

例如，根据Trie树的最大深度创建长度为|H_U∪V|的“已访问节点栈”ST， ST中每个元素包括节点的编号和节点的活跃节点集。

步骤B4：建立一个只有根节点root的动态Trie树H’，求解根节点root的活 跃节点集，并确定下一个求解活跃节点集的节点，称之为目的节点；

步骤B5：针对下一个目的节点，创建虚拟Trie树H'_u∪v；

步骤B6：基于引理1通过位于栈ST最上层元素的活跃节点集求出目的节点 的活跃节点集合；

其中引理1：给定Trie树H_x中的一个节点l及其父节点p,以及字符串编辑距 离阈值τ，对于任意的节点l'∈Q_τ(l),一定存在一个节点p'是l'的祖先节点且满足 p'∈Q_τ(p)；

步骤B7：基于Trie树活跃节点定义中对活跃节点对称性的叙述，更新栈ST 中与栈最上面的元素距离为τ之内的元素的活跃节点集；

步骤B8：判断当前处理的节点p是否为Trie树结构的某一叶子节点，如果 是，则对于输出相似字符串配对<o,p>；

步骤B9：在Trie树H'_u∪v中取出目的节点的属于同一字符集的子节点或兄弟 节点最为新的目的节点，重复步骤B5至步骤B8，直到栈ST为空为止。

作为优选，步骤B4的具体实现包括以下子步骤：

步骤B4.1：基于字符串编辑距离求出根节点的活跃节点集Q_τ(root)，将根节 点和相应的活跃节点集压入栈ST；

所述的字符串编辑距离，指定两个字符串s(s₁s₂s₃…s_m)和t(t₁t₂t₃…t_n)，s 与t的字符串编辑距离表示为ED(s,t)，表示为字符串s以单个字符为单位通过 替换、插入和删除这三种操作方式转变为t的最少操作次数；如果s为空，则表 示为ED(s,0)；

对于ED(s,t)，存在一定程度的递增性：

①ED(s_i0)＝i,ED(t_j,0)＝j,1≤i≤m,1≤j≤n；

②ED(s_i,t_j)≥ED(s_i-1,t_j)+1,1<i≤m,1≤j≤n；

③ED(s_i,t_j)≥ED(s_i,t_j-1)+1,1≤i≤m,1<j≤n；

④ED(s_i,t_j)＝ED(s_i-1,t_j-1),1<i≤m,1<j≤n,s_i＝t_j；

⑤ED(s_i,t_j)≥ED(s_i-1,t_j-1)+1,1<i≤m,1<j≤n,s_i≠t_j；

步骤B4.2：从根节点的活跃节点集中抽取出只属于字符串集U的节点集N， 从中选择最靠近根节点的节点n’。

作为优选，步骤B5的具体实现包括以下子步骤：

步骤B5.1：基于引理A和引理B在Trie树H_u∪v中筛选出与求解节点n’的 活跃节点集无关的节点区域；

所述的引理A：给定一个字符串s和t，以及字符串编辑距离阈值τ，如果 ||s|-|t||>τ，则有：ED(s,t)>τ，其中|s|和|t|分别表示字符串s和t中包含的 字符个数；

所述的引理B：给定Trie树结构H_x及其中的两个节点u和v，以及字符串 编辑距离阈值τ，如果存在以下条件之一：

(1)v是u的祖先节点，且分别以v和u作为根节点的子树含有相同的叶 子节点；

(2)只存在一个字符串将v与u同时作为前缀字符串，则在计算Q_τ(u)时， 不用考虑为v作为父节点或祖先节点的所有后续节点；

步骤B5.2：对节点区域进行灰色标记，形成一个基于原有Trie树H_u∪v的专 门针对n’的虚拟Trie树H'_u∪v。

作为优选，步骤B6的具体实现包括以下子步骤：

步骤B6.1：如果目的节点同属于两个集合，则设定目的节点属于其中某一 个集合，并在虚拟Trie树H'_u∪v中排除只属于该集合的节点；如果目的节点只属 于某一个集合，则同样，在虚拟Trie树H'_u∪v中排除只属于该集合的节点；

步骤B6.2：在H'_u∪v中，根据栈ST上的最上层的父节点的活跃节点集求出 目的节点的活跃节点集；

步骤B6.3：将目的节点压入栈ST中，最上层的元素即目的节点的编号和其 相应的活跃节点集。

本发明的优势在于在相似性检测的过程中充分利用了互联网半结构化数据 的结构特征和分布特点。一方面，基于抽取出的相似性特征分别对输入的Web 文档集进行结构建模和内容处理，并通过两级过滤从结构构建和内容分布两方面 对Web数据进行检测，从而提高了Web数据相似性检测的精度；另一方面，通 过第一级结构相似性检测过滤能够提前将一些不可能属于相似集的杂质数据剔 除，减少了后续相似性匹配候选集的元素个数。同时在相似性过程中分别采用了 多指针LSH索引和Tree树建模机制，所以提高了相似性检测的效率和实用性。 经过多次实验证明，采用本发明提出的方法能够显著提高Web领域数据相似性 检测的效果。

附图说明

图1：是本发明实施例的Web文档相似性检测并行处理流程框架图。

图2：是本发明实施例的基于路径标签的Tag树建模图，其中(a)部分为某 Web文档，(b)部分展示的是该Web文档转化而来的Tag.tree。

图3：是本发明实施例的Tag树与二叉树之间的转换示例图。

图4：是本发明实施例的二叉节点向量示例。

图5：是本发明实施例的多指针LSH算法流程框架图。

图6：是本发明实施例的top-K最邻近的桶距离的分布图，其中(a)部分为单 个不同hash值统计图，(b)部分为不同阶扰动向量所指个数统计图。

图7：是本发明实施例的基于一个示例字符串集建立的Trie树结构。

图8：是本发明实施例的两个示例字符串的编辑距离矩阵图。

图9：是本发明实施例的基于两个字符串集合建立的Trie树结构。

图10：是本发明实施例的针对与活跃节点集求解不相关的节点集区域进行裁剪 的三种方法示意图。

图11：是本发明实施例的展示Trie树节点被访问顺序的示意图。

图12：是本发明实施例的在不同字符串集之间进行字符串相似性连接的过程示 意图。

图13：是本发明实施例的基于不同参数的方法与传统方法的运行效果对比图。

图14：是本发明实施例在不同的数据集中利用本方法与传统方法的运行效果对 比图，其中(a)部分为本发明提供的方法运行效果图，(b)部分为传统方法运 行效果图。

图15：是本发明实施例的基于不同参数的方法与传统方法的精确度对比图。

图16：是本发明实施例的基于结构和内容二级过滤的相似性检测方法的流程图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对 本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解 释本发明，并不用于限定本发明。

请见图1，本发明所采用的技术方案是：一种基于结构和内容二级过滤的 Web数据相似性检测方法，在传统的通用相似性检测方法的基础上，发掘出Web 数据结构和内容分布的特点，对检测的文档集进行两级过滤；本发明认为包含相 似的Web数据的文档首先结构应该相似，如果两个文档的结构存在很大差异， 那么进一步求解内容相似性的意义不大。因此，两级过滤中的第一级过滤是结构 相似性过滤，对每个Web文档建模为Tag树结构，从而剔除在结构上不相似的 文档集，并对剩余的文档进行关键内容抽取，将其表示成元组向量的形式，将关 键信息连接起来生成字符串集；两级过滤中的第二级过滤则对第一级过滤后生成 的字符串集进行Trie树结构建模，并对相似字符串进行连接，得到最终的结果。

Tag树(Tag.tree)是本文发明的重要的数据结构，用来对Web文档结构进 行树建模，Tag.tree是根据Web文档中元素或属性的路径来分解Web文档。

在大规模Web文档数据集下，将Tag.tree中的非正文区域转化为二叉树，不 仅浪费大量存储空间，而且会影响文档结构相似性判断的准确性。为了解决这个 问题，采取对Tag.tree建立有效节点索引的方法，只转化Tag.tree的索引区域， 提高二叉树转化效率。

定义1(Web文档标签节点树)：Tag.tree是一个Web文档X的有序的带标 签根树，Tag.tree的每一个节点都与X的元素或者属性相关。每个节点的id都与 其在X文档中的顺序有关，id按照序号分级方式进行编辑。对于每一个节点， 都存在一个序号路径(tag₀,tag₁,…,tag_n)。

请见图2，图2的(a)部分为某Web文档，将标签和标签之间的内容抽象 成为简单的字母，以重点突出标签结构的分布。(b)部分展示的是该Web文档 转化而来的Tag.tree，通过路径分级方式，可以很迅速的找到某个id的父节点序 号。观察(b)可以看到Tag.tree有如下性质：

①叶子节点不存在兄弟节点。

②叶子节点为标签中对应的元素，当不存在元素时用NULL标记。

定义2(Tag.tree有效节点索引)：遍历Tag.tree，若某路径下访问到的叶子 节点中元素不为空，且不是噪声，则该路径上的所有节点为有效节点。所有有效 节点组成了Tag.tree的有效节点索引。

请见表1，标记图2中所有有效节点，标记过程如表1所示。

表1Tag树建立有效节点索引示例

Key 遍历的节点id 有效节点 (abc,w) 1，1.1，1.1.1 a,b,c (abde,null) 1，1.1，1.1.2，1.1.2.1   (abdf,null) 1，1.1，1.1.2，1.1.2.2   (agh,null) 1，1.2，1.2.1   (agik,null) 1，1.2，1.2.2，1.2.2.1 a,g,i,k (agil,null) 1，1.2，1.2.2，1.2.2.2 a,g,i,l (agim,null) 1，1.2，1.2.2，1.2.2.3 a,g,i,m (agil,null) 1，1.2，1.2.2，1.2.2.4 a,g,i,n (agj,null) 1，1.2，1.2.3  

定义3(路径编辑距离)：设T是文档X的Tag.tree，pre(T)和post(T) 分别表示树T的先序遍历操作及后序遍历操作。将pre(T)和post(T)的遍历 路径表示为字符串s1，s2，则ed(s1,s2)是s1,s2之间的路径编辑距离。树编辑 距离TD(T1,T2)与路径编辑距离ed(s1,s2)存在如下关系：

ed(pre(T1),pre(T2))≤TD(T1,T2)

ed(post(T1),post(T2))≤TD(T1,T2)

一棵树与它的二叉树可以相互转化，对于树中的任意节点，在转化为二叉树 的过程中，它的左孩子变为二叉树的左节点，它的右兄弟变为左孩子的右节点。

请见图3，将T₁₂、T₂₁转化为二叉树B(T₁₂)、B(T₂₁)时，本发明将B (T₁₂)、B(T₂₁)转化为一棵满二叉树，节点不足时用*代替。从图中可以看到， T₁₂根节点u₁的左孩子u₂为B(T₁₂)的左孩子，u₂的右兄弟为B(T₁₂)左孩子 u₂的右节点。

定义4(二叉分支Binary Branch)：设B为二叉树，存在一个二叉分 支，即节点u，及其两个孩子节点。

请见图3，展示了二叉树B(T₁₂)、B(T₂₁)的所有二叉分支。从图中可 以看到，对于B(T₁₂)、B(T₂₁)中的每个节点均存在二叉分支，例如B(T₁₂) 存在二叉分支的父节点为u₁和孩子点u₂,*。

定义5(二叉节点向量Binary Node Vector)：设B为二叉树，将B的所有二 叉分支表示为向量V＝(v₁,v₂,…,v_n)，v_i是树T的第i个分支，假设v_i标签为a， 其孩子节点标签为a,*，则vi＝(a,a,*)。

请见图4，展示了二叉树B(T₁₂)、B(T₂₁)的所有二叉节点对应的二叉 节点向量。例如B(T₁₂)存在二叉分支的父节点为u₁和孩子点u₂，*，其对应的 二叉节点向量为(a,a,*)。

定义6(二叉分支向量Binary Branch Vector)：设树T的二叉分支向量BBV (T)为(b₁,b₂,…,b_|B|)，其中b_i是指树T的二叉树B中的第i个节点的序号，|B| 表示二叉树B的大小。

请见表2，列出了图5中二叉分支向量的构建方法，若二叉树中T中存在某 二叉节点向量则标记为1，当不存在时标记为0。

表2构建二叉分支向量

  BBV(T1) BBV(T2)

(a,a,*) 1 1 (a,*,e) 1 0 (a,f,b) 0 1 (b,*,c) 1 0 (b,*,X) 0 1 (b,*,y) 0 1 (c,*,g) 1 0 (e,*,b) 1 0 (f,*,b) 0 1 (g,*,*) 1 0 (x,*,*) 0 1 (y,*,*) 0 1

定义7(二叉分支距离Binary Branch Distance)：设BBV(T1)＝ (b1,b2,…,b|B|)，BBV(T2)＝(b1’,b2’,…,b|B|’)为树T1，T2的二叉分支向量， 它们的二叉分支距离是对于任意的两个树T1，T2 满足$\frac{\mathrm{BDist}(T1,T2)}{5}\le \mathrm{TD}(T1,T2).$

定义8(哈希干扰向量Hash Perturbation Vectors)：设m维向量Δ＝{δ₁,…,δ_m}， g_i(q)是查询q在第i张哈希表中的哈希值。将干扰向量Δ应用于哈希桶，得到 哈希桶指针g_i(q)+Δ，它指向一组哈希值。通过使用多个干扰向量，可快速定 位到与查询对象哈希值最接近的哈希桶。

对于给定一个查询q，使用基本LSH算法检索哈希桶得到哈希值g(q)＝ (h₁(q),…,h_M(q))。将干扰向量Δ应用于g(q)，得到一组哈希桶的指针为g (q)+Δ。其中LSH函数形式为如果W足够大，很大的可能 性上，相似的对象具有相同的或邻近的值，因此，干扰向量Δ可用于指向这些 含有邻近的值的桶，其中δ_i∈{-1,0,1}。

将扰动向量被直接施加到查询对象的哈希值，可以避免点扰动，以及使用基 于熵的LSH方法计算哈希值的额外开销。设计一组扰动向量序列，其中每个扰 动向量都映射到一组独特的哈希值，且不会指向一个hash桶多于一次。

请见图5，设g_i(q)是查询q在第i张哈希表中的哈希值，(Δ₁,…,Δ_L)是一 个指针序列，g_i(q)+Δ₁是将干扰向量Δ₁应用于g_i(q)得到的新哈希值，它指 向哈希表中另外一个哈希桶。根据上述原理，n阶扰动向量首先指向所有的一阶 的桶，再指向二阶的桶，以此类推。基于L个hash表和每个表中M个hash函数 的LSH索引，n阶桶的总数是$L\times \left(\begin{array}{c}M\\ n\end{array}\right)\times 2^n,$在s阶内的桶的总数是 $L\times {\Sigma }_{n=1}^s\left(\begin{array}{c}M\\ n\end{array}\right)\times 2^n.$通过使用多个干扰向量本发明定位到更多的哈希桶，这些桶 中的哈希值近似于查询对象的哈希值。

多指针LSH算法的核心思想是，使用一个指针序列来检查大量的桶，这些 桶中可能含有与查询对象q最近邻的点。根据位置敏感哈希函数的性质，本发明 了解到如果一个对象跟查询点q很接近，但与q不是哈希到同一个桶中，而是在 q邻近的桶中，即两个桶的hash值只有很细微的差别。本发明的目标是定位这些 邻近的桶，因此增加查找q的邻近点的机会。

定义9(top-K最邻近分布)：设n阶哈希干扰向量Δ不为零，Δ用于探测与 给定查询哈希值最接近的桶。基于位置敏感哈希函数的属性，一阶探测指针所指 向的桶比二阶探测指针所指向的桶离查询点更近。

请见图6，展示了top-K最邻近的桶距离的分布，其中(a)部分为单个不同 hash值统计图，(b)部分为不同阶扰动向量所指个数统计图，(a)部分曲线展示 了单一hash值δ_i不同，(b)部分曲线展示了hash值的个数不同于查询点的hash 值。从曲线中可以看到，集合中所有的K最近邻点的hash值要么相同(δ_i＝0)， 要么不同δ_i+1或者δ_i-1。同理，大多数K最近邻点都hash到了离给定点的哈希 桶二阶以内的哈希桶中。

请见图16，是本发明提出的基于结构和内容的二级过滤的整体流程图，其 中左半部分阐述了第一级结构过滤的算法过程。具体包括以下步骤：

步骤1：根据Web文档中元素和属性的路径来分解Web文档，提取Web文 档结构模型Tag.tree，并建立有效索引。

子步骤1：请见图2，使用序号分级方式，按照节点在Web文档中的顺序， 构建Tag.tree。

子步骤2：计算Tag.tree的有效节点，并进行标记。

步骤2：根据有效节点建立的索引，获取Tag.tree的二叉分支向量。

子步骤1：请见图3，将Tag.tree的索引区域结构树转化为二叉树B。

子步骤2：请见图4，获取二叉树B的所有二叉分支，并将二叉树B的所有 二叉分支转化为二叉节点向量。

子步骤3：根据所有Web文档的二叉节点向量集合S，获取二叉树B的二叉 分支向量。

步骤3：为Tag.tree的二叉分支向量建立多指针LSH索引。

子步骤1：根据步骤1，步骤2获取Web文档X的二叉分支向量m。

子步骤2：初始化L个hash表，每个表中初始化M个hash函数，r个哈希 桶，对X的二叉分支向量m计算M次哈希函数，设g_i(m)是查询m在第i张哈 希表中的哈希值，即g(m)＝(h₁(m),…,h_M(m))。

子步骤3：初始化n维扰动向量Δ，其中Δ＝(Δ₁,…,Δ_L)。

子步骤4：依次将Δ中的扰动向量应用于g_i(m)，得到i(i＝1,2,…,n)阶指 针，例如g_i(m)+Δ₁是将干扰向量Δ₁应用于g_i(m)得到的哈希桶的一阶指针， 它指向哈希表中另外一组哈希桶，每个扰动向量都映射到一组独特的哈希值，且 指针指向一个hash桶至多一次。

子步骤5：对于Web文档集中每一个文档X，根据子步骤1、2、3、4建立 多指针LSH索引。

步骤4：查询给定查询q的结构相似性Web文档集S₁。

子步骤1：提取给定查询q的二叉分支向量，基于多指针LSH索引检索算法， 快速检索出q的top-k临近点。

请见图5，基于索引s快速检索出q的top-k临近点的详细过程包括以下步 骤：

①计算查询q的M次哈希函数，设g(q)是查询q在第i张哈希表中的哈 希值，即其中g(q)＝(h₁(q),…,h_m(q))。

②初始化L维干扰向量Δ，其中Δ＝(Δ₁,…,Δ_L)，且Δ_i＝{δ₁,…,δ_m}，将干扰 向量Δ₁应用于g_i(q)得到的哈希桶的一阶指针g_i(q)+Δ₁，以此类推，获取q 的各阶桶指针。

③根据LSH多指针索引，获取所有距离给定点q二阶以内的哈希桶中的向 量，即为查询q的top-k邻近点。

子步骤2：从q的top-k临近点中筛选出其二叉分支距离BDist(T_i,T_q)满足 条件的T树集合S₁，作为二级索引输入。

接着进行第二级内容字符串相似性过滤，在详细说明之前，首先给出在算法 说明过程中起着关键作用的若干个关键定义。

定义10(字符串编辑距离)：指定两个字符串s(s₁s₂s₃…s_m)和t(t₁t₂t₃…t_n)， s与t的字符串编辑距离表示为ED(s,t)。表示为字符串s以单个字符为单位通 过替换、插入和删除这三种操作方式转变为t的最少操作次数。

例如，字符串“tobe”与字符串“buffe”的字符串编辑距离ED(tobe,buffe) ＝4,即字符串“tobe”通过三个字符替换操作和一个字符删除操作可以变成字符串 “buffe”，分别是t->u,o->f,b->f，并删除字符f。

如果s为空，则表示为ED(s,0)。对于ED(s,t),很容易得出ED(s,t)存 在一定程度的递增性：

①ED(s_i0)＝i,ED(t_j,0)＝j,1≤i≤m,1≤j≤n),

②ED(s_i,t_j)≥ED(s_i-1,t_j)+1,1<i≤m,1≤j≤n

③ED(s_i,t_j)≥ED(s_i,t_j-1)+1,1≤i≤m,1<j≤n

④ED(s_i,t_j)＝ED(s_i-1,t_j-1),1<i≤m,1<j≤n,s_i＝t_j

⑤ED(s_i,t_j)≥ED(s_i-1,t_j-1)+1,1<i≤m,1<j≤n,s_i≠t_j

定义11(字符串集相似性连接与字符串相似)：给定两个字符串集合S和T， 以及字符串编辑距离阈值τ,本发明认为，判定字符s与字符串t相似的依据是s 与t的字符串编辑距离不大于设定的阈值τ,即由命题ED(s,t)<＝τ可推导出结论s≈t,“≈”表示字符串相似。字符串集合S与T的相 似性连接可以理解为从两集合中各取一个字符串组成相似字符串的匹配对。记连 接的结果为表示为

例如，两个字符串集合S与T所包含的字符串为： S＝{“internalize”,“ideology”,“emigrant”,“expand”,“principal”,“allusion”},T＝{,“immig  rant”,“internalized”,“internalizing”,“thermostat”,“delusion”,“principle”,“expend”, “compliment”},如果指定字符串编辑距离阈值τ＝1，则S与T相似性连接的结果 为如果τ＝2，则相似性连接的结果为

本发明中，如果未对字符串编辑距离阈值τ作出特别说明，默认τ＝1。

定义12(字符串前缀)：设字符串s＝s₁s₂s₃…s_n,则 s₁s₂s₃...s_m(1≤m<n)为s中位于字符s_i之前的一个字符串前缀s’。如 果将字符串s看做由各个字符按照原有顺序组成的一个集合,则s’是s的一个子集。 s’必须保持s中原有字符的顺序，且不能任意缺少其中一个字符。在字符串s中 字符c(c∈s)之前的前缀字符串表示为s^＜c。

例如，对于字符串s＝“prerequisite”而言，“pre”,“prereq”和“prerequis”均是s 的前缀。

定义13(Trie结构)：Trie结构是本发明为第二级内容字符串过滤而提出的 树状数据结构。其中，树的根在最上层，中间节点和叶子节点在下面，呈自上而 下的树状结构。Tie结构中各部分的具体含义如下所示

①根节点为root，代表空字符串φ。

②中间节点代表一个字符串的前缀字符串，至少包含一个字符。

③节点只可能有一个父节点(根节点无父节点)，而可能有0个或多个子节 点。

④从根到节点之间的路径表示各字符按照从上到下的顺序组成的一个子串 或者一个完整的字符串。该路径与其最后一个节点相对应。

⑤叶子节点代表从根节点root到它的一个路径，与一个完整的字符串对应。

⑥树中某个节点的所有子节点具有相同的前缀字符串。

请见图7，展示了几个字符串的Trie结构，分别是“barren”，“beam”，“bean”， “bear”，“exdend”，“extant”和“thorough”。每个节点旁边标注的数字代表其编 号ID，其中根节点root的ID为0。中间节点的编号ID代表了该节点所对应的 字符子串，叶子节点的编号ID代表了该节点对应的完整的字符串。图7中的编 号为15的中间节点表示子串“exde”，而编号为6的叶子节点表示为“barren”。 而反过来，字符子串或者完整的字符串也能够唯一地确定其ID，例如，“bean” 的子串“bea”与ID为8的节点a对应，字符串“extant”唯一地确定ID为21 的节点t。即ID表示的节点与字符子串或完整的字符串是相互对应的。指定字符 串集S,Trie结构表示为H_x(x∈S)，以|H'_x|表示Trie结构中节点x的深度，|H_x| 表示Trie结构的最大深度，定义根节点root到节点x之后的中间节点或叶子节 点的路径所代表的子串或完整的字符串为h^x＜。

其中，S＝{s₁,s₂,s₃,…s_k}表示字符串集S由k个字符串组成，每个字符串的长 度即所含有的字符个数，表示为|s_i|(1≤i≤k)，|S|表示成字符串集S中含有的字 符串个数，有|S|＝k,针对均能在Trie结构H_x中对应一个节点h_x，而Trie 结构便是这些节点按照树结构组成的，有H_x＝{h_x|x∈S}，设为S中各字 符串中的最大长度，有$▿\left|S\right|=\max \left|s_i\right|,1\le i\le k,s_i\in S).|H_x|=▿|S|,$此时 $x\in \left\{s_j\right|▿\left|S\right|=\left|s_j\right|,1\le j\le k\};$

设|x|表示为x节点对应的字符所在的字符串中由第一个字 符到字符x的所有字符按照原有顺序组成的字符串的长度，或者根节点到x的路 径长度。有|x|＝|J^x|,如果x是J中的最后一个字符，则有|x|＝|J|。

例如，在图7所示的Trie树中，由于最长的路径为0(root)→22(t)→23 (h)→24(o)→25(r)→26(o)→27(u)→28(g)→29(h)，路径的 长度为8，所以|H_x|＝8。如果x表示编号为9的节点，则|H'_9(m)|＝|beam|＝4。

为了便于对Trie树结构的节点和所代表的字符串进行区分，本发明对节点 的表示约定为：如果节点编号ID已知的情况下，如果节点使用字符c表示，代 表从根节点到字符c组成的字符串w，则表示为ID(c)。在其他不易引起混淆 的情况下，则用节点c予以表示。

定义14(编辑距离矩阵)：给定两个字符串s和t，值分别为 s＝s₁s₂s₃…s_m,t＝t₁t₂t₃…t_n，有|s|＝m,|t|＝n,以及字符串编辑距离阈值τ，构造一种 数据结构存储s的所有子串与t的所有子串之间的字符串编辑距离的值，即编辑 距离矩阵M_m+1,n+1,对于任意一字符串r＝r₁r₂r₃…r_n，其子串 r_sub＝{φ∪r₁r₂...r_l|1≤l≤n}，总个数为1+n。

编辑距离矩阵M_m+1,n+1的维度分别对应字符串s与t的子串总数。s的子串总 数是1+m,t的子串总数为1+n，M_m+1,n+1的元素总数为(1+m)(1+n)，对应s的 每个子串与t的每个子串计算出的编辑距离总数，矩阵的每个元素为ED(s_sub,t_sub)。 图8所示的为字符串“immortal”与字符串“latitude”的编辑距离矩阵。

由定义14中的编辑距离的相关公式可以得出编辑距离矩阵每个元素的计算 见公式：

${▿}_{i,j}=\min \left(M\right[i,j-1]+1,M[i-1,j]+1,M[i-1,j-1]+\xi )$

其中，ξ表示为s_i单个字符组成的字符串与t_j单个字符组成的字符串之间的 字符串编辑距离，自然有：

$\xi =\left(\begin{array}{cc}0& s_i=t_j\\ 1& \mathrm{otherwise}\end{array}\right),$

$M[i,j]=\left(\begin{array}{cc}j& i=\mathrm{0,0}\le j\le n,\\ i& j=\mathrm{0,0}\le i\le m,\\ ▿i,j& 0<i\le m,0<j\le n\end{array}\right)$

例如，在图8中，M[0,k]＝M[k,0]＝k,(0≤k≤8),M[2,3]＝3,M[1,3]＝3, M[2,2]＝2,M[1,2]＝2,在图示的编辑距离矩阵中，s₂＝m,t₃＝t，由于s₂≠t₃，根 据ξ的计算公式，得到ξ＝1,满足M[2,3]＝min(M[1,3]+1,M[2,2]+1,M[1,2]+1)。 而对于s_i＝t_j的情况，满足M[6,5]＝min(M[5,5]+1,M[6,4]+1,M[5,4])，且ξ＝0。

定义15(矩阵近似项与Trie树活跃节点)：依据定义13和定义14，在本发 明中将矩阵近似项定义为M[k,r],满足M[k,r]≤τ，其中0≤k≤m+1,0≤r≤n+1， 由字符串编辑距离的定义14可以看出，由于字符编辑距离的递增性，存在 M[k'>k,r]≥τ,M[k,r'>r]≥τ，图11的Trie树所有节点的活跃节点集请见表3。

表3图11的Trie树所有节点的活跃节点集

图8所示的阴影部分表示的是τ＝1时的矩阵近似项，而实线圈住的部分是 τ＝3时的矩阵近似项。容易看出，矩阵近似项的数目随着τ的增长而增长。即 判定近似的范围越宽，近似结果的取值越容易。

由于字符串s和t既可以表示成编辑距离矩阵，又可以表示成Trie树结构， 因此，给定一个字符串集字符串集S对应的Trie树H_x(x∈S),与字符 串t，其中，字符串s对应的Trie树路径为h_υ(υ∈s),对于如果存在 ED(υ,t)≤τ，则υ对应的节点称为字符串t的Trie树活跃节点。字符串t的所有 Trie树活跃节点构成Trie树活跃节点集，记做Q_τ(t)，可以得出如果ED(t,e)≤τ， 则可推出e∈Q_τ(t)。图11中标注的箭头方向展示了一般情况下求解Trie树活跃 节点集的顺序，即优先求解父节点活跃节点集，再求解子节点或兄弟节点的活跃 节点集。其中，根节点标注的集合为root在τ＝1的活跃节点集，Q₁(root) ＝{0,1,9,13}。Trie树编号范围为0～17的各节点在τ＝1和τ＝2两种情况下的活跃 节点集见表3。

给定节点n和字符串s,t，由此定义易得s出如下结论：

如果则h^n＜≈s始终不成立。其中，s^＜c表示为字符 串s中c字符之前的前缀字符串(由定义13)。h^n＜表示为字符串t所在的Trie 树中节点位于节点n之后的节点代表的子串或者字符串(见定义13)，则此结论 表明如果节点n不是字符串s的任意一个前缀字符串的Trie树活跃节点，则Trie 树中位于节点n之后的节点代表的子串或者字符串不可能与s相似。

Trie树活跃节点具有对称性，即对于Trie树结构的任意两个节点u和v，如 果u∈Q_τ(v)，则一定有v∈Q_τ(u)。例如，图11中的节点4(b)的活跃节点集 Q₁(4(b))＝{3,4,5}，而节点5(i)的活跃节点集Q₁(5(i))＝{4,5}，节点3(m)的 活跃节点集Q₁(3(m))＝{2,3,4,8,11}。因为3∈Q₁(4(b)),5∈Q₁(4(b))，所以存在 4∈Q₁(3(m)),4∈Q₁(5(i))。

定义16(节点属于字符串集合)：节点n属于字符串集合的定义描述如下：

给定一个字符串集S(s₁,s₂,s₃,..s_m),Trie树H_x(x∈S∪Δ)以及其中的一个节 点n，Δ表示Trie树中的节点集对应的其他字符串集合，如果存在一个字符串s， 满足s∈S，且节点n对应的子串s(n)是字符串s的前缀字符串。则可以得出n∈S。

活跃节点集对于求解相似字符串对起着非常关键的作用。为了求出Trie树 的所有节点的活跃节点集，可以首先计算Trie树根节点root的活跃节点集，然 后计算根节点的子节点的活跃节点集。如果遍历所有的节点求出相应的活跃节点 集是非常费资源的，应该可以探究出一些规律提高Trie树中所有节点的活跃节 点集求解的效率。因此，在本发明中，先给出提高求解效率的几种方向，然后提 出相应的引理，最后举出实例并将引理实际应用于活跃节点集的计算过程中。

提高计算效率的几种方式为以下几种：

①充分利用Trie树的结构特点。Trie树是按照字符串的所有字符的原有顺序， 从上到下将所有字符进行排列，从根节点root到每个叶子节点的路径是独一无 二的，代表一个完整的字符串。有相同前缀的一组字符串在Trie树中共享节点。 可以利用父节点的活跃节点集来计算树中的中间节点或叶子节点的活跃节点集。 这样，通过利用共同前缀来降低某些共同子串的计算次数。

②从“矩阵近似项与Trie树活跃节点”的定义15可以看出，求解字符串t 的Trie树活跃节点只利用了Trie树来对字符串s的每个字符进行节点的映射， 而没有对字符串t进行Trie树的转变。针对字符串集S与T，对于其中的任意字 符串，应该要充分利用共享前缀的优势较少活跃节点的计算量。因此，应该对字 符串集S和T都分别构建Trie树结构。图9表示了基于S和T建立的Trie树， 将所有字符串都表示成Trie树的路径，这样，可以充分利用双集合在Trie树中 表现出的特点来提高活跃节点集的计算效率。

③发掘出Trie树结构中与求解某个节点的活跃节点集无关的节点集的模式 特征，利用模式特征在从上到下计算每个节点的活跃节点集的过程中，可以对符 合某类特征的节点区域集进行裁剪，从而降低Trie树节点数目，减少无关节点 的计算。

④根据已求出的父节点的活跃节点集求解子节点的活跃节点集，虽然在一定 程序删除一些不必要节点的活跃节点集计算，降低计算的次数，但是如果为所有 节点已知的活跃节点集花费内存等资源存储，则将占用大量的内存空间，对于字 符串较长或Trie树规模较大的情况则不适用。因此，利用一些节点活跃节点集 的计算只依赖部分节点的特点及时释放对后续节点求解无效的部分节点集，将大 大降低系统资源的使用量，提高算法的实用性。

针对上文中提出的提高活跃节点集求解效率的方式，下面针对性地提出一些 引理。

引理1：给定Trie树H_x中的一个节点l及其父节点p,以及字符串编辑距离阈 值τ，对于任意的节点l'∈Q_τ(l),一定存在一个节点p'是l'的祖先节点且满足 p'∈Q_τ(p)。

例如，图11中，设节点14(o)对应的字符串为e＝“so”，以及节点15(a) 对应的字符串为w＝“soa”，w为e的子节点。要计算Q_τ(w),只需要判断任意节点 t∈Q_τ(e)，t的所有子节点是否是节点w的活跃节点即可。由表3可知，当τ＝1 时，有Q_τ(e)＝{13,14,15}，要计算Q_τ(w)，只要查看节点13,14,15以及其所有子 节点是否属于Q_τ(w)，最后检查通过的节点集即为Q_τ(w)，有Q_τ(w)＝{14,15,16,17}。

引理2：给定Trie树结构H_x及其中的两个节点u和v，以及字符串编辑距 离阈值τ，如果对于v的任意祖先节点v’，均有且对于u的任意祖先 节点u',均满足则Trie树中节点u之后的节点所代表的子串或字符串 s(u)与节点v之后的节点所代表的子串或字符串t(v)不可能相似，即s(v)≈t(v)不 成立。

例如：图11中，观察节点1(b)，节点6(e)，节点13(s)和节点14(o)， 四个节点分别代表的字符串为“b”，“be”，“s”和“so”，由于 $6\notin (Q_{\tau }\left(\mathrm{root}\right)\cup Q_{\tau }\left(13\left(s\right)\right)\cup Q_{\tau }\left(14\left(o\right)\right)),$又有$14\notin (Q_{\tau }\left(\mathrm{root}\right)\cup Q_{\tau }\left(1\left(b\right)\right)\cup Q_{\tau }\left(6\left(e\right)\right)),$有节点6(e)和节点14(o)的所有后续节点所代表的字符串不可能相似，即“bed” 和“soak”，“bem”和“soak”，“bed”和“soap”，以及“bem”和“soap”不可 能相似。

引理3：给定一个字符串s和t，以及字符串编辑距离阈值τ，如果||s|-|t||>τ， 则有：ED(s,t)>τ。其中|s|和|t|分别表示字符串s和t中包含的字符个数。

在图10的(a)部分中，在节点s以及节点t旁标注了一个字符串长度区间 其中，表示以节点e作为“根节点”的子Trie树结构中最短的路 径长度，则为最长的路径长度。图中[1,4]表示节点s的后续节点表示的字符 串的长度范围为1～4，而[7,9]则节点s的后续节点表示的字符串的长度范围为7～9。 由于即两组字符串的长度相差大于字符串编辑距离阈值，所 以，可以在求解Q_τ(t)的过程中，可以忽略节点s的所有后续节点。在以实际的 Trie树根节点root作为根节点，节点s和t作为叶子节点的子Trie树结构中， $l_{\min }^{\mathrm{root}}=l_{\max }^{\mathrm{root}}=1,$有对于节点是的任意后续节点μ，有$s\in Q_{\tau }t^\mu \notin Q_{\tau }\left(t\right).$

例如，在计算图11的节点1(b)的活跃节点集可以；利用此引理来删除一 部分与计算Q_τ(1(b))无关的节点。节点1(b)、12(e)和22(t)的字符串长度 区间分别为[4,6],[6,6]和[8,8]，由于节点12(e)与节点1(b)的字符串长度相差 为[0,2]，而节点22(t)与节点1(b)相差为[2,4]，在τ＝1的情况下，可以删除 节点22(t)，而不能删除节点12(e)。

引理4：给定Trie树结构H_x及其中的两个节点u和v，以及字符串编辑距 离阈值τ，如果存在以下条件之一：

(1)v是u的祖先节点，且分别以v和u作为根节点的子树含有相同的叶 子节点；

(2)只存在一个字符串将v与u同时作为前缀字符串，

则在计算Q_τ(u)时，不用考虑为v作为父节点或祖先节点的所有后续节点。

图10的(b)部分和(c)部分即为两种条件的具体体现。(b)中，节点t 和s拥有相同的叶子节点且t是s的父节点，则计算Q_τ(s)将不用考虑节点t的后 续节点。(c)中，由于只存在一个字符串“sto”将节点s(代表字符串“s”)和 节点t(代表字符串“st”)同时作为前缀字符串，因此计算Q_τ(s)不用考虑节点o。

引理3和引理4可以结合起来作为提高活跃节点集计算效率的重要方法。因 为这两个引理可以通过删除不相关节点的方式来降低活跃节点集的计算量。例如， 在图7中求解节点4(r)的活跃节点集Q_τ(4(r))，可以利用引理3得到 Q_τ(4(r))＝{3,4,5}，利用引理4得到Q_τ(4(r))＝{4,5}，最终结果为Q_τ(4(r))＝{3,4,5}。

对于两个字符串集间的字符串相似性比较，应该考虑字符串集的关系对算法 过程的影响，对于不同类型的字符串集都应该适用。本发明首先基于字符串的共 享前缀和字符串间的结构特征创建Trie树结构。在进行相似性计算之前进行预 处理，即为了避免重复的计算，利用与Trie树节点间的相互作用和活跃节点集 相关的引理删除与活跃节点集计算不相关的节点区域。为了提到算法效率，充分 利用Trie树结构的特点，通过父节点已知的活跃节点集来求出子节点的活跃节 点集，同时对活跃节点集未知的节点进行动态增量式访问，从而一方面可以确保 不用访问并计算每个节点，另一方面也避免了为求某一个节点的活跃节点集而对 整个Trie树结构进行遍历。通过这种方式以降低访问量的方式能够显著提高计 算效率。同时，为了避免算法占用大量内存资源，本发明中通过引入“访问节点 栈”这个数据结构来存储只对求解即将要访问的节点活跃节点集有效的已访问节 点，而不是存储所有已访问的节点信息。通过提高计算效率和限制算法系统资源 的使用，本发明中提出的算法有很好的实用性，相对已有的方法具有优势。

基于上述中提到的对算法的整体过程的文字描述，下面以具体的算法流程结 合附图说明作进一步阐述。

图16是本发明提出的基于结构和内容的二级过滤的整体流程图，其中右半 部分阐述了第二级内容过滤的算法过程，具体实现包括以下步骤：

步骤1：从第一级结构相似性过滤生成的六元组向量中提取出字符串集合U (u₁,u₂,u₃,…u_k)和V(v₁,v₂,v₃,…v_l)，两个字符串集合存在完全相同的可能性。其 中的每个字符串为每个元组向量中标题(title)，关键词(KeyWord)，内容(content) 进行串联的结果。根据实际应用情形确定字符串编辑距离阈值τ。

步骤2：对字符串集U和V中的字符串按照字典排序，形成有序集合，基于 此有序集合建立Trie树H_u∪v，Trie树由U和V中的每个字符对应的节点组成， Trie树节点保存着节点编号，节点与字符的映射关系，节点所属的字符串集以及 节点之间的结构关系。

例如，Trie树H_u∪v中，每个节点按照先序遍历编上号，基于节点所属的集合 对每个节点进行标注(只属于U，或者只属于V，或者属于U∪V)。同时，节 点需要存储与其他节点之间的父子，兄弟等位置关系，以便于遍历查找。

步骤3：创建“已访问节点栈”数据结构ST，用以存储已经访问过的Trie 树节点。栈初始化为只有根节点和其对应的活跃节点集。

例如，根据Trie树的最大深度创建长度为|H_U∪V|的“已访问节点栈”ST， ST中每个元素包括节点的编号和节点的活跃节点集。

步骤4：建立一个只有根节点root的动态Trie树H’,求解根节点root的活跃 节点集，并确定下一个求解活跃节点集的节点，称之为目的节点。包含以下子步 骤。

子步骤1：基于字符串编辑距离的定义10中递增性①求出根节点的活跃节 点集Q_τ(root)，将根节点和相应的活跃节点集压入栈ST。

子步骤2：从根节点的活跃节点集中抽取出只属于字符串集U的节点集N， 从中选择最靠近根节点的节点n’。

步骤5：针对下一个目的节点，创建虚拟Trie树H'_u∪v。包含如下几个步骤。

子步骤1：基于引理3和引理4发掘在Trie树H_u∪v中与求解节点n’的活跃 节点集无关的节点区域，

子步骤2：对节点区域进行灰色标记，形成一个基于原有Trie树H_u∪v的专门 针对n’的虚拟Trie树H'_u∪v。

步骤6：基于引理1通过位于栈ST最上层元素的活跃节点集求出目的节点 的活跃节点集合。

子步骤1：如果目的节点同属于两个集合，则设定目的节点属于其中某一个 集合，并在虚拟Trie树H'_u∪v中排除只属于该集合的节点；如果目的节点只属于 某一个集合，则同样，在虚拟Trie树H'_u∪v中排除只属于该集合的节点。

子步骤2：在H'_u∪v中，根据栈ST上的最上层的父节点的活跃节点集求出目 的节点的活跃节点集

子步骤3：将目的节点压入栈ST中。最上层的元素即目的节点的编号和其 相应的活跃节点集。

步骤7：基于Trie树活跃节点定义中对活跃节点对称性的叙述，更新栈ST 中与栈最上面的元素距离为τ之内的元素的活跃节点集。

步骤8：判断当前处理的节点p是否为Trie树结构的某一叶子节点，如果是， 则对于输出相似字符串配对<o,p>，并弹出栈ST中的最上层节点。

步骤9：在Trie树H'_u∪v中取出目的节点的属于同一字符集的子节点或兄弟 节点最为新的目的节点，重复步骤5至步骤8，直到栈ST为空为止。

图12是上述算法流程实现的一个例子，下面首先分析字符串集U和V的关 系对算法的影响，然后结合图12给出具体的算法执行实例：

设U和V为两个字符串集，其中U＝{u₁,u₂,u₃,…u_m},V＝{v₁,v₂,v₃,…v_n}。τ为字 符串编辑距离阈值，R为输出的相似字符串配对集，H_U∪V表示建立在字符串集 U和V上的Trie树结构，root表示Trie树结构的根节点。

U和V的关系影响算法的执行过程和结果。如果U与V是完全相同的集合， 即U＝V，则有R＝{<u,w>|u,w∈U∧ED(u,w)≤τ}。可以理解为，如果同一个集 合中求解相似字符串配对集，则结果集合是由同一个字符串集中两两相似字符串 组成的元组构成的。否则，有R＝{<u,v>|u∈U,v∈V,ED(u,v)≤τ}。算法的具体 执行过程如下所示：

(1)设在Trie树中，节点o的编号为ID(o)，ST表示“已访问节点栈”， 其长度|ST|≤|H_U∪V|，每个元素存储已访问过的Trie树节点o的编号ID和相应 的扩展活跃节点集Q_τ'(o)，表示为<ID(o),Q_τ'(o)>，ST初始化为 <ID(root),Q_τ'(root)>，初始化为Q_τ'(root)←φ，待第(4)步对Q_τ'(root)进行 更新。

(2)Trie树中每个节点o可以表示为o(ID(o),char(o),charset,struinfo,bel)。 其中，char(o)表示节点o对应的字符，charset表示节点o所属的字符串集合， struinfo表示节点o存储的与其他相邻节点之间的父子或兄弟等结构关系,bel表示 节点o与字符集U和V的所属关系,对于任 意字符串s∈U∪V进行字典排序生成有序集合 UΘV＝{r|r₁＞r₂＞...＞r_m+n,r∈U∪V}。“＞”表示在字典排序中，该符号前面的 字符串排在符号后面的字符串之前。

(3)基于有序集合UΘV建立Trie树H_U∪V，对属于不同集合的节点，分别 对bel初始化为不同的值。

(4)基于根节点root建立动态Trie树H’，初始化为H'←root，遍历H_U∪V求解Q_τ(root)←{q|q∈U∪V∧|q|≤τ}，将元素<ID(root),Q_τ'(root)>压入栈ST， 标记为已访问的节点。

其中，对于节点r，Q'_τ(r)对r的Trie树活跃节点集Q_τ(r)进行了扩展。Q'_τ(r) 在Q_τ(r)的基础上包含了初始字符串集的关系对算法过程的影响因素。求解 Q_τ'(r)的方法如下所示：

(5)定义dn为目的节点，dn’为下一个目的节点，初始化为dn←root.1stchild， dn'←dn.1stchild，满足其中C_S^P表示全集S中P 的补集，S←{U,V,U∪V}。

(6)如果栈ST为空，转至(15)，否则转到(7)。

(7)如果dn不为空且dn∈U，转(8)，否则转至(13)。

(8)设元素tp为栈ST的最上层元素，tp(ID(tp),Q_τ'(tp))＝ST.topElement()； 对符合引理的节点进行裁剪，形成虚拟Trie树H'_U∪V,H'_U∪V←H_U∪V-ds，ds为 符合引理的节点区域集。

(9)通过元素tp的活跃节点集(dn,Q_τ'(tp))求解Q_τ'(dn)，如果dn是叶子节 点，则转至(10),否则转(12)。

(10)设s(node)是表示节点node所代表的子串或者完整的字符串，对任 意的Trie树节点l∈Q_τ'(dn)∧l≠n∧l.child←φ,有s(dn)≈s(l)，将输出结果合并 到结果集合R中，计算R∪＝{(dn,l)}；

(11)在栈ST中，对于dn任意的祖先节点t，设|t|为t对应的栈元素的位 置，栈ST的最上层元素对应的节点为dn，有|dn|>|t|,如果节点t满足|dn|-|t|≤τ， 则将dn添加到Q_τ'(t)中，计算Q_τ'(t)∪＝{dn}。

(12)将目的节点dn压入栈ST中，ST.push(<dn,Q_τ'(dn)>),求解下一个目 的节点dn’,

(13)如果dn不为空，得出dn'←dn.nextsibling.dn.nextsibling表示节点 dn的下一个兄弟节点，转(7)；否则，转(14)。

(14)在栈ST中弹出最上层元素，tp(ID(tp),Q_τ'(tp))＝ST.pop()，同时以该 元素对应的节点的兄弟节点定为下一步访问的对象，dn'←tp.nextsibling。

(15)输出最终结果R，并观察R中的字符串相似对的实际匹配程序，算法 结束。

本发明的实验数据来自Yahoo官方网站和China Daily中的网页数据，通过 网络爬虫等工具在设定的主题内爬取得到的，经过加工处理，形成不同字符串长 度的Yahoo数据集，China Daily数据集。图13，14和15是基于实验结果数据 绘制的新旧方法对比图。

请见图13所示，在相同数据集的运行效率对比方面，本发明提出的基于二 级过滤的新方法明显优于传统方法。图13中，可以看出传统方法和本发明中提 出的方法运行的时间都是随着字符串集中的平均字符串长度的增长先出现下降 趋势，然后缓慢增加，最后趋于平缓。平均字符串长度较短的情况下，旧的方法 花费的运行时间比新的方法要多，这是因为新的方法多经过了一层结构相似性过 滤。随着平均字符串长度的增加，新方法的优势体现出来。在字符串编辑距离阈 值τ＝10的情况下下降幅度大于τ＝20的情况，这是因为字符串编辑距离阈值越 小，算法按照从父节点到子节点的顺序遍历节点，对相似性的定义越严格，则不 满足相似性定义的节点删除的层次越靠上，对总体过程的影响是需要遍历的节点 越少，则运行时间越短。从图中也可以看出，τ＝10和τ＝20的情况下，新方法 均比旧方法高效。

请见图14所示，在不同数据集的运行效率对比方面，本发明提出的基于二 级过滤的新方法均明显优于传统方法。图14显示的是在本发明提出的方法和传 统方法分别在两个不同数据集中不同平均字符串长度的情况下执行而绘制的结 果对比图，这两种数据集分别为Yahoo数据集和China Daily数据集，分成4组， 平均字符串长度分别为300，500，700和900。可以发现在里两个数据集中呈现 的规律相同，呈现与图14类似的趋势。

请见图15所示，在精确度方面，本发明提出的基于二级过滤的新方法明显 优于传统方法。图15中的三条折线分别是：本发明中提出的新方法，实际情况 下相似字符串对的个数与字符串集大小的关系以及传统相似性检测方法。从图中 可以看出，相比对传统方法，本发明中提出的二级过滤的方法与实际情况差距较 小，因此，新方法精确度更高。

应当理解的是，本发明书未详细阐述的部分均属于现有技术。

应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是 对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不 脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发 明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。