基于FFT的网页正文提取算法研究与实现.pdf

《基于FFT的网页正文提取算法研究与实现.pdf》由会员分享，可在线阅读，更多相关《基于FFT的网页正文提取算法研究与实现.pdf（4页珍藏版）》请在三一文库上搜索。

1、 计算机工程与应用 ，（） 引言 随 着 的 不 断 发 展 ，页 面 数 量 大 幅 度 增 加 ， 已 经成为巨大的、 分布广泛的信息源。许多信息包含在浩如烟海 的 中 ， 如何帮助人们迅速提取有效信息， 成为一个非常重 要的问题。 针对 网页特点， 需利用网页结构布局信息对网页进 行区域分割 ， 模拟 浏览器的显示方式， 对网页进行解析 。系 统根据人类视觉原理 ， 把网页解析处理的结果， 进行分块 。然 后根据用户需求， 提取用户需要的相关网页块的内容。 利用这 种方法 ， 把网页分割成多个区域后， 利用一定合理的算法， 把不 需要的区域过滤掉。这类似于图像处理的流程， 在 “ 频域

2、” 把高 频噪声去除。 当前比较常用的网页分割方法主要有如下几种： （）基于文档对象模 型（ ， ）的 分割法 。 找出网页 文档里的特定标签， 利用标签项将 文档表示成一个 树的结构；根据特定标签包括 、 、 和等来提取有效的树结点数据。 在许多情况下， 文档对象模型不是用来表示网页内容结构 的 ， 所以利用它不能够准确地对网页中各分块的语义信息进行 辨别 。 （）基于视觉特征的网页分割法（ ） 。 整体来说，页面的基于视觉的内容结构是结合 树以 及一些视觉提示信息而得到的 。利用字体、颜色、大小等网页版 基于 的网页正文提取算法研究与实现 李蕾 ， ， 王劲林 ， 白 鹤 ， ， 胡晶晶

3、， ， ， ， ， ， ， 中国科学院声学研究所 中心 ， 北京 中国科学院研究生院， 北京 ， ， ， ， ： ， ， ， ，（） ： ： “ ” ， （ ， ， ） ， ： “ ”， ， ， ； “” ：； （） ； 摘要： 主要研究 “正文式 ” 网页的有效信息提取算法。该种底层网页真正含有 页面所表达的主题信息， 通常包含一大段的正 文信息 ， 正文信息的前后是一些格式信息（例如导航信息、 交互信息、 脚本等 ） 。分析了此种网页的页面结构特征， 将问题 转化为 给定一个底层网页的 源文件 ， 求解最佳的正文区间； 从而提出了一种基于快速傅立叶变换的网页正文内容提取 算法 。采用窗口分

4、段的方法，利用统计学原理和 ，得出每个可能区间的权值，从而求解出最佳正文区间。实验结果表明，此种方 法能比较准确的对“正文式 ” 网页的有效信息进行提取。 关键词 ： 中文信息处理； 页面 ； 信息提取； 页面结构 ； ； 区域分割 文章编号： （） 文献标识码： 中图分类号： 基金项目 ： 国家发改委示范工程资助项目（ ） 。 作者简介 ： 李蕾（） ， 女， 博士研究生 ， 主要研究方向： 宽带通信 、 移动多媒体等领域； 王劲林（）， 男， 研究员 ， 博士生导师， 中国科学院声学 研究所网络与数字信号处理技术研究中心主任， 主要研究方向： 数字信号处理技术、 宽带通信 、 移动多媒体等

5、领域； 白鹤（） ， 男， 博 士研究生 ， 主要研究方向： 宽带通信等领域； 胡晶晶（） ， 女， 硕士研究生， 主要研究方向： 宽带通信 。 ，（） 英文字母 中文字符 标点符号 连续性 前长后短 长 较长 主要位置 文档首尾 文档中部 文档首部 表 文档三大类信号特征表面特征 ，根据一定的语义关联，将整个网页表示成一棵 树； 利用横竖线条将树节点所对应的分块在网页中 分隔开来， 构成网页的标准分块； 每个节点通过一致度（ ，） 来衡量它与其它节点的语义相关性， 从而 将相关的分块聚集在一起； 利用预先设定的一致度（ ，）作 为 阈 值 控 制 分 割 粒 度 ， 当 所 有 网页的 都不

