（计算机科学与技术专业论文）基于位置感知的web文本搜索技术研究.pdf

：l r e s e a r c ho nt h er e t r i e v a lt e c h n o l o g yo ft h el o c a t i o n a w a r e w e bs e a r c h at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y w e n x i n g ( c o m p u t e r s c i e n c ea n dt e c h n o l o g y ) t h e s i ss u p e r v i s o r ：a s s o c i a t ep r o f e s s o rf uy i n g l i a n g j u n e 2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 基王僮置壁翅的鲨曼垒塞奎塑塞煎鲞婴窒：。除论文中已 经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密( 请在以上方框内打“ ) 敝储躲i 之导师躲 粤毪 日期：加ff 年) 月上e 1 r蔫 中文摘要 摘要 随着互联网的高速发展，w e b 搜索引擎已成为人们获取信息的必不可少的工 具。很多情况下，用户查询的信息都与位置信息相关，比如旅游信息，某地商业 信息和某地发生的时间信息。用户在进行查询与位置相关的信息时，希望检索出 在特定区域内并满足检索条件中的文本约束的相关页面。随着旅游业和全球贸易 等行业的发展，人们跨区域的活动就同益频繁，人们在互联网上在查询指定的区 域检索相关的信息的需求越来越突出。由此看出，位置相关的查询需求同益增多， 同时位置信息的重要性也引起了相关领域学者的关注。 本文重点围绕如何解决基于位置感知的w e b 文本搜索中的关键技术展开研 究。本文首先对分析基于位置感知的w e b 文本搜索引擎特点后提出了其所面临的 三个关键问题：( 1 ) 确定网页地理范围；( 2 ) 地理位置信息和文本信息融合；( 3 ) 设 计一种高效的检索算法。然后通过具体研究提出了采用基于模式匹配和基于地名 数据库的方法抽取网页地理信息和通过概率分布确定网页的地理范围。在确定网 页地理范围基础之上，本文提出了一种新型的地理位置信息和文本信息融合的索 引结构m r t r e e 和倒排索引相互独立的索引结构。同时基于m r - t r e e 和倒排 索引相互独立的索引结构，设计了一种高效、稳定的查询算法。最后，在解决三 个关键问题之后，本文设计和实现了一个位置相关的w e b 文本搜索引擎的模型并 在大量现实数据集上加以测试和验证，取得了很好的效果。 实践证明，基于位置感知的w e b 文本搜索是普遍存在的现实需求，同时如何 实现该类搜索也是一类复杂问题和极具挑战性的研究工作，具有重要的理论研究 价值和现实意义。由于研究时间和自身水平有限，论文的研究工作尚缺乏深度， 且存在很多不足之处，作者将在后续的研究过程中加以持续改进。 关键词：位置相关的搜索；地理信息抽取；混合索引；基于位置感知 英文摘要 a b s t r a c t a st h ew o r l dw i d ew e bg r o w sr a p i d l y ，w e bs e a r c he n g i n e sa r eb e c o m i n g i n d i s p e n s a b l et o o l sf o ri n t e r n e tu s e r st os a t i s f yt h e i ri n f o r m a t i o nn e e d s i nm a n yc a s e s ， p e o p l e a r ei n t e r e s t e di ni n f o r m a t i o nw i t hg e o g r a p h i cc o n s t r a i n t s ，s u c ha st o u r i s m i n f o r m a t i o n ，l o c a lb u s i n e s s e s ，o rl o c a l l yr e l e v a n te v e n t s g e o g r a p h i cw e bs e a r c h e n g i n e sa l l o wu s e r st oc o n s t r a i na n do r d e rs e a r c hr e s u l t sb yf o c u s i n g aq u e r yo na s p e c i f i e dg e o g r a p h i cr e g i o n i nt h i sd i s s e r t a t i o n ，w ed e s c r i b et h ea r c h i t e c t u r ea n dm a j o r c o m p o n e n t s o fag e o g r a p h i cw e bs e a r c he n g i n ea n da d d r e s st h ec h a l l e n g e so f i n t e g r a t i n gg e o g r a p h i ci n f o r m a t i o ni n t oak e y w o r d b a s e ds e a r c he n g i n e t h e r ea r em a n yd i f f e r e n ts o u r c e so fi n f o r m a t i o na b o u tt h eg e o g r a p h i cp r o p e r t i e so f w e bd o c u m e n t st h a tc a nb ee x p l o i t e df o rd a t ae x t r a c t i o n f o re x a m p l e ，g e o g r a p h i c r e f e r e n c e sc a nb ee x t r a c t e df o r md o c u m e n t sa n du r l s ，o rf r o mt h ew h o i se n t r i e so ft h e s i t e s f o re a c hp a g e ，t h ec o l l e c t i o no fa l lr e g i o n st h a tt h ed o c u m e n tp r o v i d e si n f o r m a t i o n a b o u ti st h e ns t o r e di nas t r u c t u r ec a l l e dag e o g r a p h i cf o o t p r i n t o n c et h e s ei n i t i a l g e o g r a p h i cf o o t p r i n t sh a v eb e e nc r e a t e d ，t h e yc a nb ee n h a n c e db yp r o p a g a t i n gt h e i r i n f o r m a t i o na c r o s sh y p e r l i n k sa n ds i t es t r u c t u r e g e o g r a p h i cs e a r c he n g i n eq u e r yp r o c e s s i n gi s d i f f e r e n tf r o ms t a n d a r ds e a r c h e n g i n e s i nt h a ti tr e q u i r e sac o m b i n a t i o no ft e x ta n ds p a t i a ld a t ap r o c e s s i n gt e c h n i q u e s g i v e naq u e r y ，i ti d e n t i f i e sp a g e st h a tc o n t a i nt h ek e y w o r da n dw h o s ep a g ef o o t p r i n t i n t e r s e c t sw i t ht h eq u e r yf o o t p r i n t ，a n dr a n k st h e s er e s u l t sa c c o r d i n gt oaa l g o r i t h m sf o r e f f i c i e n tq u e r yp r o c e s s i n gi ng e o g r a p h i cs e a r c he n g i n e s ，i n t e g r a t et h e mw i t hat e x t q u e r yp r o c e s s o r , a n de v a l u a t ep e r f o r m a n c eo ft h ea l g o r i t h m so nl a r g es e t so fr e a ld a t a a n dq u e r yt r a c e s k e yw o r d s ：g e o g r a p h i c a ls e a r c he n g i n e ；g e o g r a p h i c a li n f o r m a t i o n e x t r a c t i o n ； h y b r i di n d e x i n g ；l o c a t i o n - a w a r e 目录 目录 第1 章绪论1 1 1 研究背景与意义1 1 2 国内外研究现状一1 1 3 论文研究内容6 1 4 论文结构安排7 第2 章w e b 信息检索技术8 2 1w e b 搜索引擎技术8 2 1 1w e b 搜索引擎的工作原理与结构8 2 1 2w e b 页面抓取9 2 1 3 页面分析与索引1 0 2 1 4 检索与排序。1 2 2 2 地理信息检索1 3 2 2 1 地理信息系统的概念1 3 2 2 1 地理信息系统的关键技术1 3 2 3 基于位置感知的w e b 文本搜索1 4 2 3 1 地理位置信息的获取1 4 2 3 2 地理位置信息索引结构。1 5 2 3 3 地理位置信息的检索与计算1 6 2 3 4 查询结果的排序1 7 第3 章基于位置感知的w e b 文本搜索1 8 3 1w e b 页面中的地理信息的抽取1 9 3 1 1 位置信息分类2 0 3 1 2 位置信息抽取2 1 3 2 文本信息和地理信息融合2 5 3 2 1r - t r e e 和倒排文件相互独立索引结构2 6 3 2 1 地名层次r t r e e 树( m r - w r e e ) 和倒排索引相互独立索引结构2 8 3 3 基于位置感知的查询算法。3 0 3 3 1 基本算法3 0 3 3 2 基本算法的分析3 1 3 3 3 基于m r t r e e 和倒排文件相互独立索引结构的查询算法3 3 3 4 基于位置感知搜索结果的排序算法3 4 3 4 1 文本相关性3 4 3 4 2 地理信息相关性3 6 3 4 3 混合信息相关性3 7 第4 章基于位置感知的w e b 文本搜索系统设计与实现3 8 4 1 系统设计3 8 4 1 1 地理信息抽取模块3 8 4 1 2 混合信息索引模块4 0 4 1 3 查询模块4 4 4 2 系统实现4 5 4 2 1 开发和运行环境介绍4 5 4 2 2 系统实现界面4 6 4 3 实验验证和结果分析4 7 4 3 1 实验数据准备4 7 4 3 2 位置信息抽取实验4 8 4 3 3 基于位置感知的检索实验4 8 第5 章总结与展望5 3 5 1 工作总结5 3 5 2 未来展望5 4 参考文献5 5 致谢5 9 基于位置感知的w e b 文本搜索技术研究 第1 章绪论 1 1 研究背景与意义 近年来i n t e r n e t 的发展曰益迅猛，w e b 应用也越来越广泛，万维网( w w w ) 已成人们 进行信息交流和获取各种资源的一个重要途径f 9 1 。根据著名互联网统计机构n e t c r a f l 于 2 0 0 9 年7 月发布的最新统计显示，全世界现在已有统计的网站达到了2 3 9 ，6 1 1 ，1 1 1 个之 多。同时，互联网在中国的发展速度也相当迅速，据统计，截止到2 0 1 0 年1 月1 5 日， 中国网民已经达到了3 8 4 亿，较2 0 0 8 年增长2 8 9 ，手机用户达到1 2 亿；中国的网 站数，即域名注册者在中国境内的网站数( 包括在境内接入和境外接入) 达到3 2 3 万个 【9 1 。互联网经过四十余年的发展积聚了海量的信息内容，同时促进了搜索引擎技术的快 速发展【l 2 】，出现了很多优秀的搜索引擎，从雅虎的目录搜索到百度和谷歌的全文搜索。此 外，为了让用户搜索更快更准更全，还产生了诸如元数据搜索引擎【3 棚、垂直搜索引擎1 6 - s l 等越来越智能的搜索引擎。 面对呈指数增长的互联网资源，互联网信息获取者对搜索引擎技术提出了更高的要 求，尤其随着旅游业、跨国贸易、电子商务等行业的发展，鉴于互联网上有关实体的信 息普遍有其相关的地理位置信息，基于，逐渐关注，并已成为国内外学者研究的热门课 题【2 1 。 其中如何能智能地理解用户意图进而更快更准更全地查询到需求的信息已经成为， 而且据统计表明，将近1 5w e b 搜索的任务是与特定位置相关的【1 0 1 。例如，搜索“大连市 内所有书店 。因此，世界一流的商业搜索引擎公司g o o g l e 、百度等开发出了越来越多 的与位置相关的w e b 应用服务，例如广告业务、地图服务以及旅游信息等服务。 基于上述背景，研究“通用的基于位置感知的w e b 文本搜索 对提高用户的检索信 息的准确率具有重要的实际效果，同时对w e b 文本信息检索也具有很重要的理论意义。 1 2 国内外研究现状 互联网发展到今天，我们可以使用很多搜索引擎去查询我们想要的资源，国内比较 有名的有b a i d u 、s i n a 、s o h u 等，而国外有大名鼎鼎的g o o g l e 、i n f o r s e e k 、m e t a c r a w l e r 第1 章绪论 。纵观其二十年以来的发展历程，从第一个搜索引擎a r c h i v e 到如今搜索领域的佼佼 b a i d u 、g o o g l e ，主要经历t - - 代的发展1 1 1 j 。 第一代搜索引擎出现于1 9 9 4 年前后，以a l t a v i s t a ，y a h o o 和i n f o s e e k 为代表，注重 馈结果的数量，主要特征是“求全 。它主要靠人工处理的分类目录进行查询，一般 程序员自己将站点名称、站点内容的摘要加入到搜索引擎的资料数据库中。搜索引擎 析用户输入的信息后，依据先前配置好的规则进行匹配、结果排序和显示。这类搜索 擎只能进行字符串匹配操作，不能实现全文搜索【1 2 。1 4 1 。实际上，现实的搜索引擎的性 没有理想中的那么高效，在全球十大搜索引擎中，能搜索到的网页仅仅占了互联网中 页的1 6 ，主要因为是这些搜索引擎没有试试更新自己的索引库【1 5 1 。 第二代搜索引擎是全文搜索引擎，是真正意义上的搜索引擎，首先由搜索引擎其抓 模块在互联网上分析、抓取网页，并将抓取的网页处理后保存到自己的索引库中。然 搜索引擎基于索引库根据用户输入的关键字进行匹配、结果排序和显示【婚1 9 l 。1 9 9 8 ，以g o o g l e 和d i r e c t h i t 为代表的第二代搜索引擎横空出世，这些引擎的主要特点是 准率高，可以用求精来形容其的优点。这类搜索引擎不再要求w e b 程序员将网站的 要信息手动添加到其资料库中，其能利用自己的爬虫程序将任意网页抓取到它的索引 中。第二代搜索引擎的缺点是返回结果太多，而且查询结果中无关信息太多，查询结 显示混乱，用户找到自己需要的资料很困难【2 0 , 2 1 l 。 第三代搜索引擎是是第二代搜索引擎更智能化和用户使用的个性化，主要增加了与 户的交互和语义识别等高级的技术，采用了自动分类、自动聚类等人工智能方面的技 ，而且使用了内容智能分析技术以及智能识别技术，提高了搜索引擎的检索能力【2 2 彩】。 使得搜索引擎技术更加智能化，可检索得资源更广泛，搜索方式变得更加快捷有效， 用户使用搜索引擎获取信息获得更好的体验。基于位置服务的搜索引擎正是属于第三 的搜索引擎，它能够智能地理解用户的查询语义，更强的查询能力，大大方便了用户 的查询【2 1 。 日常生活中的8 0 的信息与位置有关，足以见得位置的重要性【2 6 捌。因此，世界出 色的搜索引擎公司都相应提出了相应的位置相关的搜索服务。g o o g l e 、百度以及雅虎等 基于位置感知的w e b 文本搜索技术研究 已经开发出了了面向商业信息检索的本地化搜索应用，例如说搜索某个区域的餐馆、景 点和公司等。他们主要是通过将黄页等商业目录附属到地图中的位置信息中实现【2 8 - 3 0 l 。 g o o g l em a p g o o g l em a p 是最突出的一个地理搜索引擎的原型。但是，看起主要是通过搜索地理 信息系统，而相关的信息主要是通过附加属性信息添加进去的，而不是直接去搜索互联 网的。用户界面如图1 1 ， 图1 1g o o g l em a p f i g 1 1g o o g l em a p y a h o ol o c a l y a h o o ! l o c a l 将集成该公司的搜索技术和“y e l l o wp a g e s 、地图信息以及第三方内 容。该应用提高了用户要了解信息对象地区的搜索结果的精度、综合性以及便利性，并 将提供最新的信息。只需输入地区企业所属的城市、地址或者行业等便可方便地查到该 企业。其访问地址为：页面如图1 2 ，但是该应用只适合美国。 第1 章绪论 b a i d u 身边 图1 2y a h o ol o c a l f i g 1 2y a h o ol o c a l “百度身边”借助了百度搜索技术，与搜索引擎结合得更加紧密，并且整合了百度旗 下的地图、无线等资源优势。这意味着自诞生丌始，百度身边就直接定位于“l b s 生活 领域”。b a i d u 身边是一个刚刚开发出来的地理信息和位置相关的美食、购物、娱乐等商 家的商业目录信息整个的w e b 应用。百度身边导航栏显示围绕美食、购物、休闲娱乐、 酒店、健身、旅游、便民等领域。集合百度地图，显示相关信息的位置。允许用户添加 相关信息。百度身边首页最大的亮点是提供两个搜索框任意切换，即用户可选择商户信 息搜索，或地理信息搜索。两个搜索框代表着目前通行的两种生活信息搜索模式，前者 是先找服务，再看位置；后者则是先锁定区域，再筛选服务。其访问地址为： h t t p ：s b a i d u c o m ，用户界面如图1 - 3 所示。 基于位置感知的w e b 文本搜索技术研究 图1 3 百度身边 f i g 1 3b a i d us i d e s o c i a l v e n t s s o c i a l v e n t s 目前处于b e t a 测试阶段，基于谷歌地图，有效地聚合、整理了各类活动 信息，通过简单的、有趣的方式呈现给用户，其目前专注于美国本土的各类活动( e v e n t s ) 。 s o c i a l v e n t s 首先是一个搜索引擎，其所提供的搜索方式包括活动所在城市、日期、活动 类别( 如音乐会、电影、体育比赛等) ，然后搜索你所需要找寻的活动信息【3 1 】。此外， s o c i a l v e n t s 网站还提供活动订阅( e v e n t sf e e d ) 服务，用户可订阅特定地点、类型的活 动，这样让自己能在第一时间获知有什么活动。其访问地址为： h t t p ：w w w s o c i a l v e n t s c o m ，用户的入口如1 4 图所示。 第1 章绪论 缓敷童乏纛如五色磊幺幺缓五五麓盔珑碰盔线箍兹缓篮垅貔纽z 赫赫蓝磕碰绷磁毙磁如如斑毖缓毖缱线施醴物碰跷缓磊毖纥簦兹纪缓勉籀 糍磊缸毖毪苏燃描籀毖豹篷篮蒜珑藏盔么盔磊缓裁缝铣鲢巍碰缴菇i o 誊蠲 主件d 曩塌( e )直( d 历史( 书签：工 僭勋( h ) 国 e 毙，h脚计计w w 舯也h 粥，w 固：- ，l ， l i n u x) w a 一强a 口d b a m 删坤k 论复话曹穰嚼一舢州抽h r 啦n 口饰曲* b 阿一? j m 即】洲s p t 冀岱o t e t q = o 洲i u e嚣m hd 鲥e 细州。乜 ” 0l e s j 鹰 中山厂硒酱j 地亭市坶 0 拿譬暑舟j p 百，p 一 知门 e n ts o c 日l j 9 同曩 德：封十|! ，面氍 ，一直岳吧4 坩 2 0 1 1 年2 “ 圈蕊骚鳓瞒暖强暖嚣鞠豳霹鼹礤鞠嬲霸豫礴鼎髓强篷盈翻嬲翰麓鄹嬲灞g 嫩两，盈e 强弱豳殛稻孺髋爨圈i 翠勰艘礴嗽潮譬j 蕊曩ii ：曩嚣珏工疆覆曩正x ： 既渗覆戮缓缀绷黪爱缀嬲；鹈搿彩殇搿鬻甏繇缓筏簦i 缄戳锚m 浚缴激糍潞僦魏霸罐黜黝籍黝畿搿鞠1 3 残融虢弘i 燃强貔驰翰翰蕴猫蕊泐乍二”一髯，。j ，翻城蕴 隧警缫缫篓爱鬓覆霪瀚二。 一 ：二r。二二。：鍪鍪蚕豳目目黜 *zeh目z女gl*h-m_h_日_目一一o一日_日墨i m x g # “m 目猫* _ 1 。；j0 0 ：，j ，- ， f ：二。 露i , t 2 三鬻e0“袖嘶氍c艺ji00how 一划 e r “ ：1 e - w i 蛳：t u 3 d 却“3 f 髓1 7p h ? 0 互氯 船础s e o e 5 洲o n 三。正璺 潞，：一，：姐孓薰恚耋整三 j j 芝爹_ 憝囊麓蛩二二 ：2 翘c m l n 口s e 9 _ et m s e4 m a n c n 0 礤：，”二甏! 夕毒，：，鼍； * 4p a m e r 帅w mm tw e 虻h 封i 糊 f u n d i n c 豳鞫醯荔越器蕊盈芦黑蕊鞠p 圈i 溺缓强缝溯璐戮鼗磊勰麟黝缫怒隧麴豳鞫踺缀嘲 l 正在从n 1u o 。，t i ) 6 ：。一1 幡王象届 为了实现一个具有通用性的支持中文的位置相关的w e b 文本搜索引擎模型，必须将 现有的互联网上的w e b 文本信息和w e b 文本中的地理位置信息有效地整合，因此本文 研究课题必须解决一下难点： ( 1 ) 研究设计一种支持中文的抽取w e b 文本所描述对象的地址的方案，其主要考 虑的因数有位置相关性、地理位置的抽取和消除地名歧义； ( 2 ) 构造一种新的索引格式能包含一个对象所处的地址的地理空间信息和w e b 文 本信息，主要考虑因数有查询效率； ( 3 ) 提出一种能有效地进行普通关键词匹配同时能进行位置相关性的匹配，以保证 最优的检索策略； 基于位置感知的w e b 文本搜索技术研究 ( 4 ) 检索结果排序算法的改进，应该综合考虑将位置相关性排序和w e b 文本内容 相关性排序整合。 1 4 论文结构安排 本文一共分为五章，具体章节安排如下所示： 第1 章绪论，主要是介绍了本文的研究课题的背景及意义、基于位置相关的w e b 文本搜索的国内外研究现状、论文研究课题所涉及的主要问题以及论文的章节安排。 第2 章w e b 信息检索技术，分别介绍了本文研究的支持中文的位置相关的w e b 文 本搜索所涉及的两方面的技术，即常规w e b 文本的内容信息检索技术和w e b 文本中的 位置信息检索。 第3 章支持中文的位置相关的w e b 文本搜索，首先阐述了“支持中文的位置相关 的w e b 文本搜索”所面临的关键问题，然后分节描述了如何解决w e b 文本中地理信息 抽取、构造文本信息和地理信息混索引、位置相关查询、查询结果的排序关键问题。 第4 章一种支持中文的位置相关的w e b 文本搜索的模型设计与实现，本章开始先 提出了一种具体模型的结构，接着讲解了结构中地理信息抽取模块、混合索引模块、位 置相关查询模块以及结果排序模块的关键问题和具体解决方案，最后结合实例给出了实 验参数和实验结果。 第5 章总结与展望，总结了本文的主要研究工作，最后提出了本文研究的课题的有 待进一步完善和继续深入之处。 第2 章w e b 信息检索技术 第2 章w e b 信息检索技术 本章主要介绍了文本研究课题主要涉及的两种关键技术w e b 文本的内柔信息检索技 和w e b 文本中的位置信息检索技术。首先讲解了搜索引擎的原理和结构及其页面抓 模块、页面分析和索引模块、信息检索模块和结果排序算法，然后介绍了w e b 文本 的位置信息检索所涉及的关键技术，其中包括地理位置辞典库、位置信息抽取、文本 息和地理信息的混合索引、位置信息的匹配与计算以及查询结果的排序。 1w e b 搜索引擎技术 1 1w e b 搜索引擎的工作原理与结构 i n t e m e t 是一个广阔的信息海洋，漫游其问而不迷失那是相当困难的。如何迅速精 地在互联网上检索到自己需求的信息已变得越来越重要。搜索引擎( s e a r c he n g i n e ) 一种方便检索互联网上信息的工具，在浩瀚的互联网的资源中，它能帮助你迅速而准 地检索到所需要的资源【1 1 【3 4 。6 1 。 搜索引擎( s e a r c he n g i n e ) 是指根据一定的策略、运用特定的计算机程序从互联网上搜 w e b 页面，在对这些w e b 页面分析、处理和组织后形成一个资源库，并基于此资源 为用户提供检索服务，最后将用户检索相关的信息返回给用户的复杂系统1 3 7 , 3 8 l 。由此 见，搜索引擎一般的工作原理是：首先对互联网上的网页进行搜集，然后对搜集来的 页进行预处理，建立网页索引库，实时响应用户的查询请求，并对查找到的结果按某 则进行排序后返回给用户1 3 9 , 4 0 l 。如图2 1 所示，是一个典型的搜索引擎结构图。 8 基于位置感知的w e b 文本搜索技术研究 系f jj ，年 图2 1 搜索引擎结构图 f i g 2 1s e a r c he n g i n es t r u c t u r e 2 1 2w e b 页面抓取 网络爬虫( w e bc r a w l e r ) ，又称为网络蜘蛛( w e bs p i d e r ) 或网络机器人( w e br o b o t ) ， 是一个自动搜集互联网页面信息的计算机程序或自动化脚本，同时它也能定期地是搜索 引擎的重要组成部分【4 3 1 。网络爬虫的工作原理是从一个包含一定数量u r l 的种子集 开始运行，它首先将种子集中的u r l 全部加入到一个有序的等待抓取的队列里，按照 一定的规则从中取出u r l 并抓取、处理所指向的页面，分析页面内容，提取新的u r l 并存储到待爬行u r l 队列中，如此重复上面的过程，直到u r l 队列为空或满足某个爬 行终止条件，从而遍历整个w e b l l o l 。该过程称为网络爬行( w e bc r a w l i n g ) 。 通用网络爬虫的结构大致可以分为页面抓取模块、页面分析模块、链接过滤模块、 页面数据库、u r l 队列、初始u r l 集几个部分【删，其详细的体系结构如图2 2 所示。 第2 章w e b 信息检索技术 图2 2 网络爬虫体系结构 f i g 2 2w e bc r a w l e rs y s t e ms t r u c t u r e 为提高工作效率，网络爬虫会采取常用的爬行策略有1 4 5 】：深度优先、广度优先。 1 ) 深度优先策略：其基本方法是按照深度由低到高的顺序，依次访问下一级网页中 链接，直到没有下一级为止。爬虫在抓取完一个分支后返回到上一节点进一步抓取其 链接。当所有链接抓取完后，爬行任务正常结束。从抓取过程可以看出，这种策略能 合适地应用于垂直搜索和站内搜索，因为如果爬行页面内容层次较深时容易造成资源 巨大浪费； 2 ) 广度优先策略：这种策略是按照网页内容中链接目录层次一层一层来爬行页面， 于较浅层次的页面会先被爬行。当一层次中的所有页面完全爬行完毕后，爬虫再深入 一层继续爬行。此策略能够很好地控制爬虫的爬行深度，避免死循环，实现方便，无 存储大量中间节点，不足之处在于需较长时间才能爬行到目录层次较深的页面。 1 3 页面分析与索引 在浩瀚如烟的互联网中，网络爬虫( c r a w l e r ) 或者网络蜘蛛( s p i d e r ) 所采集的页 肯定是不计其数，据统计，到2 0 1 1 年3 月为止，w w w 上的w e b 页面已经达到了1 3 5 8 1 4 6 1 。所以面对如此庞大的数据，我们不可能用传统的数据库区存储，我们需要一种方 对w e b 页面进行预处理，并且建立一种新的数据结构来存储这些数据，以便满足搜 索引擎的快速响应的能力，这种数据结构就是索引【铜。 基于位置感知的w e b 文本搜索技术研究 网络爬虫( c r a w l e r ) 或者网络蜘蛛( s p i d e r ) 所采集w e b 页面后，我们便要为其创 建索引，一般来说，创建索引可以分为三步：w e b 页面的内容信息抽取、分词以及建立 标引库。互联网上大部分信息都是以h t m l 格式存在的，对于索引来说，只处理文本 信息【钥。因此需要把网页中文本内容提取出来，过滤掉一些脚本标示符和一些无用的广 告信息，同时记录文本的版面格式信息【1 4 】。分词是搜索引擎中重要部分，就是借助字典 库对w e b 页面内的词进行识别。同时中文分词更是中文搜索引擎所面临的难点，英文 有空格作为分隔符而中文没有，所以不容分隔容易导致语义的丢失。目前中文分词方法 都是借助中文词典库，分词时根据词典进行匹配，达到分词目的，词典的好坏直接导致 了分词的效果好坏。分词后就是对这些关键词建立标引库，这是数据索引中最复杂的步 骤【4 羽。通常要创建两种标引：文档与关键词标引。文档标引为每个w e b 页面分配一个 唯一的d o c u m e n t l d 号，然后将出现在d o c u m e n t l d 标引这个w e b 页面中出现过的词分 配给i 性一的w o r d l d ，同时为每个w o r d l d 词标记出现的次数、位置、大小写格式等，这 样就构成d o c u m e n t l d 对应w o r d l d 的对应列表；关键词标引实际上是文档标引过程的逆 向过程，根据w o r d l d 标引出这个词出现在那些网页( 用w o r d l d 表示) ，出现在每个网页 的次数、位置、大小写格式等，形成w o r d l d 对应d o c u m e n t l d 的列表。 事实上，常用的索引方式有三种，分别是倒排索引，后缀数组索引和签名文件索引。 倒排索引已经被当前大多数信息系统所广泛使用【4 9 5 0 1 。倒排索引( i n v e r t e di n d e x ) ， 索引对象是文档或者文档集合中的单词等，用来存储这些单词在一个文档或者一组文档 中的存储位黄，是对文档或者文档集合的一种最常用的索引机制。在倒排索引中，关键 字的数量并非随着文本内容的增长也线性增长。这是因为无论多大数量的文本数据库， 总能够规范出一个关键字表。这种关键字表受到实际语言因素的限制，它的增长率在文 本数据库达到一定规模后可以忽略不计。有人做过统计，对于1 g b 的文本信息来说，词 汇表( 关键字表) 的大小在5 m b 左右。倒排索引特别适合于人们的思维习惯，同时它对 关键词的检索也非常有效。后缀数组索引在短语查询是，具有较快的速度，知识构造和 维护这样的索引非常困难。签名文件索引的方式已经基本被淘汰，更多人转而使用倒排 索引。 第2 章w e b 信息检索技术 1 4 检索与排序 检索模块的工作流程是根据用户查询条件返回最相关的文档的过程，首先接受用户 入搜索条件，查询分析器对搜索条件根据词典库进行分词处理得到相应的关键字，同 利用关键字标引库转化成w o r d l d ，然后利用w o r d l d 在标引库中得到d o c u m e n t l d 列 ，对d o c u m e n t l d 列表进行扫描匹配w o r d l d ，提取满足条件的w e b 页面，然后计算 e b 页面和关键字的相关性，根据相关性的程度排序返回前n 篇w e b 页面( n 为搜索 擎返回给用户一页包含的记录数) 返回给用户【5 1 1 。如果用户查看结果的第m 页，则重 查询一次，将结果的第( m 1 ) 宰n + 1 到m * n 返回给用户，整个查询过程如图2 3 所示。 图2 3 检索模块工作流程 f i g 2 3r e t r i e v a lm o d u l ew o r k i n gp r o c e s s 其中结果排序主要是依据相关性排序的，现在的搜索引擎里使用的相关性计算方法 主要有两种：页面级另j j ( p a g e r a n k ) 和超链接分析。页面级另1 ( p a g e r a n k ) 基本思想：如果 网页t 存在一个指向网页a 的连接，则表明t 的所有者认为a 比较重要，从而把t 的一 部分重要性得分赋予a 。这个重要性得分值为：p r ( t ) c ( t ) ；其中p r ( t ) 为t 的p a g e r a n k 值，c ( t ) 为t 的出链数，则a 的p a g e r a n k 值为一系列类似于t 的页面重要性得分值的 基于位置感知的w e b 文本搜索技术研究 累加【5 2 1 。超链分析的基本原理是：在某次搜索的所有结果中，被其他网页用超链指向得 越多的网页，其价值就越高，就越应该在结果排序中排到前面。 2 2 地理信息检索 2 2 1 地理信息系统的概念 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) 有时又称为“地学信息系统”或“资源 与环境信息系统”。它是一种特定的十分重要的空问信息系统。它是在计算机硬、软件 系统支持下，对整个或部分地球表层( 包括大气层) 空间中的有关地理分布数据进行采 集、储存、管理、运算、分析、显示和描述的技术系统。 与一般的管理信息系统相比，地理信息系统具有以下特征：( 1 ) 地理信息系统在分 析处理问题中使用了空间数据与属性数据，并通过数据库管理系统将两者联系在一起共 同管理、分析和应用，从而提供了认识地理现象的一种新的思维方法；而管理信息系统 则只有属性数据库的管理，即使存储了图形往往以文件形式等机械形式存储，不能进行 有关空间数据的操作，如空间查询、检索、相邻分析等，更无法进行复杂的空问分析。 ( 2 ) 地理信息系统强调空间分析，通过利用空间解析式模型来分析空间数据，地理信 息系统的成功应用依赖于空间分析模型的研究与设计。 2 2 1 地理信息系统的关键技术 由于空间数据具有多时空性、多元性、多时空性、多语义性等特点以及存在关系模 型、层次模型、网状模型多种组织模型和栅格、矢量等多种数据结构，这导致了在进行 数据处理和分析时，面临着多源空间数据的集成融合、无缝基础地理数据库管理和数据 与互操作问题。 ( 1 ) 多源空间数据的集成融合技术 当前，集成多源数据的方法主要以下三种：1 ) 统一数据格式方式：利用数据格式转 换软件将其不同的数据格式统一转换成标准的格式，然后导入到当前系统中的数据库 中，这是当前地理信息系统数据集成的主要方法。2 ) 数据互操作方式：这种方式是在 分布式系统和异构数据库环境下，遵循权威的地理信息系统组织制定的数据共享规范， 实现对数据进行分析和共享等操作。3 ) 直接数据访问方式：在一个g i s 软件中实现对 第2 章w e b 信息检索技术 其它数据格式的直接访问、存取以及分析，不需要使用者拥有该数据格式的宿主软件和 此软件的运行，真正实现格式无关数据集成。 ( 2 ) 无缝地理数据库管理技术 如何组织和管理大规模的、不同比例尺的无缝地理数据是构建地理信息系统的一个 难点。无缝地理数据就是说明数据不再是单一的或者被硬性割裂的图幅，而是任意广阔 的地理区域。由于受到计算机软硬件的限制，在实际的实现中，地理数据将被分块存储 于分布式的数据库中，数据库中存储相应的图块拼接信息。物理上地理数据是有缝隙的， 但是可以利用地理数据库存储的图块的相连接信息及相应的拼接方法，保证地理数据在 的无缝性。 ( 3 ) 数据库与互操作技术 由于地理空间数据库和实现空间数据的转换与应用涉及多种数据源，这些数据源往 往采用不同的软件和数据格式、编码系统。为此，必须研究建立基础地理数据的自动转 换标准和相应的软件，诸如基础地理数据互操作协议、基础地理数据共享平台，或通过 软件实现异构、异库、异软件系统下基础地理数据的互操作，方便数据的交换和应用。 2 3 基于位置感知的w e b 文本搜索 2 3 1 地理位置信息的获取 位置信息的获取包括三个方面：抽取w e b 页面的位置信息、抽取用户查询条件中的 位置信息和获取用户位置信息。本论文主要涉及有抽取w e b 页面的位置信息、抽取用