基于动态后继树索引结构的密文全文检索系统的索引更新方法

摘要

本发明分案申请涉及基于动态后继树索引结构的密文全文检索系统的索引更新方法，该方法包括有增加操作、删除操作和修改操作，更新粒度为文档局部级。所述增加操作包括：为新添加的文本以相对位置建立树叶信息；解密原索引中受添加文本影响的树叶的树叶信息集；将新建立的树叶信息插入原索引中；插入过程中只对添加文本的前驱的树叶关联位置修改，使其指向添加文本的首字符树叶位置，同时将前驱树叶原先的关联位置值写入添加文本的尾字符树叶关联位置；每次插入新的位置信息后，判断树叶信息集长度，如大于设定值则进行树叶信息集划分；对得到的树叶信息集进行加密。采用本方法，可使系统安全高效地实现密文状态下的索引创建及动态更新。

说明书

本申请是申请日为2010年5月31日、申请号为201010187384.4、发明创造名称为《密 文全文检索系统》的中国发明专利申请的分案申请。

技术领域

本发明属于信息检索和信息安全领域，具体涉及一种基于动态后继树索引结构的密文全 文检索系统的索引更新方法。

背景技术

随着计算机和通信等信息技术的迅猛发展，电子媒体等各种应用激增，传统行业信息化 也快速展开，工业和科研数据自动化和半自动化的产生，使得各种数据大量累积；另一方面 存储技术发展的日新月异也使得数据总量的增长势头越来越猛。据统计，二十世纪八十年代 以来全世界信息总量以指数级增长。可以说，如今信息产生的速度远远大于人类对这些信息 进行充分消化的速度。人们对问题进行有效决策所需要的信息量也大为增加，这就使得用户 在海量数据面前想找到自己满意的信息变得越来越困难。在这样的背景下，如果不借助于有 效的检索机制，信息量过大所产生的效果与无信息可查的效果是一样的。

全文信息检索技术最早产生于20世纪50年代的美国。1950年Calvin N.Mooers首创 了信息检索这个术语，1958年Luhn提出了统计信息检索的基本理论和方法，1960年Marson 和Kuhns提出了信息检索的概率模型，1986年Gerard创立了信息检索向量空间模型，1968 年Rocchio和Salton共同提出了查询扩展的方法，1972年Lockheed公司推出的DIALOG系 统是世界首例商用在线信息查询服务系统。从上个世纪90年代开始，随着廉价海量数据存储 设备的成功研发，特别是国际互联网技术的诞生和随之而来的网络信息的爆炸式增长，使信 息检索技术进入了一个崭新的发展时期。在这一时期，具有代表性的理论成果包括潜在语义 索引技术，贝叶斯网络和神经网技术。

全文检索技术已发展得较为成熟，国外的全文检索软件已较早地得到了应用。虽然中西 文全文检索的原理是一致的，但中文本身的特点使得中文全文检索系统要比西文的复杂。国 内全文检索技术的研究开始于1987年左右，目前在国内市场占有率超过90％、具有代表性的 全文检索系统如易北宝信公司开发的TRS，支持概念检索、多媒体数据检索和原格式文件检 索，支持海量存储结构化数据处理，并提供WWW的数据库接口。

索引模型是信息检索的核心技术，对信息检索系统待处理的数据进行高效的组织是进行 信息检索的必要前提，索引存储结构影响系统的检索速度和存储空间。当前主要索引模型有： 签名文件、倒排文件、位图、Pat树、Pat数组和互关联后继树等。前三种索引模型实质上都 是把文档看成索引项的集合，索引数据必须具有文档-索引项结构，因而难以实现复杂查询。 Pat树和Pat数组将索引数据看成一组半无限串的叠加，能实现复杂查询，但存在空间开销 大等缺点。互关联后继树模型是处理中文等半无限字符串的一种新颖的索引模型，它创建效 率高、查询速度快，与Pat树一样具有查询功能全的特点以及比Pat树小的膨胀比等系列优 点，但是也存在存储结构、动态索引更新等方面的不足。

目前国内外在基于密文的全文检索领域只有少量研究，通过各著名的大型数据库和搜索 引擎检索得到的结果中，在中文的密文全文检索领域，只查到由中国科学院计算机网络研究 中心的李新在中国的发明专利申请《密文全文检索技术》(申请号为200410070113.5)和华 中科技大学在中国的发明专利申请《分布式密文全文检索系统》(申请号为200910062129.4) 等相关研究成果发表。前者的发明是对全文检索技术的改造，几乎保留了全文检索的大部分 技术，只对索引文件的索引词进行加密处理；后者实现了在密文条件下的全文信息检索，保 证了敏感数据的安全检索，具有安全性强，执行效率高的特点，其索引文件为倒排文件，但 不能进行密文子串查询及潜在的分词查询，而且不能进行密文动态更新。