6、小于 时， 网页分割就可以停止了。 基于页面结构特征把网页大致分为首页式、 列表式 、 正文 式 、 评论式等几大类： （） 首页式 ： 网站的首页， 一般含有多个栏目、 图片 、 动画 ， 以及若干文章标题链接。 如： 网易首页 。 （） 列表式 ： 信息以列表的方式给出， 一般以表格的形式列 出若干个条目， 经常含有分页功能。 例如 ： 某论坛版面的文章标 题列表 。 （） 正文式 ： 指含有正文内容的底层网页， 一般只含有不超 过一篇的文章内容， 无评论或评论较少。 如 ： 各类网站的含有具 体某篇文章的底层网页。 （） 评论式 ： 除了含有正文， 正文后面还跟有若干个评论， 以论坛为代

7、表。 本文主要研究 “正文式 ” 网页的有效信息提取算法。 该种网 页真正含有 页面所表达的主题信息 ，通常含有大段的文 字内容 。通过分析该种网页的结构特征， 提出一种基于快速傅 立叶变换 （ ，） 的网页正文内容提 取算法 ， 下面具体论述该算法及其实现。 基于快速傅立叶变换的网页正文内容提取算法 底层网页的结构特征模型分析 底层网页通常包含一大段的正文信息， 正文信息的前后是 一个格式信息 （例如导航信息、 交互信息 、 脚本等 ） 。 正文信息具有以下特点： （） 位于源文件的中部； （） 以中文字符和英文字母为主； （） 较为连续的文字； （） 正文信息的信号特性类似； （） 正文信

8、息与格式信息的信号特性不同。 格式信息具有以下特点： （） 位于源文件的开头和结尾； （） 以标点符号和英文字母为主； （） 格式信息的信号特性类似； （） 格式信息与正文信息的信号特性不同。 文档模型分析： 由三大类信号混合而成。 （）标 记 符（） ， 形 式 为 “标 记 符标 记 符属 性 值 标 记 符 ” 。 例 ： “” “” “”； （） 文本自然语言（） ， 即中英文字符组成的句子。例 ： 关于我们 ； （） 脚 本 程 序 （） 。 例 ： （， ） ， ，； （！）。 文档三大类信号的特征表如表 。 数学模型如下： ， （! （） ，“ （） ）（! （） ，“ （） ）

9、 ， （! ，“ ） ， （! ，“ ） ! ! ! 其中 ，表示 文档信号 ，表示英文字母 ， 表 示 中 文 字 符，表 示 标 点 符 号，表 示 随 机 变 量 ； 表示取值为或的序列 ， （!，“）表示由 ，组成的方 波序列 ，!表示方波中间位置 ，“表示方波的宽度。 （!，“） ，! “ ，$ 网页正文提取算法研究 本文问题的定义是， 给定一个底层网页的 源文件 ， 求解最佳的正文区间。对于任何字符串区间（， ） ，（ ，为源文件的长度，为源文件 ） ， 都有一个评价值， 问题转化 为求评价函数的最大解。 （，）（，） （， $% ） 其中 ， 评价函数 （， ） 表示该文字段（，

10、 ）是网页的正文的可 能性 。 一个区间以数字对（， ） 来表示 ， 即 到组成的区间 。 其中 ， 故一个区间就把该 所有文字段分成了 两组 ， 区间内部组的和区间外部组的。 区间内部组 包括 ， 区间外部组包括，。整个 源文件由 组的前一部分 ， ， ，组 ， ，组的后一 部分 ， ， ， 组成 。 区间的权值定义为， 组间差之和减去组内差之和。 因为正 文是 中的一段频谱类似、 位于中部、 连续的文字。 组间差 大就是差异性比较， 组内差小就是组内特征类似。 （，）（，） （，） 本文采用窗口分段的办法把文字分成若干等长窗口段， 分 别进行 变换之后， 以频域的欧氏距离计算信号特性的差

