互关联后继树技术及其在黄页搜索引擎系统中的应用

胡运发  陶晓鹏  王政华  杨笑天

（复旦大学信息科学与工程学院  上海200433）

摘  要  本文详细研究了互关联后继树技术在中国电信黄页搜索引擎系统中的应用。其技术核心是互关联后继树全文索引模型，它能够较好地满足搜索引擎对全文索引的各项要求。本文还给出了应用系统的软件设计方案，主要功能模块和使用方法。

关键词  互关联后继树  搜索引擎  黄页搜索  系统实现  使用说明

1  互关联后继树模型

搜索引擎作为一门技术，虽然相对比较年轻，但是已经有了很大的发展。在这个过程中，该技术用到了各种不同的全文索引模型。其中，比较常见和流行的有以下几种：署名文件（signature files）、位图（bit map）、倒排表（inverted files）、∑2矩阵Pat树和Pat数组等等。然而，这些模型虽然在专家们的努力下，都有了相当的发展和实践经验，可仍然不能够符合本项目的需求。

倒排表模型虽然在网页搜索引擎中得到了广泛的应用，也具有创建索引速度较快的优点，但是查询速度较慢。署名文件虽然实现简单，但是要找到一个合适的散列函数和一个宽度适合的矢量非常困难，而且因对象而异。如果没有选择好，则查询结果就会出现相当的不确定性。这同我们的设计要求是大相径庭的。位图文件索引结构思路简单，使用方便，时间效率高，在布尔检索上尤其高效，但是顾名思义，这种用Bitmap的进行组织的索引建立方式空间效率很低，即便使用了位图压缩算法，仍然难以接受。PAT树模型检索效率很高，然而同位图模型一样，空间效率极低，而且创建过程中空间开销更大。作为PAT树叶节点串行化的PAT数组模型，虽然很大程度上压缩了创建过程中的开销，但是，因为采用数组的存储方式，其创建和合并需要移动大量的数据，动态性很难令人满意。

黄页系统则采用了一种相对年轻的全文模型――互关联后继树搜索模型。它在很大程度上克服了前述几种模型的缺点，具有查询功能更加完备，创建和查询速度更快，空间效率较高等优点。同时，它还能够将全文从索引中重新生成，而在很大程度上避免了对原文的依赖。

用非形式化的语言来说，互关联后继树是将全文本对象以及检索串都看作是字符串。设长度为n的文本串s，那么它所包含的子字符串数目为：1/2n(n+1)，我们从中挑选出从文本中任一位置到文本末尾形成的字串，共有n个，并称之为半无限串（Sistring）。然后将所有半无限串的前三个字符截出，不足三个字符的则全部选中，作为建立互关联后继树的对象。

举例而言，设s为：bcaeacbcba#。则分解并编号的结果为：1）bca 2)cae 3)aea 4)eac 5)acb 6)cbc7)bcb 8)cba 9)ba 10)a。接着，找到所有可能的起始字符分别建树（在实际工程中，这些树是预先设置好的）。分别为a，b，c，e。接着用如下方式对他们进行组织：从第一个字符串开始考察，首字符为b，则应当放入b树中，同时，它的后继为字符c，则树的第一个分支设定为c，如下图：

同时，这个c的后继字符为a，则同样设置根为c，第一个分支为a的树如图。

同时，我们可以看出，b树的c分支后继的是c树的第一个分支，所以记为c（1），成为：

以此类推，可以将所有的树组织成如下模式：

通过这种方式，节点被串联起来，并可以方便地从索引中推出全文。以本串为例，第一个字符为b，则从b树开始，第一棵分支为c，数字为“1”，代表b之后的字符为c，并且后续为c的第一棵分支。然后转换到c分支，查询的第一棵分支为a，数值为1，则调转到a树的第一棵分支，以此类推，最终到结束符“#”，代表字符串结束，并获取整个原串：bcaeacbcba#。

下面对互关联后继树做一个形式化的定义：

定义1：设Σ是数目有限的字母表，数目记作|Σ|=M。例如a、b、c、……、x、y、z就是一个英文字母表。字母表中字母的有序组合便是一个文本，设为：z1z2……zm，然后在zm后认为添加一个不在Σ中的标志符，标志文档的结尾，一般用eof，在本文中统一使用“#”。

定义2:    对任意文本符号a1、a2，在字符串a1a2中，a1称为a2的前驱:a2称为a1的后继。例如：上例bcaeacbcba中，b是caeacbcba的前驱，caeacbcba是b的后继， ea是 c 的前驱，c是ea的后继。

