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

北京大学硕士研究生学位论文题目：一个借助查询历史改善结果排序的文件检索系统的设计与实现姓 名： 学 号： 院 系：信息科学技术学院专 业：计算机系统结构研究方向：计算机网络与分布式系统导 师： 1版权声明版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 2摘摘 要要随着网络的发展，网络上提供文件共享服务的服务器越来越多，共享的文件数量也随之增加。如何更好的检索、利用这些共享文件成为一个重要的问题。针对用户对文件检索的需求，本文在文件检索技术领域有如下贡献。1. 本文首先提出了一个文件检索的模型，明确了在文件检索模型中检索对象、查询串、查询与检索对象的匹配方式三部分的含义。检索对象，即文件条目表示为六元组name, ext, size, date, site, path的形式，查询串表示为以空格分隔的字符串的集合，查询与检索对象的匹配则表示为查询串与文件条目的匹配串之间的匹配。2. 提出了对文件检索系统进行评测的指标。将查询结果视作集合时以查全率、查准率为评测指标。将查询结果视作有序序列时，分析了查询结果的相关性、连接下载速度以及结果的可用性等因素对排序的影响，并提出了对排序进行评测的指标排序指数。作者还提出对于两个排序策略进行比较时，应当在结果的每个页面内部应用排序策略，而不是在全体结果集合上应用排序策略，并比较平均用户选取条目的页内排名。3. 通过统计、分析用户对文件搜索引擎的检索和对检索结果中下载地址条目的选取，作者发现了用户行为习惯中的两个重要规律：一、少数查询串占据了全部查询请求的大多数，具体而言，前 20%的热门查询串占据了全部查询请求的80%；二、对全体用户而言，假设有 n 次不同的查询请求使用了同一个查询串，并且它们代表 k 类不同的查询意图。那么通常 k3，因而在 n 较大的情况下，则 n/k 的值较大，即大量的来自不同用户的请求代表了相同的查询意图。4. 基于上文所述，作者设计并实现了一个真实的系统。该系统借助查询历史改善结果的排序。与一般基于用户历史信息的检索系统不同的是，本系统借助的历史信息不局限于当前用户的历史信息，还包含提交了相同查询串的其他用户的查询信息。或者说，即使当前用户是第一次使用本系统，本系统也能利用其他用户的历史记录来改进结果的排序和筛选。作者最后还验证了其实际的效果。应用本方法后，平均用户选取条目的页内排名从原来的13.70 名前进到了 8.93 名。试验结果表明文中所做的分析是正确的。关键词：文件检索系统，查询历史，检索模型 3The 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, k5对应的查询串的个数3315781010从上表可见，查询意图只有 13 个的查询串占全部记录数据的绝大部分，超过 5 种不同意图的查询串在统计的日志中根本就没有出现。我们再来看一下 n 和 k 的比例的分布，统计结果如下图。图中横坐标表示查询串被查询的次数 n，综坐标为 n/k 的比值。要说明一点就是为了使图像中的点线显示清晰，我们忽略了很少量的查询次数非常高的词（这些点对应的横坐标值非常大），但事后的手工验证仍然证明了它们符合本文的规律。 26110100100001002003004005006007008009001000图 4-3 查询串与查询意图种类比值分析其中横坐标为查询串查询次数 n，综坐标为 n/k 比值（为指数标度）从图中可以看到，当 n100 时，n/k 的值都在 30 以上。由上面的分析我们能够知道，尽管查询串不同，但一般说来，它们所代表的查询意图的数量并不是太多的，通常在1-3 种，并且在 n 较大的情况下（如n100），通常 n/k 的比值较大（本例中大于 30）。因此我们得到了第二个重要的规律：规规律律二二：假假设设有有 n 次次不不同同的的请请求求查查询询了了同同一一个个查查询询串串，并并且且它它们们代代表表k 种种不不同同的的查查询询意意图图。在在 n 较较大大的的情情况况下下（ n100），n/k 的的值值较较大大（ n/k30）。4.3用户行为特点的启发利用上面的用户行为特点中的两个规律，以及前面关于相关反馈方法的思路，可以考虑采用如下思路来实现一个借助查询历史信息改善结果排序的文件检索系统。从上面的特征我们知道，大多数的查询请求不仅其查询串本身是重复的，而且其所代表的查询意图也是重复的。这样我们就可以由“较早的相同的查询串的结果选取记录”作为用户的反馈信号。这样一来，后来提交同样查询串的用户不需要 27任何主动干预，就可以得到经过反馈信号处理过的重新排序的查询结果了。当然，由于用户意图并不唯一，我们并不能确定究竟本次查询的用户是哪种查询意图，但因为 k 值通常都相当小（小于等于 3），因此对用户而言，很容易从这为数极少的查询意图中找到满足自己意图的结果。具体而言，我们可以考虑如下的思路。首先记录下每次用户对查询结果的选取。我们认为，用户在查询结果中点击的下载地址，就是用户认为比较理想的下载地址。通过一段时间的记录，我们就得到了对于大量查询串的较理想的匹配结果。对于一个查询串q，我们有一个用户认为较好的文件条目的集合 S，我们将其表示为一个二元组 (q,S)。这样，我们就得到了大量的这样的二元组。依据规律 2，我们知道每个查询串可能代表几个不同的查询意图，那么不同的查询意图对应的理想下载地址肯定不同（否则就是相同的查询意图了），我们可以采用聚类的方法对每个 S 中的文件条目进行聚类。聚类后，对于每个q，我们会得到 k 种不同的类别，这 k 个类别就也就反映了不同的查询意图，而每个类别中的文件条目，就可以看作这个类别的训练集。每个类别中的条目个数，也直接反映了这个类别的权重。当再次有用户查询同样的查询串 q 时，我们首先采用原始的检索方法，得到一个结果集合，然后用聚类得到的 k 个类别和训练集对其进行分类处理。一些条目被分到这 k 个类别中，另外一些可能不属于任何类别。不属于任何类别的条目往往也是用户不太需要的条目，可以考虑抛弃或排在结果的最后输出。 28第5章 系统体系结构与主要算法5.1系统体系结构基于以上分析，我们设计了如下的检索系统来改善文件检索系统的排序。Query String (q)Normal Index System (I)Index Result (S0)Feedback data DataBaseSite List DataBasequeryClusteringThe training set for query item qItems not belong to any groupResult after Categorization (S)Categorization, OrderingFileitems that user clicked图 5-1 系统结构图下面我们来详细介绍这个模型。我们首先查看模型中的各个组成部分。Query String (q)：用户输入的查询串；Normal Index System(I)：常规的文件检索系统；Index Result(S0)：初始查询结果集；Feedback Data DB(F)：该数据库中记录了已有的每个查询请求和它对应的不同的 k 种查询意图，以及每种意图的作为训练集的文件条目。Fileitem DB(D)：该数据库中保存了每次用户进行检索后对查询结果的选取情况。具体而言，当用户进行查询后，检索系统返回结果，当用户在结果页面中对文件条目进行点击并下载时，本模型会记录用户的点击选取行为。库中的每条记录含有当前的查询串和用户点击的这条记录的具体文件信息：文件名称、扩展名称、最后修改日期、文件大小、文件所在站点和文件所在的路径。 29本检索系统的工作流程如下：数据库 F 中需要足够的数据记录系统才能够进行工作。因此在系统运行之初，系统便开始自动记录用户的点击，并将记录填充进数据库D。数据库 D 每隔一段时间，对每个查询串 q 进行一次聚类操作，这样便得到了每个查询串所代表的k种查询意图。现在我们假设 F 中已经包含有了足够的记录信息。当用户输入查询串q 后，一方面，模型中最上面的流程开始工作，常规的检索系统进行检索，得到一个原始的查询结果 S0。另一方面，如模型图示中的中层的流程， q 被送入数据库 F。数据库 F 返回对应的 k 种意图和其点击记录集合。这些记录将作为下一步分类工作的训练集。有了 S0和这 k 种类别，下面将利用这 k 种类别的训练集对 S0进行分类。分类后我们将 S0分成了 k+1 类，其中新增加的这个类别是那些不属于任何类别的文件条目 item 集合。对于不属于任何类别的条目，我们认为它是用户不太关心的结果，可以把它抛弃或放入输出结果的最后。这里有一点要注意，就是 k 种类别的地位是不同的，类别本身也是有权重的，权重可以由聚类时每个类别中的条目数量来决定。这样在最后输出时可以按照权重本身对类别进行排序。由于 k 的取值通常都比较小（小于等于 3），用户最终看到的结果往往是接近用户的真实查询意图的。然后就可以按照一般的条目列表方式或者聚类的树型结构将结果输出给最终用户。5.2主要算法5.2.1 用户点击日志的表示用户点击日志就是用户所点击的文件条目item。由前面的对文件检索的建模，我们知道可以表示为：item = name, ext, size, date, site, path我们将其改写为如下格式：pathsitedatesizeextnamexxxxxx有时候为了简便，我们也会表述为如下形式： 30654321xxxxxx对于查询串 q，价格共有 n 个记录，因此我们得到如下的矩阵：1,11,21,31,41,51,6,1,2,3,4,5,6,1,2,3,4,5,6.iiiiiinnnnnnxxxxxxxxxxxxxxxxxx5.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)(7,5)(7,6)0.0( ,1)( ,2)( ,3)( ,4)( ,5)( ,6).( ,dddddddddddddddddddddd 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(,)11( ,)ifjfpxxffpfdfd x xijf由前文文件检索模型可知，此处 p=6。我们分别计算文件条目 i 和 j 的 6 项对应属性的距离，再进行加权求和最后再进行标准化处理。由于文件条目的 6 项属性的数据类型和含义不完全相同，因此具体的计算方法区别较大，在计算时需要分别考虑。下图为各个属性的数据类型和计算方法。表格 5-1 文件条目各个属性数据类型属属性性数数据据类类型型距距离离计计算算方方法法nameStringMinimal edit distanceextStringNominal VariablessizeIntegerInterval-scaled variablesdateIntegerInterval-scaled variablessiteStringN/ApathStringSubsection string具体方法为：5.2.2.1name 属性距离的计算方法name 表示文件的不包含扩展名的主名的名称，数据类型为字符串型。对于这种字符串类型数据的处理，一般情况下可以按照文档的相似度的方式进行。但由于文件名通常都比较短小，命名多数情况下也不规范。这里并不建议按照文档的形式来处理。我们这里采用的处理方法是按照最小编辑距离的方法来处理。编辑距离是指两个字符串通过插入字符、删除字符、改写字符而变为相同字符串所需要的操作次数。比如：d(“abc”,”abd”) = 1d(“abc”,”ab”) = 1d(“abc”, “abcdf”) = 2d(“serverU”,” ser-u”) = 4利用动态规划的方法计算编辑距离，时间复杂性可以达到O(n2)，空间复杂性 32为 O（n2）。计算方法为一个递归算法：d(, ) = 0d(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 属性距离的计算方法ext 指文件的扩展名，虽然数据类型为字符串，但因此常见的文件类型是有限的，因此可以看成是枚举类型，在聚类算法中则称为标称变量。在进行距离计算时可以按照聚类算法中对于此类数据类型的标准处理方法进行处理，即其距离只是一个二值函数：取值相同则距离为 0；否则距离为 1。但考虑到文件扩展名是有实际含义的，而且很多时候这些不同的扩展名之间还有着丰富的联系，因此我们能够将其处理的更加精确。一般的，我们可以按照文件的扩展名对文件类型进行分类。比如可以将文件分成：程序、图片、音乐、影视、源码等类别。在每个类别内部，可能又有更深的层次，比如源码可能又分为 C/C+源码，JAVA 源码等，而 C/C+源码又可以进一步分为头文件和实现文件等 这样就形成了一棵树。不过要注意的是，这棵树不是平衡的，某些叶节点可能比较深，另外一些可能比较浅。为了形成这棵树，我们还需要说明如下。首先，我们假设每种扩展名只对应于树中的一个节点；其次，我们设置一个根节点，根节点本身不包含如何任何文件类型；再有，对于没有扩展名的文件，我们为其赋予一个特殊的值，并且直接位于根节点之下；对于不能识别的扩展名我们也做同样处理。这样，最后形成了一棵类似下图的树： 33rootprogramvideomusicpicturesourceotherReal format.avi.rm.rmvbC/C+ language.java.himplementation.c.cpp图 5-2 文件扩展名属性距离计算这样，计算任意两个文件条目类型属性的距离演变成了计算树中任意两个叶节点之间的关系。对于树中任意两个叶节点的距离，则表示为其相似程度的倒数。而相似程度的计算，可以按照如下算法。树中每个节点均存在一条从根节点到达它所在位置的唯一路径 P。两个节点的相似程度可以表示为它们各自路径P 中公共节点的个数的函数。在实现上，我们选取如下的函数：假设需要计算两个 ext 值分别为 e1 和 e2 的点 xi、xj在此属性上的距离。设e1 对应的路径为 p1，e2 对应的路径为 p2。p1 和 p2 的公共节点个数为 k（根节点除外），则我们取：2,2,211(,)2ijkdxx 345.2.2.3size 属性距离的计算方法size 属性表示文件条目的文件大小，以字节为单位，数据类型为整数。由于文件大小的取值范围跨度很大，一般能够从几十字节到几十亿字节，因此不适合按照一般区间标度变量的方法来计算，可以按照比例标度型变量来处理。首先对size的值取对数：,3,3log()iiyx不过在实际应用中要注意的是，因为size 的取值范围是非负整数，可能取0，因此不能直接取 log，可以考虑首先将 x1 再取 log。,3,3log(1)iiyx然后将 yi3转化为对应的 z-score 值 Zi3,33,33iiymz s其中.)31,32,3,31nm (yyyn31,332,33331(| | . |)nsymymymn 进行标准化处理之后，再求二者之差： 3,3,3,3,3(,)ijijdxxzz5.2.2.4date 属性距离的计算方法date 属性表示文件的最后修改日期，前面已经说过，我们将原来的字符串格式统一转化为整数，比如按照距离公元元年元旦的日期数。对于整数，属于区间标度变量。为了更好的计算各个项目该属性之间的距离，我们并不直接计算各个条目的差，而是先对其进行标准化处理。将Xi4转化为对应的 z-score 值 Zi4,44,44iixmz s 35其中.)41,42,4,41nm (xxxn41,442,44,441(| | . |)nsxmxmxmn 进行标准化处理之后，再求二者之差：444,4,4(,)ijijdxxzz5.2.2.5site 属性距离的计算方法由于在实际文件共享系统中， site 值最常见的情况就是 IP 地址，而两个 IP 地址之间的距离的比较是没有实际意义的，因此我们忽略两个site 属性的之间的距离，或者可以表示为：5,5,5(,)0ijdxx5.2.2.6path 属性距离的计算方法path 表示文件从根目录开始到其节点所经过的路径。其重要特点就是路径是分段的，是由多个字符串连接而成的。比如路径： /Resource/Software/Tools/network/可以看成是由分段的子字符串 Resource，Software，Tools 和 network 构成的。在对 path 进行比较的时候，我们将每个路径拆分成多个子字符串，然后比较其中公共子字符串的个数占全部子字符串的比例。6,6,6(,)comijijsdxxss公式中 si和 sj分别表示 xi和 xj的 path 属性的分段的个数， Scom为公共子字符串的个数。5.2.3 对用户点击记录进行聚类在本体系中需要对用户的点击日志进行聚类，以便能够得到这k 个不同的用户查询意图。聚类常用的方法有 Partitioning 方法，Hierarchical 方法和 Density-based 方法。根据我们的具体情况，这里选用自底向上的Hierarchical 方法。 36对本方法的图示说明如下： abcdea,bstep 0 step 1 step 2 step 3 step 4d,ec,d,ea,b,c,d,eagglomerative(AGNES)图 5-3 聚类示意图假设共有 5 个对象 a,b,c,d,e，我们将其根据彼此的相关程度进行聚类。首先，将每个待聚类的元素独立划分为一 个自己的类别，如果有 n 个元素，则开始时共有 n 类。然后将距离最近的两个元素归为一类，此时有n-1 类；此后再将距离次近的归为一类，类别共 n-2 类；如此不断重复 如果没有结束标志，则最终将会把所有类别都归为一类。所以必须要设置结束标志。这其中有几点要说明：5.2.3.1结束标志的设定结束标志可以从几个方面来综合考虑。首先是距离因素，设定当距离最近的两个类的距离大于某个类别间的距离阀值D 时不再进行合并操作，设置距离标志D可以防止最后生成的类别过少。另外由规律2 可知相同的查询串通常只表示很少的查询意图，因此可以设定一个最大类别数G，这个表示可以防止最后生成的类别数过多。通过这两个结束标志的综合运用，可以使最终的类别数量控制在较理想的范围中。5.2.3.2具有多个元素的类别之间距离的计算当类别包含多个元素时，计算它们之间的距离有三种不同的方法：计算距离最近的两点之间的距离、最远的两点之间的距离、或者用中心点来计算距离。我们这里选用中心点来计算二者的距离。这个中心点可能是类别中真实存在的一个元素， 37但也可能是一个并不真正包含的虚拟的元素。5.2.3.3孤立点的处理事实上，一些查询串可能会对应一两个或很少的孤立查询记录，这些查询记录和其余大量的查询记录的相似度很低。通过人工查看的方法，我们发现很多这些孤立查询记录其实都是看上去不太正常的记录，比如对于一些大小为0 的文件进行下载，或者下载一些快捷方式文件等。我们认为这些孤立点是因为用户不小心或不了解所致。而这些文件条目实际上并不应该被下载，而应该被抛弃。因此我们需要对这些孤立点进行丢弃。5.2.3.4训练集的生成由于在进行完聚类后我们会对查询再进行分类，因此我们考虑利用聚类中的文件条目作为分类时的训练集。在聚类完成后我们将保留每个查询串的每个类别足够的文件条目。5.2.4 对查询结果集合进行分类常用的分类算法有 k nearest neighbor(kNN), Nave Bayes, 还有 support vector machines 等。我们采用 kNN 算法。其具体步骤为：首先需要有一个训练集。对于每个可能的类别，各自有一些属于该类别的对象。给定一个待分类的对象，系统在训练集中查找与其最相似的k 个对象(称为邻居)，并根据这些邻居所属的类别情况来给该对象的候选类别评分，最后按照分值来确定待分类对象的类别。 38第6章 系统实现与评测6.1系统设计体系结构图实际系统的体系结构图如下。考虑到一些实现问题，和上一章的系统模型略有区别。 Index Part Clustering Part Collection Part 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 部分为用户点击记录收集部分，是实时运行的。在用户进行查询后，文件检索系统返回包含查询串的结果。用户从中选取自己认为正确的文件条目。用户的选取操作就是一次鼠标的点击操作。这个点击动作自动触发到我们的后台 CGI 程序，程序先将用户的下载请求转向到真正的下载地址，后台再发送一个记录点击操作的服务请求。该服务请求由ClickLog Server 接收，并记录到 ClickLog Database 中。我们称用户的每次点击对应的文件条目为 39ClickLog。经过这样反复多次后， ClickLog Database 中记录了大量的 ClickLog，每个 ClickLog 包含一个查询串和对应的文件条目item。6.1.2 聚类部分此部分为聚类操作部分，每隔一段时间运行一次。在实际系统中可以根据用户数量来设定为每小时或每天一次。这部分首先从 ClickLog Database 中读取全部的 ClickLog 条目，然后对每个查询串依次进行处理。取出每个查询串对应的ClickLog 记录，进行聚类，聚类后得到 k 个类别。如前文所述，其中可能存在一些孤立点，然后按照标准对这些孤立点进行考察，需要的话要抛弃掉其对应的孤立类别。聚类操作完成后，将聚类的结果存入Training Set Database 中。至此，我们就得到了实现免用户干预的、基于反馈信息的检索系统所需要的反馈数据。6.1.3 索引部分完成了上面两个部分的工作，就可以进行真正的反馈了。对于用户的查询串q，首先使用常规检索系统进行检索，就可得到一个文件条目Item 的集合。然后在 Training Set Database 中取出对应于查询串 q 的 k 个类别的训练集。利用这些训练集条目为刚刚通过常规查询得到的Item 集合进行分类。此处我们限定每个文件条目至多属于 1 个类别。分类后可能得到 k+1 个类别（某些 Item 可能不属于任何类别），以及每个条目和其所属类别的相似程度。利用分类的类别和相似度，系统可以重新根据此信息进行输出。对于那些不属于任何类别的文件条目，通常也是用户所不太关心的结果，可以选择抛弃或排在结果页面的最后。6.2其它实现中的问题6.2.1 记录用户对查询结果的选取对于用户对查询结果的选取的记录，一般有两种方法，采用client 端技术和server 端技术。为了方便用户的使用，不改变用户的任何使用习惯，我们采取server 端技术来记录用户的选择，这样用户在使用时就不需要丝毫的改变，而我们也能够得到足够的记录信息。 40具体说来，传统网页上的链接一般如下：qqtail.sln我们采用 javascript 技术将其进行改造，改造后的形式如下：QQTail.sln注意其中有 2 处 javascript 脚本。第一处是 onClick 信息，当用户点击了该链接时，自动重新转向到了我们的服务器上，服务器有一个接收该请求的CGI 程序clicklog，这个程序自动转向到实际的 FTP 下载地址，然后向 ClickLog Server 发送一个记录请求， ClickLog Server 就记录下整个查询串和文件条目信息。脚本中的另一处是 onMouseOver，这个是为了处理当用户已经点击该链接后却又突然想复制该链接而使用的。只所以在此处使用了 javascript 而不是直接改变链接地址，是为了便于那些并不希望通过直接点击，而是希望使用下载工具或想复制下载地址的用户的方便。通过现在这种改造，用户看到的页面和链接地址都是和原始信息是完全一致的。6.2.2 文件类型属性距离计算方法的实现前面谈到对于常见的文件扩展名，我们将其各自赋予一个属性值，属性值代表了在文件类别树中从根结点到该文件类型所在节点的所有节点编号的集合。节点的编号示例如下图所示，每个节点的子节点的编号都是从1 开始的，并没有全局性的编号。 41root1234561212121212图 6-2 ext 属性距离计算方法的实现比如对应图中左下角的灰色节点来说，对应的路径为2.1.1；右下角的灰色节点对应的路径则为 5.1.2.2。这样，如果比较两个节点的相似度，我们只需计数它们的路径中相同的节点个数即可。比如路径为 2.1.1 的节点和 2.2 的节点，它们的路径中有一个相同的节点2，或者说相似度为 1 层；路径为 2.1.1 的节点和 2.1.2 的节点，它们的相似度为2 层；路径为 5.3 的节点和路径为 7 的节点相似度则为 0。具体文件类型分类列表见附录 1。配置文件格式，扩展名分类文件的配置文件的格式举例如下：111mp3|wav|wma|112midi|mid|文件说明： 42作用：通过读取文件得到每个扩展名对应的路径。文件格式：每 3 行为一个记录。每个记录中第一行是空行；第2 行是路径，格式为每层节点编号用制表符分割；第3 行是扩展名列表，每个扩展名都以竖线“|”结束。距离计算方法的实现：在系统实现时，定义了一个 ExtVector 类，它代表了一个具体的节点路径，ExtVector 继承自 vector，这里的 vector 是标准 STL 的 vector，并且实现了如下方法来计算两个路径之间的距离：double operator (const ExtVector& e1, const ExtVector& e2); 6.3系统的评测环境我们采用天网千帆文件搜索引擎为测试系统。天网千帆文件搜索引擎为北京大学网络实验室开发的一个 FTP 文件搜索引擎，有较大的用户访问量。在2005 年4 月，我们先后运行了普通文件搜索引擎和我们设计的新型文件搜索引擎，并记录了用户的查询记录和用户对查询结果的选取信息。为了保证评测效果的准确性，在使用了新系统后，我们没有通知任何用户，也没有改变任何用户界面，使测试尽量在用户不知情的情况下进行。对于分类后不能归入任何类别的文件条目，为了保证总体查询结果数量不变，我们也没有进行抛弃，而是放在排序的最后返回给用户。这里采用的排序方法是在页内按照各个初始结果集合 S0中各个条目距离其类别的距离远近进行排序，对不同的类别之间并不进行排序。在结果的表现形式上与普通搜索引擎无异。比较试验共进行了 8 天，其中 4 天为普通文件检索系统，另外 4 天则为我们的新系统。我们分别比较了用户对前2 页查询结果页面中点击的文件条目在该页面中的排序的情况，共取得了 8 组比较数据。6.4评测结果具体比较结果参见下图。图中横坐标表示8 组比较数据，纵坐标为各组试验数据的在页面中点击的条目的排序的平均值。图中上部的曲线（虚线）为普通文件检索系统的结果，下面的曲线（实线）为新系统的试验结果。 43图 6-3 系统试验效果比较从图中可以明显的看到：在新系统下，用户所点击的文件条目在页面中的排序比普通系统有了较大幅度的提前。在我们的试验系统中，普通文件检索系统用户点击的条目在页面中的排名为13.70，而使用了新系统后，点击条目的平均排名为8.93。排名前进了 13.70-8.93=4.77 名。检索效果有了较大幅度的改进。由此可验证本文所述新型文件检索系统的正确性。 44第7章 总结与展望7.1总结作者在本文中首先对文件检索系统进行了一些基础性的研究工作，提出了文件检索系统的检索模型，并提出了评测的指标。然后在对用户使用文件检索系统的行为和习惯进行记录的基础上，发现了用户行为习惯中的两个重要规律。利用这两个规律，作者提出了一个免用户干预的、基于用户查询记录的新型文件检索模型，该模型可以有效的提高文件检索系统的精度。最后作者实现了一个真实的系统并利用该系统对本模型的有效性进行了验证。7.2展望由于研发时间仓促，系统的有些功能还没有来得急加入，有的地方还有待加强，特别如下文所述的几处。7.2.1 目录本文的全部算法都没有考虑目录的特殊性，而在实际的FTP 系统中是存在目录共享的。在本文提到的试验系统中，对目录是不加区分的看成文件来处理，这样在处理效果上就不是很理想了。目录和文件的区别主要表现在这几个方面：首先，目录不存在扩展名属性 ext，这样造成了无法利用这个属性来进行判断，而 ext 属性在距离计算中又是非常重要的一个因素。其次，目录的大小 filesize 往往比较大。因为目录是用来容纳文件的，因此目录的大小必然比其内部的任何文件都要大。这样，就不能直接将目录和文件的大小进行相似度计算。7.2.2 压缩文件类型压缩文件，比如我们通常见到的 zip 文件，rar 文件等。是一种特殊形式的文件。如文中我们所言，文件的扩展名常常表示文件的类型，比如是图片文件、音乐 45文件、视频文件等。而压缩文件本身是为了节省存储空间而通过对其它文件进行压缩而生成的。此类文件的意义在于其所压缩的文件，而本身的文件类型是没有意义的。这样就造成了文件类型属性 ext 判断的失效。在另一个属性上，文件大小，对于压缩文件也是意义不明显的。因为压缩方式的区别，造成压缩比例的差异，同样大小的原始文件，可能压缩为不同大小的压缩文件；压缩后同样大小的文件，其原始文件可能也是不同的。因此直接用文件大小这个属性来比较压缩文件也是不准确的。如上这些特性，造成了压缩文件不适于按照一般的文件类型来进行比较，应该进行专门的处理。 46参考资料Ruthven, et al., 2003 I. Ruthven and M. Lalmas, A survey on the use of relevance feedback for information access, Knowledge Engineering Review. Vol 18. Issue 2. pp 95-145. 2003.Chang, et al., 1996 Chen-Chuan K. Chang, Hctor Garca-Molina, and Andreas Paepcke. Boolean Query Mapping Across Heterogeneous Information Sources. IEEE Transactions on Knowledge and Data Engineering, 8(4): 515-521, Aug, 1996.Zhang and Dong, 2002 Dell Zhang, Yisheng Dong. A novel Web usage mining approach for search engines, computer networks, 2002, vol.39: 303-310.Allison, 1999 Allison, L. Dynamic programming algorithm (DPA) for edit distance, In Algorithms and Data Structures Research & Reference Material. School of Computer Science and Software Engineering, Monash University, Australia 3168. 1999Beeferman, et al., 2000 D. Beeferman, A. Berger, Agglomerative clustering of a search engine query log, in: Proceedings of ACM KDD, 2000, Boston, MA, USA.Salton, et al, 1983 G. Salton, M. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, New York, 1983.Lewis, 1995 D. D. Lewis. Evaluating and optimizing autonomous text classification systems. In Proceedings of SIGIR-95, 18th ACM International Conference on Research and Development in Information Retrieval, pages 246254, Seattle, US, 1995.Ripeanu, 2001 M. Ripeanu, peer-to-peer Architecture Case Study: Gnutella, Network, University of Chicago Technical Report TR-2001-26.RFC 959 RFC 959, File Transfer Protocol (FTP)陈华等，2003 陈华，李晓明，高级文件搜索引擎核心功能的实现技术，全国搜索引 47擎与 Web 挖掘进展会议，2003.3 15-27天网 天网千帆文件搜索引擎 http:/天网 maze 天网 maze 文件共享系统 http:/王建勇等, 2001 王建勇、单松巍、雷鸣、谢正茂、李晓明，海量 web 搜索引擎系统中用户行为的分布特征及其启示， 中国科学E 辑，2001 年 8 月，第 31 卷，第四期，372-384 页陈华等,2004 陈华，王继民，韩近强，谢欣，互联网上 FTP 文件的分布特征及启示，计算机工程与应用 ， 2004 年第 40 卷，129-133 48附录：文件类型列表 音频文件： 1常用：1.1 声音记录 1.1.1mp3|wav| wma| 音阶 1.1.2midi| mid|cda| mp1|m3u|mjf|voc|xm|s3m|stm|mod|dsm|far|ult|mtm|mp2|mpa|669|aac|mp4|vqf|pls|xpl|lrc|rmi|snd|aif|wax|rms|aiff|aifc|mpga| 视频文件 2电影常用格式 2.1 real 格式 2.1.1rmvb| rm| 高清晰 2.1.2avi|短篇格式 2.2 mpg| mpeg| asf| wmv| mpe| dat| asx|mkv|字幕 2.3 vob|ram|rmm|rmj|wvx|m1v|wmp|ivf|smi|mpv|ssm|mpv2|mp2v|smil|rv|rp|rf|rt| 49wm|ra|kbk|la1|lar|lavs|lmsff| 图形文件 3web 常用格式 3.1 jpg|bmp|gif| png| jpe|矢量 3.2 wmf|pcx|tif|psd|tga|pic|pcd|dib|rle|iff|lbm|jif|dcx|ico|tiff|ilbm| 代码文件 4C/C+ 4.1 c|h| cpp|hpp|JAVA 4.2 java|class|PASIC 4.3 pas|BASIC 4.4 bas|汇编 4.5 asm|perl 4.6 perl|js|inc|cxx|tli|tlh|hxx|inl|def|odl|idl|py| 压缩文件 5常用格式 5.1 rar|zip|linux 压缩格式 5.2 gz|tar|tgz|b64| gz| z|arj|cab| arc| bhx|hqx|lzh|mim|taz|uue|xxe|tz|uu| 网页文件 6静态 6.1 htm|html|shtml|动态 6.2 50 php|asp| php3|jsp|web 程序 6.3 htw|htx|css|url| 程序相关文件 7可执行文件 7.1 windows 程序 7.1.1exe|msi| Dos 文件 7.1.2com|bat| unix 程序 7.1.3out|系统文件 7.2 ocx|dll|drv| 文本文件 8txt|asa|wri|log|scp| 系统配置文件 9配置文件 9.1 ini|inf|conf|注册表文件 9.2 reg| office 文档 10Word 文挡 10.1 doc|rtf|wbk|Excel 文档 10.2 xls|xlb|xlc|PowerPoint 文档 10.3 ppt| 帮助文档 11hlp| Flash 文档 12swf|fla| Acrobat 文档 13pdf|pdx|apf|fdf|rmf|xfdf| Caj 文档 14caj|kdh|其它不可识别格式 51致谢首先要向我的导师 表示衷心的感谢，感谢他在我三年的硕士生阶段和本论文的完成工作中对我的精心指导和谆谆教诲，他踏实的治学态度和严谨的工作作风使我受益匪浅，他渊博的知识和对事业无止境的追求使我感受至深，他对我的严格要求将对我以后的工作学习产生巨大的影响，使我终生受益，我以作为他的学生而自豪。感谢我的父母，他们在我的成长过程中倾注了极大的心血，他们对我的言传身教和严格要求，将是我这一生中最宝贵的财富。要感谢我的同学，他们对我的论文写作起了非常大的帮助作用，曾经多次帮助过我。 还要感谢我的女友，在我的生活和工作中，给予了我莫大的支持和鼓励。最后，深深感谢每一位关心我的朋友和老师，感谢你们在我成长道路上对我的帮助。 52北京大学学位论文原创性声明和使用授权说明北京大学学位论文原创性声明和使用授权说明原创性声明原创性声明本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。论文作者签名： 日期： 年 月 日学位论文使用授权说明学位论文使用授权说明本人完全了解北京大学关于收集、保存、使用学位论文的规定，即：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。（保密论文在解密后遵守此规定）论文作者签名： 导师签名： 日期： 年 月 日