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

《一个借助查询历史改善结果排序的文件检索系统的与实现硕士毕业论文.doc》由会员分享，可在线阅读，更多相关《一个借助查询历史改善结果排序的文件检索系统的与实现硕士毕业论文.doc（60页珍藏版）》请在三一文库上搜索。

1、北京大学硕士研究生学位论文 题目：一个借助查询历史改善结果排序的文件检索系统的 设计与实现 姓 名： 学 号： 院 系：信息科学技术学院 专 业：计算机系统结构 研究方向：计算机网络与分布式系统 导 师： 1 版权声明版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本 论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作 者著作权之问题，将可能承担法律责任。 2 摘摘 要要 随着网络的发展，网络上提供文件共享服务的服务器越来越多，共享的文件数 量也随之增加。如何更好的检索、利用这些共享文件成为一个重要的问题。 针对用户对文件检索的需求，本文在

2、文件检索技术领域有如下贡献。 1. 本文首先提出了一个文件检索的模型，明确了在文件检索模型中检索对象、 查询串、查询与检索对象的匹配方式三部分的含义。检索对象，即文件条目表示为 六元组name, ext, size, date, site, path的形式，查询串表示为以空格分隔的字符串 的集合，查询与检索对象的匹配则表示为查询串与文件条目的匹配串之间的匹配。 2. 提出了对文件检索系统进行评测的指标。将查询结果视作集合时以查全率、 查准率为评测指标。将查询结果视作有序序列时，分析了查询结果的相关性、连接 下载速度以及结果的可用性等因素对排序的影响，并提出了对排序进行评测的指标 排序指数。作者

3、还提出对于两个排序策略进行比较时，应当在结果的每个页面 内部应用排序策略，而不是在全体结果集合上应用排序策略，并比较平均用户选取 条目的页内排名。 3. 通过统计、分析用户对文件搜索引擎的检索和对检索结果中下载地址条目的 选取，作者发现了用户行为习惯中的两个重要规律：一、少数查询串占据了全部查 询请求的大多数，具体而言，前 20%的热门查询串占据了全部查询请求的80%； 二、对全体用户而言，假设有 n 次不同的查询请求使用了同一个查询串，并且它们 代表 k 类不同的查询意图。那么通常 k3，因而在 n 较大的情况下，则 n/k 的值 较大，即大量的来自不同用户的请求代表了相同的查询意图。 4.

4、 基于上文所述，作者设计并实现了一个真实的系统。该系统借助查询历史改 善结果的排序。与一般基于用户历史信息的检索系统不同的是，本系统借助的历史 信息不局限于当前用户的历史信息，还包含提交了相同查询串的其他用户的查询信 息。或者说，即使当前用户是第一次使用本系统，本系统也能利用其他用户的历史 记录来改进结果的排序和筛选。作者最后还验证了其实际的效果。应用本方法后， 平均用户选取条目的页内排名从原来的13.70 名前进到了 8.93 名。试验结果表明 文中所做的分析是正确的。 关键词：文件检索系统，查询历史，检索模型 3 The Design and Implementation of a Fil

5、e Index System which Improve the Order by Query History Abstract With 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 t

6、he 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

7、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 evaluat

8、e 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

9、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 discovere

10、d 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, k5 对应的查询串的 个数 3315

11、781010 从上表可见，查询意图只有 13 个的查询串占全部记录数据的绝大部分，超 过 5 种不同意图的查询串在统计的日志中根本就没有出现。 我们再来看一下 n 和 k 的比例的分布，统计结果如下图。图中横坐标表示查询 串被查询的次数 n，综坐标为 n/k 的比值。要说明一点就是为了使图像中的点线显 示清晰，我们忽略了很少量的查询次数非常高的词（这些点对应的横坐标值非常大） ，但事后的手工验证仍然证明了它们符合本文的规律。 26 1 10 100 1000 01002003004005006007008009001000 图 4-3 查询串与查询意图种类比值分析 其中横坐标为查询串查询次数

12、n， 综坐标为 n/k 比值（为指数标度） 从图中可以看到，当 n100 时，n/k 的值都在 30 以上。 由上面的分析我们能够知道，尽管查询串不同，但一般说来，它们所代表的查 询意图的数量并不是太多的，通常在1-3 种，并且在 n 较大的情况下（如 n100），通常 n/k 的比值较大（本例中大于 30）。因此我们得到了第二个重要的 规律： 规规律律二二：假假设设有有 n 次次不不同同的的请请求求查查询询了了同同一一个个查查询询串串，并并且且它它们们代代表表k 种种不不 同同的的查查询询意意图图。在在 n 较较大大的的情情况况下下（ n100），n/k 的的值值较较大大（ n/k30）。