在本文中，一个全文字符串a1……a2aN #中，若出现了m个相同的字符（设为a），而a的后继共有 m 个（可能包括#在内），则记为：（a［k］，k=1、2、……、m)，a ［k］代表a的第 k个后继。

定义3：对于任意字符串a1a2…ai…aN，ai∈Σ，i=1、2、……、N，i指明字符ai在字符串中的位置,a1a2……aN构成一个全文数据库，比如上例中的bcaeacbcba#就是一个全文数据库。

定义4：在全文数据库中，若ai1、ai2、……、ain为相同的字符，设为a，显然a∈Σ，则所有a和它的后继构成一个一元后继表达式a（ai1+1、ai2+1、……、ain+1），其中a为根结点，ai1+1、ai2+1、……、ain+1为后继结点。上例中a的后续包括：e、c、#，则它和它的后继构成一元后继表达式a（e、c、#）。

定义5：在全文数据库中，若ai1ai1+1、ai2ai2+1、……、ainain+1是相同的字符串，（即ai1=ai2=……=ain；ai1+1=ai2+1=……=ain+1），不妨设他们为ab，显然a、b∈Σ，则ab和他们的后继构成一个二元后继表达式：a（b（ai1+2、ai2+2……aim+2））；其中ab为根节点。在上例中，bc出现两次，则可以建立二元后继表达式为：b（c（a、b））。

以此类推，可以定义n元后继表达式。

定义6：对全文数据库a1a2…ai…aN，存在某个一元后继表达式，a（ai1、ai2、……、ain）中某个后继的ait，1≤t≤n, 若存在ait（at1、……、atk、……、atm），1≤k≤m，且aaitayk∈所在的全文数据库a1a2…ai…aN，则称a（ai1，…ai（t-1），ait（atk），ai(r+1)，ain），为a（ai1，ai2，……，air，……，ain）关于ait的二元互关联后继表达式。

定义7：对全文数据库a1a2…ai…aN，对所有的后继表达式的所有后继子结点进行后继关联，得到的关联后继表达式的全体称为互关联后继表达式。互关联后继表达式可以用图的方式加以表达，数据结构为森林，称之为：互关联后继树。上面根据bcaeacbcba#所画的树，就是它的互关联后继树。

定义8：互关联后继树模型，若全文a1a2…ai…aN#中共有k个不同的字符，这k个字符对应于k棵不同的后继树，而这些后继树中的每个叶节点都对应于另外一棵后继树的根节点。换而言之，一个全文所对应的所有后继树是相互关联的，这种关联关系反映了字符在全文中出现的位置前后关系。我们称一个全文对应的所有后继树为全文的互关联后继树（IRST：Inter-RelevantSuccessive Trees）。

定义9：若aiai+1 ∈a1……aN，则ai<ai+1。性质:若ai<ai+1，ai+1<ai+2，则称ai<ai+2。

定义10：若后继表达式a（ai1，ai2，……，air，……，ain）中ai1，ai2，……，air，……，ain满足ai1<ai2<……<air<……<ain则称a（ai1，ai2，……，air，……，ain）为有序后继树。

定义11：映射f是后继表达式关于根结点至子结点的标记，如果f满足：f（a（ai1，ai2……aim））=a（1，2，……,m），则称映射f是一种保序映射。

定义12：互关联有序后继表达式经过保序f映射后得到的互关联后继表达式称精简的互关联后继表达式。

定义 13：在普通IRST模型精简后的基础上，对后继树的叶子进行字典排序，合并同样字符的叶子节点,对同一个字符的叶子进行保序映射，则称之为优化的IRST模型，以bcaeacbcba#为例，精简后的IRST为：

性质1：字符串的连接运算∞，对任意I，两字符串(a1a2)i与(a2a3)i+k, 当k=1时, (a1a2)i∞(a2a3)i+1=(a1a2a3)i.当k>1时,(a1a2)i∞(a2a3)I+k={(a1a2)I,(a2a3)I+k}

性质2：∞运算具有交换律，(a2a3)I+1∞(a1a2)I =(a1a2)I∞(a2a3)I+1=(a1a2a3)I

性质3：字符串的加运算+，对字符串α1与α2 ,α1+α2={α1,α2 }，一般地α1+α2+ … +αn =∑αi  ={α1,…,αn }

性质4：字符的拼接运算・，记作α1・α2=α1α2，拼接运算・对∞与+具有分配律，