发明内容

本发明的目的，在于提供一种基于动态后继树索引结构的密文全文检索系统的创建、检 索和索引更新方法。

具体技术方案包括如下内容：

一、密文全文检索系统中的密文全文索引创建方法，包括以下步骤：

(1)将用户提交的涉密原始文本文档原文转化为纯文本，提取原文本文件中的主题、正 文及其他附加属性，并形成文档概要；

(2)对原文本文件中的主题、正文、附加属性进行分词处理，并提取特征向量；

(3)对步骤(1)中得到的纯文本文档、文档概要分别加密；

(4)把步骤(3)中得到的文档密文分布存储到相应的文档密文库，把步骤(3)中得到 的文档概要密文分布存储到相应的文档概要密文库；

(5)对步骤(2)中得到的分词、特征向量分别加密；

(6)把步骤(5)中得到的特征向量密文存储到特征向量密文库；

(7)对步骤(5)中得到的密文分词分发到各索引服务器；

(8)各索引服务器根据步骤(7)中的密文分词检索得到相应的分词位置密文；

(9)对步骤(8)中得到的分词位置密文进行解密；

(10)将步骤(9)中解密后的分词位置传回相应索引服务器；

(11)索引服务器根据分词位置创建索引；

(12)对步骤(11)中得到的索引进行加密；

(13)将步骤(12)中得到的密文索引存储到相应的密文索引库；

与上述密文全文索引创建方法相对应的密文全文检索方法，包括以下步骤：

(1)对用户提交的检索词/串进行分词并作查询扩展；

(2)对步骤(1)中得到的扩展分词集进行加密；

(3)把步骤(2)中得到的扩展密文分词集以广播方式分发到各索引服务器；

(4)各索引服务器进行检索；

(5)系统收集各索引服务器返回的文档编号集；

(6)系统根据步骤(5)中得到的文档编号集读取相应文档特征向量密文；

(7)系统解密步骤(6)中得到的特征向量密文；

(8)利用步骤(7)中得到的特征向量对文档编号集进行排序；

(9)根据步骤(8)中得到的有序的文档编号集读取相应文档概要密文；

(10)将文档概要密文解密；

(11)将解密后的文档概要显示给用户；

(12)系统根据用户的选择获取相应的文档密文；

(13)将文档密文解密；

(14)将解密后的文档显示给用户。

二、基于动态后继树索引结构的密文全文索引创建方法

所述动态后继树索引结构为密文动态后继树索引结构；所述密文动态后继树索引是一个 森林，所述森林由子树组成；每一棵子树的结构包括有树根的密文，树叶的密文，以及，由 伪文档编号、树叶位置、树叶关联位置、树叶变种组成的树叶信息集的密文；

所述树根，用于指代位于树根的分词；

所述树叶，即树根的后继，用于指代位于树叶的分词；

所述伪文档编号，是伪文档编号组的一个元素；

所述树叶位置，用于指代当前树叶在文档中的位置；

所述树叶关联位置，用于指代指向当前树叶的后继的分词的指针；

所述树叶变种，用于指代代替原树叶的一串字符串；

所述密文动态后继树索引的具体建立方法是：对每一棵子树中的树根、树叶分别进行加 密，对伪文档编号、树叶位置、树叶关联位置、树叶变种进行整体加密，即可得到所述密文 动态后继树索引。

本基于动态后继树索引结构的密文全文索引创建方法，可采用前述的密文全文索引创建 方法，其特征在于，

1)上述步骤(5)中的分词采用如下加密方法：

a、根据分词分组加密信息表对分词明文进行分组，得到该分词的密钥生成参数和加密算 法编号，并发送给密钥管理器；

b、密钥管理器根据密钥生成参数计算分词分组密钥，同时根据加密算法编号到加密算法 库中提取加密算法；

c、根据所得到的分词分组密钥和加密算法，对分词进行加密。

2)上述步骤(11)中的密文索引创建采用如下方法：

a、对每个密文分词，根据文档编号信息表随机选取一个伪文档编号替换原密文分词携带 的文档编号；

b、用密文分词的前驱到密文索引库中查找树根，用密文分词本身查找树叶，获取对应的 树叶信息集；

c、解密步骤b中得到的树叶信息集，将密文分词的位置信息插入到相应的树叶信息集中；

d、若插入后的树叶信息集长度超过限定值，则对树叶信息集进行划分，当遇到终结符表 示全文已经处理完；

e、将该索引中未加密的树叶信息集进行加密；

上述步骤d、e中的树叶信息集划分及加密方法为：

