传统Web爬虫无法解决爬行Ajax应用所面临的JavaScript执行、状态识别与切换、重复状态检测等问题。为此，首先定义Ajax应用的状态转换图，并设计了一种基于状态转换图的Ajax爬行算法，通过该算法可以获取Ajax应用状态信息和后台Deep Web资源。为了提高Ajax爬行的准确性、减少待爬行的状态数目，使用Ajax指纹识别、DOM结构过滤等方法改进上述算法。实验结果表明了算法的有效性和性能。
4268 计算机应用研究 入缓存。当触发一个节点事件并进入新的状态后,需要回退到 2 aph, queue, Ic); 之前状态以触发其他节点事件时,即可通过从缓存中取值来撤 3 page ie FetchPage(url) 销DOM的变化。因算法使用广度优先策略进行遍历,极大地 4 events=Regex. Match( page, eventPattern 提高了缓存的利用率,节约了所需的缓存空间。 5 root State State( ie DOM, depth) 6 queue. En Queue( rootState 3对Aax爬行算法的改进 7 while queue. IsEmuply() du 8 slae queue DeQueue(): ie. LvadSlale( state ); 基于状态转换图的Aj爬行算法可以建模AjHx应用的状 9 if state. depth > MAXDEPTH return; 态,生成与jx应用的状态转换图,并获取指向后台 Deep Web Nodes= Regex. Match( ie DOM, jsPattern ) 资源的链接。但算法没有考虑不同的Aja开发技术的区别, 11 foreach node N 可能造成状态丟失;算法识别新状态时直接比较完整的DOM ie. TriggerEvent( node 这将产生很多不必要的状态,甚至造成状态爆炸。为了提高算 if node event. HasXHRCall() then 法爬行Aax应用的有效性和性能,使用Aiax指纹识别、DM GetDeep WebResource(); WaitforRe esponse 结构过滤等方法对Ajax爬行算法进行改进。 if IsD iff state. DOM, ie DOM)then 3.1Ajax指纹识别 16 if graph HasD OM(ie DOM)then Ax技术实现异步操作的关键是XHR对象。该对象用于 newstate= State( ie DOM, +-depth graph. AddState( new etate); 向服务器端异步发送请求,并接收服务器端的响应以进行局部 queue. En Queue( newstate) 刷浙。除了直接使用XHR对象的Ajax开发技术外,还有很多 trans=Transition( state, newstate, node) 封装了XHR对象的第三方AjHx框架和库可以用来开发Ax aph. addTrans trans 应用2。第三方Ajax框架除了以属性的形式将事件绑定到 22 ie. LoadState( state DOM元素节点外,还可能头现框架相关的事件附加模式,爬行 23 4jx应用时首先识别其是否使用了某种第三方框架,将有利 算法首先进行初始化(第2行),建立空的状态转换图和于提高识别事件的准确率,并可有针对性地优化爬行过程。 待爬行状态队列,启动嵌入式浏览器。根据给定的URL获取 直接使用XHR对象开发Ajax应用时, Javascript代码既可 Ajax应用的初始面(第3行),利用正则表达式识别Ajax应以直接放在HmM页面中,也可以作为独立的Jsri文件, 用中的所有事件(第4行),并将当前DOM结构代表的初始状第三方的Ax框架则通常都是链接到独立的 JavaScript文件。 态加人待爬行状态队列(第5行),初始状态的深度设定为0。针对这种方式,首先收集第二方Ajax框架的指纹信息,如文件 算法的主体操作是对Aa应用的状态进行广度优先遍历名、文件大小、XHR对象封装函数等,构建了一个Ax框架知 (第722行)。从待爬行状态队列取出一个元素,将其载入浏识库,并基于该知识库设计了一个A指纹识别算法,如算法 览器作为当前状态(第8行),利用正则表达式提取所有附加2所示。 有事件的DOM元素节点(第9行)。 算法2 Ajax FingerPrinting(url) 依次对每一个节点触发绑定的事件(第12行)比较其触 发前后DOM是否一致,若不一致且状态转换图中无此DOM 2 page = ie FetchPage(url) 代表的状态(第1516行),则说明生成了新状态。将新状态和3pageMatch(xmlhttprequest)thenreturnXhr 转换加入状态转换图,将新状态加人待爬行状态队列(第1821 4 jsName Regex Match( page, jsPatten 5 js= ie FetchPage(jsName 如果触发的事件中产生了XHR调用,则抽取生成的指向 6 ajax.ih= DB. Match( js Name) 后台 Deep Web资源的链接,等待并接收服务器的响应(第13 if ajax Lih && js. Match( ajax L.ih. sign, then return ajaxlib 14行),然后同样执行上述新状态识别过程。 9 if ajax Lib= DB. Hash Match( js. hash)then 当前状态中的所有节点事件处理完后,判断待爬行状态队 return ajaxlib 列是否为空(第7行),若不为空且待爬行状态的深度尚未到 11ifjs.Match(xmlhttpRequest)then 达预设最大值(第9行),则重复上述遄历过程;否则算法结 return Xhr 東,状态转换图生成完毕。 13 return error. 为了生成状态转换图,需要在每一个状态中尝试触发所有 DOM节点上绑定的 Javascript事件,但事件触发后Ajnx应用通 算法首先通过Aax应用的URL状得初始HIML页面(第 常将进入一个新的状态。为∫能够在同一状态中依次触发所2行),然后判断页面是否包括XHR调用,若存在则认为没有 有事件,需要将Aja应用恢复到一个先前的状态,即实现状态使用第三方柜架(第3行),算法结束;否则从中解析出页面链 切换。 接的 Javascript文件名(第4行),获取对应的 Javascript文件 算法通过缓存状态信息实现A应用状态快速切换(第(第5行),并与从Aju框架知识库中读取的第-方框架的文 22行)。每次从待爬行状态队列中取出一个状态时,都将其加件名依次进行比较(第6行)。若匹配成功且 JavaScript文件中 第11期 郭浩,等:一种基于状态转换图的Aax爬行算法 4269 包含有该Aia框架的指纹信息,则认为使用了该Ajax框架到的服务器端资源链接数目作为评价标准;然后比较Ajix 第78行),算法结東 ( rawler与同类Ajax爬虫的性能,以爬行时间作为评价标准。 若上述匹配失败,则直接用 Javascript文件的hash值在其中作为对比的传统Web爬虫采用开源工具 Spider,同类 Ajx框架知识库中匹配,若匹配成功则说明该应用使用了第jax爬虫采用文献[6中提供的 Crawljax,以文献[6]中设计的 方Ajax框架,只是改变了文件名(第910行),算法结束。 单页面Ajax站点作为实验环境。 Ajax Crawler与 Crawljax的状 若上述兀配仍失败但 Javascript文件中有XHR调用代码,态最大深度均设定为5,线程数设为1; Spider的页面最大深 则认为是在独立的 JavaScript文件中使用基本的Ajax开发技设为5,工作线程数设为1。实验计算机配置为P42.66GHz 术(第1112行);否则不是Ajx应用(第13行),算法结束。 处理器,512MR内存, Windows XP sp3操作系统 Ajx指纹识别算法可以有效识别出Aiax应用是否使用了4.2实验结果及分析 某种第三方框架,且可以认别出被重命名的第三方框架。 实验结果如表1所示。 3.2DOM结构过滤 表1爬虫探测结昊对比 Ajax应用的状态变化最终都体现为DOM结构的变化,这 状态数/贝面数链接数时间/ms 1254 种变化可能由与用户交互的客户端事件引起,也可能由与服务 71361 器端交互的XIR调用引起。认别状态变化最简单的方法是育 A jax Crawle 10 47546 接比较DOM结构的hash值。由丁页而中可能存在计数器、数 从表1可以看出,由于 Spider仅能抽取静态超链接 字时钟等组件,受其影响页面内容可能在持续变化,此时采用 Ajax Crawler探测到的服务器端资源链接数目显著高于Cspi 比较hash值识别DOM状态变化的方法将产生状态爆炸问题。der,其差值即为 AjaxCrawler探测到的Ajmx应用后台 Deep Web 为了解决这个问题,可以将Ajx应用的状态变化定义为资源。由此可见,基于状态转换图的Ajax爬虫可以有效爬行 Web页面行为的变化,即DOM元素节点和事件的关联情况发Ajm应用。 Crawliax仅标志状态,未提供链接抽取功能,故无 生改变或生成「新的DOM兀素节点,而不关注节点文本的变法记录探测到的链接数。由于需要执行 JavaScript代码,Ajax 化或节点字体颜色等的变化。改进后的Ajx爬行算法使用 Crawler的性能不如 Spider,但由于减少了状态数目,性能仍 DOM结构过滤算法首先将页面中DOM元素节点的文本内容明显优于 Crawljax,可见通过改进具体的算法设计可以部分弥 和与页面展现相关的属性过滤掉,然后进行DOM结构比补执行 JavaScript代码带来的性能损耗。 较。DOM结构过滤算法如算法3所示。 算法3 DOMfitering(DOM) 5结束语 由于Aax技术具有近似于实时响应的交互性,极大地改 2 DOM. Remove( space Nodes) 善了用户体验,因而正逐渐成为Web开发的主流技术。但由 3 foreach node in DOM. nodes do 于爬行Aax应用将面临 javascript执行、状态认别与切换、重 4 if node. type Type. Text then 复状态检测等问题,导致传统基于静态超链接抽取的Wcb爬 5 DOM. Remove( node)i 虫无法爬行Ajx应用,Ajax应用及其后台的服务器资源成为 6 if node type = Type Attrib then 无法被搜索引擎索引的 Deep Web资源。本文提出了一种基 7 if Regex. Match( nore, prese Pattern )then DOM. Remove( node 于状态转换图的Ajx爬行算法并对算法进行了多种改进,经 9 rely DOM 实验验证,该算法可以有效地爬行Aa应用,识别Ajax应用的 后台 Deep Web资源,且算法性能较同类算法有显著提升。在 由丁浏览器将H.文档中的所有节点、文本和属性及初步解决状态爆炸间题后,Ajax电的性能瓶敛转换为与服 它们之间的空白字符均视做DOM节点,DOM过滤算法首先移务沿端的异步通信时延,今后将主要针对这个问题对算法进行 除DOM结构中的所有空白字符(第2行);对于其余的所有优化 DOM节点,判断其节点类型。若为文本节点,则移除(第4 参考文献: 行);若为属性节点且为宁体、颜色等属性,则移除(第68行) [1 GARRETT JJ. Ajax: a new apprcach to Web applications EB/OL I 若为元素节点则不处理。由于仅识别Web面行为的变化, (2005)[2008-10-08j.http://www.adaptivepath.com/publicatiane/ 改进后的Ajax爬行算法极大地减少了状态转换图中的状态数 essays/archives/000385 php A nols usage survey results[ ER/OL] 日,且对爬行到的后台 Deep Web资源数口没有影响。 (2007).[2008-10-09].http://ajaxian.com/archives/2007-ajax 4实验与结果分析 tools-usage-survey-results/ [3 SHAH S. Craw ling Ajax-driven Wch 2. 0 applications[ R]. 2007 4.1实验设计 [4] FREY G. Indexing Ajax Weh applications D]. Zurich: Swiss Federal Institute of Technology, 2007 为了验证本文算法的有效性并评价其性能,使用C#语言 [5 MATTER R. Ajax crawl: making Ajax applications searchable[ d] 开发了基于状态转换图的Aa爬虫系统 Ajax Crawler。其中调 Zurich: Swiss Federal InsLilule of Technology, 2008 用嵌入式浏览器的操作基于开源工具WaiN实现,并分别与传61 MESBAH A, BOZDAG E, van deursen a. Crawling ajax by infer 统Web爬虫和同类Ajax爬虫进行实验比较。实验首先比较 ring user interface state changes[ C]//Proc of the &th Internationa Ajax crawler与传统Web爬虫爬行A应用的有效性,以探测 Conference on Web Engineering. 2008: 122-134