【毕业学位论文】（Word原稿）一个借助查询历史改善结果排序的文件检索系统的设计与实现-计算机网络与分布式系统

北京大学硕士研究生学位论文 题目：一个借助查询历史改善 结果 排序的文件检索 系统的设计与实现 姓 名：谢 欣 学 号： 10208105 院 系：信息科学技术学院 专 业：计算机系统结构 研究方向：计算机网络与分布式系统 导 师：李晓明 教授 2005 年 5 月 北京大学 网络实验室硕士学位论文 1 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律 责任。 北京大学 网络实验室硕士学位论文 2 摘 要 随着网络的发展，网络上提供文件共享服务的服务器越来越多，共享的文件数量也随之增加。如何更好的检索、利用这些共享文件成为一个重要的问题。 针对用户对文件检索的需求，本文在文件检索技术领域有如下贡献。 1. 本文首先提出了一个文件检索的模型，明确了在文件检索模型中检索对象、查询串、查询与检索对象的匹配方式三部分的含义。检索对象，即文件条目表示为六元组 形式，查询串表示为以空格分隔的字符串的集合，查询与检索对象的匹配则表示为 查询串与文件条目的匹配串之间的匹配。 2. 提出了对文件检索系统进行评测的指标。将查询结果视作集合时以查全率、查准率为评测指标。将查询结果视作有序序列时，分析了查询结果的相关性、连接下载速度以及结果的可用性等因素对排序的影响，并提出了对排序进行评测的指标 排序指数。作者还提出对于两个排序策略进行比较时，应当在结果的每个页面内部应用排序策略，而不是在全体结果集合上应用排序策略，并比较平均用户选取条目的页内排名。 3. 通过统计、分析用户对文件搜索引擎的检索和对检索结果中下载地址条目的选取，作者发现了用户行为 习惯中的两个重要规律：一、少数查询串占据了全部查询请求的大多数，具体而言，前 20%的热门查询串占据了全部查询请求的 80%；二、对全体用户而言，假设有 n 次不同的查询请求使用了同一个查询串，并且它们代表 k 类不同的查询意图。那么通常 k 3，因而在 n 较大的情况下，则 n/k 的值较大，即大量的来自不同用户的请求代表了相同的查询意图。 4. 基于上文所述，作者设计并实现了一个真实的系统。该系统借助查询历史改善结果的排序。与一般基于用户历史信息的检索系统不同的是，本系统借助的历史信息不局限于当前用户的历史信息，还包含提交了 相同查询串的其他用户的查询信息。或者说，即使当前用户是第一次使用本系统，本系统也能利用其他用户的历史记录来改进结果的排序和筛选。作者最后还验证了其实际的效果。应用本方法后，平均用户选取条目的页内排名从原来的 前进到了 。试验结果表明文中所做的分析是正确的。 关键词： 文件检索系统，查询历史，检索模型 北京大学 网络实验室硕士学位论文 3 of a I of of is So its to of of we 1. We a is of of an of a be is as by is by of 2. We we is a an So we in of of We to of If we to we in y of 3. By of s a we 1). 80% 0% 2) If n of of is k. k be a 应的查询串的个数 33 157 81 0 1 0 从上表可见，查询意图只有 1 3 个的查询串占全部记录数据的绝大部分，超过 5 种不同意图的查询串在统计的日志中根本就没有出现。 我们再来看一下 n 和 k 的比例的分布，统计结果如下图。图中横坐标表示查询串被查询的次数 n，综坐标为 n/k 的比值。要说明一点就是为了使图像中的点线显示清晰，我们忽略了很少量的查询次数非常高的词（这些点对应的横坐标值非常大），但事后的手工验证仍然证明了它们符合本文的规律。 北京大学 网络实验室硕士学位论文 25 11010010000 100 200 300 400 500 600 700 800 900 1000图 4其中横坐标为查询串查询 次数 n， 综坐标为 n/k 比值（为指数标度） 从图中可以看到，当 n100 时， n/k 的值都在 30 以上。 由上面的分析我们能够知道，尽管查询串不同，但一般说来，它们所代表的查询意图的数量并不是太多的，通常在 1，并且在 n 较大的情况下（如 n100），通常 n/k 的比值较大（本例中大于 30）。因此我们得到了第二个重要的规律： 规律二：假设有 n 次不同的请求查询了同一个查询串，并且它们代表 k 种不同的查询意图。在 n 较大的情况下（ n100）， n/k 的值较大（ n/k30）。 户行为特点的启发 利用上面的用户行为特点 中的两个规律，以及前面关于相关反馈方法的思路，可以考虑采用如下思路来实现一个借助查询历史信息改善结果排序的文件检索系统。 从上面的特征我们知道，大多数的查询请求不仅其查询串本身是重复的，而且其所代表的查询意图也是重复的。这样我们就可以由“较早的相同的查询串的结果选取记录”作为用户的反馈信号。这样一来，后来提交同样查询串的用户不需要任何主动干预，就可以得到经过反馈信号处理过的重新排序的查询结果了。北京大学 网络实验室硕士学位论文 26 当然，由于用户意图并不唯一，我们并不能确定究竟本次查询的用户是哪种查询意图，但因为 k 值通常都相当小（小于等于 3）， 因此对用户而言，很容易从这为数极少的查询意图中找到满足自己意图的结果。 具体而言，我们可以考虑如下的思路。 首先记录下每次用户对查询结果的选取。我们认为，用户在查询结果中点击的下载地址，就是用户认为比较理想的下载地址。通过一段时间的记录，我们就得到了对于大量查询串的较理想的匹配结果。对于一个查询串 q，我们有一个用户认为较好的文件条目的集合 S，我们将其表示为一个二元组 (q,S)。这样，我们就得到了大量的这样的二元组。 依据规律 2，我们知道每个查询串可能代表几个不同的查询意图，那么不同的查询意图对应的理想下载地 址肯定不同（否则就是相同的查询意图了），我们可以采用聚类的方法对每个 S 中的文件条目进行聚类。聚类后，对于每个 q，我们会得到 k 种不同的类别，这 k 个类别就也就反映了不同的查询意图，而每个类别中的文件条目，就可以看作这个类别的训练集。每个类别中的条目个数，也直接反映了这个类别的权重。 当再次有用户查询同样的查询串 q 时，我们首先采用原始的检索方法，得到一个结果集合，然后用聚类得到的 k 个类别和训练集对其进行分类处理。一些条目被分到这 k 个类别中，另外一些可能不属于任何类别。不属于任何类别的条目往往也是用户不太需要的条目 ，可以考虑抛弃或排在结果的最后输出。北京大学 网络实验室硕士学位论文 27 第 5章 系统体系结构与主要算法 统体系结构 基于以上分析，我们设计了如下的检索系统来改善文件检索系统的排序。 Q u e r y S t r i n g ( q )N o r m a l I n d e x S y s t e m ( I )I n d e x R e s u l t ( S 0 )F e e d b a c k d a t a D a t a B a s eS i t e L i s t D a t a B a s eq u e r yC l u s t e r i n gT h e t r a i n i n g s e t f o r q u e r y i t e m qI t e m s n o t b e l o n g t o a n y g r o u pR e s u l t a f t e r C a t e g o r i z a t S )C a t e g o r i z a t i o n , O r d e r i n gF i l e i t e m s t h a t u s e r c l i c k e 5统结构图 下面我们来详细介绍这个模型。 我们首先查看模型中的各个组成部分。 q)： 用户输入的查询串； )： 常规的文件检索系统； 0)： 初始查询结果集； B(F)： 该数据库中记录了已有的每个查询请求和它对应的不同的 k 种查询意图，以及每种意图的作为训练集的文件条目。 B(D)： 该数据库中保存了每次用户进行检索后对查询结果的选取情况。具体而言，当用户进行查询后，检索系统返回结果，当用户在结果页面中对文件条目进行点击并下载时，本模型会记录用户的点击选取行为。库中的每条记录含有当前的查询串和用户点击的这条记录的具体文件信息：文件名称、扩展名称、最后修改日期、文件大小、文件所在 站点和文件所在的路径。 北京大学 网络实验室硕士学位论文 28 本检索系统的工作流程如下： 数据库 F 中需要足够的数据记录系统才能够进行工作。因此在系统运行之初，系统便开始自动记录用户的点击，并将记录填充进数据库 D。数据库 D 每隔一段时间，对每个查询串 q 进行一次聚类操作，这样便得到了每个查询串所代表的 现在我们假设 F 中已经包含有了足够的记录信息。当用户输入查询串 q 后，一方面，模型中最上面的流程开始工作，常规的检索系统进行检索，得到一个原始的查询结果 一方面，如模型图示中的中层的流程， q 被送入数据库 F。数据库 F 返回对应的 k 种意图和其 点击记录集合。这些记录将作为下一步分类工作的训练集。 有了 这 k 种类别，下面将利用这 k 种类别的训练集对 行分类。分类后我们将 成了 k+1 类，其中新增加的这个类别是那些不属于任何类别的文件条目 合。对于不属于任何类别的条目，我们认为它是用户不太关心的结果，可以把它抛弃或放入输出结果的最后。 这里有一点要注意，就是 k 种类别的地位是不同的，类别本身也是有权重的，权重可以由聚类时每个类别中的条目数量来决定。这样在最后输出时可以按照权重本身对类别进行排序。由于 k 的取值通常都比较小（小于等于 3），用 户最终看到的结果往往是接近用户的真实查询意图的。 然后就可以按照一般的条目列表方式或者聚类的树型结构将结果输出给最终用户。 要算法 户点击日志的表示 用户点击日志就是用户所点击的文件条目 前面的对文件检索的建模，我们知道可以表示为： 我们将其改写为如下格式： p a t hs i t ed a t es i z a m e 有时候为了简便，我们也会表述为如下形式： 北京大学 网络实验室硕士学位论文 29 654321 对于查询串 q， 价格共有 n 个记录，因此我们得到如下的矩阵： 1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6, 1 , 2 , 3 , 4 , 5 , 6, 1 , 2 , 3 , 4 , 5 , 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i i i i i in n n n n nx x x x x xx x x x x xx x x x x x算文件条目之间的距离 不论是进行聚类处理还是进行分类处理，都需要进行大量的对两个文件条目(间的距离 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 ) ( 7 , 5 ) ( 7 , 6 ) 0. . . . . . . . . . . . . . . . . . . . . 0( , 1 ) ( , 2 ) ( , 3 ) ( , 4 ) ( , 5 ) ( , 6 ) . . . ( ,d dd d d dd d d d dd d d d d dd n d n d n d n d n d n d n n 1 ) 0图中我们用 d(i,j)表示项 间的距离，有 d(i,j) 0。 当 d(i,j)=0 时表示二者完全相同； 当 d(i,j)0 时表示二者不同，并且 d 的值越大表示文件 条目 间的差异越大。 对于条目 i 和 j 之间距离的 d(i,j)的计算，我们采用如下加权公式： 北京大学 网络实验室硕士学位论文 30 ( , )11( , )i f j fp x 由前文文件检索模型可知，此处 p=6。我们分别计算文件条目 i 和 j 的 6 项对应属性的距离，再进行加权求和最后再进行标准化处理。 由于文件条目的 6 项属性的数据类型和含义不完全相同，因此具体的计算方法区别较大，在计算时需要分别考虑。 下图为各个属性的数据类型和计算方法。 表格 5件条目各个属性数据类型 属性 数据类型 距离计算方法 ： 性距离的计算方法 示文件的 不包含扩展名的主名的名称，数据类型为字符串型。对于这种字符串类型数据的处理，一般情况下可以按照文档的相似度的方式进行。但由于文件名通常都比较短小，命名多数情况下也不规范。这里并不建议按照文档的形式来处理。 我们这里采用的处理方法是按照最小编辑距离的方法来处理。 编辑距离是指两个字符串通过插入字符、删除字符、改写字符而变为相同字符串所需要的操作次数。 比如： d(“” = 1 d(“” = 1 d(“ “ = 2 d(“” = 4 利用动态规划的方法计算编辑距离，时间复杂性可以达到 O(空间复杂性北京大学 网络实验室硕士学位论文 31 为 O（ 计算方法为一个递归算法： d(, ) = 0 d(s, ) = d(, s) = |s| （ |s|表示 s 的长度） d(s1+s2+= d(+ （ if ） , d(s1+ 1, d(s2+ 1 ) 性距离的计 算方法 文件的扩展名，虽然数据类型为字符串，但因此常见的文件类型是有限的，因此可以看成是枚举类型，在聚类算法中则称为标称变量。在进行距离计算时可以按照聚类算法中对于此类数据类型的标准处理方法进行处理，即其距离只是一个二值函数：取值相同则距离为 0；否则距离为 1。但考虑到文件扩展名是有实际含义的，而且很多时候这些不同的扩展名之间还有着丰富的联系，因此我们能够将其处理的更加精确。 一般的，我们可以按照文件的扩展名对文件类型进行分类。比如可以将文件分成：程序、图片、音乐、影视、源码等类别。在每个类别内部，可 能又有更深的层次，比如源码可能又分为 C/C+源码， 码等，而 C/C+源码又可以进一步分为头文件和实现文件等这样就形成了一棵树。不过要注意的是，这棵树不是平衡的，某些叶节点可能比较深，另外一些可能比较浅。 为了形成这棵树，我们还需要说明如下。 首先，我们假设每种扩展名只对应于树中的一个节点； 其次，我们设置一个根节点，根节点本身不包含如何任何文件类型； 再有，对于没有扩展名的文件，我们为其赋予一个特殊的值，并且直接位于根节点之下；对于不能识别的扩展名我们也做同样处理。 这样，最后形成了一棵类似 下图的树： 北京大学 网络实验室硕士学位论文 32 r o o tp r o g r a m v i d e o m u s i c p i c t u r e s o u r c e o t h e rR e a l f o r m a t. a v i. r m v C + l a n g u a g e. j a v a. hi m p l e m en t a t i o n. c . c p 5件扩展名属性距离计算 这样，计算任意两个文件条目类型属性的距离演变成了计算树中任意两个叶节点之间的关系。对于树中任意两个叶节点的距离，则表示为其相似程度的倒数。而相似程度的计算，可以按照如下算法。树中每个节点均存在一条从根节点到达它所在位置的唯一路径 P。两个节点的相似程度可以表示为它们各自路径 P 中公共节点的个数的函数。 在实现上，我们选取 如下的函数： 假设需要计算两个 分别为 点 此属性上的距离。设 应的路径为 公共节点个数为 k（根节点除外），则我们取： 2 , 2 , 2 11( , ) 2ij kd x x 北京大学 网络实验室硕士学位论文 33 性距离的计算方法 性表示文件条目的文件大小，以字节为单位，数据类型为整数。由于文件大小的取值范围跨度很大，一般能够从几十字节到几十亿字节，因此不适合按照一般区间标度变量的方法来计算，可以按照比例标度型变量来处理。首先对 ,3 ,3lo g ( )过在实际应用中要注意的是，因为 取值范围是非负整数，可能取 0，因此不能直接取 以考虑首先将 x 1 再取 , 3 , 3lo g ( 1 )然后将 化为对应的 3 3,3 3s 其中. . . )3 1 , 3 2 , 3 , 31 ( y y 3 1 , 3 3 2 , 3 3 3 31 ( | | | | . . . | | )ns y m y m y 进行标准化处理之后，再求二者之差： 3 , 3 , 3 , 3 , 3( , )i j i jd x x z z 性距离的计算方法 性表示文件的最后修改日期，前面已经说过，我们将原来的字符串格式统一转化为整数，比如按照距离公元元年元旦的日期数。对于整数，属于区间标度变量。为了更好的计算各个项目该属性之间的距离，我们并不直接计算各个条目的差，而是先对其进行标准化处理。将 化为对应的 4 4,4 4s 北京大学 网络实验室硕士学位论文 34 其中. . . )4 1 , 4 2 , 4 , 41 ( x x 4 1 , 4 4 2 , 4 4 , 4 41 ( | | | | . . . | | )ns x m x m x 进行标准化处理之后，再求二者 之差： 4 4 4 , 4 , 4( , )i j i jd x x z z 性距离的计算方法 由于在实际文件共享系统中， 最常见的情况就是 址，而两个 址之间的距离的比较是没有实际意义的，因此我们忽略两个 性的之间的距离，或者可以表示为： 5 , 5 , 5( , ) 0x x 性距离的计算方法 示文件从根目录开始到其节点所经过的路径。其重要特点就是路径是分段的，是由多个字符串连接而成的。比如路径： / 以看成是由分段的子字符串 成的。 在对 行比较的时候，我们将每个路径拆分成多个子字符串，然后比较其中公共子字符串的个数占全部子字符串的比例。 6 , 6 , 6( , )c o x 公式中 别表示 性的分段的个数， 公共子字符串的个数。 用户点击记录进行聚类 在本体系中需要对用户的点击日志进行聚类，以便能够得到这 k 个不同的用户查询意图。 聚类常用的方法有 法， 法和 法。根据我们的具体情况，这里选用自底向上的 法。 北京大学 网络实验室硕士学位论文 35 对本方法的图示说明如下： bs t e p 0 s t e p 1 s t e p 2 s t e p 3 s t e p 4d , d , b , c , d ,ea g g l o m e r a t i v e( A G N E S )图 5假设共有 5 个对象 a,b,c,d,e，我们将其根据彼此的相关程度进行聚类。 首先，将每个待聚类的元素独立划分为一 个 自己的类别，如果有 n 个元素，则开始时共有 n 类。然后将距离最近的两个元素归为一 类，此时有 ；此后再将距离次近的归为一类，类别共 ；如此不断重复如果没有结束标志，则最终将会把所有类别都归为一类。所以必须要设置结束标志。 这其中有几点要说明： 束标志的设定 结束标志可以从几个方面来综合考虑。首先是距离因素，设定当距离最近的两个类的距离大于某个类别间的距离阀值 D 时不再进行合并操作，设置距离标志D 可以防止最后生成的类别过少。另外由规律 2 可知相同的查询串通常只表示很少的查询意图，因此可以设定一个最大类别数 G，这个表示可以防止最后生成的类别数过多。通过这两个结束标志的综合运用， 可以使最终的类别数量控制在较理想的范围中。 有多个元素的类别之间距离的计算 当类别包含多个元素时，计算它们之间的距离有三种不同的方法：计算距离最近的两点之间的距离、最远的两点之间的距离、或者用中心点来计算距离。我们这里选用中心点来计算二者的距离。这个中心点可能是类别中真实存在的一个北京大学 网络实验室硕士学位论文 36 元素，但也可能是一个并不真正包含的虚拟的元素。 立点的处理 事实上，一些查询串可能会对应一两个或很少的孤立查询记录，这些查询记录和其余大量的查询记录的相似度很低。通过人工查看的方法，我们发现很多这些孤立查询记录其实都是看上去不 太正常的记录，比如对于一些大小为 0 的文件进行下载，或者下载一些快捷方式文件等。我们认为这些孤立点是因为用户不小心或不了解所致。而这些文件条目实际上并不应该被下载，而应该被抛弃。因此我们需要对这些孤立点进行丢弃。 练集的生成 由于在进行完聚类后我们会对查询再进行分类，因此我们考虑利用聚类中的文件条目作为分类时的训练集。在聚类完成后我们将保留每个查询串的每个类别足够的文件条目。 查询结果集合进行分类 常用的分类算法有 k 还有 。我们采用 法。 其具体步骤为： 首先需要有一个训练集。对于每个可能的类别，各自有一些属于该类别的对象。给定一个待分类的对象，系统在训练集中查找与其最相似的 k 个对象 (称为邻居 )，并根据这些邻居所属的类别情况来给该对象的候选类别评分，最后按照分值来确定待分类对象的类别。北京大学 网络实验室硕士学位论文 37 第 6章 系统实现与评测 统设计体系结构图 实际系统的体系结构图如下。考虑到一些实现问题，和上一章的系统模型略有区别。 I n d e x P a r t C l u s t e r i n g P a r t C o l l e c t i o n P a r t C l i c k L o g D a t a B a s e T r a i n i n g S e t D a t a B a s e C l i c k L o g S e r v e r C l u s t e r i n g Q u e r y q N o r m a l I n d e x S y s t e m I t e m s C a t e g o r i z a t i o n F i l t e r C a t e g o r i e s C l i c k l o g I t e m s T r a i n i n g s C l i c k l o g 图 6下面我们来详细介绍此系统设计。 户行为收集部分 分为用户点击记录收集部分，是实时运行的。 在用户进行查询后，文件检索系统返回包含查询串的结果。用户从中选取自己认为正确的文件条目。用户的选取操作就是一次鼠标的点击操作。这个点击动作自动触发到我们的后台 序，程序先将用户的下载请求转向到真正的下载地址，后台再发送一个记录点击操作的服务请求。该服务请求由 记录 到 。我们称用户的每次点击对应的文件条目为北京大学 网络实验室硕士学位论文 38 过这样反复多次后， 记录了大量的 个 含一个查询串和对应的文件条目 类部分 此部分为聚类操作部分，每隔一段时间运行一次。在实际系统中可以根据用户数量来设定为每小时或每天一次。 这部分首先从 读取全部的 目，然后对每个查询串依次进行处理。取出每个查询串对应的 录，进行聚类 ，聚类后得到 k 个类别。如前文所述，其中可能存在一些孤立点，然后按照标准对这些孤立点进行考察，需要的话要抛弃掉其对应的孤立类别。 聚类操作完成后，将聚类的结果存入 。 至此，我们就得到了实现免用户干预的、基于反馈信息的检索系统所需要的反馈数据。 引部分 完成了上面两个部分的工作，就可以进行真正的反馈了。对于用户的查询串 q，首先使用常规检索系统进行检索，就可得到一个文件条目 集合。然后在取出对应于查询串 q 的 k 个类别的 训练集。利用这些训练集条目为刚刚通过常规查询得到的 合进行分类。此处我们限定每个文件条目至多属于 1 个类别。分类后可能得到 k+1 个类别（某些 能不属于任何类别），以及每个条目和其所属类别的相似程度。利用分类的类别和相似度，系统可以重新根据此信息进行输出。对于那些不属于任何类别的文件条目，通常也是用户所不太关心的结果，可以选择抛弃或排在结果页面的最后。 它实现中的问题 录用户对查询结果的选取 对于用户对查询结果的选取的记录，一般有两种方法，采用 技术和技术。为了方便 用户的使用，不改变用户的任何使用习惯，我们采取 样用户在使用时就不需要丝毫的改变，而我们也能够得到足够的记录信息。 北京大学 网络实验室硕士学位论文 39 具体说来，传统网页上的链接一般如下： 们采用 术将其进行改造，改造后的形式如下： 意其中有 2 处 本。第一处是 息，当用户点击了该链接时，自动重新转向到了我们的服务器上，服务器有一个接收该请求的 序个程序自动转向到实际的 载地址，然后向 送一个记录请求， 记录下整个查询串和文件条目信息。 脚本中的另一处是 个是为了处理当用户已经点击该链接后却又突然想复制该链接而使用的。 只所以在此处使用了 不是直接改变链接地址，是为了便于那些并不希望通过直接点击，而是希望使用下载工具或想复制下载地 址的用户的方便。通过现在这种改造，用户看到的页面和链接地址都是和原始信息是完全一致的。 文件类型属性距离计算方法的实现 前面谈到对于常见的文件扩展名，我们将其各自赋予一个属性值，属性值代表了在文件类别树中从根结点到该文件类型所在节点的所有节点编号的集合。节点的编号示例如下图所示，每个节点的子节点的编号都是从 1 开始的，并没有全局性的编号。 北京大学 网络实验室硕士学位论文 40 r o o 3 4 5 61 21 21 21 21 2图 6-2 性距离计算方法的实现 比如对应图中左下角的灰色节点来说，对应的路径为 下角的灰色节点对应的路径则为 这样，如果比较两个节点的相似度，我们只需计数它们的路径中相同的节点个数即可。比如路径为 节点和 节点，它们的路径中有一个相同的节点 2，或者说相似度为 1 层；路径为 节点和 节点，它们的相似度为2 层；路径为 节点和路径为 7 的节点相似度则为 0。 具体文件类型分类列表见附录 1。 配置文件格式，扩展名分类文件的配置文件的格式举例如下： 1 1 1 1 1 2 文件说明： 北京大学 网络实验室硕士学位论文 41 作用：通过读取文件得到每个扩展名对应的路径。 文件格式：每 3 行为一个记录。每个记录中第一行是空行；第 2 行是路径，格式为每层节点编号用制表符分割；第 3 行是扩展名列表，每个扩展名都以竖线“ |”结束。 距离计算方法的实现： 在系统实现时，定义了一个 ，它代表了一个具体的节点路径，承自 里的 标准 且实现了如下方法来计算两个路径之间的距离： ( 统的评测环境 我们采用天网千帆文件搜索引擎为测试系统。天网千帆文件搜索引擎为北京大学网络实验室开发的一个 件搜索引擎，有较大的用户访问量。在 2005 年4 月，我们先后运行了普通文件搜索引擎和我们设计的新型文件搜索引擎，并记录了用户的查询记录和用户对查询结果的选取信息。 为了保证评测效果的准确性，在使用了新系统后，我们没有通知任何用户，也没有改变任何用户界面，使测试尽量在用户不知情的 情况下进行。对于分类后不能归入任何类别的文件条目，为了保证总体查询结果数量不变，我们也没有进行抛弃，而是放在排序的最后返回给用户。这里采用的排序方法是在页内按照各个初始结果集合 各个条目距离其类别的距离远近进行排序，对不同的类别之间并不进行排序。在结果的表现形式上与普通搜索引擎无异。 比较试验共进行了 8 天，其中 4 天为普通文件检索系统，另外 4 天则为我们的新系统。我们分别比较了用户对前 2 页查询结果页面中点击的文件条目在该页面中的排序的情况，共取得了 8 组比较数据。 测结果 具体比较结果参见下图。图中横坐标表 示 8 组比较数据，纵坐标为各组试验数据的在页面中点击的条目的排序的平均值。图中上部的曲线（虚线）为普通文件检索系统的结果，下面的曲线（实线）为新系统的试验结果。 北京大学 网络实验室硕士学位论文 42 图 6从图中可以明显的看到：在新系统下，用户所点击的文件条目在页面中的排序比普通系统有了较大幅度的提前。 在我们的试验系统中，而使用了新系统后，点击条目的平均排名为 排名前 。检索效果有了较大幅度的改进。 由此可验证本文所述新型文件检索系统的正确性。北京大学 网络实验室硕士学位论文 43 第 7章 总结与展望 结 作者在本文中首先对文件检索系统进行了一些基础性的研究工作，提出了文件检索系统的检索模型，并提出了评测的指标。然后在对用户使用文件检索系统的行为和习惯进行记录的基础上，发现了用户行