【毕业学位论文】（Word原稿）中英文发现系统的转接层子系统、索引子系统的设计与实现-计算机系网络与分布式系统

北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 1 页 论文 摘要 中国于 1994 年进入 后 中国得到了迅速的发展，中文的 息也迅速增加。这使得在搜索中文信息时也需要一定的搜索工具。由于世界上现有的搜索引擎大部分都是针对英文设计的，它们或支持中文的能力很差，或根本不支持中文。个别支持中文搜索的搜索引擎，它们的数据库中所包含的中文信息的数量十分小，搜索的结果非常不理想。对于日益增长的中国 说，实现一个具有大量中文信息数据库，能够良好支持中文检索的搜索引擎已是一种迫切的需求。 本论文所描述的系统即是作 者参与设计和实现的一个支持中文的搜索引擎。它即支持对中文，英文的简单检索，又支持逻辑运算，模糊匹配等高级检索。它通过对中文的分词，实现了对在中文词汇一级检索的支持；通过对中文，英文的编码，实现了对中文，英文系统核心实现的一致化；通过两级索引机制和索引项的特殊设计，实现了检索的快速命中。 论文首先介绍了系统设计和实现的一些背景资料，介绍了 发展于现状，世界主要搜索引擎及其比较，中文的特点与搜索引擎对中文的支持。之后，描述了系统的整体设计，详细介绍了转接层子系统和索引数据库子系统的设计。 关键词 ： 搜索引擎 中文分词 索引数据库 编码方案 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 2 页 目录 第一章 背景介绍 . 发展与现状 . 界主要得搜索引擎及其比较 . 文的特点和搜索引擎对中文的支持 .二章 系统概述 . 统设计目标 . 统总体结构 .三章 转结层子系统的设计 . 结层子系统的设计思想 . 文编码互换 . 英文编码方案 . 文分词 . 英文词汇的自动学习 .四章 索引数据库子系统的设计 . 引数据库系统的设计思想 . 引数据库的设计 . 引数据库的更新和维护 . 引数据库的检索 .五章 总结展望 . 统测试和评估 . 景展望 .谢 .考文献 .京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 3 页 第一章 背景介绍 发展与现状 前身是美国国防部高级研究计划管理局（ 1969 年建立的 ，初期只有 4 台，其设计目标是：当网络中的一部分因为战争等特殊原因而遭到破坏时，其他部分仍能正常运行。 80 年代初期， 美国国防部通讯局研制成功了用于异构网络的 后美国加州大学伯克莱分校把该协议作为其 一部分，使得该协议得以流行。 1986 年，美国国家科学基金（ 5 个科研教育服务的超级计算机中心为基础建立 络，以便在全国实现资源共享。 90 年代初到到现在，是 长最迅速的时期，每天都有许多的主机加入到 ，以下是这一时期 接主机数的统计资料： 图 90 年代 接主机数目统计表 （自 随着 迅速发展， 使用性质已从建网初期的 科研教育为主，变为现在的商业化，普及化的一种信息资源交流工具。 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 4 页 源于欧洲核子研究中心（ 它最初的目的是用于研究中心内部文档的连接。在 1990 年 9月，第一个基于文本的原形开始运作并在 1991 年国际超文本会议上作了公众演示。在 1993 年一月，第一个基于图形界面的 览器 生了。 使得网络脱离了原来单调的字符界面，以及不友好的交互方式，获 得了普通用户的喜爱，从而也推动了 身的发展。随着 新的 览器的面世，使得 览器的功能不断加强，息越来越丰富，这使得 有了更强的吸引力，使得 的发展势不可挡。 发展速度是惊人的，它的发展速度远远高于 发展速度，但这种发展速度也在随着时间的推移而逐渐下降。在 1993 年下半年， 不到三个月的时间里翻了一翻。即使到了现在， 在以每六个月翻一翻的速度飞速增长。 在 还支持许多其他服务，如 。在生之前，这些服务占用了 所有流量。 生后，便迅速增长并相继超过了所有的服务，到 1995 年四月达到了 量的第一位，直到现在还是稳定的处于第一位。 中国进入 较晚。高能所是中国第一个进入 单位，在 1994年 5 月。随后，中国教育科研网（ 6月也进入了 后， 中国也得到了 十分迅速的发展。到 1997年 1 月，在短短的不到三年的时间里，在 下的主机数已达到 19739 台，这足以证明 中国发展的迅速。 界主要得搜索引擎及其比较 由于 迅速发展， 的信息量急剧增长。在 1996 年早些时候，司通过每日的例行记录，得出的结论是网上大约有 1900 万网页。根据上面所提及的 长速度，现在网上大概拥有 1 亿个以上的网页。 在如此众多的网页中筛选用户需要的信息，没有十分有效的，自动化的搜索工具是难以想象的。这就象在一个巨大的图书馆 中，但这个图书馆没有目录。当用户希望找到一本自己需要的书时，他只能一个一个的书架，一本一本书的查找。这显然对于用户来说是不可忍受的。搜索引擎就象一个自动化的目录一北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 5 页 样，它可以帮助用户发现用户所需要的信息来源，并帮助用户去获取它。 搜索引擎的工作机制大致如下： 首先，搜索引擎用一个绰号为“蜘蛛”的自动代理软件在网址中爬行，访问网络中公开区域的每个站点并记录其网址，从而创建一个详尽的网络目录。 而后，搜索引擎根据自己的需要，访问数据库中记录的部分站点或所有站点。系统把“机器人”软件发往要访问的站点，记录每 一页的所有文本内容或者从这些信息中提取自己所需的摘要和其他信息。得到的这些信息被存放于一个数据库中，这个数据库必须经常更新，重建，以保持与信息世界的同步发展。 最后，数据库中的信息最终是为检索用户服务的。搜索引擎启动一个 符合用户请求的信息从数据库中提取出来，并按其相关程度排序后输出给用户。 随着 迅速发展，专门作为搜索引擎的站点也正以惊人的速度发展。现在网上常用的搜索引擎有 第。这些搜索引擎给 户带来了极大的方便。网上的搜索引擎大部分都是对整个 行搜索的。由于搜索的范围相同，各种搜索引擎就有了一种比较的关系。在大量的使用中，各种搜索引擎表现出了许多共同之处，同时页体现出了许多各自的特点。 相同之处： 1。搜索速度十分快，用户响应时间非常短。搜索时间一般都在 12 秒之间。这得益于竞争的结果，因为各搜索引擎的设计者都知道速度是用户的最基本需求，在速度上不能满足用户需求将使得他所设计的搜索引擎毫无竞争力。 2。搜索结果的准确性依赖于被搜索的内容。对于每一种搜 索引擎，除非让它进行以容易描述的主题为基础的简单检索，否则它就会给出相当高比例的无关信息。 3。不能很好的支持自然语言。用户的简单的搜索输入，准确的搜索输出的要求在一定的时间内是无法满足的。用户希望得到一个精确的搜索结果时，用户只能通过复杂的布尔表达式来实现其目的。 4。在进行相同的搜索时，各个搜索引擎给出的结果有很大不同，虽然结果中也有相当数量的重叠信息。对一个搜索引擎进行相同的搜索时，其返回结果总是相同的。 不同之处： 现有的搜索引擎主要的特色体现在它的查全率和查准率。查全率主要依赖于搜索引擎的 数据库的大小，在这一方面， 有数千万的网页容量，故而有很高的查全率。其他数据库相对较小的搜索引擎在查全率上无法和它们匹敌。查准率主要依赖于数据库索引的建立方式，查询时的算法和对用北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 6 页 户搜索要求的理解。在这一方面， 口碑很好。 然不能给出最全面的信息，但是其搜索结果的相关性非常的好。 以下是各种搜索引擎的对比表： 型与容量 全文本 2100 万页 全文 本 150 万页 全文本 100 万页 摘要 1900 万页 全文本 150 万页 数据库 点 无 无 无 有 有 点 无 无 无 有 有 新闻组 有 有 有 无 无 精细化搜索结果 无 无 有 无 有 事件敏感性 有 无 有 无 无 搜索 高级增强搜索 有 无 无 有 有 布尔运算 有 无 无 有 有 搜索结果描述 有 有 有 有 有 图 网络搜索引擎对比表 文的特点和搜索引擎对中文的支持 中文是一种象形文字，它与字母文字有 着十分巨大的区别。字母文字的字母数量一般都十分有限，例如英文有 26 个字母，德语有 28 个字母，俄语有 33 个字母。由于字母少这个特点， 使得字母文字在计算机上的应用十分简单，无论从文字的输入输出，还是文字的传输处理。中文的字的数量却十分的庞大，有数万个字。这些字中的使用频率有相差悬殊，有些常用词几乎每个句子中都有：如的，是等词。有些词十分罕见，只存在于某些特殊用法或姓氏中，在很多字典中都没有收录。对于这些中文的特点，古代印刷术的解释中就有说明，“遇到罕见的字，在现有的字模中没有，当即用泥土刻造该字作为字模使用。”。这也充分说明了很难将汉字搜集完整。中文由于字数多，表示复杂，使得在计算机上使用中文有一定的困难。为了将计算机对中文支持的标准化，国家标准局颁布了国家汉字编码标准（ 码）。 码使用的是扩展符集，其使用范围是 0码共收录一级，二级常用字共6768 个，每个汉字或汉字符号用两个的字节实现。第一个字节表示该汉字的区号，第二个字节表示该汉字在该区内的编号。由于国家制定了 准，使得汉字在计算机上的处理有了一定的标准。但是，在其他方面，如汉字输入，还没有相应的国家标 准，使得在这个领域相对混乱。 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 7 页 中文的另一个特点是语言的书写方式。在英文的书写中，词语之间以空格作为天然的分隔符，使得每个单词都一目了然。中文则仅仅以标点符号分隔句子，词语之间没有任何分隔符，这使得对中文词汇的划分成为一件困难的事情。 例如，句子 在古代，人们写信用毛笔。 有两种机械的分法： 1。在 古代 ， 人们 写信 用 毛笔 。 2。在 古代 ， 人们 写 信用 毛笔 。 当然，我们一眼就能看出第一种分法是合理的。因为我们能够根据汉语的语法，句子的逻辑关系，以及句子所要表达的意思 来确定哪一种分词方法是合理的。显然，第一种分词方法符合汉语的语法，而且按照这种分词方法能够正确的理解句子的意思。而在第二种分词方法中，句子则显得无法让人理解，而且在语法上也不合理，毛笔这个词在句子中的成分显得不明确。 在上面的例子中，只要用语法，基本语义等一些规则，就可以判断一个句子的分词方法是否合理。但是，在一些句子中，单单靠这些还是不够的。 例如，句子 这样的人才能出众。 有三种分词方法： 1。这样 的 人才 能 出众。 2。这样 的 人 才能 出众。 3。这样 的 人 才 能 出 众。 在这三种分词方法（三种理解方法）中，可以发现无论从语法，语义还是逻辑结构上，它们都没有任何不合理的地方。那么到底应该如何对这个句子进行分词？难道一句话的三种分词方法都正确吗？ 是的，三种分词方法都正确。这个例子就是中文中常常讲起的中文理解的歧义问题。到底应当选用哪一种分词方法就要依据句子所在的上下文环境了。在具体的上下文环境中，我们可以得到其中的一种分词方法。但是，由于中文表达信息的丰富性和不确定性，使得有时即使在确定的上下文环境中，正确的分词方法也不止一种。 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 8 页 在人工智能领域中，现在自然语 言理解，机器翻译方向十分活跃。在它们所需要解决的一些关键问题中，上面所提及的分词问题就是其中之一。对于第一个例子，只要依赖一个词库，一个语法规则库，加之以简单的语义分析即可解决。但对于第二个例子，实现起来就会十分的困难，至今还没有十分准确，有效的实现方法。 由于在中文分词中存在上述的困难，许多系统在实现中文处理系统时干脆就不考虑中文分词，而是把中文信息作为一个一个汉字的排列，即对中文信息实现基于汉字的处理。但是笔者认为，在许多的应用环境中，使用基于词的中文信息处理还是十分必要的。 汉语象其他许多语言 一样，其语义的表达是基于词汇的。当我们看到这样的一句话“我现在在计算机系学习”时，我们会很自然的把“现在”，“计算机系”，“学习”抽象出来，作为一个有意义的整体来考虑，而不会去顾及到该词中每个单字的详细意义（对于“我”，“在”等这类单字，可以作为由单个字组成的词语来处理）。这正如在生物学中，虽然细胞是由分子，原子等基本单位构成的，但我们在研究有机体的结构，功能时，总是以细胞作为基本单位一样。既然汉语的表达是建立在词汇的基础之上的，那么在计算机系统对中文进行处理时，就应当考虑到词汇的关键作用。 由于对单个 汉字的处理简单，系统实现相对容易，目前大部分中文处理系统都是基于单个汉字的。基于词汇的中文处理系统在实现上相对复杂，但由于它有良好处理性能，目前发展也十分迅速。以中文检索系统为例，基于单个字的系统对所有文章建立全文索引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引。检索词汇时一次命中，没有烦琐的逻辑运算，速度十分的快。在检索结果的全面性上基于单字的检索要优于基于词汇的检索，但在结果的相关性上基于单字的检索要差于基于词汇的检索，另外在检索速度上要基于单字 的检索要慢一些。 例如在对关键词“机能”的检索中，有一篇关于通信的文章中含有“ A 机能向 B 机发出确认”的句子。那么在基于单字的检索中，结果中将会包含这篇文章，因为句子中机，能两个字都存在而且相邻，系统就认为它符合检索的要求。在基于词汇的检索中，将不会给出这篇文章，因为机，能虽然同时存在而且相邻，但它们在句子中并不构成词汇，所以基于词汇的检索将不能命中它。由此例可见基于单字检索系统的一个致命弱点，即它不能“理解”句子的意思，因而不能给出最切合检索者检索意图的结果。基于词汇的检索系统能在一定程 度上“理解”句子的意思，因而在检索结果的相关性上要更好一些。 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 9 页 基于单字和基于词汇的检索在实现机制上的不同，它们在很多方面都有很大的区别，对于它们的比较如下： 基因字的检索 基于词的检索 实现难度 一般 较难 中文预处理的实现 容易 很难 检索核心的实现 一般 容易 索引的类型 全文索引 基于词的索引 索引的大小 很大（文章的 4） 较小（ 文 文 文 英文译码 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 13 页 图 转结层体系结构图 在具体的实现中，转结层包含了四个部分： 1。 中文编码互换 实现中文的 码之间的互相转换。 2。 中文分词 实现中文的自动分词。 3。 中英文编码方案 实现对中文，英文词汇的编码和译码。 4。 中英文词汇的自动学习 实现从用户的输入中自动学习新的中文，英文词汇的功能。 文编码互换 由于中文汉字数量多，相对英文而言编码规则比较复杂。编码规则的复杂就会导致编码种类的多样化，每种编码都有其特长，同时也有一定的使用范围。 现有的中文汉字编码有很多种，其中使用量最大的有三种： 这个系统中也主要支持这三种编码。其中 国家标准编码，对应于国家简体汉字字库的一二级常用字，主要使用地区是大陆。 台湾所制定的标准编码，它同时支持汉字的简体和繁体形式，主要在台湾以及其他需要使用繁体汉字的场合。 一种为方便网络传输所制定的编码方案，它支持汉字在网上以文本的 形式传输。 三种汉字编码都是使用两个字节来表示一个汉字，但是每个字节所使用的数字范围，以及每个字节所代表的意义不同。 码中两个字节都是使用的扩展符集，范围是 0码中第一个字节使用的是扩展的符集，范围是 0二个字节使用的是 符集和扩展符集，范围是 0码使用的两个字节都是 符集，范围是 0 在系统实现时，采用 码作为系统内部编码。当用户使用的是 者 码时，调用转换程序将其转换 码后递交给系统处理，是 码北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 14 页 时，直接交给系统处理。这样，中文编码互换主要由两个部分组成： 互换。 （ A） 互换 码之间没有相关性，在互换时采用编码转换表的方式进行。即对于一个 码的汉字，检索 编码转换表，得到该汉字的码。对于 码的转换也一样。 （ B） 互换 码之间的联系很紧密，它们之间的转换相对容易。对于一个 汉字，只要把每个字节的第 8 位更改为 0，即得到该汉字的 码； B 编码转换时只要把第 8 位更改为 1 即可。 英文编码方案 在本搜索引擎的设计中，检索是基于词汇的。因此，对中英文词汇的处理就成为了系统设计的一个核心部分。如何识别一个中英文词，如何找到该词在数据库中所对应的文章就成为了系统检索效率高低的关键。 由于中英文词汇都是人们在自然生活中形成，发展而来的，因而内容丰富，数量巨大，而且各个词的长度也相差悬殊。如果把这些自然的词汇直接交给系统核心处理，那么将会提高系统核心处理的 复杂度，降低系统核心的效率。 解决的一种方法就是利用编码。就象现在已经成为标准的英文 及中文 码方案一样，这些标准通过将自然形成的字符进行编码而使得它们易于计算机的处理。在本系统的设计中同样可以利用这种思想，将比字符更高一级的语言单位 得它易于系统核心的处理。 词汇在编码的处理上与字符的有很大的不同。字符编码的每个标准中字符集都是固定，每个字符的编码也都是固定的。而在词汇的编码中，我们不能确定词汇的集合。对于字符来说，字母文字的字符集是完全固定的；相形文字的字符集也是 相对稳定的。但对于词汇来说，无论是字母还是相形文字，它们的词汇都是在不断发展的，而且这种发展的速度还相当的快。因此，词汇的编码方案只能是一个动态增长的，而不是静态的方案。这种动态的特点给编码译码的设计带来了一定的难度。 编码译码机理描述图： 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 15 页 图 编码译码机理描述图 在这一部分的设计中，对中英文的设计是基本相同的。在这里，我们以中文为例子来介绍编码和译码部分的详细设计。 在编码 译码部分由三个子部分组成：编码，码到词的翻译，词到码的翻译。 （ A）编码： 编码采用的是从小到大依次分配的方法。即每向编码库加入一个新词时，该词便获得现在编码库中最大编码加一的编码。这样的编码设计方案中，编码和词汇之间没有必然的联系。但是，这样最大程度的利用了编码空间，使得在编码空间内没有空缺（在编码空间中每个编码都对应一个词汇）。 在实现编码时，要首先有一个原始的词库。原始词库共有词汇 N 个，从该词库的第一个词开始，到最后一个词，编码依次为 1词库需要扩充时，例如需要向词库添加 M 个词汇时 ，那么这 M 个词汇的编码为 码库以文件的方式存在。 （ B）码到词的翻译： 将编码库的词汇，按照编码的大小排序，在内存中建立一个大小为 N 的 组。在码到词的翻译中，将编码作为数组的下标，一次就可以译出对于的词汇。 码到词翻译的原理图： 对词汇 进行 编码 原始 词库 编码 词库 中英文词汇 词码互译 编码 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 16 页 图 码到词的翻译原理图 （ C）词到码的翻译： 在这个翻译过程中，词 库在内存中的组织采用有序的散列表结构。 （ a）散列表的生成： 从编码库中获得一个词后，按照下面的散列函数得到该词所对应的地址： h ( = f ( 在上个表达式中， f 函数作用是一个将中文汉字转化为一个 0 到 6767 之间的整数。这是根据 码规则设计的，其实现简单迅速。对所有的词汇进行散列后，碰撞的词汇就是以同一个中文汉字开头的词汇。对于碰撞的词汇，用快速排序的方法按照字符串的大小进行排序，保存于碰撞区里。 （ b） 译码的实现： 对于一个中文词汇，取该词汇的第一个汉字作为关键码，命中该词汇在散列表中的地址。然后，用二分法在该地址的碰撞区内对该词汇进行匹配。如果匹配成功，则返回该词汇的编码，否则，返回 词到码翻译的原理图如下： 词汇数组 词汇编码 0 1 阿拉伯 爱情 66 。 66 计算机 。 N 网络 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 17 页 图 词到码翻译的原理图 在这种译码的设计中 ，译码的效率还是相当高的。对译码的时间复杂度估计如下： 译码时间复杂度 =散列表命中时间复杂度 +碰撞区命中时间复杂度 对于散列表命中时间复杂度来说，其大小总是 1，因为它是按照散列地址一次命中的。对于碰撞区命中时间复杂度来说，可以做如下估计。 现在中文汉字词库共有词汇 62377 个，根据国家 有汉字 6767个，这样平均每个汉字的碰撞区内保存有 10 个词汇。由于使用二分法检索，其检索时间复杂度为 1 = 4； 综以上所述，译码的平均时间复 杂度为 1 + 4 = 5； 文分词 中 国 人 民 0 爱1 把。6 6 中。N 字 0 称。 。 。 1 3 2 2 华1 3 2 3 国。 。 。1 3 2 6 国 人 民。 。 。1 3 3 0 指 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 18 页 中文分词在背景资料中提及很多。在这里主要描述一下中文分词所采用的算法。北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 19 页 图 中文分词的算法描述图 N N 将短语的第一个字译为整数，并将该字记入 。 从字索引数组中得到以该字开头的词表。 比较当前项号对应词是否与短语中同长度的词相等。 当前项号为 相等？ 将该词记入 当前项号加 1。 比较当前项号对应词的第二个字是否与短语第二个字相同。 二分法在词表中查找与短语第二个字相同的表序号最小的项。若找到，记录该表序号为当前项号。否则，记录当前项号为 相同？ 返回 Y Y N Y 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 20 页 本系统中中文分词的设计是在常用的最大匹配算法之上加以加以改进。在词库的组织上仍采用中英文编码方案中的有序散列表结构。其工作机理大体可以这样描述： 第一步：根据输入串的第一个汉字命中散列表的一个地址。 第二步：在散列表该地址所对应的碰撞区中，用二分法检索与 输入串中第二个汉字匹配的所有词中的第一个。 第三步：从上一步所得的词开始，向下依次匹配，找到前两个汉字相同的最大匹配的词返回。 在这里，我们来估计分出一个中文词的时间复杂度。在工作机理的大体描述中，整个分词过程被分为了三步，总的时间复杂度相当于每一部分时间复杂度的总和。第一步是一次命中的其时间复杂度为 1；第二步相当与在译码中检索一个两个汉字组成的词，其时间复杂度同译码部分的估计，为 4。第三步，就要看何时匹配成功或者失败。这也就相当与求得中文词汇中前平均两个汉字相同的词的个数。根据现有的词库统计，这个数 据大概为 库中共有词汇 6 万余条，其中 4 万余条为两字词）。考虑成功和失败的综合因素，这一部分的时间复杂度为 2。由以上三个部分，可以得到分出一个中文词汇的时间复杂度为： 1 + 4 + 2 = 7； 英文词汇的自动学习 时代的发展，信息的扩大，同时带来了词汇量的扩大。大量具有时代特色的新词不断的产生出来，如“超媒体”，“ 词汇。如果词库采用静态的，那么它将不能适应时代的发展。许多新涌现出来的，热点的词汇在词库中无法找到，这将大大降低系统的实用价值，使得用户对系统产生怀疑和不信赖 。如果由管理员来负责人工的向词库中加入新词汇，一方面给管理员带来了极大的负担；另一方面，管理员也不可能样样精通，他所能了解到的新词将会十分的有限，虽然他可以定期给词库补充一定量的新词，但是更多的新词将会被疏漏掉。 本系统所采用的方法是用一个“学习机”来自动的学习。它从 页中和用户的检索输入中来学习最新的词汇，再由管理员进行增删后加入到词库中。这一部分的工作原理图如下： 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 21 页 图 词汇自动学习的工作原理图 对英文的学习主要来源于对 页的分析。网页搜索程序从 上获得大量的 页，并且对它们进行分析关键词，提取摘要等处理。英文就是从关键词部分学习到的。当“学习机”发现它不认识某个关键词时，它就会在预备添加词库中记录下这个词汇，准备以后向词库中加入。 对中文的学习主要来源于检索的用户。当他们检索某个中文词汇时，如果词库中没有这个词汇，分词程序将会把它分 割成几个字和词。这时，“学习机”也能发现这个事实，它将会把这个词汇记录再预备添加词库中备用。 预备添加词库中的“词汇”并不一定合理，这就是为什么需要管理员来进行人工增删管理。例如用户输入词汇“超媒体”，“学习机”学习到它，将它加入到预备添加词库中，管理员认为这个词汇是一个新产生的词汇，它就会把它加入到正式的词库中。这样，在以后的处理中，“超媒体”将会被按照一个词汇处理。如果用户随便输入一个词汇，如“大大小小”，“学习机”也会学习到它，这就需要管理员来判断它是不是一个新词了。 “学习机” 管理员 正式 词库 预备添 加词库 用 户查询信息 “学习机” 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 22 页 第四章 索引数据库子系统的 设计 引数据库子系统的设计思想 索引数据库子系统的设计与实现是在整个系统的设计与实现中占用举足轻重的作用。它直接关系到用户检索的响应速度和检索结果的质量，这两个参数都是评价一个搜索引擎优劣的极其重要的参数。 在索引数据库子系统的设计中贯穿了效率的思想，无论是在数据库设计，数据库更新的设计还是数据库检索的设计中。 正是上一章中描述的编码的思想在这里发挥了巨大的作用。有了编码，使得在数据库中的词汇都有了固定的长度（长整型），有了统一高效的处理方式。在以下索引数据库子系统的详细设计中，就 可以具体的体现到编码思想所带来的好处。 另一个提高效率的方法是悉心的设计算法，以时间复杂度为设计核心，来提高系统的运行速度。在以下的详细设计中，可以看到设计和选择和系统相适应的算法给系统所带来的运行效率的大大改善。 索引数据库子系统的体系结构图如下： 图 索引数据库子系统的体系结构图 检索数据库子系统 信息发现子系统 用户 用户请求 索引库 更新程序 索引库 检索程序 素材库 检索结果 索引库 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 23 页 索引数据库子系统的设计包含三个部分： 1。数据库的设计 设计数据库的数据结构。 2。索引数据库的更新和维护 负责索引数据库的插入，删除，更改。 3。索引数据库的检索 负责索引数据库的简单和逻辑组合检索。 引数据库的设计 图 索引数据库的结构设计图 中文词码表 中文对应关系表族 英文词码表 英文对应关系表族 文章库 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 24 页 如图 示，索引数据库主要由三个部分构成： 1。词码表： 对于一个关键词，经译码程序后被转换为一个编码，即词码。词码以下标的方式命中词码表 中的表项。词码表表项中记录了该词所对应的对应关系表在对应关系表族中的偏移量，还有这个对应关系表的长度。 2。对应关系表族： 该表族中每一项为一个对应关系表，它为词码表中的表项所对应。对应关系表中的每一项含有一个编号，就是一篇文章在文章库中的编号（关键码）。对应关系表表项还包含一个对应关系表按照编号大小内排序的指针，还有一个整数记录该关键词在文章中的权值。 3。文章库： 文章库中每一项记录有文章的作者，摘要，长度等用户可能需要了解的信息。文章库用多个文件进行模拟，本系统实现中使用了 64 个文件。 考虑中英文在编码动态增长上的需要，在词码表和对应关系表族上中英文加以分离，文章库是统一存储的（文章可以是中英文混合的）。 引数据库的更新和维护 索引数据库的更新分为三个步骤： 第一步：从素材库（存放 页和 章信息）中提取更新信息，包括删除，增加，修改三个部分。这三个部分存放于两个文件中，一个文件存放删除信息，一个文件存放增加和修改信息。 第二步：根据更改信息，更新文章库，同时生成更新索引所必须的备用文件。 第三步：根据第二步中所产生的备用文件，更新索引。 1。提取更新信息： 这一步主要目的是把索引数据库的更新和对素材库的操作隔离开来。考虑到素材库和索引数据库可能不在一个主机上，更考虑以后分布式索引数据库的需要，这个使得索引数据库和素材库相对独立的步骤是关键和必要的。 这一步的设计实现相对容易，它从素材库中利用查询语句，使用一定的查询条件即可得到。 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 25 页 2。更新文章库： 这一步主要目的是将从素材库中提取的更新信息反映到文章库中。它为每个删除的信息做无效标志；为更改信息做更改标志，把更改的信息记录到文章库中；为增加的信息在文章库中分配存放空间。 在这一步 里，涉及到对文章库中碎片的管理和对建立索引部分的支持。对文章库中碎片的管理采用可用块表；对建立索引部分的支持采用作废块表和关键词 一部分的设计参考下面的更新文章库流程图： 图 更新文章库流程图开 始 开 始 N 还 有 文 章 删 除 ？Y N 还 有 更 新 项 ？Y 将文章块号记入可用块号表 Y 该 文 章 在 库 中 ？ 加入： 给文章分配新块号 更改： 记文章块号入作废表 结 束 文章写入 指定块号 分析更新项中的关键词，加入关键词 结 束 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 26 页 3。更新索引库： 这一步利用上一步中产生的数据，建立一个高效的索引。这一部分首先利用作废块表，作废原有索引的无效部分，生成索引 A；然后利用关键词 生成新索引 B；最后将索引 A 和索引 B 合并，生成目标索引。以上三步实现了对索引的更新。其流程如图 示。 图 更新索引库流程图 引数据库的检索 索引库检索的设计是对效率的考验。对于搜索引擎的最终用 户，他们所能感受到的效率，关键就在这一部分的速度上。 由于系统的设计采用了编码的思想，将对烦琐的词汇处理抛在了系统核心之外，使得系统检索的复杂度大大降低。 在检索的逻辑运算中，采用了两重有序表结构，从而使得逻辑运算的复杂度有了极大程度的降低。 开 始 通过新的关键词 通过作废块表重构中英文词码表和对应关系表族。 归并两个中英文词码表和对应关系表族 结 束 北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 27 页 1。关键词的检索： 系统处理单个关键词的检索时，它并不直接将该关键词交给检索子系统，而是交给转结层子系统。转结层子系统对该词汇进行一系列的处理之后，将其转换为一个长整型的整数，再交给检索子系统处理。检索子系统根据该词汇的编码，以下标的形式一次命中词码表中的 对应项，提取出该词汇的对应关系表，即查询的结果。 关键词检索的原理图如下： 图 关键词检索原理示意图 2。对逻辑运算的支持： 逻辑运算相当于对两个表的处理，即求两个表的交集，并集等一些运算。如果两个表是无序的，那么这种运算的复杂度相当与 M*N。这种间复杂度在表的大小较 小时，速度是十分迅速的。但是，当表的大小变的十分大时，比如达到 1 万时，那么 M*N = 1 亿，这是不可忍受的。而在一个比较实用的搜索引擎中，其平均的每个关键词命中的文章数大概也在万的数量级。显然将表设计成无序表，其处理延时是不能达到实用要求的。 在这时就需要将表实现为有序表。对于有序表，就可以利用归并的思想，将两个表的逻辑运算的时间复杂度降为 M+N。在这样的时间复杂度情况下，我们在处理长达 1 万的表时，其所需的时间单位为： M+N = 2 万。这样一个改进，在处理关键词命中的 1 万篇文章时，其速度能提高 5000 倍 ！ 在本系统中，每个关键词对应一个对应关系表。这时对对应关系表中的文章译码 对应关系表 词表 词汇 编码 。文 章 库。北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现 第 28 页 编号域考察：在一个关键词对应的表中，文章编号是唯一的（不会出现重复的现象），故文章编号可以作为表项的关键码。通过对这个码的排序，在表进行逻辑运算是就可以实现归并算法了。 由于关键词对应的表已经按照该关键词在对应文章中的权值排序（表的前后顺序），故对文章编号的排序就被设计为内排序，通过表项中的一个指针域实现。在对整个表的使用中，两个排序同样的有效，所以称这个表为两重有序表。 根据对实际应用的统计，系统现在支持三种逻辑运算： 们在系统中的意义如下： ：对于两个关键词都命中的文章为有效文章，其结果权值为两个关键词在该文章中的权值只和。 ：对两个关键词中任何一个关键词命中的文章即为有效文章。若文章只包含一个关键词，则文章的结果权值即为该关键词在文章中的权值。若文章中包含了两个关键词，则文章的结果权值为这两个关键词在文章中权值的和。 对两个关键词中任何一个关键词命中的文章即为有效文章。若文章只包含一个关键词，