a)若树叶信息集的长度大于树叶信息集平均长度，则将其划分为若干个无交集子集，各 子集长度在系统设定的范围内；

b)为除首个树叶信息集子集之外的各子集分别随机生成树叶变种，使得每个子集都对应 一个树叶变种或一片树叶；

c)根据密文分词，在分词位置加密信息表中获取密钥生成参数和加密算法编号，并传送 给密钥管理器；

d)密钥管理器根据密钥生成参数计算得到分词位置密钥，同时根据加密算法编号在加密 算法库中提取加密算法；

e)根据d)中得到的分词位置加密算法，以及分词位置密钥对树叶信息集明文进行加密。

从上述步骤可知，所述树叶信息集加密方法可对所述树叶信息集进行分组管理，每组信 息用具有一定加密强度的不同加密算法和密钥进行加密；对高频词的树叶信息集长度进行均 衡化处理，为高频词随机产生树叶变种，将其树叶信息集划分成多个树叶信息集子集并加密， 树叶变种使密文分词数量动态变化，防止统计攻击。

三、本基于动态后继树索引结构的密文全文检索方法，采用了前述的密文全文检索方法， 其特征在于，上述步骤(4)中的检索，以检索词“qs1，qs2，…，qsi，…，qsn”为例说明， n为检索词/串的分词个数，其步骤如下：

1)判断检索词/串的分词个数：如果n＝1，则转入2)；如果n＝2，则转入3)；否则转入 4)；

2)判断树根表是否存在该分词；若存在，则检索命中结果集为该分词的树叶表中所有树 叶的树叶信息集的树叶位置的集合；检索结束；

3)判断树根表是否存在qs1；判断qs1的树叶表是否存在qs2；若qs1、qs2都存在，则 检索命中结果集为qs2的树叶信息集的树叶位置的集合；检索结束；

4)判断树根表是否存在qs1，如果存在，判断qs1的树叶表是否存在qs2；

5)若qs1、qs2都存在，则获取qs2的树叶信息集的关联位置的集合，记为Urpi；

6)以3≤j≤n进行循环，判断qsi的树叶表是否存在qsj；若存在，则获取qsj的 树叶信息集的树叶位置的集合，记为spj；计算spj与Urpi的交集，即qsj的树叶位置子集， 记为Uspj；获取qsj的树叶信息集的关联位置的子集合，记为Urpj；最多循环n-2次便得到 初步结果Urpj；

7)检索命中结果集为Urpj中所有树叶信息集的树叶位置的集合；检索结束。

四、本基于动态后继树索引结构的密文全文索引更新方法，其特征在于，采用了更新粒 度为文档局部级的密文动态后继树索引更新方法，该方法包括有增加操作、删除操作和修改 操作；

1)所述增加操作，其具体步骤如下：

a、为新添加的文本以相对位置建立树叶信息；

b、解密原索引中受添加文本影响的树叶的树叶信息集；

c、将新建立的树叶信息插入原索引中；在此插入过程中，只对添加文本的前驱的树叶关 联位置修改，使其指向添加文本的首字符树叶位置，同时将前驱树叶原先的关联位置值写入 添加文本的尾字符树叶关联位置；

d、每次插入新的位置信息后，判断树叶信息集长度，如果大于设定值，则进行树叶信息 集划分；

e、对步骤d中得到的树叶信息集进行加密；

2)所述删除操作，其具体步骤如下：

a、如果删除位置涉及多个树叶信息集，则先将其解密并合并成一个树叶信息集；

b、在需要文本删除的位置，直接修改删除部分的前驱的树叶关联位置；

c、删除需要删除部分的位置信息；

d、将删除后的树叶信息集进行长度均衡化处理，加密并存盘；

3)所述修改操作，以文本删除及添加的方式来实现。

本发明密文全文检索系统基于我们提供的密文动态后继树索引结构、分词分组方法、文 档局部级的密文动态后继树索引更新方法，实现了安全高效的索引创建、索引的动态更新以 及密文状态下的全文检索和子串查询。与现有的密文全文检索系统相比，本发明具有如下优 势：

(1)高安全性：分词分组方法保证了索引词的安全性。对动态后继树索引结构中分词加 密，屏蔽了分词的真正语义，周期性地更新分词密文使得攻击者对索引文件词表中的密文分 词分析变得无效。对树叶信息集加密，屏蔽了分词位置信息。用伪文档编号组防止了攻击者 通过获得密文分词的位置信息从而拼凑出一篇密文文档的内容。对树叶信息集进行划分，并 将得到的树叶信息子集与树叶变种捆绑加密，既防止了密文长度统计攻击，又进一步保证了 分词的安全性。检索时不需解密密文索引词，只解密检索过程中需要的树叶信息集，对不需 要的树叶信息集仍保持密文状态。

