199706中英文发现系统的转接层子系统索引子系统的设计与实现

《199706中英文发现系统的转接层子系统索引子系统的设计与实现》由会员分享，可在线阅读，更多相关《199706中英文发现系统的转接层子系统索引子系统的设计与实现（32页珍藏版）》请在装配图网上搜索。

1、北京大学学士学位论文 中英文发现系统的转接层子系统、索引子系统的设计与实现论文摘要中国于1994年进入INTERNET，之后INTERNET在中国得到了迅速的发展，中文的WWW信息也迅速增加。这使得在搜索中文信息时也需要一定的搜索工具。由于世界上现有的搜索引擎大部分都是针对英文设计的，它们或支持中文的能力很差，或根本不支持中文。个别支持中文搜索的搜索引擎，它们的数据库中所包含的中文信息的数量十分小，搜索的结果非常不理想。对于日益增长的中国INTERNET来说，实现一个具有大量中文信息数据库，能够良好支持中文检索的搜索引擎已是一种迫切的需求。本论文所描述的系统即是作者参与设计和实现的一个支持中文

2、的搜索引擎。它即支持对中文，英文的简单检索，又支持逻辑运算，模糊匹配等高级检索。它通过对中文的分词，实现了对在中文词汇一级检索的支持；通过对中文，英文的编码，实现了对中文，英文系统核心实现的一致化；通过两级索引机制和索引项的特殊设计，实现了检索的快速命中。论文首先介绍了系统设计和实现的一些背景资料，介绍了WWW的发展于现状，世界主要搜索引擎及其比较，中文的特点与搜索引擎对中文的支持。之后，描述了系统的整体设计，详细介绍了转接层子系统和索引数据库子系统的设计。关键词：搜索引擎 中文分词 索引数据库 编码方案目录第一章 背景介绍.31.1 Internet和WWW的发展与现状.31.2 世界主要得

3、搜索引擎及其比较.41.3 中文的特点和搜索引擎对中文的支持.6第二章 系统概述.102.1 系统设计目标.102.2 系统总体结构.10第三章 转结层子系统的设计.123.1 转结层子系统的设计思想.123.2 中文编码互换.133.3 中英文编码方案.143.4 中文分词.173.5 中英文词汇的自动学习.19第四章 索引数据库子系统的设计.214.1 索引数据库系统的设计思想.214.2 索引数据库的设计.224.3 索引数据库的更新和维护.234.4 索引数据库的检索.25第五章 总结展望.295.1 系统测试和评估.295.2 远景展望.29致谢.31参考文献.32第一章 背景介绍1

4、.1 Internet和WWW的发展与现状Internet的前身是美国国防部高级研究计划管理局（ARPA）在1969年建立的APPANET网，初期只有4台，其设计目标是：当网络中的一部分因为战争等特殊原因而遭到破坏时，其他部分仍能正常运行。80年代初期，ARPA和美国国防部通讯局研制成功了用于异构网络的TPC/IP协议并投入使用，此后美国加州大学伯克莱分校把该协议作为其BSD UNIX的一部分，使得该协议得以流行。1986年，美国国家科学基金（NSF）以5个科研教育服务的超级计算机中心为基础建立NSFNET网络，以便在全国实现资源共享。90年代初到到现在，是Internet增长最迅速的时期，每

5、天都有许多的主机加入到Internet中，以下是这一时期Internet连接主机数的统计资料： 图1.1 90年代Internet连接主机数目统计表（自MIT）随着Internet的迅速发展，Internet的使用性质已从建网初期的科研教育为主，变为现在的商业化，普及化的一种信息资源交流工具。WWW（World Wide Web）起源于欧洲核子研究中心（the European center for unclear research），它最初的目的是用于研究中心内部文档的连接。在1990年9月，第一个基于文本的原形开始运作并在1991年国际超文本会议上作了公众演示。在1993年一月，第一个基于

6、图形界面的WWW浏览器Mosaic诞生了。Mosaic的推出获得了极大的成功，它使得网络脱离了原来单调的字符界面，以及不友好的交互方式，获得了普通用户的喜爱，从而也推动了WWW自身的发展。随着Netscape等新的WWW浏览器的面世，使得WWW浏览器的功能不断加强，WWW信息越来越丰富，这使得WWW具有了更强的吸引力，使得WWW在Internet上的发展势不可挡。WWW的发展速度是惊人的，它的发展速度远远高于Internet的发展速度，但这种发展速度也在随着时间的推移而逐渐下降。在1993年下半年，WWW在不到三个月的时间里翻了一翻。即使到了现在，WWW也在以每六个月翻一翻的速度飞速增长。在I

7、nternet上还支持许多其他服务，如ftp，telnet，e-mail，news，irc等。在WWW产生之前，这些服务占用了Internet的所有流量。WWW产生后，便迅速增长并相继超过了所有的服务，到1995年四月达到了Internet流量的第一位，直到现在还是稳定的处于第一位。中国进入Internet比较晚。高能所是中国第一个进入Internet的单位，在1994年5月。随后，中国教育科研网（China Education and Research Network）在6月也进入了Internet。之后，Internet在中国也得到了十分迅速的发展。到1997年1月，在短短的不到三年的时间

