页面优化策略分析实验

  语料集合较大时,文档之间两两比较的次数就相当巨大,这是所有网页查重算法的瓶颈。在使用布尔模型的网页查重
算法中,两篇文档之间是否需要比较取决于它们的特征个数而不是文档长度,当特征的总个数差别在阈值d之内的时候,
就异或其二进制码;否则直接判定它们不同。
  在得到二进制码异或的结果之后,如何比较结果将在第另外一点就是在读取文档的过程中慢慢建立一个索引。该索引
的数据结构如表1所示。 其中id代表特征的唯一表示,Doic表示出现了该特征的文档的唯一标识符。当两篇文档相互
比较而结果为相异时,就将它们分别插入它们之间不同的特征链表中。当再有新的文 档需要比较时,根据该文档中出现
的特征,选择应该与它相比 的集合,以减少比较次数。
  矩阵的稀疏表示特征的个数有九万多个,如果用普通的线性存储方式十分 浪费空间,所以采取一般的二元组表示法:
I id l二进制值Iid为该特征在词表中唯一的表示标志,二进制值为0表示文档中没有该特征,为1表示该特征出现过:
在建立文档的词表过程中,只有二进制值为1的特征;二进制值为0的特征只出现在比较的过程中。
  相异度的计算
  当两篇文档需要比较时,最好的情况就是所 『 均不同,结果为0,此时的相异度就为1。当有1/5以J-n 特征不同时,
则判定两篇文档为非相似文档;如有1/5以下的特征不同,则需要计算这些不同特征总的频度(TF)。表2为相异度的计算
实例。
  表1 索引数据结构 表2 相异度的计算
  id l Doic l Doic 2
  id 2 Doic 3 Doic 5
  Dl D2 Tlfl Tf2 result
  Tl 0 l 0 2 1
  T2 1 l 1 3 0
  l 0 2 0 1
  T4 l l 5 7 0
  T5 l 1 6 2 0
  T表示文档中出现的特征,D表示特征t是否在文档Doc中出现过(0表示没有出现,1表示出现了,这就是布尔模型),1'F表
示特征t在文档中的出现频率,Result表示两篇文档之间D的异或结果:Result=D1∈i≥D2。对于两篇文档i和 ,假设它们
符合比较的条件,则它们的相异度计算公式为
  Σ(I .
  一
  . I)
  , = ————————————— ‘ ————————— ————一
  (Σ . +ΣCw )/2
  式中 表示特征W在文档i中的频率,在计算分子时,要去掉在两篇文档中频率均较高的T4。在表2中,按式(1)计算出F、2=
0.714,则文档1和文档2的相似度为S 2:1一F。2=0.286,结果是文档1和文档2不同。
  实验结果
  实验使用的语料为WTIOG(随机取了其中的2.3G),硬件平台为P4 1.4GHz,4GB内存。
  采取F值作为算法比较的依据:F=2 p×r/@ +r),其中P为正确率,r为召回率。对比算法为TF—IDF(特征的维数为20)和基
于标点符号 的特征串算法。实验结果如表3所示。各算法的综合性能比较如图1所示。
  实验结果
  算法 相似文 速度 正确率 召回率 F值
  档数目 (Mbps) (%) (% ) (%)
  1|F—IDF 9 825 1 02 954 91.2 93.25
  B001-
  M0de1 10 947 2.15 92.3 97 6 94.88
  特征串 7 934 4.08 100 84-4 91.7

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: