（计算机软件与理论专业论文）基于位置的网络搜索引擎排序技术研究.pdf

河海大学硕士研究生毕业论文基于位置的网络搜索引擎排序技术研究 摘要 万维网是一个包含丰富资源的数据库，如何有效地从其中获取所需信息是网 络数据挖掘的一个关键问题。从1 9 9 0 年丌始，搜索引擎逐渐发展称为人们在互联 网上搜索资源的主要方式。传统搜索引擎的工作机制基于关键字匹配，它们通常 利用网页文本的内容和网络链接结构来判断网页与搜索串的相似程度。但随着越 来越多的地方性资源和服务出现在因特网上，传统搜索引擎无法合理地处理包含 位置信息的搜索串和返回令人满意的结果，其原因在于以下三点：( 1 ) 将地理 位置当作普通关键字进行处理；( 2 ) 考虑的是网页在全球范围的受欢迎程度而 不是在地方的流行度；( 3 ) 没有考虑网络资源的地理范围。因此，建立专门处 理包含地理位置信息的搜索引擎是必需的。 本文在分析了基于位置的搜索引擎发展现状和相关关键技术的基础上，对基 于位置的排序技术进行了研究。本文的主要研究内容和贡献有以下几个方面： 1 提出了一种基于地方流行度的排序思想和相应的排序模型l p r m 。该排序 模型使用了g e o w e i g h t 来计算网页中地理位置的权重，它的特点在于综合考虑了 地理位置出现的次数、频率和区域；同时本文改进了p o w e r 和s p r e a d 公式，以突 出入链在排序中的重要性。 2 根据提出的排序模型，本文给出了三种排序算法c g r 、b g r 和h g r 。c g r 仅 仅考虑了网页内容中出现的地理位置，b g r 仅仅考虑了入链网页中出现的地理位 置，h g r 综合考虑了内容和入链中出现的地理位置。通过它们之间的对比可以看 出入链的地理位置和质量能反映网页的地方流行度。 3 设计和实现了一个基于位置的排序系统g r s ，通过实验对提出的三种算法 进行了评估，并详细地分析了实验结果。g r s 有两个特点：( 1 ) 与大多数相关研 究采用某一特定领域的网页作为数据集不同的是，g r s 并没有对网页的内容做出 任何限制；( 2 ) 大多数相关研究都需要部分手动参与，而g r s 会自动地将地理位 置与网页和超链接相关联，计算出一个网页的地理范围。实验主要评估和分析了 以下几个方面：地理标注结果、排序结果的精确度、根集合大小对排序的影响、 搜索串扩展效果。 关键词：网络搜索、排序、基于位置的搜索引擎 河海大学硕士研究生毕业论文 基于位置的网络搜索引擎排序技术研究 a b s t r a c t w w wi sah u g ed a t a b a s ew h i c hc o n t a i n sa b u n d a n tr e s o u r c e s i nw e bd a t a m i n i n g ，h o wt or e t r i e v en e e d e di n f o n n a t i o n 厅o mw w w i sac r u c i a lp r o b l e m s i n c e 19 9 0 ，s e a r c he n 西n e sh a v eb e c o m et h ep r i m a r yw a yt os e a r c hr e s o u r c e si nt h ei n t e m e t g e n e 豫ls e a r c he n g i n e su s eak e y w o r d s - b a s e dw a yt od e a lw i t hq u e r i e sa n dw e b p a g e s ， t h e ye x p l o i tw e b p a g e sc o n t e n ta n dl i m ( s t m c t u r et oj u d g et h es i m i l 撕t yb e t w e e n w e b p a g e sa n dq u e r i e s b mw i t hm o r ea n dm o r el o c a lr e s o u r c e sa n ds e r v i c e sa p p e a ri n t h ei n t e m e t ，g e n e r a ls e a r c he n g i n e sc a nn o td e a lw i t hl o c a t i o n - b a s e dq u e r i e sp r o p e r l y a n dr e t u ms a t i s f a c t o 眄r e s u l t sb e c a u s eo ft h ef o l l o w i n gr e a s o n s ：( 1 ) t r e a tl o c a t i o n sa s g e n e r a lk e y w o r d s ；( 2 ) c o n s i d e rt h eg l o b a lp o p u l 撕t yo faw e b p a g er a t h e rm a nl o c a l p o p u l a r i t y ；( 3 ) r e g a r d l e s so fg e o g r a p h i cs c o p eo fw e br e s o u r c e s t h e r e f o r e ， i ti s n e c e s s a r yt oe s t a b l i s hal o c a t i o n - b a s e ds e a r c he n g i n e b a s e do na n a l y s i so fc u r r e md e v e l o p m e n to fl o ca _ t i o n b a s e ds e a r c he n g i n e sa n d r e l e v a n tk e yt e c h n o l o g i e s ，t h i sp 印e rf o c u s e so nl o c a t i o n - b a s e dr a n k i n g i nb r i e et h e m a i o rr e s e a r c hs c o p ea n dc o n t r i b u t i o n so ft h i sp a p e ra r el i s t e da sf o l l o w i n g ： 1 t h i sp 印e rp r o p o s e sar a n k i n gm o d e ll p r mb a s e do nl o c a lp o p u l a r i t y t h e m o d e lu s e sg e o - w e i g h t ，w h i c hc o n s i d e r sc o m p r e h e n s i v e l yt i m e s 、自e q u e n c va 1 1 da r e a o fl o c a t i o n sa p p e a r e di nw e b p a g e s ，t oc a l c u l a t et h ew e i g h to fe v e r yl o c a t i o ni na w e b p a g e a tt h es a m et i m e ， p o w e ra n ds p r e a df o 肌u l aa r ea l s oi m p r o v e dt o e m p h a s i z em o r ei m p o r t a n c eo nb a c k l i m ( s 2 a c c o r d i n gt op r o p o s e dr a n k i n gm o d e l ，t h i sp a p e ra l s og i v e st h r e ea l g o r i t h m s ： c g r 、b g ra n dh g r c g ro n l yc o n s i d e r sl o c a t i o n sa p p e a r e di nw e b p a g e sc o n t e n t ， b g ro n l yc o n s i d e r sl o c a t i o n sa p p e a r e di n b a c k 1 i n k s ，h g rc o n s i d e r sl o c a t i o n s 印p e a r e di nb o t h 、v e b p a g e sc o m e n ta n db a c k - l i n k s c o m p 撕s o no ft h e s ea l g o r i t 王l s i n d i c a t e st h a tl o c a t i o n sa n dq u a l i 哆o fb a c k l i n k sc a nr e n e c tt h el o c a lp o p u l 撕t vo fa w e b p a g e 3 n i sp 印e rd e s i g n sa n da c c o m p l i s h e sa1 0 c a t i o n - b a s e dr a n k i n gs y s t e mg r s ， w h i c hi su s e df o re v a l u a t ea b o v e - m e n t i o n e dt l l r e ea l g o r i t h m s i na d d i t i o n ，t h i sp a p e r g i v e sa l ld e t a i l e da n a l y s i so fe x p e r i m e n t a lr e s u l t s g r sh a s 觚of e a t u r e s ：( 1 ) a p a n 舶mm o s tr e l e v a mr e s e a r c ht h a tu s i n gs e l e c t e dw e b p a g e sa sd a t a s e t ，g r sd o e s n t2 i v e r e s t r i c t i o n so nw e b p a g e sc o n t e m ；( 2 ) m o s to ft h er e l e v a n ts t u d i e sa r en e e d e dt o p a n i c i p a t ei nm a i l u a l ，b u tg r sc a na u t o m a t i c a l l ya s s o c i a t ew e b p a g e sa n dh y p e r l i n k s w i t hl o c a t i o n s ，a n df i m l l yc a l c u l a t et h eg e o g m p h i c s c o p eo faw e b p a g e t h e e x p e r i m e n tm a i n l ye v a l u a t e sa n da n a l y z e ss e v e r a la s p e c t s ：g e o t a g g i n gr e s u l t 、r a n k i n g p r e c i s i o n 、 t h ee f i e c to fr o o ts e t ss i z ea n dq u e r ye x p a n s i o n k e yw o r d s ：w e bs e a r c h 、r a n k i n g 、l o c a t i o n b a s e dw e bs e a r c h 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 学位论文使用授权说明 2 0 0 8 年5 月2 4 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：2 0 0 8 年5 月2 4 日 河海大学硕十研究生毕业论文 基于位置的网络搜索引擎排序技术研究 1 1 研究背景 第一章绪论 从1 9 9 0 年丌始，搜索引擎逐渐发展成人们在互联网上搜索资源的主要方式，大 多数搜索引擎通过基于关键字( k e y w o r d - b a s e d ) 的搜索方式来获取相关网页。据估 计每天大约有上亿条搜索串被提交给搜索引擎进行处理。以g o o g l e 为例，s u l l i v a i l 在2 0 0 6 年的调查显示g o o g l e 每天大约需要处理超过9 1 0 0 万次搜索【l j 。 对用户来说搜索引擎最大的两个特点就是高召回率和低精确性。虽然搜索引擎 能够覆盖相当大一部分网络资源，但却缺乏有效的手段来对结果进行排序并呈现在 用户面前。搜索串通常并不会很长，根据s p i n l ( & j a n s e n 在2 0 0 4 年所做的调查平均 长度只有2 4 个单词【2 】，但搜索引擎却返回了过多的结果。工业界和学术界都提出 了许多不同的索引和排序模型，试图只找出最相关的文档并以恰当的方式排序，但 结果仍然不尽如人意。根据s u l l i v a j l 在2 0 0 0 年的报告，4 4 的用户觉得搜索结果并 不理想。显然我们需要改进现有的技术来更有效地索引和表现网络资源1 3 j 。 此外，对于搜索引擎的用户来说，不同的人也有着不同的兴趣和需要。这些需 要可能包括商业、娱乐、科学或交流等方面。因此，在网络上开始出现一些专用的 搜索引擎，它们通常被用来搜索特定的网络资源，比如图片、音乐和电影等。 基于位置的搜索引擎( 也称作地理搜索引擎) 就是一种专用搜索引擎，近来已 经受到了学术界和工业界的广泛关注。从本质上，互联网发展并开始流行就是因为 它能够跨越地域的限制获取资源。但是网络上的许多服务和设施都涉及到具体的位 置，比如人们可以从网络上搜索位于特定区域的饭店、宾馆和公共设施等。通过基 于位置的搜索引擎，用户得到的结果都是与地理位置相关并按照地理位置来排序的。 然而对于一般的搜索引擎来说，其基于关键字的检索方式在面对与位置相关的搜索 时表现得十分不尽如人意。举例来说，对于“南京宾馆”这样一个搜索串，我们的 目的是找到位于南京市的宾馆，但我们却有可能得到一些不相关的结果，比如上海 市南京西路上的宾馆，其原因有多个方面：比如搜索引擎并没有考虑到网络资源的 地理范围等。因此，面对与位置相关的搜r 索，建立专门的地理搜索引擎是必须的。 1 2 研究动机与现状 根据包括s a l l d e r s o n & k o h l e 和s p i n k & j a l l s e n 5 1 在内的多项研究显示，在搜索 引擎上执行的搜索串中有超过2 0 包含地理空间信息并且涉及地球上一个具体的位 置。同时，包括移动搜索、g p s 导航等新一代的基于网络的服务都致力于将数字信 河海大学硕士研究生毕业论文基于位置的网络搜索引擎排序技术研究 息与地理位置信息进行了融合。 正是由于越来越多的这种对地理空间信息的需求，以及传统搜索引擎在处理基 于位置搜索时的种种缺点，主要的搜索引擎公司比如g o o g l e 等都已经在开发基于位 置的搜索引擎，目前在网络上也已经出现了一些功能并不完善的地理搜索引擎。有 些搜索引擎能将你的搜索范围限制到一个国家或者一个区域，比如n i n e m s n l 就是 m s n 搜索引擎提供的一个面向澳大利亚的本地搜索接口。当用户登陆n i n e m s n 进 行搜索的时候，会发现域名以“a u ”结尾的网页将会被赋予更高的优先级并出现在 搜索结果中靠前的位置。同样地，g o o g l e 和y 址o o 也都有相应的网页来提供类似的 搜索服务。这种以域名来区分网页的方式是一种最简单的基于位置的搜索模型，它 只能实现国家层次上的划分，并且也不能区分含有位置信息的搜索串与普通搜索串， 因此并不是十分有用。 g o o g l el o c a l 2 是一个正在发展中的基于位置的搜索引擎，它能搜索美国、加拿 大等国家的本地商业信息。g o o g l el o c a l 提供了两个搜索框，其中一个用来输入所 要搜索的商业信息( 比如“h o t e l ) ，而另一个则用来输入所要搜索的地理位置( 比 如“b r i s b a n e ”) ，这个位置也称为参考点，因此当用户提交搜索串时g o o g l el o c a l 将会寻找与这个地理位置相关的网页并根据其相对参考点的距离对返回结果进行排 序，同时一个电子地图也将被显示以供用户浏览和选择结果。与g o o g l el o c a l 类似 的提供基于位置搜索服务的还包括m o ol o c a l 3 和m e t a c a n a 4 等。 对于学术界来说，目前并没有很多已被发表的文献是关于基于位置的网络搜索 这个领域，并且大多数研究都集中于对网页的地理标注和如何从网页中提取出位置 信息。到目前为之，并没有一个基于位置的搜索引擎能搜索全球范围内的网页，现 有的例子也仅仅局限于特定的国家或者城市。以往的一些研究也大都没有完成，比 如n o n h e ml i g h t 5 和s p i r i t 6 就是两个未完成的项目。可以说，设计这样的一个搜 索引擎必将面临诸多困难，包括位置名可能存在的重名现象、多种多样的位置名命 名方式、一个网页可能与多个位置相联系等。 1 3 研究的主要内容和贡献 1 3 1 研究的主要内容 对基于位置的搜索引擎的研究包含多个方面的内容，比如位置名的辨析、索引 lh t t d ：n i n e m s n c o m a t l 2h 廿p ：l o c a l g o o g l e c o m 3h n p ：l o c a l y a h o o c o m 4h t n ，：w ww m e t a c a r t a c o l l l 5h n p ：w w 、v n o n h e m l i g h t c o m 6h t t p ：w w w g e 0 s p i r i t o 叫 2 河海大学硕士研究生毕业论文基于位置的网络搜索引擎排序技术研究 的建立、结果的呈现方式、排序技术等。本文将重点放在排序技术上，并结合排序 考虑与其相关的其他方面。研究主要内容如下： 1 结合目前工业界与学术界的成果，研究基于位置的搜索引擎的发展现状、核 心技术和需要解决的关键问题。 2 对传统搜索引擎的排序技术进行研究，分析它们在面对与位置相关的搜索时 的不足，并提出自己的解决思想。 3 研究如何从网页中识别、抽取地理位置和标注与地理位置相关的信息，以及 如何准确地计算网络资源的地理位置。 4 根据提出的解决思想改进现有的排序模型的不足，并提出自己的排序模型和 算法。 5 设计一个基于位置的排序系统进行实验，从精确度等角度评估所提出的排序 模型和算法。 1 3 2 论文的主要贡献 本文的贡献主要有以下三个方面： 1 提出以地方流行度进行网页排序，和以入链来计算地方流行度的思想。 传统搜索引擎考虑的是网页在全球范围内的受欢迎程度，但本文认为在基于 位置的网络搜索中应该考虑的是网页在地方的流行度。在衡量地方流行度方面，本 文认为入链的质量和分布能反映出网络资源的地方的流行度，并通过入链进行权重 传递的方式来计算地方流行度的得分。 2 在基于地方流行度的排序思想基础之上，提出了一个基于地方流行度的排序 模型l p l w 。 l p i 洲是一种以入链分析为主，结合内容分析的自动的排序模型，它主要有 三个方面的特点：( 1 ) 提出g e o w e i g h t 来计算网页中地理位置的权重，其不仅考虑 了地理位置的出现次数和频率，还考虑了地理位置的在网页中的出现区域；( 2 ) 将 d i n g 提出的p o w e r 和s p r e a d 进行分类并改进了计算公式；( 3 ) 利用改进的p o w e r 和s p r e a d 提出了c g r 、b g r 和h g r 三种排序算法。 3 根据提出的排序模型实现了一个基于位置的排序系统g r s ，并通过实验对排 序结果进行了多角度的详细分析，验证了基于地方流行度的排序模型l p l 洲的有效 性。 g r s 有两个特点：( 1 ) 与大多数相关研究采用某一特定领域的网页作为数 据集不同的是，g r s 并没有选用特殊的数据集作为实验基础；( 2 ) 许多相关研究都 需要部分手工参与，但g r s 会自动地将位置与网页和超链接相关联，计算出一个网 页的地理范围。此外，我们定义了实验的评价标准，并采用实际数据集对系统进行 了评估。实验结果说明了b g r 排序算法能有效地提高搜索质量。 河海大学硕+ 研究生毕业论文基于位置的网络搜索引擎排序技术研究 1 4 论文的组织结构 本文内容的章节安排如下： 第一章绪论。本章首先引出基于位置的网络搜索的背景，并结合学术界和工业 界的情况对研究现状进行了介绍；然后概括了本文主要的研究内容和创新点；最后 给出了整篇文章的组织结构。 第二章网络搜索与基于位置的网络搜索。本章首先介绍了网络搜索领域的发 展；接着引出了两类特殊的搜索引擎：个性化搜索引擎和专用搜索引擎；最后介绍 了基于位置的搜索引擎及其关键技术。 第三章基于链接分析的网页排序。本章首先介绍了链接分析的概念和应用领 域；然后介绍了采用链接分析的排序技术，并分析了传统链接分析算法的不足；最 后分析了地理范围的重要性及其计算方式。 第四章利用网络资源的地方流行度改进排序模型。本章首先分析了如何考虑网 络资源的地方流行度，提出了一种基于地方流行度的排序模型l p i w 。然后介绍了 l p r m 中地理位置权重衡量方式g e o w 萌g h t 、改进后的p o w e r 和s p r e a d 以及三种排 序算法；最后设计和实现了一个基于位置的排序系统g r s 。 第五章实验与算法评估。本章以g r s 系统为平台，综合评估了之前提出的三 种算法的精确度并给出了详细的分析。 第六章“总结与展望 ，对论文工作进行总结，并指出需进一步完善的地方。 4 河海大学硕士研究生毕业论文基于位置的网络搜索引擎排序技术研究 第二章网络搜索与基于位置的搜索引擎 本章首先介绍了网络搜索的发展以及各个阶段具有代表性的成果，接着讨论了 用于满足用户不同需求的个性化搜索引擎和专用搜索引擎，最后分析了基于位置的 搜索引擎的发展现状、关键技术和所面临的问题。 2 1网络搜索介绍 搜索工具和技术被研究、应用于传统信息获取( i n f o 肌a t i o nr e t r i e v a l ) 领域已 经有很长一段时间。在w 曲信息不断融合、迅速增加的过程中，搜索引擎随之出现。 搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织 和处理，并为用户提供检索服务，从而起到信息导航的目的。觚h i e l 6 j 彳艮可能是 i n t e m e t 上第一个搜索工具，它能通过关键字在文件名所组成的数据集合中进行搜 索。s c h w a r t z 【7 1 的论文指出网络搜索引擎出现在1 9 9 4 年，而根据w a l l l 8 j 网络机器人 和搜索引擎在1 9 9 3 年就已经被建立。早期主要的搜索引擎比如a l t a v i s t a 7 和e x c i t e 8 等使用的是传统信息获取技术，即对网络内容做相应的索引。它们从已经做好索引 的数据集合中获取结果，并根据关键字匹配和相似度来对结果进行排序，最后显示 给用户。但随着网络的迅速发展，数量庞大的网页和不同的文件类型使得传统的技 术越来越力不从心。因此，需要采用新的工具和技术来改进网络搜索的质量。 虽然学术界已经对网页的链接结构进行过研究，但是第一个主要的应用在1 9 9 8 年才开始出现，即g o o g l e 。b n 和p a g e 引入了p a g e r a n k 纠来寻找高质量的网页。 p a g e r a i l l ( 假设在一个特定的领域，越重要的网页通常被引用的次数也会越多。因此 一个网页的质量即p a g e r a n l ( ，可以通过计算该网页有多少反向链接( b a c k 1 i n k ) 和这些反向链接的质量来得出。h i t s 【io 】则是另一个著名的关于网络链接结构的模 型，它的特点是同时考虑网页的入链( b a c k 1 i n k ) 和出链( o u t g o i n g 1 i n k ) 。 g 0 0 9 l e 作为大规模网络搜索引擎的一个原型，很好地利用了网络链接结构。首 先，通过分布式爬虫( d i s t m u t e dc r a w l e r ) g o o g l e 抓取了数量极其庞大的网页形成 了自己的资源库。这一点十分重要，因为分布式程序能在同一时间抓取多个网页， 显然提高了效率。其次，g o o g l e 使用了p a g e r a n l ( 作为自己的网页排序模型并对每 个网页进行打分，高质量的网页将会获得更高的分数并优先显示给用户。这两点主 要因素使得g o o g l e 大获成功。截止2 0 0 4 年，g o o g l e 、m s n 和y 孔o o 作为世界上主 要的几个搜索引擎分别索引了8 1 亿、5 亿和4 2 亿的网页资源。但很明显，索引页 面的多少并不是判断搜索引擎的唯一标准，如何能找出与关键字更相关的高质量网 7h t t p ：、v w w a l t a v i s t a c o n l 8h t t p ：、v w w e x c i t e c o m 河海大学硕十研究生毕业论文基于位置的网络搜索引擎排序技术研究 页并有效地将它们呈现出来也是一个关键因素。 随着网络搜索技术的快速发展，逐渐出现了新的对网络资源的定义和分类。比 如网页分块( p a g es e g m e n t a t i o n ) 技术可以将网页划分成若干子区域广告区、 j 下文区、导航区等，从而程序可以通过识别页面不同区域的重要程度来提高搜索精 度。对h t m l 页面的分块方式通常有两种，一种是d o m 分块( d o ms e 舯e n t a t i o n ) ， 它的做法是利用h t m l 的层次结构来划分；另一种是视觉分块( s u a ls e g m e n t a t i o n ) 即从视觉角度出发识别页面的不同区域，比如微软的v i p s 【l l l 。p a g e r a n k 是基于页 面级的搜索，因此无法判断一条链接在一个页面中的权重。比如，一条由页面中的 重要内容引出的链接，与一条由广告内容引出的链接其重要性应该是有很大差别的， 而p a g e r a n l ( 对此种情况是等同对待的。页面分块技术能标识出每块的重要程度， 使得页面级搜索上升到了区块级搜索的高度，从而提高了搜索的精度。网页分块除 了在链接分析上，能够弥补g 0 0 9 l ep a g e r a i d ( 算法的缺憾外，还能够在图片搜索等 领域获得有效应用。在此之前，图片搜索在页面中抓取一个图片后，还要在页面中 寻找解释这一图片的上下文说明。而有了这个技术则可以大大提升效率，可以直接 在该图片出现的块里取说明文字，并且根据图片来自的块重要性，来决定这个图片 的重要性。此外，在做类似的信息抽取的时候，都可以用到这项技术。 w 曲网按其分布状况可以分为“表层网( s u r f a c ew | e b ) 和“深层网”( d e e pw 曲， 也有称i n v i s i b l ew 曲，h i d d e nw e b ) 。s u r f - a c ew 曲指存储在w 曲空间、由超链接连 接起来的静态网页、文件等资源，一般来说通过超链接就可以访问这些资源。这里 所洗的s 曲c ew 曲是指传统网页搜索引擎可以索引的w 曲，以超链接可以到达的 静态网页为主构成的w e b 。d e e pw 曲指那些存储在网络数据库里、不能通过超链接 访问而需要通过动态网页技术访问的资源集合。网络数据库包括搜索引擎数据库、 在线专业数据库及站内搜索数据库，统称为可搜索数据库( s e a r c h a b l ed a t a b a s e ) 。 因为担心爬行器会陷入巨量动态网页库而浪费网络带宽资源和存储资源，以及目前 的技术还无法发现潜藏在网络数据库中的信息，所以传统搜索引擎，比如g o o g l e 、 百度等网页搜索引擎，一般只索引s u r f a c ew 曲中由超链接可以到达的静态网页、 文件等资源，却不索引或很少索引d e e pw r e b 中的资源。据估计，深层网所包含的 内容至少是表层网所包含内容的4 0 倍，最多则可以达到5 0 0 倍【l 引。总之，网络搜 索经过十几年的发展后还不是非常成熟，未来各个搜索引擎公司将会进一步开发更 多的搜索工具和改善搜索质量来吸引用户。 2 2 个性化搜索引擎与专用搜索引擎 搜索引擎通常拥有广泛的用户群，每个人都有自己的兴趣和不同的关注点。在 这种情况下，没有一个搜索引擎能满足所有用户的需求。传统搜索引擎并不能区别 6 河海大学硕士研究生毕业论文 基于位置的网络搜索引擎排序技术研究 网页内容之间的差异【l3 1 ，因此对不同目的的用户搜索结果却往往是类似的。举例来 说，当用户输入“c o 腩e ”作为搜索串时，有些人可能是想了解咖啡的历史，而有 些人可能是想了解世界上哪罩的咖啡最好喝等等。与传统搜索引擎不同的是，个性 化搜索引擎( p e r s o n a l i z e ds e a r c he n g i n e s ) 能跟踪一个用户的行为并找出一个用户 的兴趣所在。首先，个性化搜索引擎会追踪并记录用户的搜索历史以及用户所打开 的网页，这是为了学习、分析用户所关注的内容。接着，当用户下次再搜索相同的 搜索串时，个性化搜索引擎会根据之前的记录和用户的兴趣排列结果。用户配置文 件同样可以被用来表示用户的兴趣，并在搜索新的搜索串时推断用户的目的。“u 、 y u & m e n g 【1 4 】设计了一个个性化搜索引擎，它使用了有着若干个分类的用户配置文 件。对于每一个分类，都有一组不同权重的关键字，并且这些都是由用户来定义的。 t i b i 锄a 也是一个有着自动学习功能的个性化搜索工具，它首先允许用户手动地对 搜索结果进行排序【l5 。当一定数量的结果被排序后，结果集将被下载和分析处理。 在机器学习过程后，t i b i a n n a 就能根据之前学习的结果动态地对搜索引擎的结果进 行重新排序以满足用户需求。 个性化搜索引擎并没有变得流行起来的原因在于它的特点：需要预定义配置文 件和机器学习过程。预定义和机器学习都是需要花费时间的过程，并且预定义文件 和机器学习的结果很可能不能准确反映用户的需求。与此同时，专用搜索引擎 ( s p e c i a l i z e ds e a r c he n 西n e s ) 作为一种面向特定领域的搜索引擎，得到了越来越广 泛的关注。举例来说，不同的搜索引擎比如g o o g l e 、a l t a v i s t a 和m o o 都开发了可 以搜索图片的专用搜索引擎，m s n 可以搜索电影，p i c s e a r c h 9 、m u s i c s e a r c h l o 和 a u d i o f i n d l l 等也都是专用的多媒体搜索引擎。但与传统搜索引擎相比，专用搜索引 擎还不是非常流行和具有影响力l l 6 。 除了诸如图片、音乐和电影等多媒体搜索引擎外，以语言和地理作为限制条件 的搜索引擎也开始出现。g o o g l e 就为超过1 0 0 个国家开发了区域搜索工具。比如， g o o g l ea u s t r a l i a l 2 能搜索以域名“a u ”结尾的网页，这样搜索出来的结果就仅限于 澳大利亚的网页。尽管能将搜索结果限制在一个区域或者一个国家，但这样的搜索 引擎由于条件太过宽泛，并不能被认为是基于位置的搜索引擎。 2 3 基于位置的搜索引擎 2 3 1 基于位置的网络搜索发展 基于位置的网络搜索技术试图根据位置信息来搜索并排列网页，这些位置信息包 9h n p ：w w w p i c s e a r c h c o m 10h t t p ：w w w m u s i c a r c h c o m 1l h t t p ：a u d i o f i n d c o n l ， l2h n p ：w ww g o o g l e c o m 州 7 河海大学硕士研究生毕业论文基丁位置的网络搜索引擎排序技术研究 括网页的物理位置( 比如i p ) 、网页内容指向的位置( 即网页所面向的用户群体) 和搜索串中包含的位置信息。因此，基于位置的网络搜索需要识别和区分与搜索串 相关的、与用户相关的和与网页相关的各种位置信息。现在，已经有一些学术项目 和商业工程涉及到基于位置的网页搜索这个领域，并取得了一定的成果。g o o g l e l o c a l 和y a h o ol o c a l 就是两个已经存在的基于位置的搜索引擎，它们能搜索位于美 国、英国和加拿大的当地信息服务信息、公共设施信息等。这些搜索引擎通常 使用了具有良好结构的地名词典( w d l s t m c m r e dg a z e t t e e r ) 来赋予网页位置信息。 s o m e w h e r e n e a r b 也是一个面向英国的基于位置的搜索引擎，它允许用户通过地名或 者邮编来搜索洒吧、餐厅和酒店等分类信息。这些分类信息是网页已经定义好的， 因此用户只需选择一样来进行搜索。n o t h e ml i g h t 也提供类似的功能，并能让用户 选择所需要结果的地理范围。不过n o m e ml i 曲t 并不是一个免费服务，它所能搜索 的范围也有限。s p i r j t 是一个研究项目，它利用地理本体设计并实现了一个基于位 置的搜索引擎，其主要特点是：搜索串扩展、相关度排序和以机器学习的方式从网 页中抽取地理信息1 1 7 j 。 在移动技术领域，地理信息在各种g p s 设备中也被广泛使用。各个搜索引擎公 司也将部分精力投入了移动电话和无线通信。比如，y a h o o 已经开发了一套移动搜 索系统，移动终端用户可以很方便地登陆y 址o ol o c a l 、y 拍o oi m a 2 e 和y a h o ow 曲 s e a r c h 来进行搜索。y e h 、t o i l m a r & d a r r e l 【1 8 j 提出了一种基于图像的方式来获取地理 信息，这种方式可以应用于带摄像头的移动设备上。在该方式中，用户首先通过拍 照的方式来制定一个位置，接着系统根据照片进行搜索并给出与该图片相关的图像 和网页。 对于基于位置的网络搜索应用，地名词典( g e o g r a p h i c a lg a z e t t e e r ) 或者地理本 体( g e o g r a p h i c a lo n t o l o g i e s ) 是必需的。地名词典就是以一定层次结构所组织起来 的地理名称列表，可以用x m l 、x s l 等各种文件格式表示。a m i t a y 等在w 曲a 啪e r e 中就利用了地名词典来构建搜索系统。而地理本体除了定义地名信息外，还加入了 这些信息间的关系，因此在文本挖掘中地理本体的功能会比普通的地名词典更加强 大【1 9 】。在s p i r i t 项目中，s m a n 、a b d e l m o t y & j o n e s 【2 0 】使用了d a m l + o i l 描述的 地理本体来构建系统。该本体定义了地理概念及它们之间的关系、层次结构和整体 性规则，主要用于s p i r j t 系统中的搜索串处理和排序处理。 2 3 2 基于位置的搜索引擎关键技术 各种搜索引擎都有一些常规的处理流程：它们首先通过网络爬虫( c r a w l e r ) 收 集网页并将它们存储在一个庞大的数据仓库( r e p o s i t o r y ) 中，接着对这些网页做索 引( i n d e x i n g ) ，最后搜索引擎将对网页进行排序( r a n k i n g ) 以响应用户的搜索串 l3h n p ：、w w s o m e w h e r c n e 札c o m 8 河海大学硕七研究生毕业论文基于位置的网络搜索引擎排序技术研究 ( q u e r i e s ) 。一个典型的搜索引擎主要具有图2 1 所示的几个功能模块。 图2 1 搜索引擎主要的功能模块 虽然大多数的搜索引擎都有一些相同或者类似的组件，但是它们实际的结构往往 会更加复杂，并且各个搜索引擎公司都不会公开自己最核心的技术。 对于专用搜索引擎，需要做的工作则比一般搜索引擎要多。一个基于位置的搜索 引擎在处理含有位置信息的搜索串时( l o c a t i o n b a s e dq u e r i e s ) 就需要考虑到以下 几个方面： 一 消除位置名之间的语义模糊( d i s 锄b i g u a t i o no f l o c a t i o nn 锄e s ) 一 识别含位置信息的搜索串和参考点( r e f e r e n c ep o i n t s ) - 信息抽取和网页的地理标注( g e o t a g g i n g ) 一 地理索引( g e o g r 印h i ci n d e x i n g ) - 基于位置的排序( l o c a t i o n - b a s e dr a n k i n g ) 2 3 2 1 位置名之间的语义模糊 首先，地理位置名之间本身就具有如图2 2 所示的层次结构，这种结构需要被基 于位置的搜索引擎考虑。层次结构的最上层是国家，比如说c h i n a 、a u s t r a l i a 等； 接下来是州或者省，比如q u e e n s l a l l d 就是澳大利亚的其中一个州；然后就是城市， 比如上海市；最后是区，比如南京市鼓楼区。当然还能往下划分，比如说街道等。 c 。u n t 胁e - 瓜 ，、 卜小删n c e 洲子6 献 j c 毗e v e - 艿京、 ，、 | s u b u m 伽e -6 鱼兮 图2 2 地理位置名之问的层次结构 其次，位置名本身又是模糊的。根据a m i t a y 的论文2 1 1 这种模糊性体现在两个方 面，一种是地名与非地名模糊( g e o n o n g e o 锄b i g u 时) ，另一种是地名与地名模糊 9 河海大学硕士研究生毕业论文基于位置的网络搜索引擎排序技术研究 ( g e o g e o 锄b i g u 时) 。地名与非地名模糊是指一个地名可能还有非地理含义，比如 m o b i l e 是美国a l a b 锄a 的一个城市名，但同时它有具有“可移动的”这个含义；再 比如r e a d i n g 是英格兰的一个城市名，但“阅读 也同时是它的含义。此外，一些 最常用的英文单词也同时就是地名，比如a s 是比利时的一处地名，比如o f 是土耳 其的一处地名等。而地名与地名模糊则是指两个不同的地点有着相同的名称。比如 在美国，有1 8 个城市都叫j e r u s a l e m ，有2 4 个城市叫p 撕s 等。 因此，根据以上关于地理位置的考虑，如果没有一个具有良好结构的地名词典 ( g a z e t t e e r ) 则很难消除位置模糊性。目前，比如g o o g l el o c a l 就采用了组织良好 的地名数据库来帮助区分位置名。其他技术比如机器学习等也应用在网络搜索中， 它们可以学习识别位置名，但并不能指出位置名具体在哪。 2 3 2 2 基于位置的搜索串和参考点 搜索串被用来分析搜索引擎用户的兴趣所在已经有很长一段时间了。在2 0 0 0 年 以前，大多数的研究包括w o l f r a m l 2 2 j 和j a s e n 、s p i n k & s a r a c e v i c l 2 3 j 都指出性是网络 搜索中最普遍的话题。从2 l 世纪开始，s p i n k 、j a s e n & p e d e r s e n 发现搜索串的内容 开始多元化，包括商业、科学、旅游和住宿等内容在内的搜索串越来越多。此外， 在搜索引擎上执行的搜索串通常都不长。一项对e x c i t e 搜索引擎的调查显示搜索串 的平均长度从1 9 9 6 年的1 5 增长到1 9 9 9 年的2 6 ，在2 0 0 4 年则又降为2 4 。 基于位置的搜索串( l o c a t i o n - b a s e dq u e r i e s ，简称l b q ) 实际上是网络搜索串( w 曲 q u e r i e s ) 的一个子集，它包含地理空间维度( g e o s p a t i a ld i m e n s i o n s ) 并涉及地球上 一个具体的地点，比