基于网页正文结构树的近似网页去重算法研究重 庆 大 学 硕 士 学 位 论 文（学术学位）学生姓名：牙 漫指导教师：熊忠阳 教 授专 业 ： 计 算 机 系 统 结 构学科门类：工 学重 庆 大 学 计 算 机 学 院二 O 一 三 年 四 月Research on Detection and Elimination ofSimilar Web Pages Based on Text StructureA Thesis Submitted to Chongqing Universityin Partial Fulfillment of the Requirement for theMasters Degree of EngineeringByYa ManSupervised by Prof. Zhongyang XiongSpecialty: Computer ArchitectureCollege of Computer ScienceChongqing University, Chongqing, ChinaApril, 2013重庆大学硕士学位论文 中文摘要摘 要据 美 国 计 算 机 协 会 统 计 ， 重 复 网 页 数 量 约 占 网 页 总 量 的 30%-45%。 伴 随 搜 索引 擎 数 量 不 断 增 加 ， 用 户 对 搜 索 引 擎 体 验 要 求 的 提 高 ， 搜 素 质 量 成 为 各 搜 索 引 擎赢 取 用 户 的 砝 码 。 搜 索 引 擎 若 能 够 及 时 去 除 这 些 重 复 网 页 ， 系 统 不 仅 能 节 省 大 量存 储 空 间 ， 间 接 降 低 设 备 采 购 成 本 ， 也 能 提 高 网 络 的 检 索 质 量 和 访 问 效 率 ， 提 高用 户 体 验 满 意 率 。网 页 正 文 内 容 的 特 征 提 取 以 及 大 规 模 相 似 性 比 较 是 网 页 去 重 的 关 键 问 题 。 按照 传 统 算 法 的 各 自 突 出 特 点 将 其 分 为 三 类 ： 基 于 URL 去 重 算 法 ， 仅 能 根 据 URL地 址 去 除 完 全 重 复 网 页 ； 基 于 特 征 串 匹 配 去 重 算 法 ， 具 有 较 高 的 准 确 率 ， 但 去 重时 间 消 耗 高 ； 基 于 聚 类 去 重 算 法 ， 具 有 较 高 的 召 回 率 ， 对 于 一 些 新 闻 题 材 或 模 板类 文 章 准 确 率 较 低 。分 析 转 载 网 页 发 现 ， 重 复 网 页 在 内 容 上 可 能 有 变 化 ， 但 文 档 格 式 较 少 发 生 改变 ， 即 网 页 正 文 结 构 几 乎 不 变 。 针 对 此 特 点 ， 本 文 提 出 基 于 正 文 结 构 树 的 两 个 去重 算 法 。通 过 分 析 重 复 网 页 发 现 ， 长 句 不 具 有 主 题 代 表 性 。 面 对 网 页 采 集 器 更 改 规 则 ，越 长 的 句 子 表 现 越 脆 弱 。 本 文 对 基 于 正 文 结 构 及 长 句 去 重 算 法 进 行 改 进 ， 提 出 基于 正 文 结 构 树 及 关 键 句 的 算 法 。 算 法 中 提 取 包 含 关 键 词 的 句 子 作 为 特 征 句 ， 且 特征 句 的 数 目 由 段 落 长 度 决 定 ， 使 得 提 取 的 特 征 句 的 数 目 更 全 面 的 概 括 文 章 内 容 。实 验 表 明 ， 改 进 算 法 去 重 准 确 率 、 召 回 率 都 有 所 提 高 。特 征 项 的 粒 度 越 小 ， 散 列 后 的 特 征 指 纹 越 不 易 被 干 扰 。 依 据 此 特 性 ， 本 文 提出 了 基 于 正 文 结 构 树 及 特 征 串 的 去 重 算 法 。 首 先 ， 此 算 法 中 提 取 网 页 中 高 频 标 点所 在 句 子 中 的 首 尾 汉 字 作 为 特 征 码 。 其 次 ， 利 用 Bloom Filter 算 法 获 取 特 征 指 纹 。最 后 ， 按 层 次 指 纹 进 行 相 似 度 判 别 。 实 验 表 明 ， 此 算 法 在 召 回 率 方 面 有 大 幅 度 提高 ， 在 对 小 文 档 去 重 上 表 现 的 尤 其 明 显 ， 且 大 大 降 低 了 去 重 时 间 。关键词：网 页 去 重 ， 正 文 结 构 树 ， 关 键 句 ， 层 次 比 较 ， 高 频 标 点I重庆大学硕士学位论文 英文摘要ABSTRACTAccording to the statistics of ACM, the number of repeated web page accounts forabout 30%-45%. With the increasing number of search engines and the improvement ofusers requirements, the search quality becomes the weight to win the users for all of thesearch engines. If the duplicated web pages removed timely, search engine can not onlysave a lot of storage space, indirectly reducing equipment procurement cost, but alsoimprove the retrieval quality of the network and accessing efficiency. Finally, itimproves satisfaction of users.The key points of the elimination of duplicated web pages are text featureextraction and the calculation of large-scale informations. Traditional text featureextraction algorithm is generally divided into three categories. The first one is based onURL which only removing the mirror site. The second one is based on the matching ofcharacter string which has high accuracy and high time complexity. The third one isbased on clustering. The last method is very high in recall, but its accuracy is relativelylow for the news and the template texts.By analyzing near-duplicated web pages, found that repeated pages may havemuch change in the content, but few document format. In view of this characteristic, thepaper puts forward two algorithms based on text structure tree.The long sentence doesnt representative theme of the web page. Facing pagecollector change rules, the longer the sentence is more fragile. This paper puts forwardthe algorithm based on text structure tree and key words to improve the algorithm basedon long sentences. The algorithm extracts sentences which contains keywords as keysentence. And the number of features is determined by the length of paragraphs.Experiment shows that the improved algorithm effectively avoids these two drawbacks,and the accuracy and recall rate are improved.The smaller feature is hashed was less interference. According to the feature,algorithm based on text structure tree and character strings is proved. Firstly, it extractsthe head and tail words of a certain sentence in which high frequency punctuationsoccur. Secondly, it generates the fingerprint with Bloom Filter algorithm. Finally, itdetermines the similarity according to the layer fingerprint. Experiment shows that thisII重庆大学硕士学位论文 英文摘要algorithm has greatly improved in the recall rate, which is especially in small documents,and greatly reduces the time complexity.Key words: elimination of near-duplicated web pages; text structure tree; key sentence;layer fingerprint; high frequency punctuationIII重庆大学硕士学位论文 目 录目 录中文摘要 I英文摘要 II1 绪 论 11.1 研究背景 11.2 研究的意义