(2)高创建效率和检索效率：经过一次扫描，即可对原文分词并创建索引树。位于树根 的分词组成树根表，位于树叶的分词组成树叶表，树叶分词在原文档中的位置信息组成树叶 信息集。每个树根表项对应一个树叶表，每个树叶表项对应一个树叶信息集，树根表和树叶 表的表项在内存中用字典顺序的HashTree来存储，检索时按需解密，提高了查找速率。

(3)索引更新的高动态：本发明提出的更新粒度为文档局部级的索引动态更新方法可在 需要更新的地方，直接对节点进行增、删、改操作，不需要预留空间，也不用附加索引，实 现了索引文件的实时动态更新。

(4)实现了密文子串查询：本系统模型利用树叶位置和树叶关联位置来记录待匹配串子 串的位置关系，在索引词不脱密状态下实现子串查询，不但保证了密文索引库的安全，同时 也节省了密文子串查询的开销。

附图说明

图1是本发明密文全文检索系统的一个实施例的体系结构图。

图2是本发明密文全文检索系统的一个实施例的结构组成示意图。

图3是本发明密文全文检索系统文档密文库和文档概要密文库的创建示意图。

图4是本发明基于动态后继树索引结构的密文全文检索系统所采用的密文动态后继树索 引的一个实施例的结构示意图。

图5是本发明基于动态后继树索引结构的密文全文检索系统的一个实施例的索引创建过 程示意图。

图6是本发明密文全文检索系统密文检索过程的示意图。

具体实施方式

以下结合附图及实施例对本发明密文全文检索系统和基于动态后继树索引结构的密文全 文检索系统及其工作原理作进一步地说明。

如图1所示，本发明系统包括：原始文本处理模块100、分词模块200、加密模块300、 文档密文存储模块400、密文索引模块500、密文检索模块600、检索结果处理模块700和系 统管理模块800。

系统工作原理步骤如下：

(1)用户通过系统管理模块800实现安全登录后，系统判断用户选择是执行创建索引文 件还是执行检索功能，如果是检索则进入第15步；

(2)系统把用户提交的涉密原始文本文档原文转化为纯文本，提取原文本文件中的主题、 正文及其他附加属性，并形成文档概要；

(3)系统对主题、正文、附加属性进行分词处理，并提取特征向量；

(4)系统对步骤(2)中得到的纯文本文档、文档概要分别加密；

(5)系统把步骤(4)中得到的文档密文分布存储到相应的文档密文库，把步骤(4)中 得到的文档概要密文分布存储到相应的文档概要密文库；

(6)系统对步骤(3)中得到的分词、特征向量分别加密；

(7)系统把步骤(6)中得到的特征向量密文存储到特征向量密文库。

(8)对步骤(6)中得到的密文分词分发到各索引服务器；

(9)各索引服务器根据步骤(8)中的密文分词检索得到相应的分词位置密文；

(10)对步骤(9)中得到的分词位置密文进行解密；

(11)将步骤(10)中解密后的分词位置传回相应索引服务器；

(12)索引服务器根据分词位置创建索引；

(13)对步骤(12)中得到的索引进行加密；

(14)将步骤(13)中得到的密文索引存储到相应的密文索引库；

(15)用户提交检索词/串；

(16)系统对对用户提交的检索词/串进行分词并进行查询扩展；

(17)系统对步骤(16)中得到的扩展分词集进行加密；

(18)系统对步骤(17)中得到的扩展密文分词集以广播方式分发到各索引服务器；

(19)各索引服务器进行检索；

(20)系统收集各索引服务器返回的文档编号集；

(21)系统根据步骤(20)中得到的文档编号集读取相应文档特征向量密文；

(22)解密步骤(21)中得到的特征向量密文；

(23)系统利用步骤(22)中得到的特征向量对文档编号集进行排序；

(24)系统根据步骤(23)中得到的有序的文档编号集读取相应文档概要密文；

(25)将文档概要密文解密；

(26)将解密后的文档概要显示给用户；

(27)根据用户的选择获取相应的文档密文；

(28)对文档密文进行解密；

(29)将解密后的文档显示给用户。

(二)下面结合图2分别对各模块在上述步骤中的作用作进一步详细地说明：

1、原始文本处理模块100：

