网页应用数据逆向工程的结构化方法

# 网页应用数据逆向工程的结构化方法 ## 1 引言 在网页数据处理中，识别网页中的信息聚合块是理解网页结构和内容的关键。通过识别这些代表语义相关对象分组的网页对象块，能够深入了解网页数据的组织和呈现方式。为了半自动化地识别以网页对象块形式组织的网页数据的结构、功能和意义，我们开发了名为 ReverseWeb 的工具，并在公开可用的网站上进行了实验。 ## 2 相关工作 目前，有多种方法和工具可用于分析网页结构和布局，以下是几种常见的方法： | 方法类型 | 特点 | 示例工具 | | ---- | ---- | ---- | | UML 基于方法 | 多数网页应用逆向工程方法和工具依赖统一建模语言（UML），提供稳定熟悉的环境来建模组件和应用行为，但更关注与网页应用的交互而非组织 | Di Lucca 等人开发的 WARE 工具、Chung 和 Lee 的方法 | | 本体基于方法 | 通过模式对网页应用进行建模，提供高级分析，但通常依赖特定领域，多数情况下需用户干预构建领域本体后才能进行数据提取 | Benslimane 等人和 Bouchiha 等人提出的 OntoWare、Lixto 工具 | | 源代码基于方法 | 对网页应用的源代码进行分析，产生特定方面的逻辑描述（主要与呈现相关） | Ricca 和 Tonella 提出的 ReWeb、Vanderdonckt 等人开发的 VAQUISTA、Antoniol 等人的 RMM 基于方法 | ## 3 页面结构提取 ### 3.1 概述 我们的方法与近期从网页提取信息的技术相关。大型网站页面中的数据通常来自后端数据库并嵌入共享 HTML 模板，提取过程可依赖对共享模板的描述推断。但现有方法未充分利用网页的超文本结构，我们的工作旨在发现这一结构。 为实现这一目标，我们定义了数据逆向工程（DRE）过程，包括以下步骤： 1. **页面分割**：根据用户的视觉感知将网站中的每个网页分割成多个块，通过分析与块关联的 DOM 得出一组结构模式。此步骤结合计算机视觉方法和 DOM 结构提取技术。 2. **模式发现**：将每个网页的模式按视觉块分组，对网站中的页面进行聚类。每个聚类代表语义相关数据的聚合，用一组结构模式表示。最后基于概念表示提取网站的逻辑模式。 ### 3.2 页面分割 我们利用网页文档的半结构化性质，通过文档对象模型（DOM）表示。但 DOM 不能很好反映页面的实际语义结构，而视觉页面布局更适合进行语义分区。因此，我们采用 VIPS 方法（基于视觉的页面分割），利用 DOM 树和视觉线索提取信息块。 VIPS 的输出为每个网页关联一个视觉块（VB）的分区树结构，这些 VB 具有高度一致性，传达页面内的同质信息。然后为树分配 XML 描述，每个 VB 通过其在 DOM 表示中的路径和页面位置来标识。 接下来分析每个识别的 VB，发现代表具有共享结构的信息聚合的重复模式。具体做法是在每个 VB 中，用哈希码标记从 VB 根到节点的任何路径，通过前序遍历生成一个哈希码向量 V。 为了识别重复路径，我们使用名为 path - mark 的算法，其灵感来自基于字典的压缩算法 LZW。以下是 path - mark 算法的伪代码： ```plaintext Algorithm 1. Path - Mark 1: Input: A visual block VB 2: Output: A Map of occurring patterns in VB, each one related to its occurrences 3: begin 4: V ← HASHPREORDER(VB) // V is a sequence 5: EMPTY(M), EMPTY(Q) // M is a map and Q a queue 6: seq_length ← LENGTH(V) 7: for win from 1 to seq_length / 2 do 8: for index from 0 to seq_length - win do 9: previous ← DEQUEUE(Q) 10: actual ← SUBSEQUENCE(V, index, index + win) 11: ENQUEUE(Q, actual) 12: if actual = previou ```