α1 ・(α2∞α3)=α1・α2∞α1・α3

α1 ・(α2+α3)=α1・α2+α1・α3

性质5：任意字符串可按∞进行关联分解, 任意文本数据库均可表达成互关联后继表达式：

a1…aN#=a1a2a3∞a2a3a4……∞aN-2aN-1aN∞aN-1aN#∞aN-1aN#∞aN#

并以此分解为依据构造互关联后继树与互关联后继表达式。

基本互关联后继树算法非常简单，同示例中所展示的过程基本相同：

第一步，根据Σ来建立基本的符号集，相当于预先处理所有的树，以为后来的扫描做准备，这样的符号集包括所有的英文符号和汉字，总数量大概8K。并将他们分支的预设指数都设置为1；

第二步，从全文数据库开始依次读入所有的字符，放入变量中（假设为variable_1，variable_2），并且根据他们确认应该放入哪一棵树中。如他们分别为a、b，则应放入a树中，并且根据分支的预设指数存放，于此同时，将a树的分支指数加一；

第三步，将variable_1，variable_2写入对应的树中；

第四步，检测是否已经到了文件末尾，如果没有，则跳转到第二步；

第五步，将最后一个结束符填入，标志文章结束。

2  应用背景

随着中国市场的进一步开放，各行各业中的公司无论在数量还是在规模上都呈现海量递增的趋势。为有需求的客户提供对口公司的相关信息作为市场经济发展中的重要环节，具有举足轻重的地位，同时也是急需解决的问题。黄页作为一种信息媒体桥梁架设在公司和客户之间为解决上述问题起着不可忽视的作用，也正因为它的作用巨大，所以在黄页信息检索中准确、快速、智能化等一系列指标和需求应运而生，共同为满足客户到公司的信息检索需求出力，为经济蓬勃发展添砖加瓦。

本文讨论的中心是互关联后继树全文索引的创建。其主线是互关联后继树模型为何会提高全文索引的空间效率、检索效率和创建效率。本文还根据实际情况给出不同的创建索引的数据结构以满足不同的需求，具体讨论了创建全文索引时用到的众多辅助策略,这些策略对于提高全文索引创建效率和检索效率都是非常重要的。

我们可以看到现有的几种全文索引模型都存在各自的局限性。为了对全文索引模型进行比较全面的功能与性能评估，我们认为还应对其加以扩充：

（1）检索质量不仅要包括查全率，还要包括查准率。为了保证在检索时能够查全，就要求对全文的每个词都要建立索引，比如，全文中有“遗传信息”，那么就要对“遗传”、“传信”、“信息”三个词都要保留索引信息，以便不管如何切词，都能保证查全。然而，这就导致了检索结果与用户要求存在偏差：比如，查“传信”会把“遗传信息”也检索出来，这显然与用户的意愿相违。所以，我们在建索引时要在推理机制中加入相应的规则来进行约束，这就保证在检索时不会从“遗传信息”中检索出“传信”来。按字索引可以提高查全率，按词索引可以提高查准率，有时需要在查全与查准之间做一折衷。

（2）索引的动态效率有以下方面：可维护性，文本数据库中的文本数据发生变更后，能够方便进行文本数据库索引结构的更新；可扩展性，当文本数据库中的数据量增加时，索引机制要能够保证不使文本数据库的各项功能/性能指标明显下降。

（3）可操作性：对于各种常用的查询方式，具有方便、高效的操作可行性。

（4）查询实时性：对用户的查询做出实时响应是文本数据库系统的一个共同要求，它直接关系到文本数据库的实用性，而索引模型的好坏是实现高效查询的保证。

（5）领域独立性：正如传统数据库是各行各业应用的基础，全文数据库也应是各不同相关行业的应用基础，因此全文数据库模型应与领域无关，这就要求全文索引模型与领域无关。不然的话，就必须引入过多的领域特性，从而影响全文数据库的一般性和通用性。

（6）时间无关性：全文数据库作为文字信息的管理系统，应可用于管理在不同历史时期，而不受不同历史时期的语言表达风格和特色的影响。因此，索引模型应该具有时间无关性。

3  应用软件主要模块功能描述

主要有五大功能模块：

（1）全文索引创建模块：使用互关联后继树索引模型创建相关词表的索引；使用互关联后继树检索模型对全文信息进行切词处理；对切词后的结果组织成合适的索引结构存放到磁盘。

