基于SIMD优化的网页去重并行方法

摘要

本发明公开了一种基于SIMD优化的网页去重并行方法，包括以下步骤：步骤1：网页文本信息提取步骤：该过程用于将网页有效信息提取出来；步骤2：Shingle提取步骤：该过程用于提取网页特征，并生成Shingles集合；步骤3：聚类步骤：该过程用于降低比对次数，减小时间和空间复杂度；步骤4：指纹比对步骤：该过程用于寻找出相似网页，将相似的网页剔除。该基于SIMD优化的网页去重并行方法能在保证查准率和查全率的同时，有效地提高网页相似度检测的速率。

主权项

1.一种基于SIMD优化的网页去重并行方法，其特征在于，包括以下步骤：步骤1：网页文本信息提取步骤：该步骤用于将网页有效信息提取出来；步骤2：Shingle提取步骤：该步骤用于提取网页特征，并生成Shingle集合；步骤3：聚类步骤：该步骤用于降低比对次数，减小时间和空间复杂度；步骤4：指纹比对步骤：该步骤用于寻找出相似网页，将相似的网页剔除;步骤4的具体步骤为：采用以下两种方法中的任一种方法：方法1：根据聚类结果，将每一个类中的网页ID取出，设该类有n个网页，对于所有的网页的指纹集合为${\mathrm{Matrix}}_{\mathrm{finger}}=\left[\begin{array}{cccc}{\mathrm{finger}}_{11}& {\mathrm{finger}}_{21}& ...& {\mathrm{finger}}_{n1}\\ {\mathrm{finger}}_{12}& {\mathrm{finger}}_{22}& ...& {\mathrm{finger}}_{n2}\\ ...& ....& ...& ...\\ {\mathrm{finger}}_{1M}& {\mathrm{finger}}_{2M}& ...& {\mathrm{finger}}_{\mathrm{nM}}\end{array}\right];$定义定义函数$v\left(x\right)=\left\{\begin{array}{cc}1,& x\ge 0\\ 0,& x<0\end{array}\right.;$考虑每一列的指纹，首先生成一个128维的向量V，每一位都初始化为0，考虑该列的每一个指纹中的每一比特，若该位为1，则向量V的相应位加1，若该位为0，则向量V的相应位减1；通过叠加后，对于向量V中为正的元素归为1，为负的元素归为0；$V_1=[v\left(\begin{array}{c}{\mathrm{finger}}_{\mathrm{1,1}}\left(1\right)\\ +\\ {\mathrm{finger}}_{\mathrm{1,2}}\left(1\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{1,M}\left(1\right)\end{array}\right),v\left(\begin{array}{c}{\mathrm{finger}}_{\mathrm{1,1}}\left(2\right)\\ +\\ {\mathrm{finger}}_{\mathrm{1,2}}\left(2\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{1,M}\left(2\right)\end{array}\right),...,v\left(\begin{array}{c}{\mathrm{finger}}_{\mathrm{1,1}}\left(128\right)\\ +\\ {\mathrm{finger}}_{\mathrm{1,2}}\left(128\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{1,M}\left(128\right)\end{array}\right)]$$V_2=[v\left(\begin{array}{c}{\mathrm{finger}}_{\mathrm{2,1}}\left(1\right)\\ +\\ {\mathrm{finger}}_{\mathrm{2,2}}\left(1\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{2,M}\left(1\right)\end{array}\right),v\left(\begin{array}{c}{\mathrm{finger}}_{\mathrm{2,1}}\left(2\right)\\ +\\ {\mathrm{finger}}_{\mathrm{2,2}}\left(2\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{2,M}\left(2\right)\end{array}\right),...,v\left(\begin{array}{c}{\mathrm{finger}}_{\mathrm{2,1}}\left(128\right)\\ +\\ {\mathrm{finger}}_{\mathrm{2,2}}\left(128\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{2,M}\left(128\right)\end{array}\right)];$$V_n=[v\left(\begin{array}{c}{\mathrm{finger}}_{n,1}\left(1\right)\\ +\\ {\mathrm{finger}}_{n,2}\left(1\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{n,M}\left(1\right)\end{array}\right),v\left(\begin{array}{c}{\mathrm{finger}}_{n,1}\left(2\right)\\ +\\ {\mathrm{finger}}_{n,2}\left(2\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{n,M}\left(2\right)\end{array}\right),...,v\left(\begin{array}{c}{\mathrm{finger}}_{n,1}\left(128\right)\\ +\\ {\mathrm{finger}}_{n,2}\left(128\right)\\ +\\ ...\\ +\\ {\mathrm{finger}}_{n,M}\left(128\right)\end{array}\right)]$${\mathrm{Matrix}}_{\mathrm{finger}}=\left[\begin{array}{cccc}{\mathrm{finger}}_{11}& {\mathrm{finger}}_{21}& ...& {\mathrm{finger}}_{n1}\\ {\mathrm{finger}}_{12}& {\mathrm{finger}}_{22}& ...& {\mathrm{finger}}_{n2}\\ ...& ....& ...& ...\\ {\mathrm{finger}}_{1M}& {\mathrm{finger}}_{2M}& ...& {\mathrm{finger}}_{\mathrm{nM}}\end{array}\right]=[V_1,V_2...V_n];$向量V_i用于表示n个文档的指纹，其中i=1,2,...,n；V_i为128位的长整型数，该长整型数表征该网页的指纹；指纹比对具体流程如下：步骤a：使用x,y,z分别代表三个128位xmm寄存器，使用a代表网页A的128位指纹，使用b代表网页B的128位指纹，将a、b分别加载到寄存器x、y；步骤b:使用_m128i_mm_xor_si128(_m128i a,_m128i b)计算a、b异或值Mask，异或值中1的个数就是a和b的海明距离；步骤c：使用_mm_cvtsd_f64获取Mask的低64位Mask_low,使用mm_unpacklo_epi64、_mm_cvtsd_f64获取Mask的高64位Mask_high；步骤d：分别使用_popcnt64计算Mask_low和Mask_high中1的个数，并相加赋值给Count；步骤e：当Count>Dx时认为网页A和网页B不相似，反之相似，Dx为第一距离阈值；方法2：考虑指纹集合：${\mathrm{Matrix}}_{\mathrm{finger}}=\left[\begin{array}{cccc}{\mathrm{finger}}_{11}& {\mathrm{finger}}_{21}& ...& {\mathrm{finger}}_{n1}\\ {\mathrm{finger}}_{12}& {\mathrm{finger}}_{22}& ...& {\mathrm{finger}}_{n2}\\ ...& ....& ...& ...\\ {\mathrm{finger}}_{1M}& {\mathrm{finger}}_{2M}& ...& {\mathrm{finger}}_{\mathrm{nM}}\end{array}\right],$对于两个网页：网页i和网页j，它们的指纹集合为：$\left[\begin{array}{cc}{\mathrm{finger}}_{i1}& {\mathrm{finger}}_{j1}\\ {\mathrm{finger}}_{i2}& {\mathrm{finger}}_{j2}\\ ...& ...\\ {\mathrm{finger}}_{\mathrm{iM}}& {\mathrm{finger}}_{\mathrm{jM}}\end{array}\right],$采用每一行进行指纹比对，然后计算出指纹之间的距离之和，当距离之和大于第二距离阈值Dy时,认为网页i和网页j不相似，反之相似。