（计算机科学与技术专业论文）元搜索技术在地图搜索中的应用.pdf

西北工业大学硕士学位论文摘要 摘要 元搜索引擎是独立搜索引擎之上的搜索引擎，是搜索引擎技术的一个重要分 支，也是搜索引擎发展的重要部分。地图搜索是搜索引擎市场的最新亮点，是搜 索引擎技术在电子地图上的重要应用。如果能将二者的优点结合起来，就能从另 一个视角来对搜索引擎进行研究，这对促进搜索引擎的发展有着重要的意义。本 文将元搜索技术应用到地图搜索之中，并建立了这样的一个系统：用户只需输入 一次地图查询请求，若干个独立的地图搜索引擎都会返回结果，系统分析这些结 果并返回给用户需要的信息。 本文所做的主要工作如下： ( 1 ) 文章的开始对元搜索引擎做了简单的介绍，探讨了将元搜索技术应用到 地图搜索中的可行性问题以及当前已经拥有的成果。 ( 2 ) 文章讨论了将元搜索技术应用到地图搜索中所需要研究的问题，这些问 题包括：基于元搜索技术的地图搜索引擎的构建方法，用户输入地址的分析方法， 各个独立搜索引擎结果信息的获取方法，结果文件的信息抽取方法，搜索结果的 最优解( 路径搜索) 查找方法。 ( 3 ) 在系统的构架上，采用了成熟的b s 结构来设计系统文章对可能用到的 技术做了详细的分析，对每个技术的应用都进行了比较和权衡，并选取最可行的 方案来建立系统，使得建立的系统在时间上和空间上都符合设计的要求。 ( 4 ) 文章对这个建成的系统进行了评估，并建立了测试项来对系统进行测试， 运用测试结果的数据来说明元搜索技术在具体的应用中所取得的成果和经验。 ( 5 ) 最后，文章给出了结论，结论中指出了当前元搜索技术研究中存在的一 些问题，阐述了元搜索引擎发展的定位和元搜索技术应当具有的发展方向。 关键词：元搜索，地图搜索，信息抽取，路径比较 西北工业大学硕士学位论文 a b s t l a c t m e t a - s 鲫c h 饥舀n ei sb a s e do nc o m l 舢e n ts e a r c he n 舀n e ，i t s 衄i m p o r t a n tb r 锄c h o fs r c h 酉n et e 舡1 0 1 0 9 y ，勰d “sa l 雅i i i 】咿。咖tp a no ft h ed e v e l o p m e n to f s e 甜c he d g i n e m a p 辩越c hi st h en 钾s t 篮主n 舱赶c h 翻啦m 舡赋勰di t sa l s o 姐 i m p o r t 觚ta p p l i c 越i o ni nc l e c 由眦i cm a p i fw e c 0 曲b i n et h e i re x c e l l e n c e w ec a nd 0t h e 坞s e a r c ho f 觚h g i n e 劬mad i 丘醯e n tp o s “i o n ，t l l i si sv e r yi m p 0 舳t 击b r 雠 d e v e l 叩m e n to fs 倒曲e n g i t h ca l t i d ea p p l i e dm e 忸- s e 融t h e o r yt om 印碱， 缸db u i ns u c ha 印s t e n l ：t l s e 蝎g e t 枷m a 衲s u n sw i t ho i l l y c ei n p u t ，t h e nm a r l y m 印卸c h 锄幛i i l 嚣w i l l t i l m 蛐l t s ，t b es y s 胁w i l l 龇l y 跫t h e s er e s u l t s 锄d 托t i i m t h e 佃f o m l a l i o n t 0 1 l s e r s w h i c h t h e y i 啪d t h e w o d 岱i h 孙，ed m e l i 或b l o w ： ( 1 ) a t 位b c g i n l l i i l g ，n 坨a n i c l em a d eab r i e f i n n d d u c t i o nf o rm e t a - s e 砌e n g i i l e ， d i s c 吣s e dt h ep o s s i b i i i t yo fa p p l y m gm e t a - s e 批ht e c b i m i o g yt om a ps e a r c h ，a n d d i s c i l s s e d t h e p r o d l 枷0 nw ea k c a d y h 绷 ( 2 ) i n 眦e dn 地p r o b l e m sw es h o l l l d l v ew h a p p l ym 咖一s e a r c ht e i ；h l o g y t om a p a r c h t h ep r o b l 伽噶i n c l i l d e ：t h em c t h o dt oc 0 璐觚l c ts has y s 岫c 0m _ b 沁 m e t a s e a r c ：ht e c h n o l o g ya n dm a p a r c h ，t h em e t h o dt h a 士a l l a l y z et h ei n p u ta d d 地s s ，m e 删t h a tg e t 蒯t 舶m 硎删蝴r c he n g 妇s t h e 删t o 删y z e & 地s l l l 协，a n dt h em e t h o dt 0f i n do l i tab e s ts o l l i 垃o n d i f 矗o n ) 胁t b e r 嚣u l t s ( 3 ) w 毫u b ss 缸u c t l l r e t 0c o n s 饥m t h es y s 自锄n l e n 吐璩a r t i c l e m a k ea c a r c f i l i l y c o m p a 北t o 廿l et c c i l i m l o g y1 l l a t 脚yb eu s e d ，b u i l dt h es ) ，s t c mw i 血m o s tp o s s i b i l 时 渊w h i c h 嫩k e s t h cs y s t e m f h u l c 唧i r e 眦m ( 4 ) t h ea n i d e m a d e as i n l p l e 酬训o n f o r t h i s s y s t e | n ，觚ds e t i l p t e s t i t e l n s t o t c s t t h i ss y s t 朗n w o 出o mt l l ep r o d u c 廿o n 锄dt l l ee x p c r i e n c e t h ea p p l i c a t i o no f m e 衄- s e a r c ht e c h l m i o g yb yt l l et e s tr e s i i l t s ( 5 ) a tl 硒t ，t h ea n i c l em a d ea 啪c l u s i o nt op o i n to i i tt b ep r o b l 锄se x i g t si nt l l e 始s e a r c ho fm e 协s e a r c ht b n o l o g y c l a r i f i c dt l l el o c a t i o no fm e 忸- 8 e a r c h 西舱s d e v e l o p m c n t 缸dm e t a s f c he n g i sd e v e l o pd i r 矗吡 k e yw o r d s ：m e 诅s e a r c 粗m a ps e a r c l l m f o i m a t i o ne x a c t ，p a = l hc o m p 哦 l 西北工业大学硕士学位论文 声明 西北工业大学业 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和电子版本人允许论文被查阅和借阋学校可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时本人 保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学 保密论文待解密后适用本声明 学位论文作者签名： 冽7 年月1 1 日 弦易 川年多月f 1 日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德本人郑重声明：所呈交的学位论文，是本 人在导师的指导下进行研究工作所取得的成果尽我所知，除文中已经注明引用的内容 和致谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果， 不包含本人或其他己申请学位或其他用途使用过的成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式表明 本人学位论文与资料若有不实，愿意承担一切相关的法律责任 学位论文作者签名： 功0 1 年) 月 日 西北工业大学硕士学位论文 绪论 第l 章绪论 元搜索是一种多元信息的、高效的、使用方便的集成搜索方法，是为了弥补 独立搜索引擎的索引覆盖面不足而形成的，元搜索的出现弥补了独立搜索引擎的 一些缺陷。本章主要对元搜索技术的历史和本篇论文所要涉及的内容做简单的介 绍。 1 。1 元搜索的历史 随着h 1 6 啪e t 的迅速发展，网上信息不断丰富和发展起来。当越来越多的人们 习惯在网上发布和获取信息的时候，砌舶僦上的信息迅速膨胀成为信息海洋，为 人们提供了丰富的信息资源。然而这些信息却是以各种形式庞杂无序地散布在无 数的服务器上，并且质量参差不齐，更新变化快，用户要得到真正有价值的东西 有很大的困难所以，人们需要一种工具，使得信息资源得到有效的利用。以因 特网上的信息为主要处理对象，根据不同的需求检索出有用的信息，因此网络搜 索引擎应运而生。搜索引擎的工作原理与传统的二次文献相同，都是先收集资源， 整理加工以提供检索入口，然后用户通过提供的检索入口进行检索。 1 9 9 4 年。蛔e t 上诞生了第一个搜索引擎w e b c m w l c r ，它通过对网页索引来 提供检索服务。它的出现对网络的发展起了极大的促进作用，自此，搜索引擎进 入快速发展阶段。同年5 月，出现了l y c o s 。1 9 9 4 年底，美国著名的门户网站m o o ! 的兴起则确立了搜索引擎在m 咖e t 的重要地位。除此之外，从1 9 9 5 年到1 9 9 7 年 底，比较重要的搜索引擎还包括i n f o s e e k 、a l t a s t a 、e x c i 氓s e 纽出，伽、h o t l l o t 、 m i c r o f i m s n 等，其中以关键词检索著称的a l t a v i s t a 宣称，其数据库已经索引 1 5 亿个页面，容量超过2 0 0 g ，堪称网上规模最大的搜索引擎。2 0 0 0 年，6 h 嘻e 出现了。g o o 西e 是目前世界上功能最强大的搜索引擎，其搜索范围包含了1 0 亿个 网页，占目前互联网页总数的2 3 。 元搜索引擎是一种基于搜索引擎的搜索引擎。在搜索引擎的实现过程中，由 于各个搜索引擎的信息搜集和索引建立有很大的不同，使得它们在收集的信息资 源范围方面产生了巨大的差异，任何单个搜索引擎都只能涵盏一部分w w w 资源， 这对于用户就意味着使用任何一个搜索引擎都不可能达到信息查全的目的。为了 克服这个缺点，在该领域就出现了一种新型的搜索引擎一元搜索引擎。所谓元 搜索引擎，就是指在统一的用户查询界面与信息反馈的形式下，共享多个搜索引 西北工业大学硕士学位论文绪论 擎的资源库，为用户提供信息服务的系统。它弥补了独立搜索引擎搜索不全的缺 点，提高了检索的全面性，是未来搜索引擎的发展方向。 第一个元搜索引擎是w 缸h i l l 垂0 n 大学硕士生e f i cs e l b e r g 和0 r e ne t z i o i l i 的 m 比咐a w l c r 。从这以后，元搜索引擎得到了长足的发展，到现在已经有近百种可 用的元搜索引擎。目前，尽管元搜索引擎存在着这样那样的功能局限，但其以涵 盖较多的搜索资源，能够在尽可能短的时间内提供相对全面、准确的检索结果等 诸多优异功能受到用户的青睐，已逐渐成为一种不可或缺的，极具潜力的网络检 索工具。在这种形势下，涌现出了一大批知名的元搜索引擎，v i s i l i l o 、d o 韶i l e 等都是它们的代表。 目前，元搜索引擎的研究、开发十分活跃。它应用到了信息检索、人工智能、 数据库、数据挖掘、自然语言理解等领域。它的理论和技术，具有综合性和挑战 性，已经引起了世界各国计算机科学界、信息产业界和商界的高度关注，已投入 了不少的人力、物力，也取得了不俗的成绩。 1 - 2 地图搜索的特点 地图搜索已经成为搜索引擎一个很重要的方面，其主要应用技术是基于g i s 地理信息系统的应用。作为一门介于信息科学、计算机科学、地理学、测绘学和 管理科学之间的新兴边缘学科，具有强大的图形数据的采集、空间数据的可视化 和空间数据分析功能，又有数据更新快捷方便，分析结果准确及时，将各种信息 与反映地理位置和有关的视图结合起来提供给用户的特点。其最大特点在于把社 会经济和人们日常生活中各种信息与反映地理位置的图形信息有机地结台在一 起。并可根据用户需要，对这些信息进行分析，绘制成各类专题电子地图。 搜索引擎的巨头g o o 酉e 最先提供了在线的地图搜索业务，除提供普通的电子 地图外，还提供了相对应的卫星地图，随后m o o 也开展了自己的地图搜索业务。 g o o 百e 最开始的业务仅面对美国地区用户，现在已经扩展到了世界多个国家。 0 0 0 9 l e 也提供中国部分城市的卫星地图，并随着时间的推移不断而更新，更多的 城市和更详细的地图信息将可以被查询到，并且对于重要的大城市，都提供最清 晰的图像。 g o o g l e 的地图搜索业务对美国地区用户同时提供地图查询和路径查询，所有 查询结果均提供1 5 级缩放。在搜索一个从a 地到b 地的开车路线时，g o o g i e 会 给出a 地到b 地的详细路径信息，使用鲜艳的颜色来将路径标注出来，并给出相 应的文字说明描述这条路径。 鼬0 0 、m a p q u e s t 也对美国地区用户提供地图查询和路径查询，使用的结果表 示方式和g o o g l e 基本相同，但不提供其它地区的卫星地图，并且缩放级别也不相 2 西北工业大学硕士学位论文 同。这些独立搜索引擎对同一个查询请求的搜索结果不一定相同，并且没有一个 独立搜索引擎在所有的查询请求上得到的都是最优结果。 总结这些地图搜索引擎，它们的共同特点是：主要提供给美国地区用户地图 搜索和路径搜索功能；路径的查询结果使用文字和地图配合的方式；提供多级缩 放；搜索结果不是绝对最优。 1 3 元搜索在地图搜索中的应用 现有的地图搜索绝大部分是基于g i s 系统的。每个搜索引擎基于的g i s 系统 不同，搜索出来的结果的精度和路径也就不同。g o o g l e 的地图对于美国的用户来 说可以搜索到非常详尽的结果，但是对于中国的用户，也许b a i d u 的地图更详细 搜索从n e w y b 出到s 姐胁n c i s c o 的开车路线，g 0 0 9 l e 和y 曲0 0 的搜索引擎都能 在地图上标出这两地之间的最佳路径，但是也许g 恢西e 地图上搜索出来的路径比 地图上搜索出来的路径略胜一筹：g 0 0 蕾e 地图搜索出来的从n e w y o r k 到s 翘 f 姗c i s c o 的开车路线有更短的距离。在这种情况下，如果使用元搜索技术，则可 以集合这若干个独立的地爵搜索引擎，发挥它们各自的优势。 定义这个带有元搜索技术的地图搜索引擎为：当用户想要知道某两地的开车 路线，只需要输入一次所要查询的路径，然后系统会向若干个独立的地图搜索引 擎发出请求，取回这些结果并比较它们，把相同的路线、不同的路线、最短的路 线、最长的路线等信息都返回给用户，用户可以根据得到的信息再去浏览各个结 果。 对于地图的搜索，可以根据需要选择不同的搜索结果，取更高的精度和更详 细的地图。对于路径搜索，可以提供若干个不同的路径，比较这些路径，并给出 最短路径，最长路径 1 。4 设计目标 设计的主要目标是建立一个应用元搜索技术的地图搜索引擎，应用范围主要 面对地图上的路径搜索，根据设计的算法来比较多个独立搜索引擎上返回的路径 搜索结果，并给出这些独立搜索引擎上的最优值。也可进行地点搜索，但是只提 供显示，不涉及相应算法问题。 整个系统的结构采用成熟的b s 结构。对于地图搜索，需要的仅仅是将不同 的结果呈现给用户。而对于路径搜索来说，则要建立相应的算法结构和路径比较 算法为了达到这个目的，需要在以下方面进行算法的设计和分析：输入查询请 求、下载结果s o u r o e 、分析结果u 磁? 和结果比较算法。本文的独特之处在于将 3 西北工业大学硕士学位论文 绪论 元搜索技术和地图搜索进行了有机的结合，并将其实现。 在此基础上，构建了一个可运行的程序。这个程序运用元搜索技术建立起来 了基于g o o g l e 、和m a p q u e s t 这三个地图搜索引擎之上的地图元搜索引擎。 对于每一次的输入，可以给出三个搜索引擎的搜索结果和比较结果，并将结果在 浏览器上显示。 1 5 小结 本章介绍了元搜索的历史和地图搜索的特点，并对元搜索技术在地图搜索中 的应用做了简要介绍。本章还提出了建立一个基于元搜索技术的地图搜索引擎， 并给出了设计目标。 4 西北工业大学硕士学位论文 应用技术基础 2 1 元搜索引擎 第2 章应用技术基础 元搜索引擎是搜索引擎之后或之上的搜索引擎，元搜索可以同时查询多个搜 索引擎的站点。相对元搜索引擎，可被利用的独立搜索引擎称为“源搜索引擎” ( l l 雠e n g i l 幛) ，或“搜索资源”( 蚓l r c h i n g 潞o l 戤s ) ，整合、调用、控制和优 化利用源搜索引擎的技术，称为“元搜索技术”( m e 钯饿搬幽n g 自嘲】i l i q l l e ) ，元搜 索技术是元搜索引擎的核心。按照处理方式来分，元搜索引擎分为并行处理式和 串行处理式两大类。使用并行处理方式的元搜索引擎将用户的查询请求同时转送 给它调用链接的多个独立型搜索引擎进行查询处理，使用串行处理方式的元搜索 引擎将用户的查询请求依次转送给它调用链接的每一个独立型搜索引擎进行查询 处理。元搜索引擎是用户同时利用多引擎进行网络搜索的中介。检索时，元搜索 引擎根据用户提交的检索请求，调用源搜索引擎进行搜索，对搜索结果进行汇集、 筛选等优化处理后。以统一的格式在同一界面集中显示。元搜索引擎虽没有网页 搜寻机制，也没有独立的索引数据库，但在检索请求提交、检索接口代理和检索 结果显示等方面，均有自己研发的特色元搜索技术支持。如提交检索请求时，根 据源搜索引擎的特点和技术参数，指定优先顺序，并对检索时间、检索结果数量 进行控制；作为若干源搜索引擎的检索接口代理，元搜索引擎必须具有较强的字 符和语法转换功能，使用户的检索请求为各具语法特点的不同的源搜索引擎所认 知和接受；而对检索结果的显示，不同的元搜索引擎有不同的处理技术，由于元 搜索引擎设定的检索结果排序依据、最大返回结果数量、相关度参数及优化机制 等不同，调用相同的源搜索引擎的不同元搜索引擎显示检索结果的数量多少、排 序先后、结果信息描述选择也有较大差异。 一款理想的元搜索引擎应该具备以下特点和功能：第一，涵盏较多的搜索资 源，可随意选择和调用源搜索引擎；其次，具备尽可能多的可选择功能，如资源 类型( 网站、网页、新闻、软件、聊m 、m p 3 、图像等) 选择、返回结果数量控制、 结果时段选择、过滤功能选择等；第三，强大的检索请求处理功能( 如支持逻辑 匹配检索、短语检索、自然语言检索等) 和不同搜索引擎问检索语法规则、字符 的转换功能( 如对不支持“n e a r ”算符的搜索引擎，可自动实现由“n e a r ”向 “a n d ”算符的转换等) ；第四，详尽全面的检索结果信息描述( 如网页名称、u i 也、 文摘、源搜索引擎、结果与用户检索需求的相关度等) ；第五，支持多种语言检索。 5 西北工业大学硕士学位论文 应用技术基础 虽然有如上的特点，但是元搜索引擎毕竟是一种正在发展的技术，元搜索引 擎也存在某些缺陷。目前运营的元搜索引擎各具特色，功能各有侧重。一些元搜 索引擎在某些方面较为优秀，而其它功能则欠缺或需改进：如大多元搜索引擎不 支持多语种，尤其是汉语检索；一些元搜索引擎实现检索语法转换的能力有限， 不支持指定字段检索，不能充分发挥各个独立搜索引擎的高级检索功能：部分元 搜索引擎无源搜索引擎列表，用户不能自主选择和调用源搜索引擎；大部分元搜 索引擎仅支持调用舢t a v i s t a 、e x c 沁、g o t o 、c o m 、m o o ! 、h l ：f o s e c k 、l y c o s 等常 用的搜索引擎，一些大型搜索引擎如n o n h e m l i g h t 、h o t b o t 等被排除在外，人为 地限制了搜索资源的利用；在检索结果上，元搜索引擎只能返回十几、数十条“相 关度”较高的结果，大量可能有价值的源搜索引擎的检索结果被忽视，影响检索 结果的全面性。元搜索引擎的功能受着源搜索引擎和元搜索技术的双重制约：一 方面，源搜索引擎的各具特色的强大功能在元搜索引擎中受到限制而不能充分体 现；另一方面，任何一种元搜索技术都不能发掘和利用源搜索引擎的全部功能。 在元搜索引擎中，每当用户的一个查询被提交，就要通过一系列的处理流程 来处理这个查询并返回处理结果。这些处理包括处理输入请求，可以对多语言查 询请求做出分析，并针对搜索语言的不同对下层搜索引擎进行选择。还包括接受 独立搜索引擎信息的方式，和独立搜索引擎交互的接口，结果聚合算法等等。结 果聚合算法是元搜索引擎的一个重要部分，因为各独立搜索引擎都有自己的排序 计算方法，为了将获取到的这些结果进行合并显示，就需要对其进行归一化处理， 因此如何将从多个独立搜索引擎获取的结果进行排序是元搜索研究的一个重要方 面。从这方面来看，用户进行一次请求，元搜索引擎需要一次性做很多的实时工 作，这就要求如果有多个用户同时提交了请求，那么搜索引擎就需要有并行能力 来处理这些请求。 除了实现，还需要有一个元搜索引擎的评价准则来对设计的系统进行评价。 可以设计算法来检查元搜索引擎返回结果同用户主观上需要的信息的匹配程度， 结果同用户的需求匹配越好，说明排序算法也越好。互联网上也有很多专业的搜 索引擎评价机构，可以根据搜索引擎的搜索结果，直接给出对某个搜索引擎的评 价结果。不管采用哪种评价方法，目的都是为了正确地评价一个元搜索引擎，使 得系统设计者可以采取相应的策略来应对问题。 元搜索引擎采取的系统构架一般是b s 模式，用户通过浏览器将自己所要查 询的请求发送给w e b 服务器，这个w c b 服务器实际上就是一个元搜索引擎。w 曲 服务器接收到来自用户的查询请求并验证了该请求之后，就把这个请求发送给各 个独立搜索引擎，然后根据从独立搜索引擎上返回的结果，对所有的这些结果进 行排序，返回给用户，这个流程顺序不可以改变。一个典型的元搜索引擎的设计 架构如图2 1 所示。 6 西北工业大学硕士学位论文 图2 一l 一个典型的元搜索引擎设计架构 应用技术基础 在g 0 0 西e 和y 抽o o 中，分别使用相同的关键字进行查询，取各自的前1 0 0 个 结果进行对比。若干次的比较之后就会发现，二者的搜索结果中，仅仅有1 0 3 0 的结果是相同的结果。原因主要有两个方面：第一，不同的网页搜集方法。搜索 引擎要对网页索引时，必须要搜集到w w w 上尽可能多的网页，因此每个搜索引 擎都有一个或者多个称之为“爬虫”的程序来自动从互联网上抓取w e b 页面。抓 取的策略不同，抓取到的结果也就不相同。加之互联网上的页面更新速度太快，“爬 虫”程序总会有搜集不到的页面第二，不同的结果排序方法。每个结果都有对 应的一个值，这个值表示该结果同查询串之间的相关程度，称之为删凸k 值。独立 搜索引擎计算一个结果的坷k 值时，要考虑到查询串在这个结果页面中的位置， 出现的次数等因素，然后根据这些因素，使用算法来计算这个结果的均n k 值。捌n l 【 值越大，表示结果越符合用户的需要，这样，当用户进行查询请求的时候，就可 以按脚咄值由大到小给用户返回结果。由于商业的因素，计算脚k 值的算法往往 是不公开的，由此导致不同的搜索引擎有不同的r a 】【l l 【值计算方法。一个结果在 g 0 0 9 l e 中也许会排在前l o 个结果之内，但是在呦o o 中，也许会在1 0 0 个结果之 后，这也是造成查询结果差别较大的原因。 7 西北工业大学硕士学位论文应用技术基础 元搜索引擎综合了这些独立搜索引擎的搜索结果，弥补了独立搜索引擎的一 些缺陷，有着覆盖众多搜索引擎，强大的检索处理功能等优点，对搜索引擎的发 展起到了一定的促进作用。 2 2 地图中的元搜索 地图搜索的核心是g i s 系统。g i s 系统早在上世纪6 0 年代就已经出现萌芽。 7 0 年代是地理信息系统走向实用的发展期。美国、加拿大、英国、西德、瑞典和 日本等国对g i s 的研究均投入了大量人力、物力和财力。8 0 年代是g i s 的推广应 用阶段，由于计算机技术的飞速发展，在性能大幅度提高的同时，价格迅速下降， 特别是工作站和个人计算机的出现与完善，使g i s 的应用领域与范围不断扩大。 9 0 年代为g i s 的用户时代，随着地理信息产业的建立和数字化信息产品在全世界 的普及，g i s 成为了一个产业，投入使用的g i s 系统，每2 3 年就翻一番，g i s 市场的增长也很快。 地图搜索正是由于g i s 的迅猛发展和互联网的爆炸式增长而出现的。很多w e b 服务商都提供地图搜索业务。对于不同的地图搜索服务，用户所能得到的服务限 于该服务商所能提供的服务种类、精度和它所依靠的g i s 系统。地图搜索网站本 身往往并没有强大的地理信息，用户向地图搜索网站发送的请求经处理后，会发 向专门的g i s 系统，g i s 系统向网站返回所需要的地理信息，这些信息经地图搜 索网站处理后以文字和图表的形式呈现给用户。 u s c r 发送请求信息 么 反运请累佰恳j n 尹一、 给搜索引擎 蚴k he n g i n e 夔 g i s 处理格式化 ) ，) 用户请求g i s 系统 组织地图信 = 名音 息结果并返 一 返回地图和回给用户 文字信息 从g i s 返回信息 蔗燕 ；。”， 讧抽，刍zj 图2 2 地图搜索引擎的基本结构 不同的地图搜索引擎可能采用不同的g i s 系统、不同的算法、不同的分级实 现模式和不同的精度来生成可视化的地图和路径。假设有两个独立的地图搜索引 8 西北工业大学硕士学位论文 应用技术基础 擎髓；和踢，船；采用1 2 级显示精度，而艇j 则采用1 5 级显示精度，艇j 的最大 精度可能到1 ：l o o o ，而艇；的最大精度可能到l ：1 0 0 0 0 。再假设a 地到b 地有若于 不同的路径，这两个搜索引擎都可以搜索由a 地到b 地的最优路径，那么它们搜 索出来的结果可能是不相同的。在这两个结果中会存在个较优解，如果能直观 地将最长和最短的路径告诉用户，那么用户从这一次查询上所获取的信息量就会 有很大增加。 为了将若干个独立地图搜索引擎的结果来进行比较和处理，就要运用到元搜 索技术。利用这种技术，可以构建这样一个系统：用户可以通过这个系统来查询 所需要的地图和路径信息；系统给用户提供的结果地图信息来自若干个独立的地 图搜索引擎；系统从各个独立搜索引擎上获取信息，把获得的信息处理之后再返 回给用户。主要分析的信息是各个独立搜索引擎的路径信息，这些信息被下载下 来，使用字符处理程序抽取其中的有用信息并格式化，再设计算法来比较这些信 息，最后将结果返回。这几个过程是顺序的过程，不能有过程被提前，但是如果 所做工作具有重复性，那么互不干扰的部分可以使用并行处理技术来提高系统的 执行效率和处理速度。图2 3 就表示了一个运用了元搜索技术的地图搜索引擎在 理论上应该具有的结构 发送请求fw w w s e r v 盯l 发送请求 1 u 瓣 、 结果呈现 结果比 较算法 送 算 法 处 理 若干个独立 的地图搜索 引擎 结 果 数 据 从各个搜索 引擎返回的 结果 图争3 运用了元搜索技术的地图搜索引擎结构 图中从向独立搜索引擎请求信息部分到结果比较之前的部分都可以适当考虑 使用并行方法来处理，因为这些部分对于独立搜索引擎来说都是互不影响的。这 9 西北工业大学硕士学位论文应用技术基础 个图描述了在地图搜索中应用元搜索技术的基本结构，具有元搜索引擎应当具有 的基本特征。 2 3 从独立搜索引擎取得搜索结果 如果需要比较若干个独立搜索引擎返回的结果，首先要做的第一步是要取得 这些结果。取得这些结果的方法有两种：使用搜索引擎提供的a p i 获取结果和使 用h 1 1 甲请求的方式直接获取结果页面。事实上h r r p 请求的方法也属于网站提 供的a p i 的一种，之所以将它们分开介绍是因为使用的方式存在较大差异。网站 提供的a p i 具有语言和格式局限性，而h 兀p 请求则没有。 2 3 1a p l 很多地图网站都提供了a p i 接口来提供给普通用户使用。例如g 0 0 9 l e 就提供 了这种a p i ，系统的设计者可以使用这些a p i 来进行编程，并且这些a p i 完全免 费。实际上这些a p i 很多都是使用j s 脚本参数来实现，将这些j s 脚本带上参数， 放在自己的网站上，就可以进行地图的查询，并返回结果。所有的操作都是在应 用了脚本的网站上进行，就好像这个网站也提供了同独立地图搜索引擎一样的地 图搜索服务，而事实上这些信息却都是从提供a p i 的独立搜索引擎得到的。例如 脚本 v a rm a p s = n 孵l t m a p s ( ”r 珏8 p s 。) ： m a p s c i t y n 锄e a n d z o o m ( 勺e i j i n g ”，2 ) ： v a rc=newl t s m a l1 m a p c o n t r 0 1 ( ) ： 腿p s a d d c o n t r o l ( c ) ： v a rp o i n t = n e 霄l t p o i n t ( ) ：b e i j i n g v a r 陋r k e r = n e wl t m a r k e r ( p o i n t ) ： m a p s a d d o v e r l a y ( m a r k e r ) ： v a rt e x t = n 趼l t m a p t e x t ( 施r k e r ) ： l o 西北工业大学硕士学位论文 应用技术基础 t e x t s e t l 角l b e l ( m yl o c a t i o n ) ： 腿p s a d d o v e r l 矗y ( t e x t ) ： 只要将这段脚本直接粘贴在网页的h n 江l 代码之内，就可以得到以( 1 l “0 9 6 9 ， 3 9 8 9 9 4 5 ) 为坐标的点的地图信息。 但是仍然存在一个问题，地图网站的公开a p i 往往有着很大的局限性，缺点 在于这些a p i 不能被灵活运用。地图网站提供的棚可以让网站管理员在1 分钟 之内就建立起来一个自己的地图系统，但是如果想要进一步获取更详细的结果就 很困难。而且这种仅仅提供了脚本参数的方法，对于做编程开发尤为不利，仅仅 提供了j a v a s c r i p t 代码，意味着我们只能在网页中嵌入这些代码。如果想使用其它 编程语言的接口，或者在程序中应用这些结果，需要地图网站给出相对应的a p i 。 如果很不幸，独立地图搜索引擎没有提供所需要的a p i ，那么就没有办法使用a p i 来实现所需的应用。 个别的地图网站，如g 0 0 百e m 印，提供了一些高级的a p i 来获取想要的信息。 但是这些a p i 都不是免费的，如果需要使用这些服务，付费才可以。而且这种服 ，务也只有g o o g l e 等这种有强大的技术力量做后盾的服务提供商才会有，大部分地 图搜索引擎都不会提供这样的a p i 来供程序设计者调用。提供a p i 的不一致性同 样增加了应用的难度 2 3 2h t t p 既然想要得到a p i 不能提供的信息，并且这些信息在地图网站的查询结果上 是可见的，那么是不是如果可以获取这个页面上面的l | r c e 文件，我们在网页上 看到的信息就都能得到? 其实理论上只要信息存在于u r c e 文件的m ，代码 中，那么我们总是可以得到我们需要的东西。为了达到这个目的，我们需要把我 们的请求做成一个普通的h r r p 请求发送给独立搜索引擎。具体的构造方法根据 运用的语言的不同而不同，但是要求使用的语言必须具有网络编程的能力。如果 运用了较低级的语言，那么就需要系统设计者自己来构造h r r p 请求。幸运的是， 大多数的高级编程语言都提供封装好的h r r p 请求接口。使用这些接口，提供一 个合适的参数，就能得到需要的h 附l u r c e 文件。我们的目的仅仅是得到这些 u r c e 文件，而不需要关心这些内容具体是怎么得到的，因此得到的途径自然是越 简单越好。在这种情况下使用高级语言的接口就是一种很可取的方法。高级语言 封装了这些特性，而且使用这些接口来进行m i 甲请求有着高效、方便的特点， 有利于加快系统开发速度。 m i 甲请求下载下来的s o u r 主要是 n m l 代码，从技术上来说，使用这种 方法使得从这些地图网站上获得的结果具有了一致性的编码格式。具体到细节上， 西北工业大学硕士学位论文 应用技术基础 无非是内容格式不同，但是由于已经具有了统一的编码格式，因此可以通过对各 个不同的格式分别编程来解决。 2 4 网页源代码的分析 为了进行结果的比较，需要有结构化的数据提供给算法。这需要从独立地图 搜索引擎上获取s o l 珊e 信息进行分析和处理，抽取需要的信息并将其格式化，以 方便算法比较。信息提取的方法有两个：使用字符串匹配算法和使用正则表达式 匹配算法。 2 4 1 字符串匹配 如果想要从一个较长的字符串中获取想要的信息，需要用到字符串的匹配。 字符串的匹配被用来从一个字符串中找到一个或者若干个匹配的子串。字符串的 匹配可以用来匹配一个固定的串，或者是一个模式串。本文中运用匹配的目的主 要是要从网页的u r c e 中抽取需要的路径信息，如路径的走向、路径的长度、分 步信息等。 对于特定的一个子串，在母串中匹配这个子串时，就要用到字符串匹配算法， 一般这种字符串匹配算法被称为串的模式匹配算法。假设有主串s 和模式串t ，需 要在s 中找到t 的匹配项。在匹配的过程中，分别利用计数指针i 和j 指示主串s 和模式串t 中当前正待比较的字符的位置。算法的基本思想是：从主串s 的第p o s 个字符起和模式的第一个字符比较之，若相等，则继续比较后续字符，否则从主 串的下一个字符起再重新和模式的字符比较之。依此类推，直至模式t 中的每个 字符依次和主串s 中的一个连续的字符序列相等，则匹配成功，否则匹配不成功。 这种算法在某些情况下效率很低，成熟的做法是使用一种改进的算法，即k m p 算 法，这个算法可以在o ( r l + m ) 的时间数量级上完成串的模式匹配操作。 对于模式子串，子串代表了一种模式。我们要在s o l l r c c 中匹配的子串，往往 就是一个模式串。例如，需要在一个主串s 中找到所有连在一起的由5 个数字组 成的字符序列，或者，需要在s o u r c e 中找到所有 标签内的所有内容。这 个时候除了要考虑已有的匹配算法外，系统的设计者也需要自己设计一部分算法， 使得这些模式的匹配能够在程序中应用。因为模式匹配算法对固定的子串很有效， 但是涉及到具体的s o u r _ c c 文件，我们可以利用h t h 也语言的标签特性来达到我们 的目的。 如果模式很简单，那么匹配是容易的，并且速度也很快。但遗憾的是，在本 文所涉及的应用中，所用到的匹配模式通常是复杂的。而且，对于不同类型的 s o u r c e ，可能需要不同的模式来进行匹配，这就意味着要为不同的s o u r c e 来编写不 西北工业大学硕士学位论文 应用技术基础 同的匹配算法。这个工作量将非常庞大。虽然在我们所应用的系统中，所用的u r c e 的类型是有限的，在理论上这样的匹配是可以实现的。但是进行这种匹配所要花 费的工作量却是很可观的。 2 4 2 正则表达式 正则表达式是一种可以用于文字模式匹配和替换的强有力的工具。是由一系 列普通字符和特殊字符组成的能明确描述文本字符串的文字匹配模式。正则表达 式并非一门专用语言，但也可以看作是一种语言，它可以让用户通过使用一系列 普通字符和特殊字符构建能明确描述文本字符串的匹配模式。除了简单描述这些 模式之外，正则表达式解释引擎通常可用于遍历匹配，并使用模式作为分隔符来 将字符串解析为子字符串，或以智能方式替换文本或重新设置文本格式。正则表 达式为解决与文本处理有关的许多常见任务提供了有效而简捷的方式。 正则表达式具有两种标准： 基本的正则表达式i 也一b 缈i cr e g u l 盯e x p r e s s i o 珊) 扩展的正则表达式r e e 跞 n d c dr e g u ke x p r e s s i 伽田 e r e 包括b r e 功能和另外其它的概念。 正则表达式目前有两种解释引擎： 基于字符驱动懈t d i d e c 自。d g i n e ) 基于正则表达式驱动- d i d b c e de n 舀n e ) ( 1 ) 正则表达式的起源 正则表达式的“祖先”可以一直上溯至对人类神经系统如何工作的早期研 究。獭l n 髓m c c l d l o c h 和w 出t e r p i t t s 这两位神经生理学家研究出一种数学方式来 描述这些神经网络。1 9 5 6 年，一位叫跏p h e l li ( 1 黜的美国数学家在m c c l l l l o c h 和p i 地早期工作的基础上，发表了一篇标题为“神经网事件的表示法”的论文， 引入了正则表达式的概念。正则表达式就是用来描述他称为“正则集的代数”的 表达式，因此采用“正则表达式”这个术语。随后，发现可以将这工作应用于 使用k 肌n l o m p s o n 的计算搜索算法的一些早期研究，k e n1 1 l o n l p s o n 是u n 呔的 主要发明人正则表达式的第一个实用应用程序就是u l l i 】【中的q e d 编辑器。从 那时起直至现在正则表达式都是基于文本的编辑器和搜索工具中的个重要部 分。具有完整语法的正则表达式使用在字符的格式匹配方面上，后来被应用到熔 融信息技术领域。自从那时起，正则表达式经过几个时期的发展，现在的标准已 经被i s o ( 国际标准组织) 批准和被o p e ng r o u p 组织认定。 ( 2 ) 正则表达式的使用 在这里我们并不讨论正则表达式的具体用法，只是想说明，正则表达式可以 实现从一个字符串种获取需要的复杂信息。最简单的正则表达式就是文字字符串 西北工业大学硕士学位论文应用技术基础 特定的字符串可通过文字本身加以描述；像t c s t 这样的r e g e x 模式可精确匹配输 入的字符串”t e s t ”，但是它也可以匹配t h i s i s a t e s t c a ，这就不是我们想要得结 果。当然，使用正则表达式匹配等于它自身的精确字符串是没有价值的实现，不 能体现正则表达式的真正作用。但是，假如要查找的不是t c s t ，而是所有以字母t 开 头的单词，或所有4 个字母的单词，那么使用正则表达式就可以很轻松地做这些 事情，这正是为什么使用正则表达式的原因。因此，为了从下载下来的s o u r c e 种 抽取需要的各种复杂信息，我们需要正则表达式这种强大的匹配工具来为我们服 务。 2 5 小结 本章讨论了建立地图元搜索引擎所涉及到的技术。这些技术主要包括：如何 从独立搜索引擎上获取结果，如何分析这些结果。获取结果的方法有a p i 的方法 和发送h r r p 请求的方法，分析结果的方法有字符串匹配的方法和正则表达式的 方法。本章的讨论为后续章节的工作做了良好的铺垫。 1 4 西北工业大学硕士学位论文 应用过程 3 1 环境的选择 第3 章应用过程 不同的开发环境影响开发效率，在使用具体的应用来验证理论时，选择合适 的开发环境是应用成功的重要保证。为了进行快速开发，尽量跳过与本文无关的 技术细节，选择了尽可能易用的开发环境：使用谢n d o 郴作为基本操作系统，编 译环境使用v s n c t 集成工作环境，编程语言使用c # 。当然，【抽戳和p 球也是可 选项，并且从效率和可移植性的方面来说，这个方案在长远上看似乎是更好的一 个解决方案。但是考虑到人手，人员对环境的熟悉程度，时间和工作量上的考虑， 还是选择了前者 在应用中要建立一个元搜索引擎在地图搜索中的解决方案，重点在于所运用 的概念和所研究的算法，以及对这些概念和算法的研究和探讨。因此，时间不能 都花费在对开发环境的适应和糟糕的调试环境上，建立一个简单、易用、能直接 研究问题的开发环境是有必要的。 w 如服务器采用a p a c h e 服务器，主要是基于舢坦c h e 优异的性能和高可配置 性所决定的。因为选择了。n e t 开发环境，而a