8、里，在cn域下的主机数已达到19739台，这足以证明Internet在中国发展的迅速。1.2 世界主要得搜索引擎及其比较由于WWW的迅速发展，WWW上的信息量急剧增长。在1996年早些时候，Lycos公司通过每日的例行记录，得出的结论是网上大约有1900万网页。根据上面所提及的WWW增长速度，现在网上大概拥有1亿个以上的网页。在如此众多的网页中筛选用户需要的信息，没有十分有效的，自动化的搜索工具是难以想象的。这就象在一个巨大的图书馆中，但这个图书馆没有目录。当用户希望找到一本自己需要的书时，他只能一个一个的书架，一本一本书的查找。这显然对于用户来说是不可忍受的。搜索引擎就象一个自动化的目录一样

9、，它可以帮助用户发现用户所需要的信息来源，并帮助用户去获取它。搜索引擎的工作机制大致如下：首先，搜索引擎用一个绰号为“蜘蛛”的自动代理软件在网址中爬行，访问网络中公开区域的每个站点并记录其网址，从而创建一个详尽的网络目录。而后，搜索引擎根据自己的需要，访问数据库中记录的部分站点或所有站点。系统把“机器人”软件发往要访问的站点，记录每一页的所有文本内容或者从这些信息中提取自己所需的摘要和其他信息。得到的这些信息被存放于一个数据库中，这个数据库必须经常更新，重建，以保持与信息世界的同步发展。最后，数据库中的信息最终是为检索用户服务的。搜索引擎启动一个CGI程序接受用户的搜索请求，把符合用户请求的信

10、息从数据库中提取出来，并按其相关程度排序后输出给用户。随着WWW的迅速发展，专门作为搜索引擎的站点也正以惊人的速度发展。现在网上常用的搜索引擎有Alta Viasta，Excite，InfoSeek，Guide，Lycos，Open Text等第。这些搜索引擎给WWW用户带来了极大的方便。网上的搜索引擎大部分都是对整个WWW进行搜索的。由于搜索的范围相同，各种搜索引擎就有了一种比较的关系。在大量的使用中，各种搜索引擎表现出了许多共同之处，同时页体现出了许多各自的特点。相同之处：1。搜索速度十分快，用户响应时间非常短。搜索时间一般都在12秒之间。这得益于竞争的结果，因为各搜索引擎的设计者都知道速

11、度是用户的最基本需求，在速度上不能满足用户需求将使得他所设计的搜索引擎毫无竞争力。2。搜索结果的准确性依赖于被搜索的内容。对于每一种搜索引擎，除非让它进行以容易描述的主题为基础的简单检索，否则它就会给出相当高比例的无关信息。3。不能很好的支持自然语言。用户的简单的搜索输入，准确的搜索输出的要求在一定的时间内是无法满足的。用户希望得到一个精确的搜索结果时，用户只能通过复杂的布尔表达式来实现其目的。4。在进行相同的搜索时，各个搜索引擎给出的结果有很大不同，虽然结果中也有相当数量的重叠信息。对一个搜索引擎进行相同的搜索时，其返回结果总是相同的。不同之处：现有的搜索引擎主要的特色体现在它的查全率和查准

12、率。查全率主要依赖于搜索引擎的数据库的大小，在这一方面，Alta Vista和Lycos拥有数千万的网页容量，故而有很高的查全率。其他数据库相对较小的搜索引擎在查全率上无法和它们匹敌。查准率主要依赖于数据库索引的建立方式，查询时的算法和对用户搜索要求的理解。在这一方面，InfoSeek的口碑很好。InfoSeek虽然不能给出最全面的信息，但是其搜索结果的相关性非常的好。以下是各种搜索引擎的对比表：Alta VistaExciteInfoSeekLycosOpen Text类型与容量全文本2100万页全文本150万页全文本100万页摘要1900万页全文本150万页数据库FTP站点无无无有有Gop

13、her站点无无无有有新闻组有有有无无精细化搜索结果无无有无有事件敏感性有无有无无搜索高级增强搜索有无无有有布尔运算有无无有有搜索结果描述有有有有有图 1.2 网络搜索引擎对比表1.3 中文的特点和搜索引擎对中文的支持中文是一种象形文字，它与字母文字有着十分巨大的区别。字母文字的字母数量一般都十分有限，例如英文有26个字母，德语有28个字母，俄语有33个字母。由于字母少这个特点，使得字母文字在计算机上的应用十分简单，无论从文字的输入输出，还是文字的传输处理。中文的字的数量却十分的庞大，有数万个字。这些字中的使用频率有相差悬殊，有些常用词几乎每个句子中都有：如的，是等词。有些词十分罕见，只存在于某

14、些特殊用法或姓氏中，在很多字典中都没有收录。对于这些中文的特点，古代印刷术的解释中就有说明，“遇到罕见的字，在现有的字模中没有，当即用泥土刻造该字作为字模使用。”。这也充分说明了很难将汉字搜集完整。中文由于字数多，表示复杂，使得在计算机上使用中文有一定的困难。为了将计算机对中文支持的标准化，国家标准局颁布了国家汉字编码标准（GB编码）。GB编码使用的是扩展ASCII字符集，其使用范围是0xA10xFF。GB编码共收录一级，二级常用字共6768个，每个汉字或汉字符号用两个的字节实现。第一个字节表示该汉字的区号，第二个字节表示该汉字在该区内的编号。由于国家制定了GB标准，使得汉字在计算机上的处理有