（2）全文索引添加/修改模块：使用互关联后继树分库/合库技术实现添加/修改功能；从关系数据库批量导入修改的数据，修改后批量导出到全文数据库。

（3）黄页信息检索模块：使用互关联后继树检索模型对用户输入进行准确查找/全文查找；检索结果按照一定的商业规则进行排序；快速返回检索结果到客户端页面。

（4）应用接口模块：①协同接口部分。服务器端协同操作关系数据库和全文数据，可以让应用程序不必考虑什么时候访问关系数据库什么时候访问全文数据。②提供可二次使用的DLL。服务器的程序以DLL的方式对外提供服务，若对应用程序有任何的变动不需要改动服务器程序，让开发人员方便地二次使用服务。

（5）软件安装模块组合：①工作站应安装远程桌面链接；②数据库服务器安装SQL Server 2000，互关联后继树全文数据库管理系统，互关联后继树检索引擎；工作站和数据库服务器，可以是同一台机器。

4  应用系统使用说明

本部分是黄页信息检索系统服务器端软件的使用说明，该软件是由复旦大学计算机与信息技术系数据库中心胡运发教授领导的小组与上海电信黄页信息有限公司联手开发和研制而成。

（1）主界面说明（2）创建索引

①创建词表索引：主菜单Create→创建词表索引。词表路径中选择各个词表（主体词表，同义词表……）保存的目录夹；词表索引保存路径中设置词表索引保存在磁盘上的路径；全部路径设置完毕后确认，则可以建立各个词表的索引到磁盘上，该索引留待创建数据库词索引的时候用于切词目的。②创建数据库词索引：主菜单Create→创建词索引。词表路径中设置各个词表（主体词表，同义词表……）所在的目录夹；词表索引保存路径中设置各个词表创建的索引所在的目录夹；文本库索引保存路径则设置全国数据创建索引后该索引保存的路径；数据库IP地址为拥有全国数据的关系数据库服务器IP；数据库名称中设置全国数据所在的数据库名称；数据库登陆用户名设置全国数据的关系数据库的登陆帐户；用户登陆密码设置登陆帐户的密码；表名称中设置全国数据中的主库表名称（强烈建议在使用本软件创建全文索引前对关系数据库中主库表(yellow)中的字段key,key_sub,mkey_sub, tel, addr, 深度信息表(Customer)中的字段key,分类表(Classify)中的字段name,code创建索引)；初始索引大小中设置预留的全国数据索引空间（强烈建议设置值>2GB）；创建关键字映射表为系统保留选项，选中即可；确认设置后开始创建数据库词索引。（3）读取索引

主菜单Read→读取词索引。分别在词表索引所在路径和文本库索引所在路径中设置之前在创建索引中设置的目录夹，确认后即可读取索引。（4）数据更新

①索引更新：主菜单Update→更新/删除/添加/修改（注：目前版本不支持修改单条记录）。选择相应更新菜单后弹出更新数据对话框；源数据表名称，由需要更新的数据记录组成的一张临时表格（由用户在数据库中生成，名称由用户设定）；目标数据表名称，关系数据库中已有的需要被更新的主库数据表（用户在创建索引的时候指定的主库数据表）；确认设置后进行相应的更新。②词表更新：主菜单Update→修改词表。在词表修改对话框中选择要修改的词表，然后进行词表内容编辑。特别注意：主题词表中词不可重复，其他词表中的词以空行隔开成组出现。（5）检索功能

主菜单Search→检索功能菜单（检索功能只在创建索引或者读取索引后方可以使用）。（6）其他

①主菜单File→文档选项（后续功能扩充用，目前版本不支持）。②主菜单View→功能视图选项，打开或者关闭相应的视图窗口。③主菜单Refresh→刷新条目（后续功能扩充用，目前版本不支持）。④主菜单Setting→System Path设置系统路径。⑤词索引路径设置子对话框中设置各个路径。⑥数据库连接子对话框中设置关系数据库连接的各个属性。 

胡运发  男，1940年生，复旦大学信息科学与工程学院教授，博士生导师，主要研究方向是程序设计语言、知识工程与知识库、专家系统与机器学习。

陶晓鹏  男，1970年生，复旦大学信息科学与工程学院副教授，主要研究方向是自然语言处理、文本管理、信息检索。

王政华  男，1980年生，复旦大学信息科学与工程学院硕士生，主要研究方向是全文检索、文本管理、信息检索。

杨笑天  男，1980年生，复旦大学信息科学与工程学院硕士生，主要研究方向是全文检索、文本管理、信息检索。