文档库

最新最全的文档下载
当前位置:文档库 > 垂直搜7索引擎中过滤器的设计与实现

垂直搜7索引擎中过滤器的设计与实现

第26卷第12期2009年12月

计算机应用与软件

ComputerApplications

andSoftware

V01.26No,12

Dec.2009垂直搜索引擎中过滤器的设计与实现

梁党卫1彭文滔2边利亚2

(胜利油田有限公司物探研究院山东东营257000)

2(上海大学计算机3-程与科学学院上海200072)

摘要从海量Web资源中高效、快捷地检索信息的常规的方法是搜索引擎和信息抽取等技术,而过滤器则起着重要的Web网页预处理作用。提出了基于DOM树结构的过滤器方法,讨论了垂直搜索引擎中页面预处理的方法、设计与实现,并给出了具体的实现算法。最后结合在石油领域垂直搜索引中的具体应用,总结了过滤器适应于当前网页的结构和设计的特点,验证了方法的正确性和适用性,大大提高了垂直搜索引擎的效率和准确率。

关键词网页预处理过滤器DOM搜索引擎

DESIGNINGANDIMPLEMENTINGTHEFILTERoFVERTICALSEARCHENGINE

LiaugDangweilPengWenta02BianLiya2

。(GeophysicalResearchInstituteofShengliOilField,D0nsying257000,Sandong,China)

2(SchoolofComputerEngineeringandScience,ShanghaiUniversity,Shanghai200072,China)

AbstractConventionalmethodoffastandefficientlyretrievinginformationfrommflgsWebresourcesisthetechniqueofsearchenginesandinformationextraction,ere.,andthefilterplaysanimportantroleinpre?treatingtheWebpages.InthispaperweproposeafiltermethodbasedonDOMtreestructure,discussthepre-treatmentapproach,designingandimplementationofthepagesinverticalsearchenginewithaconcreterealisationalgorithm.Atlast,wesummarisethestructureanddesigncharacteristicsofthefilteradaptingtothecurrentwebsiteincon-junctionwiththespecificapplicationoftheverticalsearchengineinoilfield,andvalidatethecorrectnessandapplicabilityofthemethod.Thesearchengineefficiencyandaccuracyhavebeengreatlyimproved.

KeywordsPagepretreatmentFilterDOMSearchengine

0引言

随着互联网逐渐成为全球信息传播与共享的重要来源,互联网上的数据呈几何级数增长,Web数据的不断增长和异构数据源集成的应用,导致了大量半结构数据的产生。人们在摆脱了信息匮乏的困境的同时,海量的资源与人的有限认知能力之间的矛盾更加突出;加之网络资源的异构性、弱相关性及强的动态性等,使得人们在这浩瀚无序的Web资源中获取到符合自己需求的内容将是一件非常困难的事情。

目前这些数据大多是通过HTML语言来展现,而HTML语言的一个显著特点是结构隐含、不规则或不完整。结果使得Web上的数据处于杂乱无序的状态,数据集成性差,应用程序无法直接懈析、获取并利用web上海量的信息,给Web应用的建立造成了极大的困难。然而人们从Web上获取和利用有用信息的要求却与日俱增。如何从浩繁的Web数据中抽取出有用的信息成为众多研究工作希望解决的问题。

网上的信息载体主要是文本,目前获取这些信息最有效和最常规的方法是搜索引擎等技术。而垂直搜索与通用的搜索引擎相比,无论从定位、内容、用户,还是需求等方面,都存在着一些不同。例如,石油领域经常浏览网页的用户,大都希望了解比通用网页更为详尽的信息,如石油开采、开发技术,国内外石油形势、新闻等,而不是像Goosle那样内容泛泛的介绍性网页。换句话说,石油垂直搜索引擎,用户需求较为明确,搜索范围相应比较小,提供的信息应该更为详尽,即必须能够向客户提供差异化的服务。而要使得垂直搜索引擎能够有效地工作,对Web页面进行预处理是至关重要的一步。它可以过滤掉那些干扰视线的无用信息,保留用户感兴趣的主体内容,这种方法相应简化了垂直搜索的处理过程,提高了结果的准确性。