15、了一定的标准。但是，在其他方面，如汉字输入，还没有相应的国家标准，使得在这个领域相对混乱。中文的另一个特点是语言的书写方式。在英文的书写中，词语之间以空格作为天然的分隔符，使得每个单词都一目了然。中文则仅仅以标点符号分隔句子，词语之间没有任何分隔符，这使得对中文词汇的划分成为一件困难的事情。例如，句子在古代，人们写信用毛笔。有两种机械的分法：1。在 古代 ， 人们 写信 用 毛笔 。2。在 古代 ， 人们 写 信用 毛笔 。当然，我们一眼就能看出第一种分法是合理的。因为我们能够根据汉语的语法，句子的逻辑关系，以及句子所要表达的意思来确定哪一种分词方法是合理的。显然，第一种分词方法符合汉语的语法

16、，而且按照这种分词方法能够正确的理解句子的意思。而在第二种分词方法中，句子则显得无法让人理解，而且在语法上也不合理，毛笔这个词在句子中的成分显得不明确。在上面的例子中，只要用语法，基本语义等一些规则，就可以判断一个句子的分词方法是否合理。但是，在一些句子中，单单靠这些还是不够的。例如，句子这样的人才能出众。有三种分词方法：1。这样 的 人才 能 出众。2。这样 的 人 才能 出众。3。这样 的 人 才 能 出众。在这三种分词方法（三种理解方法）中，可以发现无论从语法，语义还是逻辑结构上，它们都没有任何不合理的地方。那么到底应该如何对这个句子进行分词？难道一句话的三种分词方法都正确吗？是的，三种

17、分词方法都正确。这个例子就是中文中常常讲起的中文理解的歧义问题。到底应当选用哪一种分词方法就要依据句子所在的上下文环境了。在具体的上下文环境中，我们可以得到其中的一种分词方法。但是，由于中文表达信息的丰富性和不确定性，使得有时即使在确定的上下文环境中，正确的分词方法也不止一种。在人工智能领域中，现在自然语言理解，机器翻译方向十分活跃。在它们所需要解决的一些关键问题中，上面所提及的分词问题就是其中之一。对于第一个例子，只要依赖一个词库，一个语法规则库，加之以简单的语义分析即可解决。但对于第二个例子，实现起来就会十分的困难，至今还没有十分准确，有效的实现方法。由于在中文分词中存在上述的困难，许多系

18、统在实现中文处理系统时干脆就不考虑中文分词，而是把中文信息作为一个一个汉字的排列，即对中文信息实现基于汉字的处理。但是笔者认为，在许多的应用环境中，使用基于词的中文信息处理还是十分必要的。汉语象其他许多语言一样，其语义的表达是基于词汇的。当我们看到这样的一句话“我现在在计算机系学习”时，我们会很自然的把“现在”，“计算机系”，“学习”抽象出来，作为一个有意义的整体来考虑，而不会去顾及到该词中每个单字的详细意义（对于“我”，“在”等这类单字，可以作为由单个字组成的词语来处理）。这正如在生物学中，虽然细胞是由分子，原子等基本单位构成的，但我们在研究有机体的结构，功能时，总是以细胞作为基本单位一样。

19、既然汉语的表达是建立在词汇的基础之上的，那么在计算机系统对中文进行处理时，就应当考虑到词汇的关键作用。由于对单个汉字的处理简单，系统实现相对容易，目前大部分中文处理系统都是基于单个汉字的。基于词汇的中文处理系统在实现上相对复杂，但由于它有良好处理性能，目前发展也十分迅速。以中文检索系统为例，基于单个字的系统对所有文章建立全文索引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引。检索词汇时一次命中，没有烦琐的逻辑运算，速度十分的快。在检索结果的全面性上基于单字的检索要优于基于词汇的检索，但在结果的相关性上基于单字的检索要差于基于词汇的检索，另

20、外在检索速度上要基于单字的检索要慢一些。例如在对关键词“机能”的检索中，有一篇关于通信的文章中含有“A机能向B机发出确认”的句子。那么在基于单字的检索中，结果中将会包含这篇文章，因为句子中机，能两个字都存在而且相邻，系统就认为它符合检索的要求。在基于词汇的检索中，将不会给出这篇文章，因为机，能虽然同时存在而且相邻，但它们在句子中并不构成词汇，所以基于词汇的检索将不能命中它。由此例可见基于单字检索系统的一个致命弱点，即它不能“理解”句子的意思，因而不能给出最切合检索者检索意图的结果。基于词汇的检索系统能在一定程度上“理解”句子的意思，因而在检索结果的相关性上要更好一些。基于单字和基于词汇的检索在