文本的预处理主要包括有两个方面：物理上，是对文档实物电子化处理；逻辑上，是对 电子文档归一化和分类处理。如图2所示，该原始文本处理模块100包括有转化单元110、 提取单元120和概要单元130，其中，转化单元110实现电子化纸质文档，就是使纸质文档 经过扫描等方式后，得到可以处理的电子化原始文档，以及，将需要处理的电子文档统一转 化为纯文本文档；提取单元120负责对上述纯文本文档中的文档信息进行提取，提取的信息 包括但不限于主题(标题、摘要、关键字)、正文、附加属性(作者、作者单位、来源、时间)； 概要单元130将主题、摘要、作者、时间、来源等组织成文档概要。

2、分词模块200：

分词模块200用于对所述原始文本处理模块所提供的文档主题、正文及附加属性等进行 分词并提取特征向量，以及，用于对所述密文检索模块提供的检索词/串进行分词和查询扩展。 其中，分词单元210对传送过来的主题、正文、附加属性、检索词/串等进行分词；特征向量 单元220从分词结果中提取文档特征词，形成特征向量；查询扩展单元230对检索词/串分词 进行查询扩展。

3、加密模块300：

加密模块300，包括提供加密和解密功能，具体包括有文档加密单元310、分词加密单元 320、分词位置加密单元330：

(1)文档加密单元310，负责对原始文本预处理模块100传送来的纯文本文档、文档概 要，分词模块200传送来的特征向量进行加密处理；该文档加密单元310中，包括有文档加 密信息表、加密运算器；所述文档加密信息表用于获取对纯文本文档、文档概要、特征向量 加密所需的密钥和加密算法；

(2)分词加密单元320，负责对分词模块200传送来的分词明文进行加密处理。分词加 密单元320中包括有分词分组子模块、分词分组加密信息表、加密运算器。所述分词分组加 密信息表用于获取对分词加密所需的密钥和加密算法；其加密过程中还需要使用到密钥管理 器、加密算法库。在对分词进行加密时，利用分词分组加密信息表中的参数计算分词加密密 钥，为相同的分词提供相同的加密算法和密钥，保证相同的分词加密的密文结果相同。 所述分词分组子模块负责对分词明文进行分组，其分词分组方法包括分词分组创建和分 词分组更新两种操作，其中分词分组创建是对来自分词模块200的分词明文进行随机分组， 分词分组更新是使每个分词在不同的周期内属于不同的分词分组，增强分词分组的随机性。

1)分词分组创建

分词分组创建时，分词加密单元320首先接收来自分词模块200的分词明文，根据分词 分组加密信息表对分词明文进行分组，并将处理得到的分词分组信息发送给密钥管理器；所 述密钥管理器根据分词分组信息到加密算法库中提取加密算法，并计算分词分组密钥，然后 对分词进行加密处理，并将得到的密文分词发送给密文索引模块500。

2)分词分组更新

由系统触发当前分词分组与它相邻的下一个分词分组之间的更新。因为密钥管理器是利 用分词分组信息生成分词分组密钥，所以系统会同时触发索引词密文的更新。为了防止索引 词密文比较频繁的更新，将分词组间更新的周期设置为分词分组更新的周期的整数倍。

分词分组更新时，分词分组子模块随机交换相邻的两个需要更新的分词分组中的分词， 得到并保存新分词分组信息；根据分词分组加密信息表查找加密算法库，得到两个相邻分词 分组当前的分词分组加密算法和下一周期的新分词分组加密算法；根据新旧分词分组和分词 分组当前周期分别计算两个相邻分词分组的当前分词分组密钥和下一周期的新分词分组密 钥；根据新旧密钥对和加密算法对，加密分词分组中的各个分词，得到新旧分词密文对集； 根据新旧分词密文对，更新旧分词密文；更新结束。

(3)分词位置加密单元330：包括有分词位置加密信息表、加密运算器；所述分词位置 加密信息表用于获取对分词位置信息加密所需的密钥和加密算法；

所述文档加密单元310、分词加密单元320、分词位置加密单元330在加密过程中还需要 使用到密钥管理器、加密算法库；

4、文档密文存储模块400

文档密文存储模块400用于分布存储、提供文档概要密文和文档密文，包括有文档密文 分布代理模块410和分布式文档密文管理模块420。文档密文分布代理模块410根据文档标 准码将文档密文和文档概要密文分发到相应的文档密文服务器。分布式文档密文管理模块420 用来管理文档密文和文档概要密文，可由若干个文档密文服务器、文档概要密文库和文档密 文库组成。文档密文服务器负责对所属的文档概要库和文档密文库进行存取。

下面结合图3介绍文档密文库和文档概要密文库的创建过程：

(1)原始文本处理模块100对文档进行预处理，生成文档编号、文档标准码、纯文本文 档、文档概要；

