【算法研究】网页信息提取 文献总结&&差异&&对比

【算法研究】网页信息提取 文献总结-差异和对比

零、基础知识

结构化数据

1. 2015_《Fundamentals of Database Systems (5th Edition)》 存储在数据库中的信息称为结构化数据; XML 文档是架构信息的半结构化数据与数据值混合在一起，而 HTML 中的 Web 页面是非结构化的

文档规范化

将格式不正确的文档转换为格式良好的 HTML 文档。

一、综述型文章

1. 2002_《A brief survey of web data extraction tools》 Laendar 等人提出，通过区分每种方法生成包装器所使用的主要技术，来区分结构化数据提取方法，如基于 NLP 的方法、基于模型构建的方法等等。
2. 2006_《A Survey of Web Information Extraction Systems》 CH Chang 等人从提取任务的困难程度、使用的方法、自动化程度对网页提取进行分类。
   • 提取任务的困难程度
     • 输入文档的类型（结构化、半结构化、非结构化）
     • 提取目标（记录级、页面级、站点级）
   • 使用的技术 （标记/编码方法、提取规则类型、特征提取/机器学习）
   • 自动化程度 （需要用户参与的、不需要用户参与的）（手动构建的、监督的、半监督的、无监督的）
3. 2012_《Web Data Mining》 Bing 等人根据自动化程度对数据提取方法进行分类，将结构化数据提取方法分为人工、半自动和全自动的方法。
4. 2013IEEE《A Survey on Region Extractors from Web Documents》 Sleiman 等人聚焦于区域提取器，介绍了区域提取器的发展历程，比较了不同的区域提取器。
5. 2019_《An Analytic Hierarchy Process Based Comparative Study of Web Data Extraction Approaches》 介绍从 web 页面中提取数据的方法，详细介绍每种方法，最后根据定义良好的精确标准对所有方法进行比较。

二、基于 HTML 页面代码的方法

手动方法

1. 1997_《Semistructured data: the TSIMMIS experience》 TSIMMIS 是第一个为手工构建 Web 包装器提供框架的方法之一，允许程序员输入一系列的指令来确定数据应当如何提取。
2. 1998_《WebOQL: restructuring documents, databases and Webs》
   • WebOQL 是本文提出的一种功能语言，需要先通过程序将 web 编码转换为类似于 DOM 树的 Hypertrees 结构，然后再模拟嵌套关系代数中的所有操作。
   • 包装器开发过程由三个独立的层组成：检索，提取和映射层。
   • 使用了基于 DOM 树路径编码的方法来定位数据，如<< html.body.ol[0].li[*].pcdata [0].txt >>

半自动方法

1. 2000_Snowball: extracting relations from large plain-text collections 微软提出的一种从文本文档中提取有价值的结构化数据的方法，先从用户那里获得少量的培训示例作为种子元组，用以生成提取模式，然后从文档集合中提取新的元组对，多次迭代后获得最终数据。
2. 2007_《Open information extraction from the web》 从语料库里构建提取范式，从而不需要人工输入，自动发现可能存在的利益关系，实现了一个无监督的从 Web 进行大规模数据提取的过程。
3. 2007_《Annotating Structured Data of the Deep Web》 解决如何自动为从 Web 数据库中返回的 SRR 数据记录分配有意义的标签。 Lu Y 等人将数据单元对齐到不同的组中，使得同一组中的数据具有相同的语义，然后对于每个组从不同方面对其进行注释，并聚合不同的注释以预测最终的注释标签。
4. 2013_《A Novel Method for Extracting Entity Data from Deep Web Precisely》 Yu HT 等人针对 DeepWeb 的动态特性，将网页资源进行预处理和规范化后，结合 XPath 与 Regexp 精确定位实体数据，缺点在于无法泛化，提取目标页面之前需要自行定义正则表达式。
5. 2018_User-Friendly and Extensible Web Data Extraction Serrano T. NovellaI. Holubová 等人提出了一种新的包装语言，它有三个目标：（1）在受限环境中运行的能力，例如浏览器扩展，（2）可扩展性以平衡命令集表达性与安全性之间的权衡，以及（3）处理能力，以消除额外程序清理提取数据的需要。

全自动方法

1. 2001_《RoadRunner: Towards Automatic Data Extraction from Large Web Sites》RoadRunner 是一种全自动的包装器，不依赖于用户的任何交互，但是一次至少需要处理两个及以上的页面，因为算法核心是基于基于给定的一组属于同一类的 HTML 示例页面并从中提取数据。RoadRunner 使用了一种名为 ACME 的匹配技术，用于寻找两个页面中的公共结构（对齐相似的标签并折叠不相似的标签），从标签生成包装器。因为算法的比较机制，RoadRunner 会将一些噪声块也包含进来。

三、基于 DOM 树进行正文识别

半自动方法