21、实现机制上的不同，它们在很多方面都有很大的区别，对于它们的比较如下：基因字的检索基于词的检索实现难度一般较难中文预处理的实现容易很难检索核心的实现一般容易索引的类型全文索引基于词的索引索引的大小很大（文章的4-5倍）较小（文章的2倍）对逻辑运算的支持一般一般对输出结果按相关度排序很难容易检索速度较慢很快查全率很高较高查准率较低较高图 1.3 基于单字和基于词汇的中文检索系统的比较第二章 系统概述2.1 系统设计目标 1.开发能支持HTTP,NEWS协议的信息发现系统。 2.设计具有高度智能性和适应性的信息发现方法。 3.支持多种汉字编码，如HZ、GB、BIG5等。 4.使用中文分词技术，提取中

22、文摘要和关键词，使中文信息的分析和索引更为有效。 5.跟踪研究HTML、HTTP等相关协议和技术，尽量支持最新的Internet标准。 6.设计开发大型信息索引数据库，及相关的高效的管理和检索算法。 7.开发WWW、EMAIL两种用户访问接口。用户既可以使用任何WWW浏览器进行访问，也可通过发EMAIL来检索。不需要专门的客户程序。 8.开发提供一定的URL映像功能。用户可以直接从本服务器下载已映像的URL的内容，无须再访问原URL。这能在一定程度上减少网络流量。 9.开发跟踪检索功能。能根据用户需要，对某方面的信息进行跟踪查找，定期将新发现的信息用EMAIL通知用户。 10.为用户开发一些信

23、息发现的实用工具程序。2.2 系统总体结构如图2.1所示（下页），系统由HTML存取分析子系统，NEWS存取分析子系统，主控子系统，索引数据库子系统，检索接口子系统，在加上图上未表示出的转接层子系统共6个子系统组成。系统内含有三个数据库，即素材数据库DB1，素材数据库DB2，和索引数据库。系统运转时序如下：第一步：主控子系统控制HTML、NEWS存取分析子系统从WWW和NEWS服务器上获得原始信息，并存入素材数据库DB1和DB2。第二步：索引数据库子系统从素材数据库DB1和DB2中取出原始信息，分析整理后生成索引数据库。第三步：接收到用户的WWW或E-mail格式的检索要求，检索接口子系统通过

24、索引数据库子系统得到检索结果，输出给用户。 图 2.1 系统总体结构图HTML文档 News 服务器 HTML 存取分析 HTML 存取分析 News 存取分析总控索引数据库子系统 E_mail 接口处理 WWW 接口处理 httpd电子邮件 浏览器索引数据库数据库DB1数据库DB2第三章 转结层子系统的设计3.1 转结层子系统的设计思想转结层严格的说不属于系统的核心，因为它的功能只是在处理系统核心和用户之间的交互。用户的需求是多种多样的。对于本系统而言，用户可能是在用英文或中文，对于中文用户，他的中文编码类型可能是GB，BIG-5，HZ等。对于每一种语言，由于它们都是自然语言，在语法，表达方

25、式上都于计算机系统所擅长处理的语法严格，格式固定的数据有相当巨大的差别的。转结层的任务就是把用户多种多样的，复杂的输入转变为数字化，格式固定的系统核心易于处理的输入；再把核心的输出转换为用户能够方便理解的表达。转结层在某种意义上很象在计算机通信中常用的Modem，时时的实现着两种信息的互相转换。转结层子系统的功能示意图如下：自然语言输入编码输入转接层子系统用户系统核心编码输出自然语言输出图 3.1 转结层功能示意图转结层子系统的体系结构图如下：用户转结层子系统中文分词和译码系统核心中文HZBIG-5GB中文BIG-5HZGB中文GB英文英文译码图 3.2 转结层体系结构图在具体的实现中，转结层

26、包含了四个部分：1。 中文编码互换实现中文的GB，BIG-5，HZ编码之间的互相转换。2。 中文分词实现中文的自动分词。3。 中英文编码方案实现对中文，英文词汇的编码和译码。4。 中英文词汇的自动学习实现从用户的输入中自动学习新的中文，英文词汇的功能。3.2 中文编码互换由于中文汉字数量多，相对英文而言编码规则比较复杂。编码规则的复杂就会导致编码种类的多样化，每种编码都有其特长，同时也有一定的使用范围。现有的中文汉字编码有很多种，其中使用量最大的有三种：GB，BIG-5和HZ，在这个系统中也主要支持这三种编码。其中GB是国家标准编码，对应于国家简体汉字字库的一二级常用字，主要使用地区是大陆。B

27、IG-5是台湾所制定的标准编码，它同时支持汉字的简体和繁体形式，主要在台湾以及其他需要使用繁体汉字的场合。HZ是一种为方便网络传输所制定的编码方案，它支持汉字在网上以文本的形式传输。三种汉字编码都是使用两个字节来表示一个汉字，但是每个字节所使用的数字范围，以及每个字节所代表的意义不同。GB编码中两个字节都是使用的扩展ASCII字符集，范围是0xA1-0xFF。BIG-5编码中第一个字节使用的是扩展的ASCII字符集，范围是0xA1-0xFF,第二个字节使用的是ASCII字符集和扩展ASCII字符集，范围是0x40-0xFF。HZ编码使用的两个字节都是ASCII字符集，范围是0x21-0x7F。

