（计算机系统结构专业论文）手机桌面搜索引擎的研究与实现.pdf

大连理工大学硕士学位论文 摘要 随着移动终端的功能日益增强，移动终端软硬件技术的发展，移动终端中存储的数 据的种类和数量也在不断增加，如何快速将用户所需要的数据准确地呈现给用户成为了 一个迫切的问题。然而手机类型多种多样，数据管理方式也各不一样，大部分手机上的 文件系统对用户来说是透明的，手机用户将不能像p c 一样方便快速地定位手机上某文 件的位置，正因如此，手机桌面搜索需求日益突出。然而，目前大部分主流的搜索引擎 如l u c e n e 、n u t c h 、i n d r i 等从开始就只是针对p c 的数据模型进行设计的，而g o o g l e 、 百度等由于自身商业定位偏于网页的索引和搜索服务，所以它们并不能适应智能手机特 殊的需求。为了提高智能手机用户的体验和效率，本文结合s q l i t e 3 数据库引擎研究并 设计了一种新的适合智能手机的微型搜索引擎，同时与l u c e n e 进行比较，分析了本文 搜索引擎的优缺点。 论文首先对手机系统进行分析，并归纳出引擎设计中需要考虑的手机特性。接着阐 述了目前流行的搜索引擎框架l u c e n e 的优缺点，发现l u c e n e 不能很好地适应手机特性。 因此，本论文结合l u c e n e 的优点并针对手机特性，全新设计了引擎的索引策略和搜索 策略，实现了手机桌面引擎h a w a i i 。本文还将h a w a i i 应用于g o o g l ea n d r o i d 系统上， 介绍了a n d r o i d 应用程序的开发流程和引擎的最终应用效果。在此基础上测试了引擎的 性能，证明了引擎是可行的和高效的。 关键词：移动搜索；桌面搜索引擎；s q l i t e 3 数据库；a n d r o i d 大连理= 大学硕+ 学位论文 t h er e s e a r c ha n di m p l e m e n t a t i o no fm o b i l es e a r c he n g i n e a b s t r a c t w i t ht h ed e v e l o p m e n to ft h eh a r d w a r ea n ds o f t w a r et e c h n o l o g ym o b i l et e r m i n a l ，t h e f u n c t i o no ft h em o b i l ep h o n ei sb e i n ge n h a n c e di n c r e a s i n g l y a tt h es a m et i m e ，t h eq u a n t i t y a n dt h et y p eo ft h ed a t as t o r e di nt h em o b i l ep h o n ea r ea l s oi n c r e a s i n gq u i c k l y h o wt o d i s p l a yt h ed a t at h a tu s e r sn e e dq u i c k l ya n da c c u r a t e l yh a sb e c o m ea nu r g e n tp r o b l e m b u t t h e r ee x i s tv a r i o u sk i n d so fm o b i l ep h o n e s ，a n dt h ed a t am a n a g e m e n to ft h e mi sn o tt h es a m e n o tl i k et h ep e r s o n a lc o m p u t e r ，m o b i l ep h o n e sf i l es y s t e mi st r a n s p a r e n c yt ot h eu s e r s t h e m o b i l eu s e r sc a nn o tl o c a t et h ef i l et h e yw a n ta se a s ya st h ep cu s e r s a n dt h em a i n s t r e a m s e a r c he n g i n e s ，l i k el u c e n e ，i n d r ia n dn u t c he t c ，a r en o t b o r n e df o rm o b i l e p h o n e s m o r e o v e r ，t h eg o o g l e ，b a i d ua n dy a h o oe t c a r el e a nt os e r v i c et h ew e b p a g e sf o rt h e i r b u s i n e s ss t r e t a g y s ot h e ya l la r en o tf i tf o rt h em o b i l ep h o n e s i nt h i sp a p e r an e w d e s i g no f d e s k t o ps e a r c he n g i n ef o rm o b i l ep h o n ei sp r o p o s e d t h ee n g i n es u f f i c i e n t l yc o n s i d e r st h e s p e c i a l t yo fm o b i l ep h o n ea n dp r o p o s e st h en e wi n d e x i n gs t r a t e g ya n ds e a r c hs t r a t e g yt o s u p p o r tt h em o b i l ep h o n e i nt h ed e s i g n ，t h es t o r a g ec a p a b i l i t yi si n v o l v e di nc o n s i d e r a t i o n ，s o s q l i t e 3 ，al i g h te m b e d d e dd a t a b a s ee n g i n e ，i sa d o p t e dt om a n a g et h ei n d e xd a t a a tl a s t 。a n a s y n c h r o n o u sm o d e li sd e s i g n e dt oi m p r o v eu s e re x p e r i e n c e n i s p a p e rs t u d i e dt h ep o p u l a rs e a r c he n g i n ef r a m e w o r k ，l u c e n e ，i nd e e p b a s e do i lt h e p a r t i a ld e s i g ni d e ao fl u c e n ef r a m e w o r k ，t h i sp a p e rs t u d i e st h ef e a t u r e so fm o b i l ep h o n ea n d d e s i g n e dt h ei n d e xa n ds e a r c hs t r a t e g yo ft h ee n g i n ef r o ms c r a t c h t h e nt h ee n g i n ei sa p p l i e d o nt h ea n d r o i dp l a t f o r m ，t h e nt h ee n g i n ep e r f o r m a n c ei st e s ta n dv e r i f i e do nt h ep l a t f o 加t h e p e r f o r m a n c ed a t as h o w st h a tt h ee n g i n ep r o p o s e di n t h i sp a p e ri sf e s i a b l e ，p r a c t i c a b l ea n d e f f i c i e n t k e yw o r d s ：m o b i l es e a r c h ；d e s k t o ps e a r c he n g i n e ；s q l i t e 3 ；a n d r o i d i - 大连理下大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 1 绪论 随着移动通信的不断发展，移动手机终端功能日益增强，手机中的数据的种类和容 量也不断的增加，如何快速准确地定位用户需求的数据成为了手机系统迫切需要解决的 问删。尤其是智能手机日益普及和3 g 的不断成熟，手机用户可以任意定制自己的应 用程序和应用设置。a p p l e 和g o o g l e 等的a p ps t o r e 推出后，手机的应用越显差异化， 摆在用户面前的问题是定位并启动应用程序将要花费更长的时间。正是为了解决这些问 题，本文设计并实现了适用于移动手机终端的搜索引擎，从而解决用户使用手机的效率 问题，并试图让用户们随时随地地获得他们想要的信息。在本章接下来的部分，将简要 介绍一下论文的研究意义、研究目标以及论文的结构。 1 1 研究意义 在手机移动终端的搜索引擎需求还没有如此迫切之前，p c ( p e r s o n a lc o m p u t e r ) 及 互联网的搜索引擎是多种多样。以雅虎为代表的第一代目录式搜索引擎以及以谷歌、百 度为代表的第二代机器人搜索引擎均得到了商业上的巨大成功和技术上的快速发展，网 络搜索引擎已经成为了人们使用网络资源的主要途径和手段；作为网络搜索引擎向终端 的延伸和扩展，随着电脑存储数据种类和数量的增加，桌面搜索引擎得到了长足的发展， m s n 搜索、谷歌桌面、雅虎桌面搜索等一一出现【2 】，这些搜索引擎主要对p c 机中存储 的用户资源的内容及标题进行搜索。当前，3 g 的到来带来了互联网慢慢向移动互联网 的过渡，并将在不到五年的时间高速地发展，因此也将带来商业模式的深刻变革。 手机移动搜索是通过手机通信网络与互联网的连接，将互联网中的网页以无线搜索 技术通过转换代码的形式转换为手机所能接收的信息，为用户提供最精确、最有价值的 内容。与传统搜索不同的是，手机用户无需连接p c 或其他设备可直接实现搜索功能， 且在搜索过程中会把网页中多余图片、超级链接、f l a s h 等进行过滤，为用户呈现出最 准确的搜索结果。与传统互联网搜索引擎相比，基于移动通信网络的手机搜索有以下五 个特点。 ( 1 ) 搜索成本较低 移动搜索无需上网设备，只需一台普通的手机，相对于p c 而言，手机的灵活性、 便利性和终端价格等方面优势很明显。目前中国的手机用户已经超过5 亿，是互联网用 户的5 倍，庞大的手机用户量及其高速地增长，为移动手机搜索服务提供了良好的用户 基础。 ( 2 )自由度更大 手机桌面搜索引擎的研究与实现 手机用户可以随时、随地、随需搜索，不受互联网网络限制，而且移动通信网络速 度也变得越来越快。随着无线开发商从第二代技术向高性能的2 5 g 以及3 g 技术发展， 下行速度可以达到3 1 m b p s 。现在，开发商的目标更是望向了3 5 g ，其速度将可能达到 1 4 4 m b p s ，最后是4 g ，预期速度是1 0 0m b p s 或者更高。这些基础网络的升级给用户使 用手机的自由度增加提供了必要的基础。 ( 3 ) 使用效率高 移动手机检索结果将更有针对性，不同于传统桌面搜索引擎动辄返回成百上千个结 果，手机搜索由于受到屏幕、带宽以及流量等方面的限制，用户不可能花费过多的时问 和金钱等待和浏览过多的检索结果，这就要求搜索到的信息更加精练，针对性更强，能 够根据用户的习惯偏好提供个性化服务。 ( 4 ) 时效性强 手机搜索可以采用短信之类的即时通信方式进行互动。例如，用户想要知道他们感 兴趣的篮球比赛的比分或者当天的火车、航班信息，通过发送查询短信就可以在第一时 间获知结果，甚至只需在手机桌面敲入需要的信息关键字，即可马上获得结果。 ( 5 )良好的付费习惯 传统互联网用户已经习惯了免费模式，例如，g o o g l e 超过9 0 的收入来自广告，用 户进行搜索则是免费的，用户在传统互联网上使用资源是没有付费习惯的。而在手机上 开发搜索业务，用户会对收费模式坦然接受，因为在移动通信业务中，大部分业务都是 对用户收费的，这也鼓励了网络服务商的积极性1 3 j 。 在这种市场的背景条件下，桌面搜索对搜索引擎开发商而言无疑具有相当重要的作 用，它可以增加用户粘度、增强品牌效应，具有潜在的商业价值。但是目前主要的问题 是，手机移动平台上几乎没有一款成型或商业的桌面引擎，手机独特的系统结构和商业 特点决定了p c 机中的搜索引擎并不能简单的过渡到手机移动平台上。 综上，研究如何结合搜索引擎的特性和手机系统特点设计适用于手机移动平台的桌 面搜索引擎具有重要的现实意义。 1 2 研究目标 接下来将结合对手机系统深入研究后归纳的手机系统的结构特点，提出本文手机桌 面搜索引擎针对手机特性进行针对性设计的研究目标。 首先，经过对手机系统的深入分析与综合研究，并结合各参考文献的描述，将手机 系统的结构特点归纳如下五点。 大连理工大学硕十学位论文 ( 1 ) 运算速度：相对于p c 设备，手机等移动终端的处理能力很低。智能手机很 多采用a r m ( a d v a n c e dr i s cm a c h i n e s ) 处理器芯片，以i p h o n e 为例，其采用了三星 电子生产的$ 3 c 6 4 0 0 型处理器，基于a r m l l 架构，a r m l l 7 6 jz f 程序内核的运行频 率为6 2 0m h z ，就当前而言，这在智能手机领域基本上可堪称最高频率。而一些高端机， 例如n o k i an 9 5 的处理速度也仅为3 3 0 m h z ，由此可见，手机的运算处理能力相对依然 很低。索引的建立、更新过程以及遍历过程对c p u ( c e n tr a lp r o c e s s i n gu n i t ) 的处理能 力要求很高。因此需要研究在充分考虑终端自身的处理能力的情况下，选择运算复杂度 合理的搜索算法，并根据存储空间的大小，做到时间复杂度和空问复杂度的平衡。 ( 2 ) 存储能力：手机的存储空间相对于p c 而言，存储空间很低。传统的功能性 手机，一般内置存储空间从几m 到几十m 不等，并且不提供扩展存储卡的功能；就智 能手机而言，芯片内置存储空间根据手机的不同大概会有几十m 左右的存储空间，外 置存储卡一般支持最高8 g b 左右的存储能力：尽管手机存储空间在接下来的几年内有 望达到1 0 0g b ，但就现阶段而言，存量终端以及市场上销售的终端的存储能力一般都 不超过8g b 。因此，需要研究如何保持索引文件的紧凑，充分利用存储空间；同时需 要根据内存以及存储卡容量等，结合i o ( i n p u t o u t p u t ) 操作速度进行搜索引擎的优化。 ( 3 ) 屏幕尺寸及分辨率：手机以其小巧和便携性而得到了快速地发展，因此手机 的屏幕一般都不会太大。现在主流的屏幕分辨率一般从1 2 8 x1 6 0 像素到4 8 0 x6 4 0 像素 不等，大小一般为1 1 5 寸到3 1 5 寸不等，因此搜索的结果需要尽量地做到简单、直观、 便于浏览和操作。一种可行的方案是让不同的内容分类显示，并将不同分类的内容以“选 项卡”的方式进行展现i 。 ( 4 ) 电池续航能力：手机电池技术一直滞后于其他软硬件技术的发展，是移动终 端发展领域的一个瓶颈，限制了很多业务的开展。现有电池一般都是锂离子电池或者锂 离子聚合物电池，电池续航时间根据手机的使用情况有很大的不同。搜索引擎的索引建 立、更新以及查询过程，涉及大量c p u 的运算以及i o 操作，对电池是一个很大的考验， 因此电池的续航能力是需要重点考虑的内容，在研究技术上不断改进的同时，也需要结 合用户层面的策略或使用习惯，优化搜索引擎的效率，例如：提供给用户选择的机会， 从而决定何时建立索引、何时更新索引以及何时启动搜索等等。 ( 5 ) 文件格式：文件主要包括通讯录、短信、邮件、记事本、音视频文件等。手 机主流操作系统主要包括s y m b i a n 、w i n d o w sm o b i l e 以及a n d r o i d l 4 j 等，不同手机操作 系统的文件结构有所不同；同一种操作系统的不同厂家的封装形式也不尽相同，例如基 于s y m b i a n 系统的u i q 平台和$ 6 0 平台；同一操作系统、同一厂家以及同一平台的不 同手机版本的文件格式也有所差别，比如$ 6 0v e r s i o n 5 和$ 6 0v e r s i o n 3 就存在差别；即 手机桌面搜索引擎的研究与实现 使以上都相同，不同的手机型号由于硬件等差异，文件的支持程度也是有所差别的，因 此手机中文件格式的不一致性尤为突出。因此，在建立索引之前，需要对格式进行一致 化，以便于后续相关流程的简化。 因此，本文的研究目标就是结合手机的特性，设计出适合的微型轻量级引擎索引策 略和搜索策略，辅助用户快速准确地定位所需信息，从而实现如下基于此引擎的应用体 验： 想发短信时，若发现想要键入的信息是某联系人在以前曾经给自己发送过来的 或是自己曾经给别人发送过的信息，那么此时呼出搜索框，键入记忆中的关键词，就可 以通过本文设计的引擎快速定位信息，并将感兴趣的文本粘贴到当前编辑的文本中。 想启动程序时，用户并不知道去哪启动此程序，但是知道程序的名字或者标题 里含有某个词，那么此时也可以呼出搜索框，键入关键词快速定位并启动程序。 想听音乐时，用户不需关心自己手机上是否存在想听的歌曲，只需键入歌曲名， 该引擎自动搜索本地，并在本地未找到目标后自动从互联网搜索并列出最相关的几个歌 曲，并让用户选择是否下载歌曲资源。 想将手机模式设为静音，输入“静音”，到“设置分类视图里快速定位设置 手机模式的选项，按次键便可将手机模式设置成想要的方式。 1 3 内容安排 本文将重点介绍适用于手机的引擎的核心策略索引策略和搜索策略，结合笔者 所做的工作，本文的结构安排如下： 第一章，阐述本文的研究意义，研究目标和所做的工作。 第二章，分析经典引擎l u c e n e 优劣，并在参考其框架设计思想的基础上，提出本 文引擎h a w a i i 的架构及设计。 第三章，结合手机系统结构的特点，研究并设计了引擎h a w a i i 的索引策略，重点 包括文本预处理、索引的建立、索引的维护以及引擎索引模块对外提供的应用程序接口。 第四章，针对手机系统的特性，研究并设计了h a w a i i 的搜索策略，重点包括搜索 的查询策略、搜索结果去重与过滤算法、结果的排序算法以及搜索模块对外提供的应用 程序接口。 第五章，实现了第三、四章设计的h a w a i i ，然后将h a w a i i 应用于g o o g l ea n d r o i d 移动平台，并对引擎进行了评测。 一4 一 大连理工大学硕士学位论文 2 引擎框架研究与设计 本章将首先介绍应用广泛的经典引擎框架l u c e n e 的设计特点，并分析其相对于手 机这种嵌入式系统平台的不足。针对这些不足，在本章后半部分，提出了本文引擎h a w a i i 的特点并介绍了其系统框架的设计。 2 1 经典引擎l u c e n e 分析 l u c e n e 5 1 是a p a c h e 软件基金会项目，是一个开放源代码的全文检索引擎工具包，即 它不是一个完整的全文检索引擎，而是一个全文检索引擎的架构，提供了完整的查询引 擎和索引引擎，部分文本分析引擎。l u c e n e 的目的是为软件开发人员提供一个简单易用 的工具包，以方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整 的全文检索引擎。 作为一个开放源代码项目，l u c e n e 从问世之后，引发了开放源代码社群的巨大反响， 程序员们不仅使用它构建具体的全文检索应用，而且将之集成到各种系统软件中去，以 及构建w e b 应用，甚至某些商业软件也采用了l u c e n e 作为其内部全文检索子系统的核 心。a p a c h e 软件基金会的网站使用了l u c e n e 作为全文检索的引擎，i b m 的开源软件 e c l i p s e2 1 中也采用了l u c e n e 作为帮助子系统的全文检索引擎，相应的i b m 的商业软 件w e bs p h e r e 中也采用了l u c e n e 。l u c e n e 以其优异的索引结构、良好的系统架构、开 放源代码的特性获得了越来越多的应用。 l u c e n e 作为一个全文检索引擎，其具有如下突出的优点： 索引文件格式独立于应用平台。l u c e n e 定义了一套以8 位或字节为基础的索引 文件格式，使不同平台的应用或兼容系统能够共享建立的索引文件。 在传统全文倒排索引的基础上，实现了分块索引，并且能够针对新的文件建立 小文件索引，提升索引速度。然后通过和原有小索引的合并操作，达到优化索引效率的 目的。 优秀的面向对象的系统架构，使得学习对l u c e n e 进行扩展的难度降低，方便扩 充其新功能。 l u c e n e 设计了独立于文件格式及语言的文本解析接口，索引器通过接受单词流 完成索引文件的创建，用户扩展新的语言和文件格式，只需要实现文本分析的接口。 已经实现了一套默认的功能强大的查询引擎，用户无需自己编写代码就可以让 系统获得强大的查询能力，l u c e n e 的查询引擎中默认实现了布尔操作、模糊查询( f u z z y s e a r c h ) 等等。 手机桌面搜索引擎的研究与实现 l u c e n e 【6 l 作为一个优秀的全文搜索引擎，其系统结构具有良好的面向对象的特征。 首先是通过抽象将系统的核心组成部分设计为抽象类，具体的平台实现部分设计为抽象 类的实现，其次，定义了一个与平台无关的索引文件格式，此外与具体平台相关的部分 比如文件存储也封装为类，经过层层的面向对象式的处理，最终达成了一个高效率低耦 合，容易二次开发的搜索引擎系统。 图2 1l u c e n e 系统结构与源码组织图 f i g 2 1 l u c e n es y s t e ms t r u c t u r ea n ds o u r ec o d eo r g n i z a t i o n 图2 1 中可以清楚的看到，l u c e n e 系统由对外接口、索引核心、基础结构封装三大 部分组成。其中，面对索引文件对其进行直接操作的索引核心是系统的重点。从面向对 象的观点来考察，l u c e n e 应用了最基本的一条程序设计准则：引入额外的抽象层以降低 耦合性。首先，引入对索引文件的操作o r g a p a c h e 1 u c e n e s t o r e 的封装，然后将索引部分 的实现建立在( o r g a p a c h e 1 u c e n e i n d e x ) 其之上，完成对索引核心的抽象。h a w a i i 将参 考这一设计，在索引文件存储的上一层加入索引文件数据存储抽象层。在每一个局部细 节上，比如某些常用的数据结构与算法上，l u c e n e 也充分的应用了这一条准则。在高度 的面向对象理论的支撑下，使得l u c e n e 的实现容易理解，易于扩展。而在设计h a w a i i 时本文也将参考这一准则。 l u c e n e 在系统结构上的另一个特点表现为其引入了传统的客户端服务器结构以外 的应用结构。l u c e n e 可以作为一个运行库被包含进入应用本身中去，而不是做为一个单 一6 一 大连理工大学硕十学位论文 独的索引服务器存在。这自然和l u c e n e 开放源代码的特征分不开，但是也体现了l u c e n e 在编写上的本来意图：提供一个全文索引引擎的架构，而不是实现。h a w a i i 也将以此形 式存在。 搜索应用程序和l u c e n e 之间的关系如图2 2 所示，图中也反映了利用l u c e n e 构建 搜索应用程序的流程。同时，也反映了本文h a w a i i 引擎与应用程序的关系。 应 用 程 序 图2 2 搜索应用程序和l u c e n e 之间的关系 f i g 2 2 r e l a t i o nb e t w e e na p p l i c a t i o na n dl u c e n e 2 2h a w aii 引擎特点 l u c e n e 虽然具有2 1 节中提到的很多优点 7 1 ，但是其内部的索引策略和搜索策略却 不太适用于手机系统。 首先，l u c e n e 源码采用j a v a 编写，当然也有c + + 版本，对手机系统而言，无论是 在可移植性和效率上都不能让人满意。 其次，l u c e n e 的优势在手机上转化为劣势，l u c e n e 的劣势是通用性，大而全，而 手机却是嵌入式系统，要求专用性能，要求简而精。于是，l u c e n e 如果应用于手机势必 导致其代码效率的低下。因为在实际实现时某些功能并不使用，导致代码效率在空间上 有浪费，对手机系统来说是不能容忍的。 本文在总体架构上参考了l u c e n e 的设计，但是在索引和查询策略上针对1 2 中分析 的手机结构特点，重新进行了需求分析和策略设计，这将是第三、四章重点阐述的内容。 手机桌面搜索引擎的研究与实现 在完成具有针对性的设计与实现之后，本文的搜索引擎核心h a w a i i 将希望具有以下五 个特点： ( 1 ) 索引文件小且易于伸缩 由于手机“短小文件居多”且“存储空间小”，引擎的索引文件应尽量小从而节省空间。 再者，索引文件不易伸缩，索引的伸和缩是指索引数据的添加和删除，尤其是删除索引 的代价很高。该过程通过开发人员来实现极其复杂。为了解决此问题，本文引擎将采用 轻量级开源数据库引擎s q l i t e 3 来管理索引数据。 ( 2 ) 用户等待时间短 目前，智能手机运行频率受到电池等各方面的限制，c p u 性能远低于p c 机。如果 搜索时结果集的数据量很大，用户需等待的很长时间。此情况只能通过更有效的用户体 验来弥补手机性能不足。引擎将索引和搜索设计成异步模型，引擎将分阶段返回索引状 态或搜索结果。在很短的时间后即可得到第一批结果返回从而提升用户体验。 ( 3 ) 跨平台应用 手机常用操作系统多样，如w i n d o w sm o b i l e 、w i n dr i v e r 、s y m b i a n 、a n d r o i d 、p a l m 等。为了让引擎适用于大部分手机，本文采用跨平台性良好的c 语言和p o s i x 标准编 码。 ( 4 ) 支持多语言、多格式 为尽可能的支持各种语言英语，德语，汉语等，引擎的索引数据采用u t f l 6 编码， 这种编码格式几乎覆盖了世界上所有的语言文字。另一方面，为了支持多种语言，引擎 中需要设计不同的语言分词器。同时，手机存有各种格式的数据，如s m s 、c a l l l o g 、 c o n t a c t s 、e m a i l 等。为便于找到不同类型的数据，引擎对多格式数据的支持也是很有必 要的。 ( 5 ) 索引实时更新 为了在手机运行过程中引擎的索引文件能够实时体现出手机的实时状态，如手机接 收到一条短信，在搜索引擎上能够立即查询出此条短信。而当删除某条短信后，立即使 搜索引擎不能检索出此短信。也就是说，无论手机文档的增加、删除、更新都能够触发 索引文档的实时更新，而不需要整体进行重新索引。 2 3h a w aii 引擎框架 针对以上对h a w a i i 提出的希望具有的五个特点，在参考l u c e n e 的设计准则：“引 入额外的抽象层以降低耦合性”后，设计出如图2 3 所示的h a w i i 引擎软件架构。 一8 一 大连理工大学硕十学位论文 异步任务管理模块( 索引与搜索) 文档分析器搜索串分析器 索引模块密搜索模块 索引数据存储抽象层 s q l i t e 3 数据库接口 文件系统接口 手机存储系统 图2 3 引擎软件架构 f i g 2 3e n g i n ea r c h i t e c t u r e 高层 底层 其中，“索引模块完成文档分析、分词及索引功能。此模块中，统一格式文档、 分词、倒排索引信息、索引策略和存储方式都进行了针对性的设计，这些将在接下来的 第三章进行详细地介绍。 “搜索模块”完成用户的查询请求，其中h a w a i i 自定义一套简化的查询语句、给 出了按匹配模式检索的策略以及提出了“点击频率 的概念及其存储方案和运算流程和 公式。这些将在第四章进行详细介绍。 “索引数据存储抽象层”的加入使得“索引模块 和“搜索模块”的实现不需要依 赖或者关心索引数据的存储方式，可以灵活使用s q u t e 3 管理索引数据和使用文件系统 直接管理索引文件两种方式。这里参考了l u c e n e 的设计原则。 “异步任务调度模块”完成各个异步索引和搜索任务的调度和回调功能，实现异步 分批次结果返回的功能，提高用户体验。 “多语言分词器”为“索引模块”和“索引模块 提供多语言支持。在实现中，h a w a i i 对外提供了一个分词器回调接口，可以让开发者提供自己的分词器。而且h a w a i i 也提 供了两个缺省的分词器来完成简单的分词，参见3 3 1 。 “文档分析器 负责将多种文档格式( s m s ，e m a i l 等) 转换成统一的索引前文档 格式，h a w a i i 自定义了有别于搜索引擎中常用的x m l 的中间文档格式，参见3 2 1 。 “搜索串分析器 完成与“文档分析器”类似的功能，将不同的搜索字符串转换成 本文自定义的搜索字符串格式。 本文的引擎架构虽然与l u c e n e 等引擎没有明显差异，但是各模块的设计和实现却 有很大不同，从下一章开始，将详细阐述引擎各主要模块的设计思想。 手机桌面搜索引擎的研究与实现 3 索引策略研究与设计 索引是现代搜索引擎的核心，建立索引的过程就是把源数据文档处理成非常方便查 询的索引文件的过程。试想用户如果现在要在大量的文档中搜索含有某个关键词的文 档，那么不建立索引的话就需要把这些文档按顺序读入内存，然后检查此文档中是否含 有要查找的关键词。如此，就会耗费非常多的时间。想想搜索引擎可是在毫秒级的时间 内查找出结果的1 8 j ，这是瞬间就能完成的事情。这是由于搜索引擎建立了索引的原因， 可以把索引想象成这样的一种数据结构，它能够使随机访问存储在索引中的关键词更加 快速，进而找到该关键词所关联的文档。经常采用的索引机制是一种称为反向索引或者 说倒排索引( i n v e r t e di n d e x ) 的机制【9 j 【1 0 】。反向索引( 或倒排索引) 就是说引擎维护了 一个词语或短语表，对于这个表中的每个词语或短语，都有一个链表描述了有哪些文档 包含了这个词或短语。如此，在用户输入查询语句的时候，就能非常快地得到搜索的结 果。通常，建立索引的流程都需要经过如图3 1 所示的步骤。 图3 1 索引流程示意图 f i g 3 1 s k e t c hm a po fi n d e x i n gp r o c e s s 3 1 术语定义 本文涉及到各种文件数据，在其他领域中的定义可能都不一样。本节为了让表述更 加清晰并使文中的常用词语的含义保持一致，对本文常用的术语进行定义如下： ( 1 ) 文档( d o c u m e n t ) 被索引的各种格式文档，如短信息( s m s ) 、通话记录( c a l l l o g ) 、图片( i m a g e s ) 、 视频( v i d e o ) 等等。 ( 2 ) 单词项( t e r m ) 大连理一 大学硕十学位论文 文档中词汇分割的最小单位。 ( 3 ) 域( f i e l d ) 文档中的元数据信息及文档内容，如e m a i l 中含有标题域、发送者域、接收者域和 正文域等等。 ( 4 ) u r i 统一资源标识符( u n i f r o mr e s o u r c ei d e n t i f i e r ) 。这罩表示的是文档在手机里的唯 一标识。如在g o o s ea n d r o i d 系统中某短信的u r i 为：c o n t e n t ：s m s 2 。 ( 5 ) 域类型值( f i e l d t y p e ) 在h a w a i i 中用整数来表示域的类型，如5 表示短信的发送者等等。 ( 6 ) 文档号( d o c l d ) 被索引的文档在索引文件中的序号，也表示了文档在索引时的先后顺序。 3 2 文本预处理 搜索引擎需要处理各种格式和类型的文章和数据，所有文档都需要经过预处理和分 词过程【1 l l 。不同语言文字的预处理和分析过程各有差别，但预处理的目的和结果基本一 致。预处理后的文档是一系列基本语素单元的集合，通常会根据文本的统计特性，去掉 部分连接符。 预处理功能包含了一系列的过程，不同的操作次序往往会得到不同的结果。通常采 用固定的模式，以一定的流程来处理。基本的处理流程是文档格式转换、词汇分割、词 汇过滤、结果输出，索引或者查询操作【1 2 l 【1 3 】。在这一节接下来的部分将按文本处理的流 程顺序介绍索引文本预处理的每个步骤，其中词汇分割( 即分词) 部分参见3 3 2 。 3 2 1中间格式定义 s 髑lc a - 1 b g 量皿t ：j 妇g e 墨 、l 统一的中间格式 - 图3 2 统一的中间格式 f i g 3 2 u n i f o r m a td o c u m e n t 手机桌面搜索引擎的研究与实现 由于手机系统文件格式多种多样，有s m s 、c a l l l o g 、p d f 、w o r d 、h t m l 等等。 引擎不可能对每一种文件格式的文件按不同的方法索引，于是，越来越多的人想到用标 准的中间格式作为自己引擎的数据输入接口。 通过解析程序解析成统一的中间格式，这样引擎便可以不用关心被索引文档的类 型，统一对不同的文件按相同的方式进行数据索引。通常，这种中间格式主要以x m l 为主，如图3 2 所示。 这一节要解决的问题就是对各种手机中的文档预处理成统一的中间格式供引擎索 引。x m l 虽然在传统引擎中应用比较广泛【1 4 】，但是手机的特点决定了x m l 并不太适 合成为本文引擎的中间格式。因为采用x m l 具有如下缺点：首先，每份文档需要存储 多余的x m l 标记，浪费空间；其次，引擎端需要额外的x m l 分析器识别并过滤x m l 标记，这样必然降低引擎效率。 对此，本引擎定义了自己的统一中间格式( u n i f o r m a td o c u m e n t ) ，所有格式的文 档将在预处理中被转换成如图3 3 所示的文档。 域的个数n 域l 的类型 域1 的内容 域2 的类型 域2 的内容 n 对自非 域n 的类型 域n 的内容 息 图3 3 本引擎自定义中间文档格式 f i g 3 3i m p r o v e du n i - f o r m a td o c u m e n t 其中， “域的个数( f i e l d c o u n t ) 和“域的类型( f i e l d t y p e ) 为整数值，分别 表示文件中包含的域的个数和每个域的类型，“域的内容( f i e l d c o n t e n t ) ”则为每个域 的内容，开发人员可以自定义各个f i e l d t y p e 并根据不同类型的被索引文件动态伸缩该 格式文档。 人连理t 大学硕士学位论文 举例说明，有一条如下的短信： 可以将其转换成统一索引前文档格式为： 第一行的“4 ”，表示接下来有“4 个域”； 第二行的“1 ，表示此域存储的是“被索引文件的u r i ( u n i v e r s er e s o u r c e i d e n t i f i c a t i o n ) ”； 第三行的“c o n t e n t ：s m s 6 ”，表示此短信的u r i ； 第四行的“2 ”，表示此域存储的是“文件类型”； 第五行的“6 ，表示被索引文件为短信( 文件类型是自定义的) ； 第六行的“5 ”，表示此域存储的是“文件正文”； 第七行，表示此被索引文件的正文内容为“ia mw a i t i n gf o ry o ua tn a n j i n gr o a d ”； 第八行的“7 ，表示此域为“发送者”； 第九行则为发送者的名字“j o ex i e ”( 如上表示域的整数值根据不同应用可以定义 不同的值) 。 此方法的优点在于此格式文档通过内存传递且在引擎的索引模块端易于分析，这样 可以提高文件从应用程序到引擎的转换和传递速度。当然，此方案也有缺点，那就是在 异步模型中同一时间将存放多份统一格式文档从而增加内存的消耗。但是在同步模型中 同一时间只存储一份，因此并不存在类似缺点，而且其可读性和可调试性不如x m l 。 在比较上述优缺点与x m l 的优缺点后不难得出自定义的中间格式更适合手机搜索引 擎。 手机桌面搜索引擎的研究与实现 3 2 2 停用词过滤 为节省存储空间和提高搜索效率，搜索引擎在索引页面或处理搜索请求时会自动忽 略某些字或词，这些字或词即被称为s t o pw o r d s ( 停用词) 。 通常意义上，停用词大致为如下两类： ( 1 ) 这些词应用广泛，在因特网上随处可见，比如“w i n d o w s 一词几乎在每个 网站上都会出现，对这些词搜索引擎无法保证能够给出真正相关的搜索结果，难以帮助 缩小搜索范围，同时还会降低搜索的效率。 ( 2 ) 第二类词包括了语气助词、副词、介词等，只有将其放入一个完整的句子中 才有一定作用，如常见的“的 、“是之类。举例来说，比如“i t 行业”，虽然其中 的“f r ”的原来是指“i n f o r m a t i o nt e c h n o l o g y ，而且这种缩写能够为大多数人接受， 但对搜索引擎来说，此“i t ”也可理解成“i t ，即“它”的意思，这在英文中是一个 极其常见同时意思又相当含混的词，在通常情况下将被忽略。 在内容中适当地减少停用词出现的频率，可以有效地帮助引擎提高关键词密度，而 在网页中避免出现停用词往往能够让h a w a i i 优化的关键词更突出。尤其是在手机中停 用词的过滤更加重要，由于停用词在文档中占有很大比例，进行停用词过滤可以大幅度 地降低索引存储空间的消耗。 在设计停用词过滤器时，需要考虑的问题是如何快速判定单词是否为停用词。本文 使用静态哈希方式存储停用词列表f 1 5 】，这样可以快速定位是否在停用词列表中。 3 3 索引的建立 3 3 1 词汇分割 在采用倒排索引作为搜索引擎的核心结构后，词汇分割就成了不可避免的一个环节 ( 后面将“词汇分割”简称“分词”) 。然而由于全世界语言类型丰富，各种语言的语 法结构都不相同，因此词汇分割的实现部分不可能都放在引擎核心中实现，而需要各国 开发人员根据需要来提供。考虑到这一点，h a w a i i 在设计中提供一个分词器接口，让开 发人员在开发应用程序时提供特定的分词器函数入口。详细的描述请参看3 6 节中索引 模块的i n i t l n d e x e r 接口。， 在此基础上，h a w a i i 只在引擎核心中实现了两种比较常用的分词逻辑：第一种只是 简单根据文档的天然分隔符如空格，逗号，句号等处理欧洲拉丁文；第二种是在第一种 的基础上加入对中文的简单处理，即对中文词按单个词进行分隔i l6 。，如，将“g o o d b y e ! 大连理工大学硕士学位论文 小王! ”分词成“g o o d b y e ”、“小”和“王 三个词条。此分词方式已基本能够解决中文 搜索的功能需求。 由于目前的中文自动分词方法的分词正确率都不能保证达到1 0 0 ，所以肯定有被 误分割的词汇。为了解决这个问题，有人提出在使用自动分词后结合单个词分割的结果 i l l 。这种方式固然好，但是必然导致更高的空间消耗，在手机系统上是不太理想的方法。 为了查全且节省空间，本文并不将单个词分割与自动词语分割相结合，而是只使用单个 词分割的方法。但是，按单个词分割并不能很好的将天然的短语词组组合在一起，有可 能出现搜索“术语时，出现“语术”的结果。为了弥补这一缺点，本文将过滤非 分词顺序的结果，在索引存储时按照分词的先后进行存储。比如“术语的分词顺序是 先“术”后“语 ，在索引中每条索引项都有一个序号，“术的索引项序号要大于“语”。 在查询结果合并时，将根据索引项的序号排除那些语序不正确的结果。