PDF《基于最小可查询模式的 Deep Web 查询》

②一次查询需要完成整个表单的填写,降低 了爬取效率. 无先验知识的查询方法克服了上述方法的不足, 查 询过程不依赖先验知识, 能较好地处理包含信息较少的 查询表单.该类方法通过解析当前已获取的 Deep Web 数据记录以产生新的候选查询关键词.Barbosa 等最先 提出这种思想,并给出了基于频率的选词方法[3] ,通过 选择在已获记录中频率最高的关键词进行查询,然而, 使用已获取记录中的高频关键词并不能保证查询获得 较多的新记录.为此,Ntoulas 等提出了一种基于期望 回报率的贪婪选词方法[7] ,该方法根据本地已有信息产 生候选关键词并估算其期望回报率, 选择回报率最大的 关键词进行查询. Wu 等用图对 Web 数据库进行建模, 将求解最优选词策略的问题转化为寻找图的最低带权 支配集(weighted minimum dominating set)的问题,提出 了基于链的贪婪查询选词(greedy link-based query selection)策略来求解近似最优解,并引入领域知识增强 了爬取效果[8] .相对于基于先验知识的查询方法,无先 验知识的查询方法提高了查询处理能力,然而,该类方 法仍存在以下

3 方面问题: ①仅能对单文本框进行查询 并默认获取到的关键词与该文本框匹配;

②只能根据当 前已获取的局部信息来估算下一次查询选择,存在 近 视估算 问题;

③初始查询的关键词选择缺乏足够依据. 上述问题限制了 Deep Web 查询方法的能力,从而导致 数据孤岛 现象,即仅能获得整个数据库中的一部分 记录. 通过对大量 Deep Web 查询表单的分析,本文提出 了最小可查询模式 MEP(minimum executable pattern)的 概念,并据此提出一种自适应的 Deep Web 查询方法. 该方法将查询由单文本框推广到 MEP 集,通过选择 MEP 和与该 MEP 匹配的关键词向量共同确定一次查 询,并根据已获取的 Deep Web 信息自适应地产生期望 回报率最大的下一个查询,直到满足查询停止条件.该 方法不仅具备无先验知识方法的优点, 而且由于充分利 用了查询表单 MEP 集中控件的查询能力,能较好地克 服 数据孤岛 问题.在6个Deep Web 网站的实验表 明,该方法与 LVS 方法、针对单文本框的无先验知识 方法等相比,具有更好的爬取效率.

1 基本概念 定义

1 查询表单.查询表单是 Deep Web 的查询接 口,可表示为所包含控件元素的集合,即查询表单 F={e1, …, en},其中,ei 为F的控件元素. 每个控件元素有相应的取值空间,设iD为元素 i e 的值域.若iD为有限集,则ie为有限域元素;

若iD为无限集, 则ie为无限域元素. 描述元素的一个重要属性 是标签,用label( i e )表示[4] .在不被误解的情况下,本 文用元素的标签来指代元素. 定义

2 可查询模式 (executable pattern, EP). 给定 查询表单 F={e1, …, en}, ? {e1 '

, …, em '

}∈2F , 1≤m≤n, 若对{e1 '

, …, em '

}中的控件元素赋值后进行Deep Web 数 据库检索能返回检索结果,则称集合{e1 '

, …, em '

}为F的一个可查询模式. 可查询模式满足以下单调特性: ①若{e1 '

, …, em '

}为可查询模式,则任何包含 {e1 '

, …, em '

}的F的子集也是可查询模式;

②若{e1 '

, …, em '

}不是可查询模式,则{e1 '

, …, em '

} 的任意子集也不是可查询模式. 通过可查询模式返回的检索结果也包括零结果. 对 非可查询模式中的元素赋值后无法执行数据库检索, Deep Web 站点一般会给出错误提示或跳转到无关新页 面.因此,一次查询由一个可查询模式中的元素和这些 元素的赋值唯一确定. 定义