28、在系统实现时，采用GB编码作为系统内部编码。当用户使用的是BIG-5或者HZ编码时，调用转换程序将其转换GB编码后递交给系统处理，是GB编码时，直接交给系统处理。这样，中文编码互换主要由两个部分组成：GB和BIG-5的互换，GB和HZ的互换。（A）GB和BIG-5的互换GB和BIG-5编码之间没有相关性，在互换时采用编码转换表的方式进行。即对于一个GB编码的汉字，检索GB到BIG-5的编码转换表，得到该汉字的BIG-5编码。对于BIG-5到GB编码的转换也一样。（B）GB和HZ的互换GB和HZ编码之间的联系很紧密，它们之间的转换相对容易。对于一个GB编码的汉字，只要把每个字节的第8位更改为0，

29、即得到该汉字的HZ编码；HZ编码向GB编码转换时只要把第8位更改为1即可。3.3 中英文编码方案在本搜索引擎的设计中，检索是基于词汇的。因此，对中英文词汇的处理就成为了系统设计的一个核心部分。如何识别一个中英文词，如何找到该词在数据库中所对应的文章就成为了系统检索效率高低的关键。由于中英文词汇都是人们在自然生活中形成，发展而来的，因而内容丰富，数量巨大，而且各个词的长度也相差悬殊。如果把这些自然的词汇直接交给系统核心处理，那么将会提高系统核心处理的复杂度，降低系统核心的效率。解决的一种方法就是利用编码。就象现在已经成为标准的英文ASCII以及中文GB编码方案一样，这些标准通过将自然形成的字符进

30、行编码而使得它们易于计算机的处理。在本系统的设计中同样可以利用这种思想，将比字符更高一级的语言单位-词汇进行编码，使得它易于系统核心的处理。词汇在编码的处理上与字符的有很大的不同。字符编码的每个标准中字符集都是固定，每个字符的编码也都是固定的。而在词汇的编码中，我们不能确定词汇的集合。对于字符来说，字母文字的字符集是完全固定的；相形文字的字符集也是相对稳定的。但对于词汇来说，无论是字母还是相形文字，它们的词汇都是在不断发展的，而且这种发展的速度还相当的快。因此，词汇的编码方案只能是一个动态增长的，而不是静态的方案。这种动态的特点给编码译码的设计带来了一定的难度。编码译码机理描述图：对词汇进行编

31、码原始词库编码词库中英文词汇词码互译编码图 3.3 编码译码机理描述图在这一部分的设计中，对中英文的设计是基本相同的。在这里，我们以中文为例子来介绍编码和译码部分的详细设计。在编码译码部分由三个子部分组成：编码，码到词的翻译，词到码的翻译。（A）编码：编码采用的是从小到大依次分配的方法。即每向编码库加入一个新词时，该词便获得现在编码库中最大编码加一的编码。这样的编码设计方案中，编码和词汇之间没有必然的联系。但是，这样最大程度的利用了编码空间，使得在编码空间内没有空缺（在编码空间中每个编码都对应一个词汇）。在实现编码时，要首先有一个原始的词库。原始词库共有词汇N个，从该词库的第一个词开始，到最后

32、一个词，编码依次为1-N-1。当词库需要扩充时，例如需要向词库添加M个词汇时，那么这M个词汇的编码为N-N+M-1。编码库以文件的方式存在。（B）码到词的翻译：将编码库的词汇，按照编码的大小排序，在内存中建立一个大小为N的char*数组。在码到词的翻译中，将编码作为数组的下标，一次就可以译出对于的词汇。码到词翻译的原理图：词汇数组词汇编码01阿拉伯爱情66。66计算机。N网络图 3.4 码到词的翻译原理图（C）词到码的翻译：在这个翻译过程中，词库在内存中的组织采用有序的散列表结构。（a）散列表的生成：从编码库中获得一个词后，按照下面的散列函数得到该词所对应的地址：word_offset = h

33、 ( word ) = f ( first chinese char )在上个表达式中，f函数作用是一个将中文汉字转化为一个0到6767之间的整数。这是根据GB编码规则设计的，其实现简单迅速。对所有的词汇进行散列后，碰撞的词汇就是以同一个中文汉字开头的词汇。对于碰撞的词汇，用快速排序的方法按照字符串的大小进行排序，保存于碰撞区里。（b）译码的实现：对于一个中文词汇，取该词汇的第一个汉字作为关键码，命中该词汇在散列表中的地址。然后，用二分法在该地址的碰撞区内对该词汇进行匹配。如果匹配成功，则返回该词汇的编码，否则，返回-1。词到码翻译的原理图如下： 中 国 人 民 图 3.5 词到码翻译的原理图

34、在这种译码的设计中，译码的效率还是相当高的。对译码的时间复杂度估计如下：译码时间复杂度=散列表命中时间复杂度+碰撞区命中时间复杂度对于散列表命中时间复杂度来说，其大小总是1，因为它是按照散列地址一次命中的。对于碰撞区命中时间复杂度来说，可以做如下估计。现在中文汉字词库共有词汇62377个，根据国家GB编码标准，共有汉字6767个，这样平均每个汉字的碰撞区内保存有10个词汇。由于使用二分法检索，其检索时间复杂度为log210 + 1 = 4；综以上所述，译码的平均时间复杂度为 1 + 4 = 5；3.4 中文分词中文分词在背景资料中提及很多。在这里主要描述一下中文分词所采用的算法。NN将短语的第