13、4.3用户行为特点的启发 利用上面的用户行为特点中的两个规律，以及前面关于相关反馈方法的思路， 可以考虑采用如下思路来实现一个借助查询历史信息改善结果排序的文件检索系统。 从上面的特征我们知道，大多数的查询请求不仅其查询串本身是重复的，而且 其所代表的查询意图也是重复的。这样我们就可以由“较早的相同的查询串的结 果选取记录”作为用户的反馈信号。这样一来，后来提交同样查询串的用户不需要 27 任何主动干预，就可以得到经过反馈信号处理过的重新排序的查询结果了。当然， 由于用户意图并不唯一，我们并不能确定究竟本次查询的用户是哪种查询意图，但 因为 k 值通常都相当小（小于等于 3），因此对用户而言，

14、很容易从这为数极少的 查询意图中找到满足自己意图的结果。 具体而言，我们可以考虑如下的思路。 首先记录下每次用户对查询结果的选取。我们认为，用户在查询结果中点击的 下载地址，就是用户认为比较理想的下载地址。通过一段时间的记录，我们就得到 了对于大量查询串的较理想的匹配结果。对于一个查询串q，我们有一个用户认 为较好的文件条目的集合 S，我们将其表示为一个二元组 (q,S)。这样，我们就得 到了大量的这样的二元组。 依据规律 2，我们知道每个查询串可能代表几个不同的查询意图，那么不同的 查询意图对应的理想下载地址肯定不同（否则就是相同的查询意图了），我们可以 采用聚类的方法对每个 S 中的文件条

15、目进行聚类。聚类后，对于每个q，我们会 得到 k 种不同的类别，这 k 个类别就也就反映了不同的查询意图，而每个类别中的 文件条目，就可以看作这个类别的训练集。每个类别中的条目个数，也直接反映了 这个类别的权重。 当再次有用户查询同样的查询串 q 时，我们首先采用原始的检索方法，得到一 个结果集合，然后用聚类得到的 k 个类别和训练集对其进行分类处理。一些条目被 分到这 k 个类别中，另外一些可能不属于任何类别。不属于任何类别的条目往往也 是用户不太需要的条目，可以考虑抛弃或排在结果的最后输出。 28 第5章 系统体系结构与主要算法 5.1系统体系结构 基于以上分析，我们设计了如下的检索系统来

16、改善文件检索系统的排序。 Query String (q) Normal Index System (I) Index Result (S0) Feedback data DataBase Site List DataBase query Clustering The training set for query item q Items not belong to any group Result after Categorizati on (S) Categorization, Ordering Fileitems that user clicked 图 5-1 系统结构图 下面我们来详细

17、介绍这个模型。 我们首先查看模型中的各个组成部分。 Query String (q)：用户输入的查询串； Normal Index System(I)：常规的文件检索系统； Index Result(S0)：初始查询结果集； Feedback Data DB(F)：该数据库中记录了已有的每个查询请求和它对应的不 同的 k 种查询意图，以及每种意图的作为训练集的文件条目。 Fileitem DB(D)：该数据库中保存了每次用户进行检索后对查询结果的选取情 况。具体而言，当用户进行查询后，检索系统返回结果，当用户在结果页面中对文 件条目进行点击并下载时，本模型会记录用户的点击选取行为。库中的每条记

18、录含 有当前的查询串和用户点击的这条记录的具体文件信息：文件名称、扩展名称、最 后修改日期、文件大小、文件所在站点和文件所在的路径。 29 本检索系统的工作流程如下： 数据库 F 中需要足够的数据记录系统才能够进行工作。因此在系统运行之初， 系统便开始自动记录用户的点击，并将记录填充进数据库D。数据库 D 每隔一段 时间，对每个查询串 q 进行一次聚类操作，这样便得到了每个查询串所代表的k 种查询意图。 现在我们假设 F 中已经包含有了足够的记录信息。当用户输入查询串q 后， 一方面，模型中最上面的流程开始工作，常规的检索系统进行检索，得到一个原始 的查询结果 S0。另一方面，如模型图示中的中