(2)对纯文本文档和文档概要加密；加密过程如下：加密模块300收到一篇纯文本文档 和文档概要，向加密模块300的加密算法库获取一个随机的文档加密算法，由加密模块300 的密钥管理器生成文档加密密钥，同时密钥管理器向文档加密信息表新增一条记录；使用该 算法和文档加密密钥对纯文本文档和文档概要加密，得到文档密文和文档概要密文，由加密 模块300将文档密文和文档概要密文传给文档密文存储模块400；

(3)文档密文存储模块400中的文档密文分布代理模块410根据文档标准码对文档密文 和文档概要密文分发到相应的文档密文服务器；文档密文服务器把文档密文和文档概要密文 存放到相应的文档密文库和文档概要密文库。

5、密文索引模块500：

密文索引模块500包括有密文分词分布代理模块510、分布式密文索引管理模块520。其 中，密文分词分布代理模块510负责将密文分词分布到索引服务器上；分布式密文索引分布 管理模块520包括有至少一个索引服务器和若干个密文索引库，由索引服务器管理各个密文 索引库；各索引服务器接收来自所述加密模块提供的密文分词和分词位置信息创建索引，存 储密文索引到相应的密文索引库；索引服务器包括有文档编号信息表；所述文档编号信息表 用于记录文档对应的伪文档编号组；所述伪文档编号组是文档编号的一个一对多映射组成的 集合，由系统生成。

(1)密文动态后继树索引结构

在本发明密文全文检索系统中，还应用有本发明人首次提出的密文动态后继树索引结构， 下面结合图4和实例进一步介绍：

密文动态后继树索引是一个森林，其每一棵子树的结构包括树根的密文，树叶的密文， 以及伪文档编号、树叶位置、树叶关联位置、树叶变种组成的树叶信息集的密文；

树根，用于指代位于树根的分词；

树叶，即树根的后继，用于指代位于树叶的分词；

伪文档编号，是伪文档编号组的一个元素；

树叶位置，用于指代当前树叶在文档中的位置；

树叶关联位置，用于指代指向当前树叶的后继的分词的指针；

树叶变种，用于指代代替原树叶的一串字符串；

子树的索引结构可以表示为：树根<树叶([伪文档编号，{(树叶位置，树叶关联位置)}]， 树叶变种)>，其中同一树根下的树叶密文之间互不相同；[伪文档编号，{(树叶位置，树 叶关联位置)}]为一个树叶信息，由伪文档编号、位置列表组成，伪文档编号用来干扰文档 的真正编号，以防止攻击者获得位置信息后拼凑出该篇文档的密文；一片树叶对应一个树叶 信息集和一个树叶变种，树叶变种允许为空，但树叶信息集不能为空。

(2)密文动态后继树索引创建

密文动态后继树索引创建时，如图5所示，分词模块200接收来自原始文本处理模块100 的主题、正文及附加信息，由分词单元210对这些信息进行分词处理；分词单元210将得到 的分词传送给加密模块300，由其分词加密单元320对分词进行加密；分词加密单元320将 密文分词传送给密文索引模块500，由密文分词分布代理模块510提取密文分词对应的文档 标准码，根据文档标准码将密文分词分布到分布式密文索引管理模块520中对应的索引服务 器；索引服务器为新增的各文档编号分配伪文档编号组，并记录到文档编号信息表；查找当 前可用的索引库，并将此库中受新增文档影响的树叶及树叶信息集发送到加密模块300；分 词位置加密单元330对接收到的树叶的树叶信息集解密后发送回相应的索引服务器；索引服 务器随机选取伪文档编号为相应文档创建索引；索引服务器将相应的树叶信息集发送到分词 位置加密单元330；分词位置加密单元330对接收到的树叶信息集进行加密，加密后传回索 引服务器；索引服务器将收到的密文索引存储到相应的密文索引库；

密文动态后继树索引结构中所有的树根节点组成一个树根表，相同树根下的所有树叶节 点组成一个树叶表；每个树根表项对应一个树叶表，每个树叶表项对应一个树叶信息集和一 个树叶变种。其创建算法如算法1所示。

算法1：密文动态后继树索引创建算法

输入：密文分词

输出：密文索引文件

for(每个密文分词)

{

把密文分词插入索引；

if(树叶信息集长度大于平均长度)

进行树叶信息集划分；

}

加密树叶信息集并存盘；

算法结束。

(3)树叶信息集加密

为保证索引的安全，对树叶信息集进行加密，屏蔽树叶分词在原文档中的位置信息。由 于高频词的树叶信息集长度可能过长，容易让攻击者通过统计密文长度而获得高频词相关信 息，因此我们采用了树叶信息集划分的方法。该方法均衡了树叶信息集长度，可防止密文长 度统计攻击。下面描述几个定义：