1. 2001_《Building Intelligent Web Applications Using Lightweight Wrappers》W4F（World Wide Web Wrapper Factory） 是一个用于生成 Web 包装器的 Java 工具包。它提供了一种表达语言用于从 HTML 页面中提取 DOM 树状结构，提取数据之后映射到 XML 或者 Java 对象中，同时提供了一些可视化工具，使得包装过程更快更容易。
2. 2002_《XWRAP: An XML-Enabled Wrapper Construction System for Web Information Sources》 XWRAP 是一种半自动的方法，分析页面的 DOM 结构，使用了组件库为包装器程序提供基本构建块，引导用户通过点击选中需要的组件生成包装器代码，同时 XWRAP 还能输出信息抽取规则.
3. 叶子节点融合的相关算法 《Web Content Information Extraction Based on DOM Tree and Statistical Information》
   • GetRealNode() 先获取子节点再进行融合， 直至公共的祖先节点CommonAncestor
   • 结合节点中的超链接文本的个数、长度以及层级，为每一个节点 Node Block 进行打分（判断是否是重要节点）
   • 设置阈值区分内容块和噪声块

全自动方法

1. 2001_《A fully automated object extraction system for the World Wide Web》Omini 将网页解析成 DOM 树，然后通过子树提取算法来定位包含感兴趣对象的最小子树，并且通过对象提取算法来定位正确的对象分隔符标签，从而有效地分离对象。缺点是子树提取算法以及对象分割符提取算法都依赖与标签计数，数据库局限于常见的论文、文章和书籍数据库网站，结构较为简单。
2. 2003_《Automatic information extraction from semi-structured Web pages by pattern discovery》 IEPAD (Automatic information extraction from semi-structured Web pages by pattern discovery) 是一种基于模式发现的方法。
   • 半结构化 Web 页面上的数据通常以具有规则且连续的模式的某种特定布局格式呈现。通过在目标网页中发现这样的模式，可以生成提取器。
   • 通过对路径进行编码发现其中的重复模式。
3. 2003_《Mining Data Records in Web Pages》 MDR 方法基于两个观察和三个步骤：
   1. 两个观察
      • 数据区域： 数据记录通常出现在页面的特定区域内
      • Web 页面中 HTML 标记的嵌套结构自动形成了 DOM 树
   2. 两个假设
      • 所有数据记录都有相同的父记录
      • 多个数据记录之间拥有相似的结构
   3. 方法主要分成三个步骤
      • 构建 DOM 树（构建页面的标记树）
      • 挖掘数据区域 区域聚焦（使用标记树和字符串比较来挖掘页面中的数据区域）
      • 运用了编辑距离（计算文本相似度）来框定数据区域
      • 标识每个数据区域的数据记录
4. 2005_《Web data extraction based on partial tree alignment》 DEPTA （即 MDR2）
   1. 主要流程
      • 标识页面的数据记录（基于视觉信息的数据记录分割方法）
      • 从标识的数据记录中对齐和提取数据项（基于树匹配的局部对齐技术）
   2. MDR2 挖掘数据区域（基于部分树对齐）
      • 确定 HTML 标记树（构建页面的标记树）
      • 使用标记树挖掘页面中的数据区域
      • 标识每个数据区域中的数据记录
5. 2017_《Web Content Extraction Using Clustering with Web Structure》 CECWS 先提取出了来自同一网站的一组相似页面，删除其中内容相同的部分（噪声数据），然后再提取数据。
   • 对于相似的 DOM 结构，静态内容常为一些噪声块，动态内容为主要内容。
   • 通过聚类算法 Canopy 把有监督的训练变成无监督的训练，聚类用于识别训练集中内容结构相似的页面（目标是聚合来自同一网站的页面划分为同一集合）
   • 缺点在于有些噪声块也可以为动态内容，无法对单页面进行识别，需要至少两个以上的页面。
6. 2018_《A novel alignment algorithm for effective web data extraction from singleton-item pages》 DCA Divide-and-Conquer Alignment 关注单例页面（ singleton-item pages）中顺序对数值的提取。 本文的主要贡献是
   • （i）为单例页面提出了一种新颖的数据对齐技术
   • （ii）应用 LIS 来处理不一致的地标，即多阶模板
   • （iii）从单例页面中提取完整的模式并在现实世界网站的几个领域的三个基准数据集上比较分而治之对齐（DCA）与最先进技术的有效性和效率。

四、基于视觉信息进行数据提取