本文结合石油搜索引擎的应用,重点研究基于DOM树的Web网页预处理过滤器方法。基于DOM树的过滤器的方法完成页面预处理,可大大提高垂直搜索引擎的准确率。将HTML网页解析成了DOM,不仅可从大的逻辑单元检索信息,还可以对小的单元,如链接进行操作。本文的三种过滤器,每个过滤器都可由用户设置,自行制定需要过滤的内容,以完成不同的过滤,并可以按照恰当的顺序选择和叠加各个过滤器。用户可以使用DOM树作为网页中要处理信息的表达方式,而不是网页全部内容的表达方式,以完成页面信息的清洗。文章还给出了各个过滤器实现的具体方法,并对过滤器在石油搜索实际中的应用给出了相应的评价。

收稿日期:2009—09一18。粱党卫,高工,主研领域:信息抽取,数据库。

万方数据

第12期梁党卫等:垂直搜索引擎中过滤器的设计与实现149

1页面预处理技术

随着Web广泛应用于各行各业,Web网页的结构和形式有了非常大的变化,网页中存在很多凌乱多余的信息,比如菜单、flash动画、随机分布的链接、侧面链接条、脚本、广告条,以及不相关的图片等,这些信息混杂在网页之中,严重干扰了检索到的实际内容。所以在信息检索系统中页面的预处理也就是页面的清洗工作显得特别的重要。

解决页面预处理的过滤器方法,目标是过滤掉网页中凌乱多余的信息,而不是提取细粒度的数据。虽然已经有大量的研究工作,但是都不能做到完全自动的提取,通常是面向某个领域、某个网站或者某个特定格式。

早在2000年Kaasinen等就提出将网页分解成类似于扑克牌中的卡片的形式,将网页分解成一组分层的“卡片”,并把他们放人“扑克牌”内。然后以每次一张卡片的形式展示给用户,从而达到对网页内容的方便浏览,同时将图片等信息从网页中移去,使浏览者无需过多滚动便可以遍览内容。这种方案是在假设HTML文件扁平的基础上提出的,不提供树状结构的操作方法,因此这使其在处理表中嵌表的结构时便会出现问题。此外,虽然切分出的每张卡片是便于浏览的,但浏览者想要找到真正感兴趣的内容所在的卡片还是比较困难的。

Finn等人在2001年提出了对“单篇文章”网页进行内容抽取的方法。该算法首先将网页表征成文本或标签的方式,然后将其划分为三个连续的区域,并往其中加入分界,对文档进行划分。这样的处理后,绝大多数的标签被放入外面的区域,而文本的表征则被放入中央区域。这种方法的缺陷是对于只有一个主题的文档处理效果较好,但对于有多个主题的文档,则很难达成很好的处理效果。

哥伦比亚大学的McKown等人2003年研制出ArticleEx.tractor,专门从新闻页面中发现并抽取出文章。ArticleExtractor通过统计某个特定标签间的词数,分析出页面中的主体数据部分,它将网页基于HTML的结构(通常是使用div和table元素)划分为多个文本块,然后应用规则来对这些块进行分类,区分出文本、垃圾,或是其他的类别。但是ArticleExtractor没有从人的观察角度来对数据进行分类,它只对“文本”感兴趣,并将其抽取成为一种文本格式,忽视了网页的结构信息。这种方法之所以能够适用,是因为它主要用于对新闻页面的处理。

本文采用基于DOM树的方法来完成对页面的预处理工作,就是采用DOM树表示网页,树状结构是一种高效的数据结构且容易处理和遍历。过滤器可以有效地用于树中的全部节点。完成本文所述的几种方法中对结构的分析和分解的任务,过滤器递归地遍历DOM树,使用一套过滤技术去除或者修改某些特殊节点,使处理过的树中仅剩下主体内容部分。

2过滤器