35、一个字译为整数，并将该字记入ret_str中。从字索引数组中得到以该字开头的词表。比较当前项号对应词是否与短语中同长度的词相等。当前项号为-1？相等？将该词记入ret_str。当前项号加1。比较当前项号对应词的第二个字是否与短语第二个字相同。二分法在词表中查找与短语第二个字相同的表序号最小的项。若找到，记录该表序号为当前项号。否则，记录当前项号为-1。相同？返回ret_str.YYNY图 3.6 中文分词的算法描述图本系统中中文分词的设计是在常用的最大匹配算法之上加以加以改进。在词库的组织上仍采用中英文编码方案中的有序散列表结构。其工作机理大体可以这样描述：第一步：根据输入串的第一个汉字命中散

36、列表的一个地址。第二步：在散列表该地址所对应的碰撞区中，用二分法检索与输入串中第二个汉字匹配的所有词中的第一个。第三步：从上一步所得的词开始，向下依次匹配，找到前两个汉字相同的最大匹配的词返回。在这里，我们来估计分出一个中文词的时间复杂度。在工作机理的大体描述中，整个分词过程被分为了三步，总的时间复杂度相当于每一部分时间复杂度的总和。第一步是一次命中的其时间复杂度为1；第二步相当与在译码中检索一个两个汉字组成的词，其时间复杂度同译码部分的估计，为4。第三步，就要看何时匹配成功或者失败。这也就相当与求得中文词汇中前平均两个汉字相同的词的个数。根据现有的词库统计，这个数据大概为1.5（词库中共有词

37、汇6万余条，其中4万余条为两字词）。考虑成功和失败的综合因素，这一部分的时间复杂度为2。由以上三个部分，可以得到分出一个中文词汇的时间复杂度为：1 + 4 + 2 = 7；3.5 中英文词汇的自动学习时代的发展，信息的扩大，同时带来了词汇量的扩大。大量具有时代特色的新词不断的产生出来，如“超媒体”，“VCD”等词汇。如果词库采用静态的，那么它将不能适应时代的发展。许多新涌现出来的，热点的词汇在词库中无法找到，这将大大降低系统的实用价值，使得用户对系统产生怀疑和不信赖。如果由管理员来负责人工的向词库中加入新词汇，一方面给管理员带来了极大的负担；另一方面，管理员也不可能样样精通，他所能了解到的新词

38、将会十分的有限，虽然他可以定期给词库补充一定量的新词，但是更多的新词将会被疏漏掉。本系统所采用的方法是用一个“学习机”来自动的学习。它从WWW网页中和用户的检索输入中来学习最新的词汇，再由管理员进行增删后加入到词库中。这一部分的工作原理图如下：WWW网页“学习机”管理员正式词库预备添加词库用户查询信息“学习机”图 3.7 词汇自动学习的工作原理图对英文的学习主要来源于对WWW网页的分析。网页搜索程序从WWW网上获得大量的WWW网页，并且对它们进行分析关键词，提取摘要等处理。英文就是从关键词部分学习到的。当“学习机”发现它不认识某个关键词时，它就会在预备添加词库中记录下这个词汇，准备以后向词库中

39、加入。对中文的学习主要来源于检索的用户。当他们检索某个中文词汇时，如果词库中没有这个词汇，分词程序将会把它分割成几个字和词。这时，“学习机”也能发现这个事实，它将会把这个词汇记录再预备添加词库中备用。预备添加词库中的“词汇”并不一定合理，这就是为什么需要管理员来进行人工增删管理。例如用户输入词汇“超媒体”，“学习机”学习到它，将它加入到预备添加词库中，管理员认为这个词汇是一个新产生的词汇，它就会把它加入到正式的词库中。这样，在以后的处理中，“超媒体”将会被按照一个词汇处理。如果用户随便输入一个词汇，如“大大小小”，“学习机”也会学习到它，这就需要管理员来判断它是不是一个新词了。第四章 索引数据

40、库子系统的设计4.1 索引数据库子系统的设计思想索引数据库子系统的设计与实现是在整个系统的设计与实现中占用举足轻重的作用。它直接关系到用户检索的响应速度和检索结果的质量，这两个参数都是评价一个搜索引擎优劣的极其重要的参数。在索引数据库子系统的设计中贯穿了效率的思想，无论是在数据库设计，数据库更新的设计还是数据库检索的设计中。正是上一章中描述的编码的思想在这里发挥了巨大的作用。有了编码，使得在数据库中的词汇都有了固定的长度（长整型），有了统一高效的处理方式。在以下索引数据库子系统的详细设计中，就可以具体的体现到编码思想所带来的好处。另一个提高效率的方法是悉心的设计算法，以时间复杂度为设计核心，来