树叶信息集长度：一个树叶信息集所包含的字节数；

树叶信息集平均长度：密文动态后继树索引中，全部树叶信息集所包含的字节数的平均 值；

树叶信息集划分：在密文动态后继树索引中，任意一个树叶信息集的长度若大于树叶信 息集平均长度，则将其划分为多个无交集子集，各子集长度在系统设定的范围内，并为除首 个树叶信息集子集之外的各子集分别随机生成树叶变种，使每个子集都对应一个树叶变种或 一片树叶。

下面进一步描述树叶信息集的加密过程：

1)对一个树叶信息集明文，分词位置加密单元330向加密模块300中的密钥管理器请求 对应的分词位置密钥和分词位置加密算法编号；

2)根据密文分词，在分词位置加密信息表中获取密钥生成参数和分词位置加密算法编号， 并传送给密钥管理器；

3)分词位置加密单元330根据分词位置加密算法编号从加密算法库中获取对应的分词位 置加密算法，并用分词位置密钥对树叶信息集明文进行加密。

(4)索引密文更新包括分词密文的更新和树叶信息集密文的更新：

分词密文的更新：由系统触发，按分词分组逐步更新，以密文索引库返回成功更新响应 后重置更新计时器为结束。其详细过程见分词分组方法中分词分组的更新。

树叶信息集密文更新：由系统触发，按分词分组逐步更新，以密文索引库返回成功更新 响应后重置更新计时器为结束。密钥管理器首先接收来自分词位置加密信息表中需要更新的 树叶信息集对应的加密信息；根据加密信息计算分词分组密钥，新旧分词位置密钥；查找加 密算法库，得到分词分组加密算法和新旧分词位置加密算法；加密运算器对分词进行加密得 到密文分词；根据密文分词在密文索引库中查找相应的树叶信息集密文；分词位置加密单元 330根据旧分词位置密钥和算法对树叶信息集密文解密，得到树叶信息集明文；用新分词位 置密钥和算法对树叶信息集明文进行加密，得到新的树叶信息集密文；用新树叶信息集密文替 换密文索引库中的旧树叶信息集密文。

(5)更新粒度为文档局部级的密文动态后继树索引更新方法

密文动态后继树的索引更新是在密文状态下用更新粒度为文档局部级的索引动态更新算 法，实现密文动态后继树索引的高动态性，提高密文索引更新的效率。密文动态后继树上更 新粒度为文档局部级的索引动态更新主要包括增加、删除和修改操作。

增加操作是对添加文本的前驱的树叶关联位置进行修改，使其指向添加文本的首字符树 叶位置，同时将前驱树叶原先的关联位置值写入添加文本的尾字符树叶关联位置。每次插入 新的位置信息后，将该密文分词的树叶信息集长度与平均长度进行比较，若小于平均长度， 则无需进一步处理对应的树叶信息集，增加操作完成；若大于平均长度，则需要对该分词的 树叶信息集进行树叶信息集划分，同时根据划分的子集数量n，随机产生n-1个树叶变种， 将树叶变种插入到对应树根的树叶表中。

在进行删除操作时，如果需要对包含两个以上的树叶信息集进行操作，则先将其解密并 合并成一个树叶信息集。在单个树叶信息集上，修改删除部分的前驱的树叶关联位置，并删 除需要删除的位置信息，再将删除后的树叶信息集进行长度均衡化处理，加密并存盘。

修改操作：以文本删除及添加的方式来实现，可以看成删除和增加的复合操作。

更新过程如算法2所示。

算法2：密文状态下更新粒度为文档局部级的索引动态更新算法

输入：文档变更部分

输出：变更后的索引文件

对索引中每个分词的树叶信息集进行解密；

把文档变更部分在旧文档中的上下文位置信息保存到临时状态表；

if(增加)对变更部分用相对位置创建树叶信息再并入原索引中；

else

if(删除)在原索引中直接删除变更部分；

else在原索引中直接对变更部分修改；

对索引中每个分词的树叶信息集进行加密；

算法结束。

6、密文检索模块600

密文检索模块600是为系统的合法用户提供相应级别的信息检索功能，包括检索语句提 交单元610和检索服务器620。检索服务器620用于将扩展密文分词集以广播方式分发到各 索引服务器，接收并处理各索引服务器返回的结果，然后将得到的无序文档编号集发送给检 索结果处理模块700。

密文检索过程如图6所示。在检索过程中，合法用户输入检索词/串，并由检索语句提交 单元610提交给分词模块200，由分词模块200中的分词单元210和查询扩展单元230对检 索词/串进行分词及扩展得到扩展分词集，再由加密模块300中的分词加密单元320对扩展分 词集进行加密得到密文分词，将密文分词通过检索服务器620以广播方式分发到分布式密文 索引管理模块520中各索引服务器，由各索引服务器进行检索，最后由检索服务器620收集 各索引服务器返回的文档编号集，去重并提交给检索结果处理模块700。