本文设计的三种过滤器是基于DOM树结构的,其操作对象为DOM树,而不是原始的HTML标签文件。因此首先要使用HTMLpal葛er创建一个表示页面的DOM树。这里我们采用NekoHTML作为HTMLparser,它同时还可以对HTML中的错误进行纠正,然后生成的DOM文件被还原成HTM所表示的页面形式。DOM树可以分层布置,被分部分或者整体地进行分析,这就为过滤器算法提供灵活的处理方法。过滤器递归地遍历DOM树.采用一系列不同的过滤技术去除并修改节点,只留下主体内容节点,详情如图1所示。

图1主体内容过滤过程

我们设计的三种过滤器分别为:广告过滤器、无用链接过滤器以及空表格过滤器。每个过滤器去除页面的一个小部分,将适当的过滤器以恰当的顺序叠加作用。为使得用户可以直观方便地设置这些过滤器,我们提供了GUI界面。可以为每个过滤器定制不同程度的过滤,并可以方便地打开或者关闭。每个过滤器也可以单独作用于DOM树,以生成新树,然后这个新树被下一个过滤器处理,进行下一轮的过滤。过滤器均提供一种定义非主体内容元素的方法,这样按照用户的设置就可以将其从页面中过滤掉。通过测试,决定哪些过滤被采用.哪些过滤不合理,最后将过滤器组合,经过它将页面中与主题不相关的内容进行清洗,完成搜索引擎页面的预处理工作。

广告过滤器用来专门去除广告,当解析完网页生成DOM树后,对可设置或返回热点图连接的URL页面中“SRC”和“HREF”属性进行分析,确定出这些链接所指向的服务器地址。利用事先制定的有用广告服务器列表,可以确定这些广告是否要被删除,如果与列表里面的内容相符,就保留该广告。这个类似于操作系统中用“HOSTS”文件来阻止链接到当前计算机的服务器。

无关链接过滤器是一种提供清除“链接列表”的过滤器技术,此链接列表由多个表格单元格组成,记载“无关链接的词数量”与“相关链接的词数量”比率的阈值。当解析成DOM树时遇到表格单元,无关链接过滤器就计算“无关链接的词数量”与“相关链接的词数量”的比率,如果比率超过用户设定的阈值就会认为是无关链接而被过滤掉。

空表格过滤器是用来过滤空的“实体”信息的。用户可以通过设置来决定过滤哪些HTML的标记,以及将多少个字符的表格看成是一个实体。当过滤器对表进行处理时,检查表中的内容,如果表中的内容少于用户设定的值或没有内容,则会被过滤掉。这对于过滤那些少量不重要信息的表格是非常重要和有效的。

经过这三个过滤器的处理,整个DOM树被遍历完,得到的清洗后的页面,可以用HTML的形式表示,也可以用文本的形式表示出来。

3算法描述

过滤器算法从DOM树的根部开始利用深度优先遍历的方法进行操作,直至完成整棵树的遍历。

网页的处理从filterNode()方法开始,此方法输入一个节

垂直搜7索引擎中过滤器的设计与实现

万方数据

150计算机应用与软件2009卑

点,在该节点以及子节点上运行过滤器。如果在DOM树的根节

点上运行filterNode(),则过滤器将递归地作用于该树的全部节

点,这是一个典型的递归操作DOM树的方法。fiherNode()使

节点按照遍历的次序通过一系列的过滤器,然后根据pass?

ThroughFiher方法的变量mCheckChildren来确定是否应用过滤

器对其子节点进行过滤。部分算法实现伪代码如下:

PrivatevoidfiherNode(NodeiNode)

初始化变量mCheckChildren;

passThroughFilter(iNode);

if(mCheckChildren);

fiherChildren(iNode);l

PrivatevoidfilterChildrcn(NodeiNode)

If(Node拥有子节点)

t对Node的子节点进行操作,深度优先递归}

passThroughFilter()方法决定哪些过滤器将作用于该节点。

该方法首先获取输入节点的有关信息,如节点类型、其父节点、

属性等数据。然后,根据该节点是什么类型,决定执行哪几个过

滤器。其变量mCheckChildren的状态的改变(true或者false),

则通知递归方法检测或无需检测其子节点。,

过滤器只在元素节点上运行,这些节点以诸如<BR>以

<FONT>等标签为标志。处理需经过几个阶段,第一个阶段是