41、提高系统的运行速度。在以下的详细设计中，可以看到设计和选择和系统相适应的算法给系统所带来的运行效率的大大改善。索引数据库子系统的体系结构图如下：检索数据库子系统信息发现子系统用户用户请求索引库更新程序索引库检索程序素材库检索结果索引库图 4.1 索引数据库子系统的体系结构图索引数据库子系统的设计包含三个部分：1。数据库的设计设计数据库的数据结构。2。索引数据库的更新和维护负责索引数据库的插入，删除，更改。3。索引数据库的检索负责索引数据库的简单和逻辑组合检索。4.2 索引数据库的设计中文词码表中文对应关系表族英文词码表英文对应关系表族文章库图 4.2 索引数据库的结构设计图如图4.2所示，索引

42、数据库主要由三个部分构成：1。词码表：对于一个关键词，经译码程序后被转换为一个编码，即词码。词码以下标的方式命中词码表中的表项。词码表表项中记录了该词所对应的对应关系表在对应关系表族中的偏移量，还有这个对应关系表的长度。2。对应关系表族：该表族中每一项为一个对应关系表，它为词码表中的表项所对应。对应关系表中的每一项含有一个编号，就是一篇文章在文章库中的编号（关键码）。对应关系表表项还包含一个对应关系表按照编号大小内排序的指针，还有一个整数记录该关键词在文章中的权值。3。文章库：文章库中每一项记录有文章的作者，摘要，长度等用户可能需要了解的信息。文章库用多个文件进行模拟，本系统实现中使用了64个

43、文件。考虑中英文在编码动态增长上的需要，在词码表和对应关系表族上中英文加以分离，文章库是统一存储的（文章可以是中英文混合的）。4.3 索引数据库的更新和维护索引数据库的更新分为三个步骤：第一步：从素材库（存放WWW网页和NEWS文章信息）中提取更新信息，包括删除，增加，修改三个部分。这三个部分存放于两个文件中，一个文件存放删除信息，一个文件存放增加和修改信息。第二步：根据更改信息，更新文章库，同时生成更新索引所必须的备用文件。第三步：根据第二步中所产生的备用文件，更新索引。1。提取更新信息：这一步主要目的是把索引数据库的更新和对素材库的操作隔离开来。考虑到素材库和索引数据库可能不在一个主机上，

44、更考虑以后分布式索引数据库的需要，这个使得索引数据库和素材库相对独立的步骤是关键和必要的。这一步的设计实现相对容易，它从素材库中利用查询语句，使用一定的查询条件即可得到。2。更新文章库：这一步主要目的是将从素材库中提取的更新信息反映到文章库中。它为每个删除的信息做无效标志；为更改信息做更改标志，把更改的信息记录到文章库中；为增加的信息在文章库中分配存放空间。在这一步里，涉及到对文章库中碎片的管理和对建立索引部分的支持。对文章库中碎片的管理采用可用块表；对建立索引部分的支持采用作废块表和关键词-文章对照表。这一部分的设计参考下面的更新文章库流程图：将文章块号记入可用块号表将文章块号记入作废块号表

45、加入：给文章分配新块号更改：记文章块号入作废表文章写入指定块号分析更新项中的关键词，加入关键词-文章对应表图 4.3 更新文章库流程图3。更新索引库：这一步利用上一步中产生的数据，建立一个高效的索引。这一部分首先利用作废块表，作废原有索引的无效部分，生成索引A；然后利用关键词-文章对照表，生成新索引B；最后将索引A和索引B合并，生成目标索引。以上三步实现了对索引的更新。其流程如图4.4所示。通过新的关键词-文章对应表得到新的中英文词码表和对应关系表族。通过作废块表重构中英文词码表和对应关系表族。归并两个中英文词码表和对应关系表族图 4.4 更新索引库流程图4.4 索引数据库的检索索引库检索的设

46、计是对效率的考验。对于搜索引擎的最终用户，他们所能感受到的效率，关键就在这一部分的速度上。由于系统的设计采用了编码的思想，将对烦琐的词汇处理抛在了系统核心之外，使得系统检索的复杂度大大降低。在检索的逻辑运算中，采用了两重有序表结构，从而使得逻辑运算的复杂度有了极大程度的降低。1。关键词的检索：系统处理单个关键词的检索时，它并不直接将该关键词交给检索子系统，而是交给转结层子系统。转结层子系统对该词汇进行一系列的处理之后，将其转换为一个长整型的整数，再交给检索子系统处理。检索子系统根据该词汇的编码，以下标的形式一次命中词码表中的对应项，提取出该词汇的对应关系表，即查询的结果。关键词检索的原理图如下

47、：译码对应关系表词表词汇编码图 4.5 关键词检索原理示意图2。对逻辑运算的支持：逻辑运算相当于对两个表的处理，即求两个表的交集，并集等一些运算。如果两个表是无序的，那么这种运算的复杂度相当与M*N。这种间复杂度在表的大小较小时，速度是十分迅速的。但是，当表的大小变的十分大时，比如达到1万时，那么M*N = 1亿，这是不可忍受的。而在一个比较实用的搜索引擎中，其平均的每个关键词命中的文章数大概也在万的数量级。显然将表设计成无序表，其处理延时是不能达到实用要求的。在这时就需要将表实现为有序表。对于有序表，就可以利用归并的思想，将两个表的逻辑运算的时间复杂度降为M+N。在这样的时间复杂度情况下，我