1. 2003-Vips: a vision-based page segmentation algorithm Cai D 等人首先从 DOM 树中提取出所有的合适的页面块，然后根据这些页面和分割条，重新构建 Web 页面的语义结构。
2. 2005-Fully automatic wrapper generation for search engines 作者主要提出了一种ViNT的方法 针对搜索引擎的界面（比如百度页面和谷歌界面），需要同个搜索引擎下的多张页面。
   • ViNT 利用了由搜索引擎动态生成的结果页面上的可视内容特征，结合 HTML 标记路径，通过对多个候选页面提取内容行和块结构，提出了一种完全自动化的生成包装器的技术。
   • SRR Search Result Records 搜索结果记录
   • Content Line 内容行，在同一水平线上呈现的文本
   • Block Shape Block 就是多个内容行形成的区域，其形状定义为其内容行的位置序号（x 横向坐标）所形成的有序列表
   • Block Similarity 块的类型代码为包含的内容行的类型序列，块的形状距离定义为块形状的相对值
   • CCLS Candidate record line separators 候选内容行分隔符
   • Tag Path 标记路径，将 tag 提取出来，形成一个 tag 树，树枝上的所有叶子节点都对应了一个路径。
3. 2013-Annotating search results from web databases 基于 ViNT 进行数据记录 SRR 的提取，然后进行数据对齐，生成多类的注释包装器。
4. 2010-ViDE: A Vision-Based Approach for Deep Web Data Extraction
   • 可视化树和视觉特征
   • 位置特征（PFs）
     • PF1 ：数据区域始终水平居中。
     • PF2 ：数据区域的大小通常比整个页面的区域大小大。
   • 布局功能（LFs）
     • LF1 ：数据记录通常在数据区域中左对齐。
     • LF2 ：所有数据记录都是相邻的。
     • LF3 ：相邻的数据记录不重叠，任何两个相邻记录之间的空间相同。
   • 外观特征（AFs）。这些功能捕获数据记录中的可视功能。
     • AF1 ：数据记录的外观非常相似，相似性包括它们包含的图像大小和它们使用的字体。
     • AF2 ：不同数据记录中的相同语义的数据项具有关于位置，大小（图像数据项）和字体（文本数据项）的类似呈现。
     • AF3 ：不同语义的相邻文本数据项通常（并非总是）使用可区分的字体。
   • 内容功能（CF）。这些功能暗示了数据记录中内容的规律性。
     • CF1 ：每个数据记录中的第一个数据项始终是强制类型。
     • CF2 ：数据记录中数据项的显示遵循固定顺序。
     • CF3：数据记录中经常存在一些固定的静态文本，这些文本不是来自底层 Web 数据库。
   • 数据提取的标准
     • 提取数据区域中的所有数据记录
     • 对于每个提取的数据记录，不丢失任何数据项并且不包括不正确的数据项。
   • 数据提取过程
     1. 首先通过 PFs 特征，调整阈值来框定数据区域
     2. 过滤噪声块 判断噪声块的位置是否向左靠齐
     3. 数据视觉块聚类
     4. 块重组
     5. 数据块对齐
   • 基于视觉的数据记录包装器 (f,l,d)
     • 本质上就是一组数据记录粒度的模板
     • 通过收集不同的模板，当有数据匹配的时候进行输出
   • 本文方法包括四个主要步骤：可视化块树构建，数据记录提取，数据项提取和可视化包装器生成。
5. 2013_Visually extracting data records from the deep web
   • rExtractor针对查询结果页面，获取数据记录之间的可视化信息和内容的相似性
   • 首先形成 VBM（Visual Block Model）,然后寻找视觉块之间的相似性
   • 通过 ULAM 螺旋和视觉规律来寻找正文区域
   • 通过寻找区域中拥有最多相似节点的节点，将其和相似节点作为数据记录输出（难以适应单记录页面）

4.3 基于机器学习进行模式识别

• 非常依赖特定的模式组合
• 输入一个需要被识别的模式样本库，比如商品模块，依靠训练让机器记住这种模式
• 样本库包含两个部分
  • 视觉信息（网页截图）
  • 文本信息（文本编码）
• 从类似的网页中提取对应模式的数据（从候选框中选取样本，将其坐标投影到最终的特征向量，然后再用 softmax 将其分类）

4.4 基于机器学习进行区域定位

《Deep web data extraction based on visual information processing》

• 使用 CNN 对网页的截图进行卷积
• 使用类 VIPS 算法进行视觉块生成
• 结合两者进行区域的识别

五、基于模板进行正文识别

主要的步骤是

• 形成一个模板库
• 对比网页的 dom 结构和模板，计算相似度
• 选择模板进行信息提取

六、基于语义标签进行正文提取

• 并非所有的网页都是具有<content>标签的 H5 页面
• 大部分的网页其内容还是会被包裹在 DIV 这样的标签中。

七、基于词库进行信息提取

• 大致过程就是通过词向量归纳相类似的词，比如电影领域的词库，然后对 DOM 节点进行配对，猜测是否为目标节点。
• 结合 RNN 构建一个信息抽取的模型，对节点进行标记
• 首先需要获取一定数量的主题型页面（比如电影页面），并对用户指定的关键目标信息进行标记
• 然后使用的标记过的样本页面进行训练，使系统获得识别目标信息的能力
• 网页内容预处理（手动预处理，筛节点，然后添加一些关键词标记）
• 缺点是需要构建词库并进行手动标记