收集更多的信息,检查节点是否是一个链接或是一个图片,此信

息被登记下来,然后进入下一个阶段。第二个阶段过滤器对元

素的属性进行修改,包括表格以及表格单元的宽度属性等。经

过属性修改后,节点接着经过对某些元素节点进行删除的过滤

器,比如广告链接去除等。

isLink()方法用于检查一个节点是否是链接。它首先获得

节点的类型及节点属性;然后判断其是否是一个元素且包含

HREF属性,若真,则指示该节点是一个链接,否则,返回false。

islmage()用来检查一个节点是否是图片,其算法与isLink()相

似。islmageLink()用来检查一个节点是否是一个有图片的链

接,或者是一个有链接的图片。方法是先检测节点是否是一个

链接,然后检测其子节点中是否有图片,若真,则返回true,表示

节点确为一个图片链接。或者方法先检测节点是否是一个图

片,然后检测其父节点是否是一个链接,如果是这样的情况,同

样表明该节点是一个图片链接。若以上情况都不满足,则方法

返回false。

passThroughFilters()方法用于检测此为文本节点还是元素

节点,并实施不同的操作,其算法部分伪代码如下:

PrivatevoidpassThroughFilters(finalNodeiNode)

Inttype=iNode.getNodeType();//取得输入节点的相关信息

Node

parent=iNode.getParentNode();

∥取得其父节点的相关信息

NameNodeMapattr=iNode.getAttributes();

//取节点属性

If(type==Node.ELEMENT—NODE)//元素节点

1//设置条件,使只编辑节点而不对其实施删除操作

if(isLink(iNode))

recordLink(iNode);if(islumge(iNode));//记录链接节点

reeordlmage(iNode)://记录图片节点

if((name.equalslgnoreCase(”TD”)11name.equalsl印oreCase(”

TABLE”))&&Settings.ignoreCellwidth)//空表格

}removeAttribute(iNode.“width”);}

//移除表宽属性elseif(name.equalslgnoreCase(“DIV”)&&

settings.ignoreDivstyles)//DIV样式

{removeAttribute(iNode,“style”);}

//移除D1V样式

该算法的时间复杂度为O(n),其中,l是HTML页面被解析后所生成的DOM树的节点数。对于那些格式不规范的HTML

页面,由于在页面被解析成DOM树时被自动纠错的缘故所以

也是适用的,所以算法可以处理大多数的页面。但是在处理那

些页面中包含有极大量链接的时侯,效果欠佳,特别是当文本的

链接比例接近100%时,算法可能出现反常表现。

算法对于处理不同类型的页面时,其过滤效果也不尽相同。

当网页中包含大块文本及中等至较长的信息段时,算法效果明

显。此时,绝大部分的广告、导航条、空表格和贞面中无关元素

均被过滤,存储的纯文本结果,绝大部分内容均为页面的主体内

容。对于个别页面来说,有砦比较重要的信息,可能由于处于算

法判定的非主体块中而被过滤掉。但是,由于网络上的资源非

常丰富,这些信息很可能出现在另一张页面的主体块中。因而,

从全局的观点来看,信息的查全率仍是可以得到保证的。

4过滤器的应用

本文提出的基于DOM数结构的过滤器用于胜利油田网站的“石油搜索引擎”项目,该搜索引擎的目标是建立针对石油行

业的信息进行垂直搜索的专业搜索引擎。过滤器工作就是去除

掺杂在页面中的无关信息,对网页进行预处理,最大程度地保留

主体的内容,为搜索引擎中的处理器提供有效数据。

在Web网页过滤过程中,为了使用户可以根据自身对网页感兴趣部分的需要来进行主体内容的过滤,将无用不相关的信

息清除掉,设计了图形用户界面以满足用户选择的需要,如图2

所示。

图2过滤器基本设置

对于每个过滤器还可以进行有关过滤内容更详细的高级设

垂直搜7索引擎中过滤器的设计与实现

置,如定义过滤链接列表怎样处理、空表格过滤的标签属性选

万方数据

第12期梁党卫等:垂直搜索引擎中过滤器的设计与实现151