48、们在处理长达1万的表时，其所需的时间单位为：M+N = 2万。这样一个改进，在处理关键词命中的1万篇文章时，其速度能提高5000倍！在本系统中，每个关键词对应一个对应关系表。这时对对应关系表中的文章编号域考察：在一个关键词对应的表中，文章编号是唯一的（不会出现重复的现象），故文章编号可以作为表项的关键码。通过对这个码的排序，在表进行逻辑运算是就可以实现归并算法了。由于关键词对应的表已经按照该关键词在对应文章中的权值排序（表的前后顺序），故对文章编号的排序就被设计为内排序，通过表项中的一个指针域实现。在对整个表的使用中，两个排序同样的有效，所以称这个表为两重有序表。根据对实际应用的统计，系统现在

49、支持三种逻辑运算：and，or，comma。它们在系统中的意义如下：and：对于两个关键词都命中的文章为有效文章，其结果权值为两个关键词在该文章中的权值只和。or：对两个关键词中任何一个关键词命中的文章即为有效文章。若文章只包含一个关键词，则文章的结果权值即为该关键词在文章中的权值。若文章中包含了两个关键词，则文章的结果权值为这两个关键词在文章中权值的和。comma：对两个关键词中任何一个关键词命中的文章即为有效文章。若文章只包含一个关键词，则文章的结果权值即为该关键词在文章中的权值。若文章中包含了两个关键词，则文章的结果权值为这两个关键词在文章中权值最大的那一个关键词的权值。在实际的检索实现

50、中，对含有逻辑运算的检索通过如下三步实现：第一步：对每个关键词进行检索得到该关键词的对应关系表。第二步：对得到的对应关系表进行用户指定的逻辑运算。得到按文章编号排序的中间结果表。第三步：对中间结果表进行按照权值排序（快速排序），将排序好的表输出给用户。对复杂检索的时间复杂度估计：假设有两个关键词做以上所支持的三种逻辑运算，并假设第一个关键词命中文章M篇，第二个关键词命中文章N篇，则检索的时间复杂度为：（2）+（M+N）+（LOG（M+N）*（M+N）上式中的三个部分分别对应复杂检索的三个步骤。根据数量级的观点，检索的时间复杂度为：（M+N）*LOG（M+N）第五章 总结展望5.1 系统测试和评

51、估WebGatherWWW搜索引擎经过项目开发组精心的设计，辛苦的编程和调试，目前正处于测试阶段。通过一段时间的运行测试，各子系统都基本达到了设计目标。转结层子系统实现了将复杂的文字信息与核心的隔离，核心运行速度而高效。由于转结层自身设计时对效率的追求，使得转结层自身并没有给系统带来任何的负担。分词，译码，中文编码互译都达到了设计的目标。索引数据库子系统的运行也十分成功。在对索引数据库添加1万篇新文章时，从开始到添加完成共用时间11分钟，通过对运行时的观察统计，有相当的时间消耗在硬盘读写上，如果使用高速硬盘，速度可以进一步提高。检索在检索数据库中有2万篇文章的条件下进行。对于启动一个检索器对单

52、个关键词检索时，系统立即响应，检索时间为0秒（UNIX系统统计，时间精确到秒，以下相同）。当启动一个检索器对多个关键词进行复杂检索时，词汇个数为29个，使用三种逻辑运算，所得检索时间大部分为0秒，个别为1秒。当启动多个检索器同时进行检索时（检索器个数25），检索时间一部分为0秒，一部分为1秒。从以上运行的实际效果和获得的具体数字来看，系统在小数据量时体现了良好的性能。对于大数据量情况下的性能和统计数据，只有在系统投入实际运行中，在数据量积累到一定程度时才能得到。通过对系统实现复杂度和系统规模之间的关系的推导，我们对系统在大数据量情况下的性能十分有把握。5.2 远景展望现在所实现的搜索引擎是一个

53、集中式的，它只拥有一个控制中心和一个检索中心。在数据规模不大（几十万篇文章），检索用户不多（同时有十个左右）的情况下可以发挥其良好的性能。当数据规模再扩大，用户数目再增加时，集中式的系统就很难承受。同时考虑到WWW网页和检索用户的地域特性，使用分布式系统也会带来良好的效用。在这个集中式系统成熟后，项目开发组会继续进行分布式中文搜索引擎WebGather的设计与开发。这个搜索引擎在两年内将会在Internet上投入使用。届时，它将提供功能强大的中英文检索支持。它将侧重于中文信息的发现，向全世界的中文用户提供准确，有效的网络中文信息，使得在Internet对中文信息的检索和发现象英文信息的检索和发现一样的方便，迅速。致谢在系统的设计与实现中，我的指导教师周利民老师给予我了大量的帮助。他指导我阅读了大量的相关资料，在开发过程中给我提出了许多具有创建性的思想，并精心审阅了论文全稿。周老师丰富的知识，谦逊的待人态度，使我受益非浅。陈葆珏教授，刘建国老师在开发中经常参加我们的讨论，给我提出了大量宝贵的建议，使我所实现的系统更加完善，高效。在此，我向几位老师表示衷心的感谢。在共同开发系统的过程中，李全忠、熊怡、王利民、吴小勇同学给予我