【毕业学位论文】（Word原稿）搜索引擎的日志分析-方法、技术和应用-计算机系网络与分布式系统

北京大学学士学位论文 第 1 页 论 文 摘 要 本文首先介绍了 迅速发展状况，分析了 息资源的特点。在介绍已有的搜索引擎之后，分析了这些搜索引擎的特点。 随后，本文对“天网”搜索引擎系统进行了介绍，给出了该系统的总体结构、技术特征，并分析了该系统的性能。 然后，文章介绍了“天网”系统中的信息统计子系统。信息统计子系统是为系统管理人员评估系统性能、维护系统效率、更好满足用户的查询要求而设计实现的。本文给出了信息统计子系统的总体结构，并详细介绍了该子系统的 两个重要部分，数据库信息处理和日志文件信息处理的设计目标和实现算法，并介绍了如何让机器自动学习新词。 关键词 ： 搜索引擎、信息统计、机器学习新词 北京大学学士学位论文 第 2 页 目 录 目 录 . 2 第一章 背景介绍 . 3 发展与现状 . 3 索引擎技术的发展与现状 . 5 第二章 系统概述 . 6 统的总体结构 . 6 统技术特征 . 6 体性能 . 8 第三章 信息统计子系统 . 10 统的改进需求 . 10 息统计子系统的总体结构 . 10 行条件 . 11 用界面 . 11 第四章 数据库信息处理的实现 . 14 计目标 . 14 据库处理 . 14 用次数排行表 . 15 . 16 计各个域内的主机数目 . 18 机情况查询 . 19 第五章 日志文件信息处理的实现 . 20 计目标 . 20 件处理 . 20 词学习 . 22 致谢 . 25 参考文献 . 26 北京大学学士学位论文 第 3 页 第一章 背景介绍 发展与现状 一个规模巨大、自治性强、发展变化快，用户访问频繁的国际互联网络。 前身是 60 年代末， 70 年代初美国国防部高级研究计划署的实验性网络 建 最初原因是当时计算机的价格非常昂贵，所以科研工作者们想通过网络进行远程计算。后来，人们才逐渐认识到它作为通讯手段的好处。 1983 年后， 有关军事的部分被隔离为 后， 1986年诞生的美国国家科学基金会 发展起了划时代的作用。 90 年代初到现在，是 长最迅速的时期。 1993 年， 增长速度是 341%。截止到 1996 年 7 月， 连接了 134336 个网络，入网主机 1228 万台，以及数以亿计的用户。 的信息资源随着 信息量大而且分散 自治性强 信息资源多种多样 信息变化快 不一致和不完整性 这些特点对网络软件的性能提出了很高的要求。 全球性的网络信息系统。一九八九年，位于瑞士的先开始了 研究工作。随后，许多其它的研究机构、大学和公司也加入 究者的行列，并相继开发出各自的 件。这些 件的运行平台覆盖了目前主流的计算机硬件和操作系统。在此过程中， 不断完善和发展。同时，为了保证不同 件之间的互操作性，一系列 议和标准也正在使用和完善之中。 基于超文本（ 超媒体 (分布式信息系统。超文本和超媒体是信息的一种组织形式，如图 示： 北京大学学士学位论文 第 4 页 在超文本文件中，包含有许多指针，这些指针被称为超文本链 (每一个超文本链都指向其它的超文本信息。这些超文本信息可能存放在同一台计算机中，也可能存放在 息系统的其它计算机中。读者并不关心这些超文本信息存放在何处，如果他们想了解这些信息，他们就可以通过超文本链得到。超媒体是对超文本的扩展。在超媒体系统中，超媒体链可以指向 任何媒体信息，包括图象、音频、视频等等。超文本和超媒体为用户进行信息检索提供了极大的方便。 . . . 图 京大学学士学位论文 第 5 页 索引擎技术的发展与现状 随着 迅速发展， 出现了 息查询服务，它们通常被称作搜索引擎。这些搜索引擎一般是预先由程序自动地在网上递归地访问 访问的信息存入数据库。然后将数据库中的信息建立索引，并提供给用户 查询界面。搜索引擎根据用户的请求查询数据库，并将结果按相关程度排序后输出给用户。 目前的搜索引擎大致可分为三大类：分类编目搜索引擎 (机器人搜索引擎 (元搜索引擎（ 分类编目搜索引擎以 代表，机器人搜索引擎以 司的 代表 , 元搜索引擎以 国外搜索引擎起步较早，功能全面，性能良好，但是它们的共同缺点是都不能很好地支持中文信息的发现和查询。虽然 搜索引擎在 1998年上 半年宣布支持中文，但在对中文信息的处理上尚存在很多不足，如不能准确切词，不能在上下文环境中理解语义等等。 北京大学学士学位论文 第 6 页 第二章 系统概述 统的总体结构 “天网（ 中英文搜索引擎系统是为满足用户对中国教育科研计算机网（ 的信息资源的检索和查找需要而研制开发的。本系统的研制列入 用系统课题项目，其目标是建立 能广泛应用的 源索引与查找系统。它符合相关的 准，能够自 动对 时建立 源索引数据库，以满足远程 览器的交互式查询请求，并将查询的结果以 件的形式返回给用户。 本系统主要由 息存取和分析子系统、 息收集控制子系统、 源索引数据库、信息检索子系统、管理和监控子系统等几个部分组成。其总体结构如图 示。 统技术特征 本系统有以下技术特征： 1 信息收集符合 相关协议和标准。 因为本系统收集的主要是 的信息，所以在设计开发时把对有 关协议和标准的支持 作为一个重要的目标。这些协议和标准包括： 议、言、 准、 议。 2 实用、高效的信息分析方法。 本系统主要根据 不同的 分页面中各个部分信息内容在文章中的重要性和所处的位置，并结合使用中文分词、词频统计和一定的自然语言理解技术，智能化地提取该页面的关键词和摘要。 3 高度智能性和适应性的信息发现方法 我们在本系统中主要使用程序方式自动收集 息，即 器人方式。在该方式中，有一个能自动在 中获取信息并进行漫游的程序根据 档中 的超链，自动收集和索引 息这种方式速度快、基本不需人工干预。 北京大学学士学位论文 第 7 页 务器 取分析 存取分析 存取分析 部接口 部接口 部接口 主控模块 索服务器 索引数据 库 口处理 口处理 子邮件 浏览器 档 图 京大学学士学位论文 第 8 页 4 中文信息处理技术 中文信息处理与英文存在很大不同，这是因为中文信息处理具有很多自己 的特点，这使中文信息的词语切分 (切词 )成为汉语信息处理的第一道关口，也是建立中文信息发现和检索系统的关键性技术之一。我们使用 以带词类标记的词典为基础、以切词与标注相结合的方法处理中文信息， 较好地解决了汉语的切词问题。 5 可伸缩的分布式结构 本系统主要由信息收集子系统和信息检索子系统两部分组成。这两个子系统之间既相互联系，又相互独立，可以分布在不同的主机上分别运行。 6 基于词的大型、高效的信息索引数据库和快速、准确的检索方法。 本系统主要采用基于词的索引，以达到较快的速度和较高的准确性，同时减少索引信息对磁盘空间 的占用。 在索引库中采用分级的优化索引结构和多级索引技术，将较小的一级索引驻留内存，检索操作过程大部分在内存中进行，尽量减少对硬盘文件的访问。因而大大提高了检索的响应速度。索引库支持增量修改和索引。以减少数据复制时产生的网络流量，提高索引速度。 7智能化、多功能的用户检索接口。 用户可以通过浏览器直接访问本系统，还可以使用 询接口。 体性能 存 引数据库和检索数据库分开等先进 、 有效的技术，使得系统占用资源少、信息收集 速度快、用户查询响应时间快（系统对 上的查询可在 1秒钟之内作出响应）、查准率和查全率较高，基本达到了实用化程度。 系统在设计和实现过程中，充分考虑到了用户和管理员的使用习惯，提供了浏览器、电子邮件、中英文用户接口和方便易用、功能丰富的管理工具，因而有很好的可用性和易用性。 天网从 1997年 10月在 到了用户的欢迎和好评。 统计数字表明了系统的使用情况： 北京大学学士学位论文 第 9 页 时间 1998 年 1999 年 3 月 1999 年 4 月 平均每天访问人次 2200 10113 15333 由于天网功能全面、性能突出，软件世界杂志年第 7期将天网评价为国内最好的中英文搜索引擎。 北京大学学士学位论文 第 10 页 第三章 信息统计子系统 统的改进需求 经过测试和改进，到 1998 年，天网搜索引擎已经可以很好地为广大网络用户服务了。在 ，平均每天有几千人次访问天网搜索引擎。许多研究人员、教师都把天网搜索引擎作为他们工作中的重要工具。为数众多的大中院校学生每天通过天网搜索引擎查询专业信息，了解社会动态，和娱乐消遣。 随着系统的 广泛使用，对索引数据库以及用户查询记录进行处理，从中提取出有用的信息，帮助系统管理人员评估系统性能、维护系统效率、更好满足用户的查询要求，成为一个急待解决的问题。信息统计子系统就是为这个目的而设计的。 该子系统通过处理索引数据库产生关于网上页面、主机状况的信息，如页面的平均长度、页面的被引用情况、页面的编码类型、主机上的页面数等等；通过处理用户查询记录文件产生关于用户需求的信息，如用户的访问次数、访问类型、常查询的词语，并可以自动学习新词。 息统计子系统的总体结构 界面程序 数据库信息 处理程序 日志信息 处理程序 用户查询 日志文件 索引 数据库 结果文件 图 求 结果 调用 调用 北京大学学士学位论文 第 11 页 信息统计子系统的总体结构如图 示。 信息统计子系统主要分为三大模块。第一部分是数据库信息处理程序，它启动运行后，从索引数据库中读取数据，统计出信息，写在结果文件中。这部分内容又可分为统计页面信息和统计主机信息两部分。第二部分是日志处理程序，它读取用户查询日志文件，处理得到的信息也记录在几个结果文件中。第三部分是使用界面程序，它根据使用者的要求启动数据库信息处理程序、日志信息处理程序、或是显示某些查询结果。 行条件 本子系统与主系统一样，硬件平台选用的是 作站。整个程序是在 境下用 C 语言开发的。程序中使用了一些 C 语言的库函数，数据库统计部分采用 嵌入式数据库查询语言。 用界面 界面部分使用网络研究室自己开发的 C 语言图形编辑函数库，采用 主菜单的形式如下： 菜单：脱机启动各统计程序。 菜单：清除以前的统计记录，使 得以后运行各统计程序得到的结果并不在这之前的记录上累加。 菜单：查询与用户查询情况有关的信息。 菜单：查询与数据库内页面有关的信息。 菜单：查询与数据库内主机有关的信息。 菜单：退出主菜单。 单的形式如下： 京大学学士学位论文 第 12 页 项：启动统计页面情况的程序。 项：启动统计主机情况的程序。 项：启动统计用户日志情况的程序。 单的形 式如下： 项：删除以前统计的词的查询频率的记录。 项：删除以前统计的新词频率记录。 项：清空所有的查询次数计数器。 单的形式如下： 项：查询次数和种类的统计信息。 项：显示近期内的查询统计信息。 菜单：查询词语的出现频率。 菜单：查询学习到的新词。 单的形式如下： 项：查询各编码类型的页面数。 项：查询与页面长度有关的信息。 项：显示被引用次数最高的一百个页面。 项：显示总页面数。 单的形式如下： 项：显示主机总数。 项：显 示每个域的主机数。 项：查询有关某个主机的信息。 北京大学学士学位论文 第 13 页 单的形式如下： 项：显示被查询次数在 5 到 10 次之间的词。 项：显示被查询次数在 10 到 20 次之间的词。 项：显示被查询次数在 20 到 50 之间的词。 项：显示被查询次数在 50 到 100 之间的词。 项：显示被查询次数在 100 以 上的词。 单的形式如下： 项：显示学习到的长度为 2 的词。 项：显示学习到的长度为 3 的词。 项：显示学习到的长度在 4 以上的词。 北京大学学士学位论文 第 14 页 第四章 数据库信息处理的实现 计目标 1 统计数据库中一共有多少个页面，这样可以帮助估计数据库的规模和系统的服务能力。 2 统计数据库中一 共有多少个主机。 3 统计各种编码类型的页面各有多少，这样可以知道大部分用户查询需要怎样被处理，从而估计影响系统效率的关键因素。 4 统计被引用次数最多的 100 个页面，这可以反映出网上比较受欢迎的信息。 5 统计数据库中各个长度范围的页面数和页面的平均长度，用来估计系统所占用的空间。 6 统计各个域内的主机数目，反映网上的主机分布情况。 7 查询某个主机是否在索引数据库中收录，如果被收录，它的上面有多少页面被收录到索引数据库内。 据库处理 功能示意图如下： 索引 数据库 读数据库 函数 中间文件 全局变量 图 京大学学士学位论文 第 15 页 对索引数据库的处理分为 两部分，一部分是对页面的统计，主要是对据库中的 中的数据进行处理，提取出关于页面的有用信息；另一部分是对主机的统计，主要是对 据库中的 中的数据进行统计，提取出关于主机的有用信息。 由于索引数据库中的信息量很大，共有一百多万页面，七千多个站点，对数据库内的数据如果完全用 句处理，会使统计的速度非常慢。因此，采用的算法是只通过一遍扫描，将数据库中有用的信息存在一些中间文件和 后用双链表等手段处理这些中间文件，得到 结果文件。 为保证系统的效率，程序中只用了一条最简单的 句。 页面统计程序中，每从数据库中读取一个信息，都要进行如下处理： 将该页面的网址写在一个文件中。 将该页面所在的主机的信息插入 ，并在 相应的项的域中记录该页面的网址在上一文件中的位置。 页面数计数器加 1。 增加页面总长度。 该页面长度所在的范围的计数器加 1。 该文件所属的编码类型的计数器加 1。 将该页面的网址、标题、引用次数写入一个文件。 主机统计程序中，每从数据库中读取一个信息，都要进行如下处理： 主机数计数器加 1。 找到 该主机所在的域，并将该域的计数器加 1。 用次数排行表 将所有页面的引用次数都记录在一个文件中后，要对该文件进行处理，从中找出引用次数最高的 100 项。 因为数据库中有一百多万个页面，所以该文件的数据量很大，必须采用高效的算法。又因为最终只要产生前 100 项就可以了，所以不必将文件中的数据全部排序。 北京大学学士学位论文 第 16 页 经过比较，我采用了下面的算法： 1 将中间文件中的前 100 项用插入排序法加入双链表。 2. 读中间文件后面的项，如果某一项的引用次数小于当前双链表中的最后一项，直接将它略去；否则，将它插入双链表，并将最后一项除去， 保证双链表中只有 100 项。 算法效率评估： 该算法只需要一遍扫描文件，刚开始时，双链表的内容变换比较频繁，但处理过一些数据之后，双链表中的 100 项的引用次数就会高于文件中的大多数项。这时，很多项都不需要插入双链表。 在 100 项的双链表中插入一项的平均比较次数是 50 次，在双链表中插入和删除一项时，并不需要移动别的项。 如果文件中有 N 项，该算法所需的比较次数远小于 50N 次。所以，该算法的时间复杂度为 O(N)，效率较高。 该算法所占用的空间仅为 100 项的双链表所需的空间，空间代价也较低。 存放各主机上的页面信息。 1 的结构如下： 表中共有 99991 项，每一项是一个记录，该记录的结构是： 内 容 类 型 主机 址 字符串 主机上的页面数 整数 主机上的页面总长度 双精度浮点数 各编码类型的页面数 整数数组 存放页面地址链表中的最末项位置 整数 下一表项的指针 指针 存放页面地址的链表 指针 北京大学学士学位论文 第 17 页 2 数如下： 将 址看作以 256 为基数的整数，将它除以 99991 的余数作为散列地址。 为防止计算整数时溢出，采用如下方法： （ 1） 先计算 256 的 N 次方除以 99991 的余数，放在一个数组中。流程图如下： （ 2） 址中的每一位，如果是数字，就把该位看作是该数字表示的数，如果是 .，就把该位看作 10。计算余数的流程如图 示。 3 每处理一个页面，就调用一次 数，如果该页面所在的主机没有被插入 ，就插入该主机的信息；否则，修改 中记录的该主机的页面数和页面总长度，并把中间文件中存 放该页面网址的位置加入结构体的最后一项所表示的链表。 第一项 = 1 第二项 = 256 第三项 = （ 256*256） %99991 j 16 ? 第 j 项 = （第 *第 1 项） % 99991 j = j+1 j = 3 结束 no 京大学学士学位论文 第 18 页 4 因为共要处理一百多万个页面，所以如果存放页面地址链表中的每一项只放一个地址，就会耗尽系统的存储空间。解决方法是将链表中的一项定义成一个数组，再用一个整数表示该链表的最后一项所指的数组中最后一项的位置。 计各个域内的主机数目 每个域各有一个码字和一个域标号，对任何一个主机，如果某个域的码字取反，在与该主机的 址相交，得到的是这个域的域标号，那么该主机属于这个域。 设数据库内共有 N 个主机，有 n 个域，该算法的时间代价为 O( j = 0 地址 = 0 中的第 j 位 为结束标志 地址 =地址 +第 j 为表示的数 *余数数组的 第 j 位 j = j+1 地址 =地址 % 99991 结束 no 京大学学士学位论文 第 19 页 机情况查询 在将 的内容写入结果文件时，每将一个主机的信息写入文件，同时按照存放页面地址的链表，将该主机上的所有页面的网址从中间文件中找到，并拷贝到结果文件中。 这样得到两个文件： 在一个文件中可以查到主机 址，主机上的页面数，主机上的页面网址在另一页面上的起始位置。在另一文件上，每个主机上的页面都存放在一起。根据起始位置和页面数，就可以顺序读取该主机上所有页面的网址 。 用户查询时，可以输入主机的 址或主机域名，程序会自动将域名转化为 址，然后根据 址从第一个文件中找到该主机的项，再根据第一个文件中的起始位置和页面数，从第二个文件中找到该主机上的所有页面。 第一个文件只有几千项，查找时间较短。第二个文件虽然有一百多万项，但可以直接定位，顺序地读所有需要的项。所以，该算法的时间代价不高，可以满足实时查询的需要。 主机 起始位置 m 页面数 n m m+n 文件 1 文件 2 图 京大学学士学位论文 第 20 页 第五章 日志文件信息处理的实现 计目标 1 统计总查询次数，反映用户的使用情况。 2 统计 中率，反映系统的 运行效率。如果 中率过小，说明系统的效率需要改进。 3 统计 中的查询所需要的总时间，和从数据库中得到查询结果的操作所需要的总时间。用来反映 效率如何，如果需要，可以以此数据为基础，变换 大小。这两个数据也反映了系统的平均查询时间，即对用户要求的反映速度。 4 统计 作和 作的总次数，表明用户操作的类型，可以帮助估计系统处理的关键操作是什么，把提高系统性能的关键放在优化处理关键操作的算法上，较少出现的情况不必投入太多的精力。 5 统计最近一个月内每天用户查询的次数，本年 内每月的用户查询次数，去年的用户查询次数，和今年的用户查询次数。通过这组数据来反映系统近期内的使用情况，以便及时了解用户的动态，更好地满足用户的要求。 6 统计数据库内的词语被查询的次数，并按照查询频率的不同范围分类，在各类内排序。了解词库的使用情况。 7 自动学习新词语，并按照词语的出现频率将词语排序。每过一段时间，提交给系统管理员一份新词表，系统管理员经过筛选，可以将部分词语加入词库。使得系统管理员可以随时根据用户的需求调整词库的内容。 件处理 有一个日志文件编辑程序，用来处理日志文件。 首先，它先 打开一个配置文件，从该配置文件中读取要处理的日志文件名。配置文件中可以有一个或多个日志文件名。如果有多个，就会顺序处理这些文件。 打开要处理的日志文件后，一行一行地读文件。每读出一行，就分析该行的北京大学学士学位论文 第 21 页 内容。日志文件中关于一次查询的内容如图 示。 6 15:27:53 1998 :367 :P : : :葡萄品种 : : :1 :126 * 图 据每行开始的内容，可以转而进行不同的处理。情况如下： 第一个词是 行时间处理，如果进行查询时的时间是在本月内，当天的查询次数加 1。如果是在本年内，当月的查询次数加 1，并且本年的查询次数加 1。如果是在去年，去年的查询记录加 1。 第一个词是 种情况统计查询次数。 前两个词是 行查询内容处理。 前两个词是 种情况 统计查询次数。 前两个词是 种情况统计查询所用的总时间。 第一个字符是 * 、 -，或者第一个词是 者前两个词是 接处理下一行。 其他情况，进行错误处理。 查询内容处理进行的操作如下： 北京大学学士学位论文 第 22 页 1 调用分词程序，将用户提交的查询信息分成单个的词。 如： “阿联酋是一个国家” “阿 联 酋 是 一 个 国家” 2 将分出的词逐个加入 ，统计词的出现频率。 3 用另一个 进行新词学习。 词学习 用户的查询语句中很可能会出现一些词库中没有的词，碰到这种情况，系统会调用分词程序，将这些词分成几个的词。 如： “红楼梦” “红 楼 梦” “信息化” “信息 化” 系统为检索这样的信息，就要进行多次匹配，如上面的“红楼梦”就要匹配三次，而“红”，“楼”，“梦”等单字词的出现频率是很高的，所以这样的查询会需要较长的时间。如果要系统管理员自己人工学习这些新词，将是一个很繁重的工作，而且系统管理员无法去了解 所有的领域，找出所有的社会热点。如果系统能够根据用户的查询信息，将这些经常出现在用户的查询要求中，但词库中又没有收录的汉字组合整理出来，提交给系统管理员，系统管理员只要稍稍修改，就可以直接加入词库。这将是一种比较方便和高效的算法。新词学习程序的任务就是发现这些新词。 新词学习程序的处理过程是： 调用分词程序之后，用户一次提交的查询内容被分为单词，如： “阿联酋是一个国家” “阿 联 酋 是 一 个 国家” 从第一个单 词开始，将词的组合插入 ，直到组合的长度大于 8 为止。 如上例中，得到： 阿联、阿联酋、阿联酋是、阿联酋是一、阿联酋是一个、阿联酋是一个国家 很明显，这样得到的组合中，很多都是不可能作为一个词的， 如： 阿联酋是、阿联酋是一、阿联酋是一个、阿联酋是一个国家 我们可以作这样的改进。“是”，“的”，“了”等词在句子中出现时，大多北京大学学士学位论文 第 23 页 数情况下，并不会与其它的字组成词，而是用来连接别的词。所以，我们可以在碰到这些词的时候，就停止处理。 在系统中有一个禁用 词文件，所有该文件中的词，在分词后都有一个特殊的返回码。我们可以简单地通过返回码来判断是否停止处理。 经过这样的改进之后，“ 阿联酋是”、“阿联酋是一”、“阿联酋是一个”、 “阿联酋是一个国家”，就不会被插入 了。 然后，再从第二个词开始寻找组合，以此类推。 因为用户提交的查询一般都不会太长，所以该算法的时间代价不会超过 O（ N）。 在处理完日志文件后，所有的新词组合都被插入 。把这些新词从写到一个文件中，写入时，将出现频率太低的组合都舍去