择、最小文本长度定义等。过滤器提供两种输出格式:HTML和文本格式。在以HTML格式输出的时候,由于链接的过滤有可能将某砦重要的导航链接移除而得不到显示,用户可以选择在页面底部湿示移除的链接。以文本格式输出的时候用户可以设置换行符的数量,来控制一行显示的内容等。

经过系统过滤后的网页前后对比如图3、图4所示。从这两幅图可以看到网页中的广告、无关链接等信息都过滤掉,留下来的信息主要是主体信息。

图3过滤前网页

图4过滤后网页

搜索引擎从网络抓取到的的页面中往往都存在很多广告等干扰信息,这些信息一般不是浏览者所关注的,而且这些无用信息的存在,大大影响了处理器相关性分析的效果,造成垂直搜索的失误。利用过滤器能够使得用户按照网页的特点,设置去除广告等无用信息的特性,从而只保留下部分用户感兴趣的内容。对于网页中的链接也可以做类似的处理,使得得到的内容非常符合用户的需求。经过一段时间的试用,该系统运行良好,搜索结果用户反映相当满意。

5结论

本文分析了搜索引擎中页面预处理技术的过滤器的各种方法,针对传统的技术产生的一些问题,提出了一种网页预处理的改进方法一基于DOM树结构的过滤器。经过过滤器处理后的网页,去掉了页面中大量杂乱无章的无用信息,保留了页面的主体内容,完成了网页清洗的任务,为下一步工作带来了便利,提高了垂直搜索引擎的效率和准确率。今后.需要在过滤结构复杂的网页和提高过滤的准确性、减少误过滤等方面做进一步的深入研究。

参考文献

[1]CharuAggarwal,FatimaA1_Garawi。PhillipYu.IntelligentcrawlingontheWorldWideWebwitharbitrarypredicates[C]//proceedingsofthe10thInternationalWorldWideWebConference.2001:96—105.[2]陈康,武港山.基于Ontology的信息检索技术研究[J].中文信息学报,2005,19(2):5I一57.

[3]张树喻,等.基于Web的半结构化信息抽取技术研究[J].系统工程与电子技术,2004.26(5):610—612.

[4]cChLatiri。SBenYahia.Queryexpansionusingfuzzyassociationrulesbetweentenn8[J].ConferenceJourneesInformatiqueMessine,Metz,France.2003

[5]欧阳柳波,李学勇.网络蜘蛛搜索策略进展研究[J].小型微机计算机统,2005,26(4):703—706.

[6]CharkrabartiS,DomB.Focusedcrawling:anewapproachtotopic—spe?eificWebfe∞urcediscovery[C]//Proceedingsofthe8thInternationalWWWConfel'ence.1999:6—9.

(上接第128页)

4结论

业务流程建模问题一直是学术界关注的热点问题。本文提出采用形式化方法PI演算对CRM系统业务流程建模,突出了工作流模型中的客户与执行者之间语言行为交互和承诺;并且通过一个实例,应用PI演算精密而抽象地描述业务流程的全过程,解决了CRM系统中数据冲突问题,定义相应的规则;最后对所建模型进行了完整的验证、分析、检测、跟踪系统流程交互的每一步,保证了模型的正确性。这样,大大地降低了企业实际开发软件的风险,节约了成本。在下一步的工作中,一方面我们将考虑建模过程中资源、角色以及时间的问题,对系统的流程进行全面的仿真模拟;另一方面将进一步运用PI演算的互模拟等价、弱互模拟、强互模拟及观察等价等定理进行业务流程的优化。

参考文献

[1]郑怀强,吕振肃.基于UML的系统分析一客户关系管理系统设计[J].计算机应用研究,2002。(12).

[2]蹇玉清.于张红,闫忠文,等.客户关系管理CRM设计与研发[J].长春:工业大学学报,2006,12.

[3]刘怡.张子刚,张戡.工作流模型研究述评[J].计算机工程与设计.2007,28(2):1.

[4]李红臣,史美林.工作流模型及其形式化描述[J].计算机学报,2003,26(11):1456—1463.

[5]AalstwWvander,HEEKvan.工作流管理模型、方法和系统[M].王建民,闻立杰,等译.北京:清华大学出版社,2004.