19、层的流程， q 被送入数据库 F。数 据库 F 返回对应的 k 种意图和其点击记录集合。这些记录将作为下一步分类工作的 训练集。 有了 S0和这 k 种类别，下面将利用这 k 种类别的训练集对 S0进行分类。分类 后我们将 S0分成了 k+1 类，其中新增加的这个类别是那些不属于任何类别的文件 条目 item 集合。对于不属于任何类别的条目，我们认为它是用户不太关心的结果， 可以把它抛弃或放入输出结果的最后。 这里有一点要注意，就是 k 种类别的地位是不同的，类别本身也是有权重的， 权重可以由聚类时每个类别中的条目数量来决定。这样在最后输出时可以按照权重 本身对类别进行排序。由于 k 的取值通

20、常都比较小（小于等于 3），用户最终看 到的结果往往是接近用户的真实查询意图的。 然后就可以按照一般的条目列表方式或者聚类的树型结构将结果输出给最终用 户。 5.2主要算法 5.2.1 用户点击日志的表示 用户点击日志就是用户所点击的文件条目item。由前面的对文件检索的建模， 我们知道可以表示为： item = name, ext, size, date, site, path 我们将其改写为如下格式： pathsitedatesizeextname xxxxxx 有时候为了简便，我们也会表述为如下形式： 30 654321 xxxxxx 对于查询串 q，价格共有 n 个记录，因此我们得到如

21、下的矩阵： 1,11,21,31,41,51,6 ,1,2,3,4,5,6 ,1,2,3,4,5,6 iiiiii nnnnnn xxxxxx xxxxxx xxxxxx 5.2.2 计算文件条目之间的距离 不论是进行聚类处理还是进行分类处理，都需要进行大量的对两个文件条目 (item)之间的距离 d 的计算。或者说，需要通过上文中的二模矩阵，得到下面的表 示条目之间距离的单模矩阵： 0 (2,1)0 (3,1)(3,2)0 (4,1)(4,2)(4,3)0 (5,1)(5,2)(5,3)(5,4)0 (6,1)(6,2)(6,3)(6,4)(6,5)0 (7,1)(7,2)(7,3)(7,4

22、)(7,5)(7,6)0 .0 ( ,1)( ,2)( ,3)( ,4)( ,5)( ,6).( , d dd ddd dddd ddddd dddddd d nd nd nd nd nd nd n n1)0 图中我们用 d(i,j)表示项 xi和 xj之间的距离，有 d(i,j)0。 当 d(i,j)=0 时表示二者完全相同； 当 d(i,j)0 时表示二者不同，并且 d 的值越大表示文件条目 xi和 xj之间的差 异越大。 对于条目 i 和 j 之间距离的 d(i,j)的计算，我们采用如下加权公式： 31 (,) 1 1 ( ,) ifjf p xx ff p f d f d x x ij

23、 f 由前文文件检索模型可知，此处 p=6。我们分别计算文件条目 i 和 j 的 6 项对 应属性的距离，再进行加权求和最后再进行标准化处理。 由于文件条目的 6 项属性的数据类型和含义不完全相同，因此具体的计算方法 区别较大，在计算时需要分别考虑。 下图为各个属性的数据类型和计算方法。 表格 5-1 文件条目各个属性数据类型 属属性性数数据据类类型型距距离离计计算算方方法法 nameStringMinimal edit distance extStringNominal Variables sizeIntegerInterval-scaled variables dateIntegerInt

24、erval-scaled variables siteStringN/A pathStringSubsection string 具体方法为： 5.2.2.1name 属性距离的计算方法 name 表示文件的不包含扩展名的主名的名称，数据类型为字符串型。对于这种 字符串类型数据的处理，一般情况下可以按照文档的相似度的方式进行。但由于文 件名通常都比较短小，命名多数情况下也不规范。这里并不建议按照文档的形式来 处理。 我们这里采用的处理方法是按照最小编辑距离的方法来处理。 编辑距离是指两个字符串通过插入字符、删除字符、改写字符而变为相同字符 串所需要的操作次数。 比如： d(“abc”,”abd

25、”) = 1 d(“abc”,”ab”) = 1 d(“abc”, “abcdf”) = 2 d(“serverU”,” ser-u”) = 4 利用动态规划的方法计算编辑距离，时间复杂性可以达到O(n2)，空间复杂性 32 为 O（n2）。 计算方法为一个递归算法： d(, ) = 0 d(s, ) = d(, s) = |s| （|s|表示 s 的长度） d(s1+ch1, s2+ch2) = min( d(s1, s2) + （if ch1=ch2 then 0 else 1）, d(s1+ch1, s2) + 1, d(s1, s2+ch2) + 1 ) 5.2.2.2ext 属性距离