动态后继树索引结构的检索，根据分词的个数划分为单分词检索、双分词检索、多分词 检索，以检索词“qs1，qs2，…，qsi，…，qsn”为例说明，n为检索词/串的分词个数，其 步骤如下：

1)判断检索词/串的分词个数：如果n＝1，则转入2)；如果n＝2，则转入3)；否则转入 4)；

2)判断树根表是否存在该分词；若存在，则检索命中结果集为该分词的树叶表中所有树 叶的树叶信息集的树叶位置的集合；检索结束；

3)判断树根表是否存在qs1；判断qs1的树叶表是否存在qs2；若qs1、qs2都存在，则 检索命中结果集为qs2的树叶信息集的树叶位置的集合；检索结束；

4)判断树根表是否存在qs1，如果存在，判断qs1的树叶表是否存在qs2；

5)若qs1、qs2都存在，则获取qs2的树叶信息集的关联位置的集合，记为Urpi；

6)以3≤j≤n进行循环，判断qsi的树叶表是否存在qsj；若存在，则获取qsj的 树叶信息集的树叶位置的集合，记为spj；计算spj与Urpi的交集，即qsj的树叶位置子集， 记为Uspj；获取qsj的树叶信息集的关联位置的子集合，记为Urpj；最多循环n-2次便得到 初步结果Urpj；

7)检索命中结果集为Urpj中所有树叶信息集的树叶位置的集合；检索结束。

以上的结构表明，本检索可以实现密文子串查询和检索过程按需解密：

(1)密文子串查询是密文全文检索系统查全率的重要保障。本系统模型利用树叶位置和树 叶关联位置来记录待匹配子串的位置关系，在索引词密文不脱密的状态下实现子串查询，不 但保证了索引库的安全，同时也节省了对密文子串查询时的开销，具有查询效率高，无漏检 的特点。

(2)基于动态后继树索引结构的检索，由于该索引结构结合了词表法和单汉字法，可以实 现按需解密，即只需对检索到的树叶信息集密文进行解密，提高了系统安全性和检索效率。

7、检索结果处理模块700

检索结果处理模块700负责检索结果集的排序和显示，包括检索结果排序单元720和结 果显示单元730。检索结果排序单元720用于对无序的文档编号集进行排序。结果显示单元 730包括文档概要显示和文档显示，文档概要显示内容包括：主题、摘要、作者、时间、来 源等。图2所示的检索结果处理模块700中，从方便分析系统工作流程及保持图面整洁的角 度考虑，还包括有特征向量密文库710，但根据本领域技术人员的常识，所述特征向量密文 库710作为一个数据库，并不限定放置于所述检索结果处理模块700中。

检索结果处理模块700接收到检索结果集中的文档编号集，由检索结果排序单元720提 取文档特征向量密文并发送到加密模块300解密，然后对结果集进行排序。根据有序的结果 集提取相应的文档概要密文并解密返回给用户，再按照用户选择的文档进行文档密文提取， 经过加密模块300解密后将整篇文档返回给用户。

检索结果排序及显示过程：

(1)检索结果处理模块700接收到无序的结果集，到特征向量密文库710读取相应文档 的特征向量密文，将特征向量密文和文档编号发送给加密模块300；

(2)加密模块300中的密钥管理器读取文档加密信息表，动态生成文档加密密钥，并将 加密密钥和文档加密算法传递给文档加密单元310。文档加密单元310对特征向量密文进行 解密，得到特征向量明文；

(3)在检索结果排序单元720计算查询串与特征向量明文的相关度，对文档编号集按相 关度降序排列得到有序的文档编号集，并将有序文档编号集发送给文档密文分布代理模块 410；

(4)文档密文分布代理模块410根据文档标准码将文档编号发送到相应的文档密文服务 器；

(5)文档密文服务器从文档概要密文库获取各文档的文档概要密文，并发送到加密模块 300进行解密，其解密方法如步骤(2)所述；

(6)解密后的文档概要由结果显示单元730展示给用户；

(7)当用户选择某一篇文档后，系统从文档密文库中获取到该文档密文，解密并显示给 用户。

8、系统管理模块800

系统管理模块800用来管理用户权限，对部门、角色、用户的基本信息以及它们之间的 映射关系进行维护更新等；该模块包括用户信息表、角色权限表、部门信息表、用户部门关 系表以及用户角色关系表；其中，角色权限表用来记录角色基本信息和角色权限，可由16位 权限位串组成。