[6]徐宝文,周毓明,卢红敏.UML与软件建模[M].北京:清华大学出版社,2006.

[7]SmithH,FingarP.WorldlowisjustaPIprocess[EB/OL].(2004一O】).http://www.bptrends.eo/n.

[8]MilnerR,farrowJ,WalkerD.Acalculusofmobileprocesses,partI/11.JournalofInformationandComputation,1992.100(1):1—77.[9]MilnerR.CommunicatingandMobileSystems:TheH--Calculus.Cambridge:CambridgeUniversityPress,1999.

[10]JoachimParrow.AnIntroductiontothe竹?Calculus[C]//HandbookofProcessAlgebra.Elsevier.200l:479—543.

[11]BjOrnVictor.TheMobilityWorkbenchUser'sGuide:Polyadicversion3.122.DepartmentofInformationTechnology.UppsalaUniversity,1995.[12]BjOrnVictor,FarnnMoiler.Themobilityworkbench:a100lforthe竹.

垂直搜7索引擎中过滤器的设计与实现

垂直搜7索引擎中过滤器的设计与实现

calcIIlus.万方数据

垂直搜7索引擎中过滤器的设计与实现

垂直搜索引擎中过滤器的设计与实现

作者:梁党卫, 彭文滔, 边利亚, Liang Dangwei, Peng Wentao, Bian Liya

作者单位:梁党卫,Liang Dangwei(胜利油田有限公司物探研究院,山东,东营,257000), 彭文滔,边利亚,Peng Wentao,Bian Liya(上海大学计算机工程与科学学院,上海,200072)

刊名:

垂直搜7索引擎中过滤器的设计与实现

计算机应用与软件

英文刊名:COMPUTER APPLICATIONS AND SOFTWARE

年,卷(期):2009,26(12)

被引用次数:0次

参考文献(6条)

1.Charu Aggarwal.Fatima Al-Garawi.Phillip Yu Intelligent crawling on the World Wide Web with

arbitrary predicates 2001

2.陈康.武港山基于Ontology的信息检索技术研究[期刊论文]-中文信息学报 2005(02)

3.张树瑜基于Web的半结构化信息抽取技术研究[期刊论文]-系统工程与电子技术 2004(05)

4.C Ch Latiri.S BenYahia Query expansion using fuzzy association rules between terms 2003

5.欧阳柳波.李学勇网络蜘蛛搜索策略进展研究 2005(04)

6.Charkrabarti S.Dom B Focused crawling:a new approach to topic-specific Web resource discovery 1999

本文链接:http://www.wendangku.net/doc/fabb16d87f1922791688e8a7.html/Periodical_jsjyyyrj200912048.aspx

授权使用:吕先竟(wfxhdx),授权号:4cd349eb-5333-4e60-875e-9e7501420b48

下载时间:2011年1月24日

江苏金湖大华自动化仪表有限公司座落于碧荷飘香、风景秀逸、人杰地灵具有“天下第一荷花”的金湖水乡。公司物资力量雄厚,生产设备先进,检测设施齐全,并且制定了科学合理的生产工艺和健全的质保体系,汇聚了许多对仪器仪表制造有着特殊追求和造诣的科技人员及职工队伍。在温度、压力、流量、显示、效验等仪表的制造均领先于同行业。公司主营产品有有纸记录仪,,压力变送器热电偶、热电阻、双金属温度计、变送器、流量计、数显仪、效验装置、自动化成套设备、电线电缆、线缆桥架等。产品主要用于电力、化工、冶金、钢铁等众多行业。业绩的取得来源于客户的厚爱,公司一直遵循着用质量打造品牌的宗旨,以诚信待人为守则。期盼着与各界友人的愉快协作,共同创造优越的的业绩篇章。

诚信:以诚信打造企业一流服务品牌

求实:以求实作为企业稳固发展的基石

合作:以合作实现与客户和伙伴共同成长

创新:以不断创新推动企业可持续发展

服务:以专业服务实现最高的客户满意度

http://www.wendangku.net/doc/fabb16d87f1922791688e8a7.html/