26、的计算方法 ext 指文件的扩展名，虽然数据类型为字符串，但因此常见的文件类型是有限的， 因此可以看成是枚举类型，在聚类算法中则称为标称变量。在进行距离计算时可以 按照聚类算法中对于此类数据类型的标准处理方法进行处理，即其距离只是一个二 值函数：取值相同则距离为 0；否则距离为 1。但考虑到文件扩展名是有实际含义 的，而且很多时候这些不同的扩展名之间还有着丰富的联系，因此我们能够将其处 理的更加精确。 一般的，我们可以按照文件的扩展名对文件类型进行分类。比如可以将文件分 成：程序、图片、音乐、影视、源码等类别。在每个类别内部，可能又有更深的层 次，比如源码可能又分为 C/C+源码，JAVA 源

27、码等，而 C/C+源码又可以进一 步分为头文件和实现文件等 这样就形成了一棵树。不过要注意的是，这棵树不 是平衡的，某些叶节点可能比较深，另外一些可能比较浅。 为了形成这棵树，我们还需要说明如下。 首先，我们假设每种扩展名只对应于树中的一个节点； 其次，我们设置一个根节点，根节点本身不包含如何任何文件类型； 再有，对于没有扩展名的文件，我们为其赋予一个特殊的值，并且直接位于根 节点之下；对于不能识别的扩展名我们也做同样处理。 这样，最后形成了一棵类似下图的树： 33 root programvideomusicpicturesourceother Real format .avi .rm.rm

28、vb C/C+ language .java .h implemen tation .c.cpp 图 5-2 文件扩展名属性距离计算 这样，计算任意两个文件条目类型属性的距离演变成了计算树中任意两个叶节 点之间的关系。对于树中任意两个叶节点的距离，则表示为其相似程度的倒数。而 相似程度的计算，可以按照如下算法。树中每个节点均存在一条从根节点到达它所 在位置的唯一路径 P。两个节点的相似程度可以表示为它们各自路径P 中公共节 点的个数的函数。 在实现上，我们选取如下的函数： 假设需要计算两个 ext 值分别为 e1 和 e2 的点 xi、xj在此属性上的距离。设 e1 对应的路径为 p1，e2

29、对应的路径为 p2。p1 和 p2 的公共节点个数为 k（根节点 除外），则我们取： 2,2,2 1 1 (,) 2 ij k dxx 5.2.2.3size 属性距离的计算方法 size 属性表示文件条目的文件大小，以字节为单位，数据类型为整数。由于文 34 件大小的取值范围跨度很大，一般能够从几十字节到几十亿字节，因此不适合按照 一般区间标度变量的方法来计算，可以按照比例标度型变量来处理。首先对size 的值取对数： ,3,3 log() ii yx 不过在实际应用中要注意的是，因为size 的取值范围是非负整数，可能取 0，因此不能直接取 log，可以考虑首先将 x1 再取 log。 ,

