一个借助查询历史改善结果排序的文件检索系统的设计与实现--硕士毕业论文.doc

北京大学硕士研究生学位论文题目：一个借助查询历史改善结果排序的文件检索系统的设计与实现姓 名： 学 号： 院 系：信息科学技术学院专 业：计算机系统结构研究方向：计算机网络与分布式系统导 师： 52版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。摘 要随着网络的发展，网络上提供文件共享服务的服务器越来越多，共享的文件数量也随之增加。如何更好的检索、利用这些共享文件成为一个重要的问题。针对用户对文件检索的需求，本文在文件检索技术领域有如下贡献。1. 本文首先提出了一个文件检索的模型，明确了在文件检索模型中检索对象、查询串、查询与检索对象的匹配方式三部分的含义。检索对象，即文件条目表示为六元组name, ext, size, date, site, path的形式，查询串表示为以空格分隔的字符串的集合，查询与检索对象的匹配则表示为查询串与文件条目的匹配串之间的匹配。2. 提出了对文件检索系统进行评测的指标。将查询结果视作集合时以查全率、查准率为评测指标。将查询结果视作有序序列时，分析了查询结果的相关性、连接下载速度以及结果的可用性等因素对排序的影响，并提出了对排序进行评测的指标排序指数。作者还提出对于两个排序策略进行比较时，应当在结果的每个页面内部应用排序策略，而不是在全体结果集合上应用排序策略，并比较平均用户选取条目的页内排名。3. 通过统计、分析用户对文件搜索引擎的检索和对检索结果中下载地址条目的选取，作者发现了用户行为习惯中的两个重要规律：一、少数查询串占据了全部查询请求的大多数，具体而言，前20%的热门查询串占据了全部查询请求的80%；二、对全体用户而言，假设有n次不同的查询请求使用了同一个查询串，并且它们代表k类不同的查询意图。那么通常k3，因而在n较大的情况下，则n/k的值较大，即大量的来自不同用户的请求代表了相同的查询意图。4. 基于上文所述，作者设计并实现了一个真实的系统。该系统借助查询历史改善结果的排序。与一般基于用户历史信息的检索系统不同的是，本系统借助的历史信息不局限于当前用户的历史信息，还包含提交了相同查询串的其他用户的查询信息。或者说，即使当前用户是第一次使用本系统，本系统也能利用其他用户的历史记录来改进结果的排序和筛选。作者最后还验证了其实际的效果。应用本方法后，平均用户选取条目的页内排名从原来的13.70名前进到了8.93名。试验结果表明文中所做的分析是正确的。关键词：文件检索系统，查询历史，检索模型The Design and Implementation of a File Index System which Improve the Order by Query History AbstractWith the rapid expansion of the Internet, there are more sharing file servers. And the number of sharing files is increasing rapidly too. So its more important to retrieve these files easily.For the requirement of file retrieving of the users, we did the following jobs:1. We proposed a file index model. The model is composed of the expression of an index object, the expression of a query, and how the query word matches the index object. The index object can be expressed as name, ext, size, date, site, path, the query string is expressed as strings separated by space, and the matching between query and index object is realized by matching the query string and the matching strings of the file item.2. We also proposed the evaluation indicator for the file index evaluation. The precision and recall are useful when we evaluate the query result. But the result is not a set, but an ordered list. So we indicated the factors in order: the relativity of the item, the connecting and download speed and the availability of the site. We proposed how to evaluate the order: average rank of chosen items. If we just want to compare two ranking strategy, we should not reorder all items in the result set but only reorder the items within each page and compare the average rank of chosen items within page.3. By analyzing the records of users queries and the file items that users chosen from a real file search engine, we discovered two lows. 1). Most query strings are repeating hot query strings. 80% query words are the top 20% hot query strings. 2) If there are n times of queries using the same query strings, and the total number of different intensions is k. Then k should be a very small number (usually, k4), and n/k is a large value if n is large enough. It means, lots of queries using same query string are with the same intension.4. Based on the above work, we designed and realized a system, which is based on users queries history and improves the rankinge of the items. This system is not only based on the history of the current user, but also other users who submitted the same query words. That means the system can improve the ranking for a usere, even hee/she is new to it. With the new system, the average chosen item within a page is improved from 13.70 to 8.93. Ite verified our research.Keywords: file search engine, query history, index model目 录第1章引言11.1研究背景11.1.1文件检索系统的发展历史11.1.2文件检索系统的发展现状21.1.3目前遇到的问题31.2本文的研究内容41.3本文贡献41.4本文组织5第2章文件检索系统及相关研究62.1文件检索系统的基本使用方法62.2常规文件检索系统体系结构72.3文件搜索引擎与网页搜索引擎的比较72.4文件搜索引擎对查询结果的排序和过滤82.4.1排序82.4.2过滤82.5基于用户反馈信号的文件检索系统9第3章文件检索模型103.1检索对象的表示103.1.1文件服务器返回的原始信息103.1.2文件属性的演化113.1.3文件的最终表示123.2查询的表示方式133.3查询与文件的匹配过程133.4文件检索性能的评测指标133.5排序准确程度的评测指标143.5.1影响排序的因素143.5.2对排序进行评测的方法153.5.3排序指数183.6比较排序策略的一个简便方法19第4章用户行为特点分析204.1查询串的特点204.2用户查询意图的特点224.3用户行为特点的启发25第5章系统体系结构与主要算法275.1系统体系结构275.2主要算法285.2.1用户点击日志的表示285.2.2计算文件条目之间的距离295.2.3对用户点击记录进行聚类345.2.4对查询结果集合进行分类36第6章系统实现与评测376.1系统设计体系结构图376.1.1用户行为收集部分376.1.2聚类部分386.1.3索引部分386.2其它实现中的问题386.2.1记录用户对查询结果的选取386.2.2文件类型属性距离计算方法的实现396.3系统的评测环境416.4评测结果41第7章总结与展望437.1总结437.2展望437.2.1目录437.2.2压缩文件类型43参考资料45附录：文件类型列表47作者就读期间参加的科研项目和发表的论文50致谢51 图目录图 21 文件检索系统使用示例6图 22 常规文件搜索引擎体系结构图7图 23 基于反馈信号系统的标准模型9图 31 Serv-U FTP服务器接收LIST命令后返回的信息10图 32 文件检索性能评测示意图14图 33 理想检索系统排序方式16图 34 系统排序比较17图 41 用户查询串集中程度分析21图 42用户查询串分布的函数拟和22图 43查询串与查询意图种类比值分析25图 51 系统结构图27图 52 文件扩展名属性距离计算32图 53聚类示意图35图 61体系结构图37图 62 ext属性距离计算方法的实现40图 63系统试验效果比较42表格目录表格 11主要文件检索系统量化比较2表格 12主要文件检索系统查询结果数量示例3表格 21网页搜索引擎和文件搜索引擎比较8表格 31文件各属性信息说明12表格 32文件条目的最终表示形式12表格 33系统排序比较17表格 41用户查询意图抽样统计23表格 42查询串查询次数与用户查询意图种类比值23表格 43 查询意图统计分析24表格 51 文件条目各个属性数据类型30第1章 引言1.1 研究背景1.1.1 文件检索系统的发展历史万维网（World Wide Web，简记为Web）是因特网上最成功的应用，起源于1989年欧洲粒子物理研究室CERN。Web的最初计划是由CERN的物理学家Tim Berners-Lee于1989年3月提出的，第一个基于文本的原型于18个月后运行。除web外，网络上还存在着其它形式的服务，如FTP服务器提供的文件共享服务等。本文的研究对象就是文件共享服务。在FTP服务器出现多年后，又出现了P2P文件共享系统，比如Kazaa，天网maze等，他们同样提供了对文件的下载服务。基于web的网页数量大量增加，推动了以网页为检索对象的搜索引擎的出现。而类似的，FTP和其他文件共享系统中共享文件数量的增加，也促使文件检索系统、尤其是文件搜索引擎的出现和发展。最早的文件搜索引擎是基于文本显示的Archie。Archie实际上是一个大型的数据库，再加上与这个大型数据库相关联的一套检索方法。该数据库中包括大量可通过FTP下载的文件资源的有关信息，包括这些资源的文件名、文件长度、存放该文件的计算机名及目录名等。可以通过远程登录到Archie主机来使用Archie服务器，用Archie作为登录名。一旦登录成功，一个Archie程序将自动执行，这时每次输入一条命令，告诉Archie想查寻的内容，Archie将检索自己的数据库并显示检索的结果。如果用户对自己想要的东西并不太清楚，Archie还提供“whatis”服务项目，该服务提供成千上万个程序文件、数据文件和文档的简短说明。 WWW的出现改变了Archie在文件搜索方面的统治地位，在美观、方便的WWW页面上搜索FTP文件成为用户的自然需求，即人们需要有一种基于Web的FTP搜索引擎。在功能上，基于Web的FTP搜索引擎与Archie基本一样，都是对用户提交的查询串进行匹配找到可以下载的FTP站点文件的链接。1.1.2 文件检索系统的发展现状目前应用较为广泛的文件检索系统以表现形式分类主要有基于web的文件搜索引擎和内嵌于共享软件的文件检索系统两种形式。一般FTP搜索引擎以web形式居多，P2P软件则以软件内嵌的形式居多。Web形式的著名的文件搜索引擎有：n 天网千帆文件搜索引擎（）n 星空文件检索系统（n Philes ()n Alltheweb ()P2P文件共享系统有n 天网maze ()，n kazaa()下面我们对一些著名的文件检索系统作一以简单比较：表格 11主要文件检索系统量化比较搜索引擎名称文件条目总数（条）站点数量（个）天网FTP搜索引擎13,000,00046065209,698,206没有统计没有统计没有统计76,039,149没有统计18,216,064238837,813,0402,683星空搜索没有统计没有统计天网maze文件共享系统160,000,000100,000从使用方式上讲，不论哪种形式的检索系统，基本上都是相同的。一般是用户在查询框中输入查询词，搜索引擎返回包含该查询词的文件条目信息。文件条目信息通常包括文件名称、大小、时间、下载地址等。从工作原理上讲，现在主流的文件搜索引擎采用了和web搜索引擎类似的系统：首先启动多个网络爬虫，对待检索的文件服务器进行抓取，得到全部文件的描述信息（如文件或目录的名称，时间、大小、路径等）。然后对全部ftp文件建立索引（通常是倒排表索引），索引建立完成后则可以启动服务。当用户提交查询给检索系统时，系统返回包含该查询词的所有文件条目。1.1.3 目前遇到的问题从搜索引擎系统本身的结构上讲，文件搜索引擎和基于web的网页搜索引擎的结构非常相似。但从研究和搜索精度的角度来讲，文件搜索引擎和网页搜索引擎的差距是非常明显的。抛开商业、应用等因素，只从理论和技术等方面分析其原因，能够发现web上的网页和文件系统（此处以FTP为例）中的文件所能提供的信息量的差别是很大的。Web上的网页既可以看成是一个文本文档，又有着丰富的格式描述信息，还有彼此的链接关系。而文本检索本身已经比较成熟，此领域又有深入的研究。网页之间的链接关系又使图论在此能够得到深入的应用。相对于web上的网页，文件共享服务器能提供的文件信息则少的多。全部信息只是名称、大小、时间、路径等；而且各个站点彼此又是完全独立的，没有任何联系。文件名本身的命名又带有很多的个人习惯，没有太多的规律可循。所有这些特点使得一般的文档检索方法以及常规搜索引擎的处理办法在对文件的处理上都不再适用，因此文件搜索引擎检索的效果普遍不高。而与之相对应的是，目前文件共享服务的数量和规模都在大幅度的增加，用户的需求也在不断的膨胀。作者曾于2005年4月对在中国教育科研网上公布的全部免费IP地址进行过一次全网的FTP服务扫描，共发现了370,222个开放的FTP服务器。在当时天网千帆文件搜索引擎的文件索引量也已经达到了2700万。可见目前对文件共享服务的应用和需求都是非常广泛的。目前在这些常用文件搜索引擎中进行检索时，往往得到了大量的检索结果。比如下表显示了在上面提到的几个主要文件服务器中检索常用软件“winzip”和操作系统“linux”时返回的结果数量。表格 12主要文件检索系统查询结果数量示例搜索引擎名称查询winzip的返回结果数量查询linux时的返回结果数量天网FTP搜索引擎194332,4792249超过24,000170068,000超过2000超过2,000超过1000超过1,0003200超过20,000星空搜索227460,027天网maze文件共享系统5945202从表中可见，返回的结果数量都相当之大，而到目前为止，文件检索尚没有一个行之有效的排序方式（比如pagerank之于web搜索引擎），只是单纯的返回在文件名称中包含用户的查询词的条目，因此搜索结果中有大量并不是用户所需要的结果。而用户面对如此大量的查询结果，从中选取真正准确的文件条目也是非常繁琐的事情。所以说，对常规的文件检索系统进行改进，提高其检索准确度是目前文件搜索引擎发展的当务之急。1.2 本文的研究内容本文中的研究主要围绕以下几个方面开展：首先对文件检索系统本身进行研究，建立文件检索模型，并提出评测方法；在对真实文件检索系统进行数据记录的基础上，分析用户对文件搜索引擎的使用行为的习惯和特征，挖掘其中的规律；最后根据发现的用户行为的规律，尝试提出新的文件检索系统，来提高检索的精度。1.3 本文贡献本文在文件检索技术领域有如下贡献。本文首先提出了一个文件检索的模型，明确了在文件检索模型中检索对象、查询串、查询与检索对象的匹配方式三部分的含义。检索对象，即文件条目表示为六元组name, ext, size, date, site, path的形式，查询串表示为以空格分隔的字符串的集合，查询与检索对象的匹配则可以表示为查询串与文件条目的匹配串之间的匹配。提出了对文件检索系统进行评测的指标。将查询结果视作集合时以查全率、查准率为评测指标。将查询结果视作有序序列时，指出了查询结果的相关性、连接下载速度以及结果的可用性等影响排序的因素，并提出了对排序进行评测的指标排序指数。作者还提出对于两个排序策略进行比较时，应当在结果的每个页面内部应用排序策略，而不是全体结果集合应用排序策略，并比较平均用户选取条目的页内排名。通过统计、分析用户对文件搜索引擎的检索和对检索结果中下载地址条目的选取，作者发现了用户行为习惯中的两个重要规律：一、少数查询串占据了全部查询请求的大多数，具体而言，前20%的热门查询串占据了全部查询请求的80%；二、对全体用户而言，假设有n次不同的查询请求了同一个查询串，并且它们代表k类不同的查询意图。那么通常k3，因而在n较大的情况下，则n/k的值较大，即大量的来自不同用户的请求代表了相同的查询意图。基于上文所述，作者设计并实现了一个真实的系统。该系统借助查询历史改善结果的排序。与一般基于用户历史信息的检索系统不同的是，本系统借助的历史信息不局限于当前用户的历史信息，还包含提交了相同查询串的其他用户的查询信息。或者说，即使当前用户是第一次使用本系统，本系统也能利用其他用户的历史记录来改进结果的排序和筛选。作者最后还验证了其实际的效果。应用本方法后，平均用户选取条目的页内排名从原来的13.70名前进到了8.93名。试验结果表明文中所做的分析是正确的。本文的创新之处主要在于以下几点： 提出了一个对排序算法进行实际评测的指标排序指数。并提出了比较两个排序策略的方法：在得到相同的结果集合后，应用排序算法时，应该在每页内部应用各自的排序算法，而不是在全体结果集合中应用排序算法，并比较各自的平均用户选取条目页内排名。并列举了一个反例说明了在全体结果集合中应用排序算法可能出现的评测错误。发现了用户对文件检索系统使用的两个规律：少数查询串占据了全部查询请求的大多数；大量的来自不同用户的请求代表了相同的查询意图。设计并实现了一个基于用户历史信息的文件检索系统，该系统有别于同类系统的最大特点在于：该系统对查询历史的使用不局限于当前用户的历史，而是能够借用其它用户的查询历史。这样，即使面对一个全新的用户，我们同样能够借助以前其它用户的查询历史来改进排序。1.4 本文组织本文首先介绍了文件检索领域的相关背景和现状信息；第2章首先考察了文件检索系统基本情况以及相关的研究工作；第3章建立了一个文件检索系统的模型；第4章分析了用户行为特征并发现了两个重要规律；第5章提出了一个系统。该系统借助查询历史改善结果的排序；第6章讨论了系统实现和实现中的主要问题，并对系统进行了评测，证明了该模型和方法的正确性；在最后一章作者做了工作总结和展望。第2章 文件检索系统及相关研究2.1 文件检索系统的基本使用方法我们这里以天网千帆文件搜索引擎为例，看一下文件检索系统的基本使用方法。假设用户希望下载即时通讯软件“QQ”，于是输入该查询串，得到的结果如下图所示：图 21 文件检索系统使用示例检索系统根据用户输入的查询串，返回所有包含该查询词的文件条目。由于满足条件的文件条目可能非常多，因此会被分为多个页面。用户再从返回的结果中进行选取，点击自己认为准确、快捷的下载地址进行下载。2.2 常规文件检索系统体系结构此处我们以常见的FTP搜索引擎的体系结构来表示文件检索系统的基本结构。它和一般的基于web的搜索引擎的结构类似。下图是其基本的体系结构。图 22 常规文件搜索引擎体系结构图图中各个部分的介绍如下：Site list Database：站点列表数据库。其中存放着可能提供文件共享服务（如FTP服务）的各个站点的列表；Crawler：进行网络抓取的程序，抓取文件共享系统中的文件信息；File item Database：存放全部的文件条目的数据库；Indexer：索引建立程序。根据用户的文件条目建立索引；Index Database：索引库，通常为倒排表结构；Query Server：提供查询服务的程序；Query：用户的查询串。整体工作流程如下：首先Crawler从Site list Database中逐一取出站点，然后对每个站点进行文件信息的抓取。抓取的结果存入File item Database中。当File item Database中有足够多的文件条目信息后，对其建立索引（倒排表）。然后启动Query Server，待用户提交查询串query后，在Index Database中对其进行检索，并返回查询结果。2.3 文件搜索引擎与网页搜索引擎的比较和文件搜索引擎关系最为密切的要属网页搜索引擎了，但二者在研究、应用等方面的差异较大，我们在此做一比较：表格 21网页搜索引擎和文件搜索引擎比较比较内容网页检索文件检索相关研究非常深入很少提供的信息丰富：文本、链接、tag等很少：名称、大小、时间、路径常见处理方法文本分析；超链分析；tag分析单纯字符串匹配搜索的查准率比较高低；冗余信息很多从上面的比较看出，网页检索和文件检索的差异还是非常大的。和网页检索相比，文件检索不论在相关研究还是本身能够提供的信息方面，都和网页检索相差较远。2.4 文件搜索引擎对查询结果的排序和过滤目前的文件搜索引擎对于查询结果的处理普遍比较简单。最常见的方法是不作任何处理，直接进行输出。其它处理方式有：2.4.1 排序文件搜索引擎对于结果的排序方式非常简单，目前能够见到的有如下四种排序方式：按文件大小排序、按文件修改时间排序、按文件名称长短排序、以及按照站点IP地址与查询者IP地址之差（将IP地址直接转化为整数数值进行计算）的绝对值排序。这些排序方式都是按照文件的某种单一属性进行的排序。其排序效果并不是很理想。2.4.2 过滤某些文件搜索引擎提供了按照文件类型进行过滤的方式进行处理，它可以限制搜索结果只显示指定类型的文件扩展名的结果，而忽略那些尽管包含用户的查询串、但并不是所指定的文件类型的文件。从查询效果上来讲，这些排序、处理方式都过于简单了，效果也并不理想。2.5 基于用户反馈信号的文件检索系统一般的，基于用户反馈信号的系统结构如下图所示：图 23 基于反馈信号系统的标准模型对应于我们的检索系统，可以进行如下的理解。系统首先进行初始的检索，得到初始查询结果S0并输出给用户。用户对输出结果进行判断，并将判断结果通知系统，系统根据用户的反馈和初始结果S0进行再运算，得到新的结果S1如此k次迭代，结果将会达到用户满意的程度。在网页搜索引擎中，确实有基于反馈信号的系统存在：用户提交查询串，在检索系统返回初始的结果后，用户再对部分结果进行相关性评分，并将评分结果反馈给系统，系统根据反馈信息和原始结果重新生成新的结果后，再次输出给用户。如此反复几次后，最终得到的结果将是对此用户而言，相关度非常高的结果。但是在实际应用中，尤其是在搜索引擎系统中，用户常常倾向于较简单的操作，多数用户都不愿进行过于繁琐的打分等反馈操作，因此真正的多次迭代很难发生。用户需要的是一种更为简单的方式，并且尽可能将迭代次数k减到最小。在极限情况下，假设用户只需要进行k=0次迭代就可以得到满意的结果。那么这就意味着我们必须能够“预测”用户的真实意图。而本文所研究的重点，就是如何构造这样一个能够预测用户意图的基于反馈的文件检索系统。第3章 文件检索模型建立一个文件检索模型是进行各种后续研究的基础。我们知道，一个检索模型主要包括三个方面：检索对象的表示、查询的表示、以及查询与检索对象的匹配过程。下面我们分别来看这三个方面。3.1 检索对象的表示文件检索系统的检索对象是文件，为了确定其表示形式我们首先考察一下文件共享服务器能够给用户提供的全部信息。3.1.1 文件服务器返回的原始信息对于文件共享系统来讲，其表现形式是多种多样的。但究其内容却大同小异，最早的文件共享服务器是FTP服务器，各种后来出现的文件共享系统基本上都参考了FTP的模式，因此此处我们以FTP为例来对文件的表示形式进行剖析。当我们登陆FTP后，发送列文件目录命令LIST，返回的结果大致如以下形式：图 31 Serv-U FTP服务器接收LIST命令后返回的信息返回结果从左至右共有9列，其中有3列共同构成时间，所以共有7类信息，它们分别是：文件权限位，文件链接数，所有者名称，所有者所在组的名称，文件大小，最后修改时间（占3列）和文件名称。除去显示的这些信息之外，其实还有两项隐含信息，在返回的结果中没有显示，就是当前的站点名称和当前的路径地址信息。以上列出的是应用非常广泛的FTP服务器Serv-U输出的信息。不同的文件共享服务器输出的信息可能不尽相同，比如很多P2P软件并不包含前四项信息（文件属性、链接数、文件所有者和所有者所在组）。一方面考虑到这四项信息的实际检索意义不大，另一方面为了保证模型的统一性和有效性，我们仅仅考虑通用的文件属性。通用的属性有文件名称、最后修改时间、文件大小，另外再加上文件所在的路径。因此对于文件条目，我们将其表示为如下形式（为了便于在后文写入公式中，我们此处用英文表示）：item = name, time, size, path对于FTP来说，很多时候我们只能够得到文件的最后修改日期，而得不到具体时间（指时分秒信息），所以我们将最后修改时间改为最后修改日期，因此得到：item = name, date, size, path3.1.2 文件属性的演化上面的表现形式只是文件的原始属性，为了便于检索等操作，我们需要对其进行适当的演化。首先，文件名称通常可以分为文件主名和扩展名两部分。文件主名一般表示文件所代表的具体内容信息，其信息接收者通常是人；而扩展名则往往表明文件的存储格式和类别，其信息接收者往往是计算机，用于确定该文件的打开（读取）方式。由于这二者的含义是不同的，并不适合放在一起进行处理。因此我们将这二者拆开分别进行处理。文件主名表示为main name，扩展名为ext。在下文中，为了简略，在后面的文章中，为我们仍然使用name来代替main name，来表示文件主名。再者，文件（或目录）所在路径包含站点名称和文件路径两个部分。站点名称可以看作以点号“.”分割的字符串，而路径则是以斜线（“/”）分割的字符串。由于二者的表现形式不同，其代表的含义也有所不同，我们在这里也对其采取分开表示的方式进行处理。并分别称为site和path。最终，我们得到在文件共享系统中，每个文件对象（item）的全部属性如下：item = name, ext, size, date, site, path具体含义为：表格 31文件各属性信息说明属性中文说明注释name文件主名不包含扩展名ext文件的扩展名文件可能会没有扩展名size文件的大小date文件的最后修改日期site站点名称域名或IP地址path路径不含站点名称部分下面我们再来看各个属性项的数据类型：name, ext的数据类型都是字符串形式；size则为整数形式；date虽然默认情况下是一个字符串，但其实表示为一个整数更加利于处理，在具体转换方法上可以表示为对某个固定日期的天数之差；site和path则分别为字符串。除去上文所述，还有两点要特殊说明一下：在实际的FTP服务器中，除了文件之外，还有目录，并且目录也是一种特殊形式的文件。但在很多P2P文件共享系统中，并不包含目录信息，所以在此我们并没有对目录进行考虑。对于文件的扩展名，要注意的是并不是所有的文件都有扩展名，因此一个文件的扩展名是可能为空的。3.1.3 文件的最终表示经过以上分析，一个文件条目最终可以表示为一个6元组的形式：item = name, ext, size, date, site, path具体说明如下表：表格 32文件条目的最终表示形式属性数据类型能否为空说明namestringN文件主名（注：不包含扩展名）extstringY文件的扩展名sizenumberN文件的大小datenumberN文件的最后修改日期sitestringN站点名称（域名或IP地址）pathstringN路径（不含站点名称部分）而一个文件共享服务器就可以看作是多个这样的文件条目的集合。整个网络中的共享文件服务器则可以看成是一个更大的集合。3.2 查询的表示方式对文件检索系统的查询是以查询串的形式出现的。其表现形式为：用户输入一个查询串，提交给系统，系统在所有文件条目中对其进行匹配。该查询串可能为一个字符串或以空格分隔的多个字符串，如果是多个字符串，表示需要包含其中的每个字符串。我们称用户提交的查询为“查询串”query，其数据类型为字符串。如果查询串中包含空格，表示需要系统进行匹配查询串中的全部子字符串。3.3 查询与文件的匹配过程当用户提交了查询串后，系统根据查询串进行匹配、检索。在实际进行字符串匹配的时候，如果单纯只是进行文件名（name和ext部分）的匹配有时是不够的，效果不够理想，因此我们有必要重新构造一个专门用于匹配的字符串。我们称其为“匹配串”。匹配串用于和查询串进行匹配。在简单实现时，匹配串可以用包含扩展名的文件名来替代；但为了得到更好的效果，我们会做一些改变，比如对某些类型的文件采用包含路径（或路径的一部分，如上层目录）、文件名、扩展名的字符串作为匹配串等方式等。查询与文档进行匹配时，将查询串中的全部子字符串与匹配串进行匹配。匹配成功的那些文件条目作为待返回的结果集合。最后将待返回的结果集合中的文件条目按照某种顺序进行排序，并返回给用户。要注意的是，最后返回的结果不是文件条目的集合，而是文件条目的有序序列。3.4 文件检索性能的评测指标参考一般的文本检索系统，最常用的评测指标有查全率和查准率。假设有查询请求I，对文件条目集合进行检索，其中相关的文档集合为R，我们设|R|为集合中元素的个数。对于一个检索策略，我们得到的结果为集合A，类似的，用|A|表示集合A中元素的个数。同时，我们用|Ra|表示R和A的交集的个数，图示如下：图 32 文件检索性能评测示意图查准率查准率用于表示得到结果集合中相关条目的比例。查全率查全率表示了全部相关文档被返回的比例。3.5 排序准确程度的评测指标上面两个是最常用的评测指标，不过在这两个评测指标中，是将查询结果视作集合的方式来进行处