11、异程度 ， 从而来评价组间和组内元素的差别。 本文对文字进行预处理， 不使用原始的 编码值作 为信号输入， 而是通过统计学的方式， 把原始文字转化为正文 强度值 。对于在位置 出现的字符 ， 其正文强度值公式如下： （，） ?（ ! “ ） ） ， ， ?（ ! “ ） ） ） & ( ( ( ( ( ( ( ( ) 其中 ， !是字符出现位置的均值 ，“ 是字符出现位置的标 准方差 ，是字符出现的次数 。 因为正文包含更多的中英文字符， 而包含较少的标点符 号 ； 如 果 字 符 是 文 字 类 型 的 （即 ， ， ） ， 则用正态分布公式作为其编码转换函数， 结果非负； 其他字符， 则用

12、正态分布加上偏移量的公式， 作为转换函数 ， 结 果非正 。 即公式对于中英文字符是正数， 对于标点符号是负数。 因为正文位于文档中部， 而标点符号位于文档两端； 所以公式 对于中英文字符是把信号强度集中在文档中部， 对于标点符号 李蕾， 王劲林 ， 白鹤， 等： 基于 的网页正文提取算法研究与实现 计算机工程与应用 ，（） 是把信号强度分散到文档的两端 ，如图所示。 频繁出现的中英文字符， 往往是常用词的反映， 其信号强 度按比例增大； 频繁出现的标点符号， 往往是排版格式的反映， 例如小于号和大于号， 其信号强度在负数方向按比例增大。 网页正文提取算法的实现 核心原理： 正文是 中的一段频

13、谱类似、 位于中部 、 连 续的文字。通过以下步骤， 求解最佳正文区间。 （） 读入文件， 转换为 读 入 文 件 ， 转 换 为 ， 英 文 字 母 在 ， 之间 ， 中文在。读入为 字符数组 ， 长度 为 。 （） 窗口分段 窗口的大小为 ，把文件切分为长度为 的若干连续字符 段 ， 一共 段。同时将后面不足 的剩余字符删除； 得到字符串 数组 ， 长度为 。 * ，? ， ，（） ， ? ， ，（ ） ， ，（ ） 其中 ， 表示窗口的二维数组， 表 示 窗 口 编 号 ， 表 示 窗 口 内 位置 。 （） 应用统计学原理， 对字符进行强度编码转换 首先对每一个出现的字符，分析它在文档

14、中分布的规律； 通过对字符在文章中的位置进行统计学分析， 得到均值、 标准 方差和出现次数。 应用正文强度值公式。 根据字符段的字符强度值和所在位置， 进行编码转换得到 强度值序列 。 ，（，?）（ ? ，?） ， ，（ ） ， ， （） （） 对每一段窗口作 对每一段窗口作快速傅立叶变换， 得到频域的 向量 。 （） （） 各段频域互相求差 计算任意两段之间的距离， 两段的距离定义如下： 各频率 上的欧式距离的总合。 ， （ ， ） ， ，（ ） ! ， ， # （） 计算每个区间的权值 一个区间定义为若干个连续的窗口的组合， 以数字对 （， ） 来表示 ， 也即 到 组成的区间 ， 其中

15、。故一个 区间就把所有窗口段分成了两组，区间内部组和区间外部组。 区间内部组 包括，区间外部组包括， 。 所 有 窗 口 段 由组 的 前 一 部 分 ， ， ，组 ， ， ，组的后一部分 ， ， 组成。 区间的权值定义为， 组间差之和减去组内差之和。 因为正 文是 中的一段频谱类似、 位于中部、 连续的文字。 组间差 大就是差异性比较， 组内差小就是组内特征类似。 （，）（，） （，） （， ） （）（） ! ， （，） （） （） ! ， （） 依据权值排序 依据权值从大到小， 对区间进行排序。 权值最大的区间 ， 即 为最佳的正文区间（， ）。 （） 加权平均 对于权值大于 的区间 ，

16、进行加权平均 ， 算出平均意义上 的最佳正文区间（， ） 。 因为权值小于 的区间排名非常靠 后 ， 所以可以忽略不计。 （， ） （，） ! （，） ?（，） （，） ! （，） 加速算法： 使用累计距离 在算法实现中， 使用了一种加速算法。使用累计距离表可 以快速地计算两个连续组的差值之和 ， 见图 。 & ， ， ， ， ! ， ， ， ， ， ， ! ， & ， & ， & ， & ， 实验与结果 实验设计与数据选取 本文选取窗口 。 本文仅对“正文式 ” 网页进行研究。从页面结构来讲， 该种 网页只含有一段正文， 没有评论或评论较少； 而正文的具体内 容则关系不大。 为 了 验 证

17、算 法 的 可 行 性 ， 随 机 选 取 网 易 旅 游（： ） ，游 天 下（： ） ， 红袖添香 （：） ， 水木论坛 （） ， 科 苑 星 空 论 坛（ ） 这 个 网 站 的 “正文式 ” 网页进行实验。各选取 个页面 ， 共计 个页面 。 人工观察源代码中正文开始和结束的位置， 即正确的正文 区间 ， 记作（， ）； 程序运行结果给出的权值最大的区间 ， 即最 佳正文区间， 记作（， ） ； 通过加权平均得到的区间 ， 即平均 意义上的最佳正文区间， 记作（， ） 。源代码经处理后 的总段数记作 。则得出权值法求解最佳正文区间准确度 ， ，（） 均值 均值 网易旅游 游天下 红袖添

18、香 水木论坛 科苑星空论坛 表 正文区间准确度与 权值法准确度区间 （， （， （， （， （， 网易旅游 游天下 红袖添香 水木论坛 科苑星空论坛 表 权值法准确度区间的页面个数统计表 加权平均法求解最佳正文区间准确度 。 （）（） （ ）（ ） 结果图表与分析 程序运行结果如表 。对每个网站的 个页面的运行结 果 ， 分别取 和 的均值 。 由表 可知 ， 该算法对不同结构网页的正文内容提取的准 确 度 都 较 高 。均 值 都 在 以 上 ，个 网 站 的均 值 约 为 。 有 类网站的均值在 以上 ，个网站的均值 约为 。 下面分别对各类网页运行结果所在准确度区间（权值法 ） 的页面个

19、数做一个统计。 如表 和图所示 。 分析这 个网页的页面结构及其对应的实验结果， 得出 结论如下： （） 网易旅游、游天下 、 红袖添香这类门户网站的页面 结构比较复杂。正文前后都有网站的文字链接导航信息， ， 文字链接式或图片、 动画式广告， 交互信息 ， 以及网站的版权申 明等“噪声 ” 区域 。 在正文的四周往往还紧跟有热门文章推荐、 热门评论、 同作者其他文章等若干条文章标题链接以及一些评 论文字的干扰信息。 这类干扰信息在 源代码中与正文文 字连接紧密， 当正文文字较短（） 时 ， 较易对程序的运行结 果 正 文 区 间 的 判 断 造 成 较 大 影 响（如 ： 程 序 运 行 结

20、 果 把 正 文 前 后 的 其 他 文 章 标 题 链 接 或 评 论 文 字 也 包 括 在 正 文 区 间内 ） 。 （）本文随机挑选水木和科苑星空论坛的各个版（， ，）精 华 区 的 文 章 ， 此 类 文 章 较 长 ， 对于信息收集和提取来讲也更有价值。页面结构比较简单； 正 文后面跟有文字签名档； 正文中往往含有若干英文单词和一些 ，发文换行随意；有些文章多版转载。当正文文字较短时， 程序运行结果较易把签名档等无关文字信息也包括在正文区 间内。 （）综合来看， 正文长短与文字密集度对于程序判断影响 较大 。文字越长 ， 越密集（一整段文字， 或正文中格式性的代码 较少）， 则结果

21、越好。 若换行空行过多， 或文字很少的连续若干 行出现在文章的头尾， 则较易影响正文区间的程序判断。若正 文较短 （） ， 且正 文 前 后 紧 跟 有 其 他 文 章 标 题 链 接 或 评 论 信息 ， 则运行结果较易把这部分也包含在正文区间内。 （） 正文中部含有图片， 不影响程序判断。 因为图片在源代 码中以 地址的形式出现， 所以若图片出现在正文前或后， 则较易对结果造成影响。 （） 在正文内容较长的情况下， 即使页面结构复杂， 程序运 行结果也很好， 基本可以区分开正文和页面的其他部分。 结论与展望 本文主要研究 “正文式 ” 网页的有效信息提取算法。 该种类 型的底层网页通常包含

22、一大段的正文信息， 正文信息的前后是 一些格式信息（例如导航信息、 交 互 信息 、 脚 本 等）。 本文分析了此种网页的页面结构特征， 将问题转化为给定 一个底层网页的 源文件 ， 求解最佳的正文区间； 从而提 出了一种基于快速傅立叶变换的网页正文内容提取算法。 本文 采用窗口分段的方法， 利用统计学原理和 ， 得出每个可能 区间的权值， 从而求解出最佳正文区间。 实验结果表明， 此种方 法能比较正确的对“正文式 ” 网页的有效信息进行提取， 区分开 正文与页面的其它部分。 在未来的工作中， 将加入对标识符的预处理， 改进算法 ； 以 及继续研究 “ 列表式 ” ，“评论式 ” 等类型网页的

23、结构特征， 从而 设计出适应不同页面结构的网页有效信息提取算法。 （收稿日期： 年 月） 参考文献 ： 于满泉 ， 陈铁睿 ， 许洪波 基于分块的网页信息解析器的研究与设 计计算机应用， ， （ ） ： 王琦 ， 唐世渭 ， 杨冬青 ， 等 基于 的网页主题信息自动提取 计算机研究与发展， ， （ ） ： 胡飞 基于标记树的 页面区域划分和搜索方法计算机科学， ， （ ） ： 常育红 ， 姜哲 ， 朱小燕 基于标记树表示方法的页面结构分析计 算机工程与应用， ， （） ： 瞿有利 ， 于浩 ， 徐国伟等 页面信息块的自动分割 中文信息 学报 ， ， （ ）： ， ， ， ， ： 李蕾， 王劲林 ， 白鹤， 等： 基于 的网页正文提取算法研究与实现