30、3,3 log(1) ii yx 然后将 yi3转化为对应的 z-score 值 Zi3 ,33 ,3 3 i i ym z s 其中) 31,32,3,3 1 n m (yyy n 31,332,3333 1(| | | . |) n symymym n 进行标准化处理之后，再求二者之差： 3,3,3,3,3 (,) ijij dxxzz 5.2.2.4date 属性距离的计算方法 date 属性表示文件的最后修改日期，前面已经说过，我们将原来的字符串格式 统一转化为整数，比如按照距离公元元年元旦的日期数。对于整数，属于区间标度 变量。为了更好的计算各个项目该属性之间的距离，我们并不直接计算

31、各个条目的 差，而是先对其进行标准化处理。将Xi4转化为对应的 z-score 值 Zi4 ,44 ,4 4 i i xm z s 其中) 41,42,4,4 1 n m (xxx n 41,442,44,44 1(| | | . |) n sxmxmxm n 35 进行标准化处理之后，再求二者之差： 444,4,4 (,) ijij dxxzz 5.2.2.5site 属性距离的计算方法 由于在实际文件共享系统中， site 值最常见的情况就是 IP 地址，而两个 IP 地 址之间的距离的比较是没有实际意义的，因此我们忽略两个site 属性的之间的距 离，或者可以表示为： 5,5,5 (,)

32、0 ij dxx 5.2.2.6path 属性距离的计算方法 path 表示文件从根目录开始到其节点所经过的路径。其重要特点就是路径是分 段的，是由多个字符串连接而成的。比如路径： /Resource/Software/Tools/network/ 可以看成是由分段的子字符串 Resource，Software，Tools 和 network 构成的。 在对 path 进行比较的时候，我们将每个路径拆分成多个子字符串，然后比较其 中公共子字符串的个数占全部子字符串的比例。 6,6,6 (,) com ij ij s dxx ss 公式中 si和 sj分别表示 xi和 xj的 path 属性的分

33、段的个数， Scom为公共子字符 串的个数。 5.2.3 对用户点击记录进行聚类 在本体系中需要对用户的点击日志进行聚类，以便能够得到这k 个不同的用 户查询意图。 聚类常用的方法有 Partitioning 方法，Hierarchical 方法和 Density-based 方法。 根据我们的具体情况，这里选用自底向上的Hierarchical 方法。 对本方法的图示说明如下： 36 a b c d e a,b step 0 step 1 step 2 step 3 step 4 d,e c,d,e a,b,c,d, e agglomerative (AGNES) 图 5-3 聚类示意图 假

34、设共有 5 个对象 a,b,c,d,e，我们将其根据彼此的相关程度进行聚类。 首先，将每个待聚类的元素独立划分为一 个自己的类别，如果有 n 个元素， 则开始时共有 n 类。然后将距离最近的两个元素归为一类，此时有n-1 类；此后 再将距离次近的归为一类，类别共 n-2 类；如此不断重复 如果没有结束标志， 则最终将会把所有类别都归为一类。所以必须要设置结束标志。 这其中有几点要说明： 5.2.3.1结束标志的设定 结束标志可以从几个方面来综合考虑。首先是距离因素，设定当距离最近的两 个类的距离大于某个类别间的距离阀值D 时不再进行合并操作，设置距离标志D 可以防止最后生成的类别过少。另外由规

35、律2 可知相同的查询串通常只表示很少 的查询意图，因此可以设定一个最大类别数G，这个表示可以防止最后生成的类 别数过多。通过这两个结束标志的综合运用，可以使最终的类别数量控制在较理想 的范围中。 5.2.3.2具有多个元素的类别之间距离的计算 当类别包含多个元素时，计算它们之间的距离有三种不同的方法：计算距离最 近的两点之间的距离、最远的两点之间的距离、或者用中心点来计算距离。我们这 里选用中心点来计算二者的距离。这个中心点可能是类别中真实存在的一个元素， 但也可能是一个并不真正包含的虚拟的元素。 37 5.2.3.3孤立点的处理 事实上，一些查询串可能会对应一两个或很少的孤立查询记录，这些查

36、询记录 和其余大量的查询记录的相似度很低。通过人工查看的方法，我们发现很多这些孤 立查询记录其实都是看上去不太正常的记录，比如对于一些大小为0 的文件进行 下载，或者下载一些快捷方式文件等。我们认为这些孤立点是因为用户不小心或不 了解所致。而这些文件条目实际上并不应该被下载，而应该被抛弃。因此我们需要 对这些孤立点进行丢弃。 5.2.3.4训练集的生成 由于在进行完聚类后我们会对查询再进行分类，因此我们考虑利用聚类中的文 件条目作为分类时的训练集。在聚类完成后我们将保留每个查询串的每个类别足够 的文件条目。 5.2.4 对查询结果集合进行分类 常用的分类算法有 k nearest neighb

37、or(kNN), Nave Bayes, 还有 support vector machines 等。我们采用 kNN 算法。 其具体步骤为： 首先需要有一个训练集。对于每个可能的类别，各自有一些属于该类别的对象。 给定一个待分类的对象，系统在训练集中查找与其最相似的k 个对象(称为邻居)， 并根据这些邻居所属的类别情况来给该对象的候选类别评分，最后按照分值来确定 待分类对象的类别。 38 第6章 系统实现与评测 6.1系统设计体系结构图 实际系统的体系结构图如下。考虑到一些实现问题，和上一章的系统模型略有 区别。 Index Part Clustering Part Collection Pa

38、rt ClickLog DataBase Training Set DataBase ClickLog Server Clustering Query q Normal Index System Items Categorization Filter Categories Click log Items Training set Click log 图 6-1 体系结构图 下面我们来详细介绍此系统设计。 6.1.1 用户行为收集部分 Collection Part 部分为用户点击记录收集部分，是实时运行的。 在用户进行查询后，文件检索系统返回包含查询串的结果。用户从中选取自己 认为正确的文件条

39、目。用户的选取操作就是一次鼠标的点击操作。这个点击动作自 动触发到我们的后台 CGI 程序，程序先将用户的下载请求转向到真正的下载地址， 后台再发送一个记录点击操作的服务请求。该服务请求由ClickLog Server 接收， 并记录到 ClickLog Database 中。我们称用户的每次点击对应的文件条目为 39 ClickLog。经过这样反复多次后， ClickLog Database 中记录了大量的 ClickLog， 每个 ClickLog 包含一个查询串和对应的文件条目item。 6.1.2 聚类部分 此部分为聚类操作部分，每隔一段时间运行一次。在实际系统中可以根据用户 数量来设

40、定为每小时或每天一次。 这部分首先从 ClickLog Database 中读取全部的 ClickLog 条目，然后对每个查 询串依次进行处理。取出每个查询串对应的ClickLog 记录，进行聚类，聚类后得 到 k 个类别。如前文所述，其中可能存在一些孤立点，然后按照标准对这些孤立点 进行考察，需要的话要抛弃掉其对应的孤立类别。 聚类操作完成后，将聚类的结果存入Training Set Database 中。 至此，我们就得到了实现免用户干预的、基于反馈信息的检索系统所需要的反 馈数据。 6.1.3 索引部分 完成了上面两个部分的工作，就可以进行真正的反馈了。对于用户的查询串 q，首先使用常规

41、检索系统进行检索，就可得到一个文件条目Item 的集合。然后 在 Training Set Database 中取出对应于查询串 q 的 k 个类别的训练集。利用这些训 练集条目为刚刚通过常规查询得到的Item 集合进行分类。此处我们限定每个文件 条目至多属于 1 个类别。分类后可能得到 k+1 个类别（某些 Item 可能不属于任何 类别），以及每个条目和其所属类别的相似程度。利用分类的类别和相似度，系统 可以重新根据此信息进行输出。对于那些不属于任何类别的文件条目，通常也是用 户所不太关心的结果，可以选择抛弃或排在结果页面的最后。 6.2其它实现中的问题 6.2.1 记录用户对查询结果的选

42、取 对于用户对查询结果的选取的记录，一般有两种方法，采用client 端技术和 server 端技术。为了方便用户的使用，不改变用户的任何使用习惯，我们采取 server 端技术来记录用户的选择，这样用户在使用时就不需要丝毫的改变，而我们 也能够得到足够的记录信息。 40 具体说来，传统网页上的链接一般如下： qqtail.sln 我们采用 javascript 技术将其进行改造，改造后的形式如下： QQTail.sln 注意其中有 2 处 javascript 脚本。第一处是 onClick 信息，当用户点击了该链 接时，自动重新转向到了我们的服务器上，服务器有一个接收该请求的CGI 程序

43、clicklog，这个程序自动转向到实际的 FTP 下载地址，然后向 ClickLog Server 发 送一个记录请求， ClickLog Server 就记录下整个查询串和文件条目信息。 脚本中的另一处是 onMouseOver，这个是为了处理当用户已经点击该链接后却 又突然想复制该链接而使用的。 只所以在此处使用了 javascript 而不是直接改变链接地址，是为了便于那些并 不希望通过直接点击，而是希望使用下载工具或想复制下载地址的用户的方便。通 过现在这种改造，用户看到的页面和链接地址都是和原始信息是完全一致的。 6.2.2 文件类型属性距离计算方法的实现 前面谈到对于常见的文件扩

44、展名，我们将其各自赋予一个属性值，属性值代表 了在文件类别树中从根结点到该文件类型所在节点的所有节点编号的集合。节点的 编号示例如下图所示，每个节点的子节点的编号都是从1 开始的，并没有全局性 的编号。 41 root 123456 12 12 12 12 12 图 6-2 ext 属性距离计算方法的实现 比如对应图中左下角的灰色节点来说，对应的路径为2.1.1；右下角的灰色节 点对应的路径则为 5.1.2.2。 这样，如果比较两个节点的相似度，我们只需计数它们的路径中相同的节点个 数即可。比如路径为 2.1.1 的节点和 2.2 的节点，它们的路径中有一个相同的节点 2，或者说相似度为 1

45、层；路径为 2.1.1 的节点和 2.1.2 的节点，它们的相似度为 2 层；路径为 5.3 的节点和路径为 7 的节点相似度则为 0。 具体文件类型分类列表见附录 1。 配置文件格式，扩展名分类文件的配置文件的格式举例如下： 111 mp3|wav|wma| 112 midi|mid| 文件说明： 42 作用：通过读取文件得到每个扩展名对应的路径。 文件格式：每 3 行为一个记录。每个记录中第一行是空行；第2 行是路径， 格式为每层节点编号用制表符分割；第3 行是扩展名列表，每个扩展名都以竖线 “|”结束。 距离计算方法的实现： 在系统实现时，定义了一个 ExtVector 类，它代表了一个

46、具体的节点路径， ExtVector 继承自 vector，这里的 vector 是标准 STL 的 vector，并且实现了如 下方法来计算两个路径之间的距离： double operator (const ExtVector 6.3系统的评测环境 我们采用天网千帆文件搜索引擎为测试系统。天网千帆文件搜索引擎为北京大 学网络实验室开发的一个 FTP 文件搜索引擎，有较大的用户访问量。在2005 年 4 月，我们先后运行了普通文件搜索引擎和我们设计的新型文件搜索引擎，并记录 了用户的查询记录和用户对查询结果的选取信息。 为了保证评测效果的准确性，在使用了新系统后，我们没有通知任何用户，也 没有

47、改变任何用户界面，使测试尽量在用户不知情的情况下进行。对于分类后不能 归入任何类别的文件条目，为了保证总体查询结果数量不变，我们也没有进行抛弃， 而是放在排序的最后返回给用户。这里采用的排序方法是在页内按照各个初始结果 集合 S0中各个条目距离其类别的距离远近进行排序，对不同的类别之间并不进行排 序。在结果的表现形式上与普通搜索引擎无异。 比较试验共进行了 8 天，其中 4 天为普通文件检索系统，另外 4 天则为我们 的新系统。我们分别比较了用户对前2 页查询结果页面中点击的文件条目在该页面 中的排序的情况，共取得了 8 组比较数据。 6.4评测结果 具体比较结果参见下图。图中横坐标表示8 组

48、比较数据，纵坐标为各组试验数 据的在页面中点击的条目的排序的平均值。图中上部的曲线（虚线）为普通文件检 索系统的结果，下面的曲线（实线）为新系统的试验结果。 43 图 6-3 系统试验效果比较 从图中可以明显的看到：在新系统下，用户所点击的文件条目在页面中的排序 比普通系统有了较大幅度的提前。 在我们的试验系统中，普通文件检索系统用户点击的条目在页面中的排名为 13.70，而使用了新系统后，点击条目的平均排名为8.93。排名前进了 13.70- 8.93=4.77 名。检索效果有了较大幅度的改进。 由此可验证本文所述新型文件检索系统的正确性。 44 第7章 总结与展望 7.1总结 作者在本文中

49、首先对文件检索系统进行了一些基础性的研究工作，提出了文件 检索系统的检索模型，并提出了评测的指标。然后在对用户使用文件检索系统的行 为和习惯进行记录的基础上，发现了用户行为习惯中的两个重要规律。利用这两个 规律，作者提出了一个免用户干预的、基于用户查询记录的新型文件检索模型，该 模型可以有效的提高文件检索系统的精度。最后作者实现了一个真实的系统并利用 该系统对本模型的有效性进行了验证。 7.2展望 由于研发时间仓促，系统的有些功能还没有来得急加入，有的地方还有待加强， 特别如下文所述的几处。 7.2.1 目录 本文的全部算法都没有考虑目录的特殊性，而在实际的FTP 系统中是存在目 录共享的。在本文提到的试验系统中，对目录是不加区分的看成文件来处理，这样 在处理效果上就不是很理想了。 目录和文件的区别主要表现在这几个方面： 首先，目录不存在扩展