基于MRDI的关键词语义扩展密文检索技术研究

摘要：面向云环境中精确密文检索需求，设计了一种多属性、双索引（Multi-Rationality for Dual-Indexing，MRDI）检索方案。检索时对查询关键词进行语义扩展，并利用语义相似度过滤扩展结果来获得扩展查询集，以便更好地理解用户查询意图。从建索和检索两方面改进传统密文检索方案，高效检索出包含对应关键词的文件目录信息，同时提高了查准率。实验结果表明，该方案具有高效性和可行性。

正文内容：

0　引　言

在蓬勃发展的信息检索领域，数据量日益增大，信息安全问题凸显，如何对密文信息进行高效检索是急需解决的问题。密文全文检索，即快速而准确地从密文信息中检索出用户想要的信息，宗旨是“安全+高效”，涉及的主要技术有密文线性检索、索引的维护管理、文档和索引的安全性（加密）、密钥管理等。密文全文检索的高效与安全之间存在矛盾，一旦将安全机制引入，为提升检索效率而设计的全文索引结构将大受影响，安全和性能之间的平衡成为目前的研究重点。

密文全文检索的基本思路是：先对文本分析建立索引，通过索引对密文文本进行快速检索。Song等人提出了一种线性检索（Linear Scan）方案[1]，Eu-jin等人提出了基于布隆过滤器（Bloom Filter）的方法[2]。这两种方案检索时都需要遍历整个索引，所需开销将随索引数量的增加而快速增长。Mehmet等人提出了让用户自己选取关键词建立索引的方案[3]，能减少检索时间开销，但主观性强、增加用户负担，在云环境中面向云用户时扩展性不佳。Wang等人引入TF-IDF值到排序搜索算法[4]，对文档相关度进行排序，计算量小、检索快，但它采用单关键词匹配技术，只有当用户提供的查询词与文档关键词完全匹配时才能检索出文档，使得一些包含相关语义的有效文档被忽略，查准率不高。

本文结合矩阵索引和线性索引引入文档属性值，建立了一种多属性双索引结构。检索时，通过本体技术扩展关键词，充分挖掘用户查询意图，对检索结果进行相关度排序，返回用户最关心（排序靠前）的文档，使系统更加友好。

1　方案整体工作流程

本文的密文检索结构如图1所示。

数据持有者首先对上传文档进行预处理，提取并加密关键词后对密文建立索引。本文索引由线性、矩阵、多属性三种索引技术耦合后建立形成。随后把加密文档上传至云端数据库，索引和云端数据库建立对应关联信息，该信息需要实时维护和更新。检索时，客户端接收用户输入的关键词，经语义扩展后得到关键词扩展语义集密文，然后以密文集作为关键词在已经建好的多属性双索引中检索，检索结果返回给云服务器。服务器根据检索结果从云端数据库中取出相应文档，以供用户下载。

2　多属性双索引建索方案

2.1　分词技术

数据上传者首先根据文档生成文档元数据，包括关键词及其词频信息，通过分词技术将关键词从文档中提取出来。常见的分词种类有基于字典的、基于统计的、基于规则的分词，算法则分为正向最大匹配、逆向最大匹配两大类。分词过程包括词语提取、停用词（如标点和常见助词等）和低频词过滤以及词频统计，最后得到关键词集合K=(K1,K2,…,Kn) 及其词频信息作为文档元数据。

2.2　权重计算

关键词的重要程度通过权值来衡量。设用户上传文档集总数为M ，可以通过关键词Ki(i=1,2,…,n) 在文档中出现的次数和含有关键词Ki 的文档占总文档的比例来计算权重，计算如式（1）所示：

式中TFi 为关键词Ki 在文档中出现的次数，M 为文档总数，Fi 为含有关键词 Ki文档数。权重Wi 越大，表明关键词Ki 在该文档中越重要。

2.3　文档属性信息收集

用户上传文档到云数据库时，服务器需要记录该文档的相关信息，如文件大小、上传时间。这样用户在查询时可以对文件进行详尽描述，从而更方便快捷地找到所需文件，提高检索效率。同时，统计文档被下载次数、被引次数、最近访问时间等有效属性，分别赋予各属性相应的权值比重，使之和为1。该权重数据可在建立多属性索引时使用，防止检索结果对关键词过分依赖。

2.4　建立索引

本文采用矩阵和线性多属性耦合建立密文双索引结构。

2.4.1　矩阵索引

以密文形式的关键词Ki(i=1,2,…,n) 为横坐标，密文形式的文档Dj(j=1,2,…,t) 为纵坐标，设关键字Ki 相对文档Dj 的词频权值为dij ，创建如式（2）的矩阵向量：

若关键字Ki 与文档Dj 无关联，则记元素dij=0 。通过和值统计函数将每个关键词和文档名对应的词频权值相加，即将矩阵的第i 行元素和第 j列元素的和值分别进行统计记为Ni 和Sj ，有：

Ni 值越大，其对应的文档Di 被检索的可能性越大；Sj 值越大，其对应的关键词Kj 对检索贡献度越大。为了提高检索效率，根据Ni 值的大小将矩阵索引进行行变换，使得Ni 值大的文档名靠近矩阵上侧。根据Sj 值的大小将矩阵索引进行列变换，使得Sj 值大的关键词靠近矩阵左侧。经过以上矩阵变换后形成了元素尽量分布在左上侧的类稀疏矩阵，将被检索期望值高的关键词和文档名集中在索引矩阵的左上角，然后检索的遍历从左上角开始，大大提升了检索效率。由于是简单的二维矩阵变换，所以建索时的计算开销、索引更新的时间开销均在可接受范围。

2.4.2　线性多属性索引

为减少检索结果对关键词的依赖，充分考虑用户检索行为和提高服务器检索效率，引入多属性索引。本文通过改进传统倒排索引结构，每一个关键词的索引指向域包括除密文文件名之外的文件大小、上传时间、被下载次数和最近下载时间共4个属性。多属性指针域的索引结构如图2所示。

文档的属性可以反映它某方面的特征，如下载次数多反映文档的实用性广，最近下载时间近反映近期云用户对该文档的关注度高。可以根据实际检索需求在索引中为文档的多属性设置不同权值组合。例如，在初始模式下各属性权重一样，均为0.25；常态模式下关键词对应文件的文件大小、上传时间、下载次数、最近下载时间属性比重分别为0.2、0.2、0.3、0.3；在被下载次数优先模式下对应比重调整为0.1、0.1、0.7、0.1，以此突出下载次数在检索时的重要性。设计者可以根据实际需求为文档设置多条属性值和比重不一但合理的权重值。

建立和更新多属性线性索引以矩阵索引为依据，根据矩阵索引的横标关键词排序将线性索引中的关键词进行同样排序，使线性索引在检索时也具备与矩阵索引排序一致的遍历顺序，增加检索高效性。

2.4.3　双索引多属性耦合

云环境中，在密文检索时采用多线程并行计算对矩阵索引、线性多属性索引同时进行检索，其返回值都是关键词对应的两个文档名称集合，且每个文档名都对应有一个权值，二者权值和也为1。一个关键词对应的多个文档进行排序，依据除了常用的根据综合相关score大小进行排序[5]外，还需要结合该文档各个属性的属性值与权值比重乘积之和排序。基于以上两种机制综合排序，返回用户最关心的排名前 篇文档。

3　密文关键词查询扩展方案

3.1　查询扩展技术

查询扩展是解决信息过载、不匹配等问题的重要技术。传统的关键词匹配技术重点关注查全率，而未考虑与关键词语义相关的词语，导致一些语义相关的文档被忽略，查准率得不到保证。用户只好尽可能多、尽可能准地输入关键词，使系统容易遭受字典攻击，也降低了用户使用体验。通过构建本体[6]知识库，对用户输入的关键词进行推理扩展得到关键词集合。若扩展的关键词集过大，会对原始查询产生噪声影响，增加系统负荷。因此，利用语义相似度检查设定相似度阈值，只选大于相似度阈值的词语加入扩展关键词集合，从而在保证一定查全率的情况下提高查准率。

3.2　查询关键词扩展算法

本文借助通用本体WordNet知识库。该库中词间关系主要有同义词、上下位、整体与部分等关系。利用以上关系构建以原始查询关键词为根节点的语义树。当用户输入查询关键词a时，利用WordNet的层次结构知识库构建以a为根节点语义树，得到与a语义相关的词作为树的下一级子节点。依此继续扩展，同时依次计算根节点与各节点的语义相似度，将相似度大于设定阈值的词加入扩展集合，与a一起作为新的密文查询关键词集合。

一般用语义相似度描述词语的相似程度，计算公式如下：

式中Ni 和Nj 分别表示概念词Vi 、Vj 与最近公共父节点概念词V 间的最短路径，H 表示从V 到根节点的最短路径。两个词的语义越接近，语义相似度越大。设语义相似度阈值为t ，以关键词K0 为根节点构建扩展语义树的流程如图3所示。

首先查询WordNet知识库，若以关键词K 为根节点的扩展树尚未建立，则以K0 为根节点构建扩展树，接着查询该节点是否有同义词节点。若无流程，直接结束；若有，则计算该扩展词汇Ki 与K0 的语义相似度是否大于阈值t 。大于，则将Ki 词汇加入扩展关键词集，直到语义相似度小于阈值为止。该流程图以同义词关系扩展为例，也可以选择上下位关系、整体与部分的关系进行本体语义扩展[7]。

利用此算法给出一个以“protocol”为关键词的扩展树示意图如图4所示。可以看到，通过语义扩展，得到“protocol”的同义词“communications protocol”，上位词“rule”“prescript”，下位词“file_transfer_protocol”“TCP”等扩展词汇，为关键词查询提供了更多语义信息，能够更好地领会用户的查询意图。

4　实验测试与分析

4.1　语义扩展方案测试分析

实验硬件平台为Intel core_i5_750M CPU、64位系统、4G内存，采用检索引擎工具包Lucene2.4.3、WordNet2.1搭建实验环境，测试文档集为RFC标准文档集，文件格式为.txt，选其中500篇文档作为测试集。

用“information”作关键词进行检索，设置语义相似度阈值为0.5，按照WordNet知识库的语义树期望，“information”的同义词有“message”“info”“news”等。运行语义扩展搜索后会发现，包含“message”“information”“info”的数据都被检索到了，说明关键词语义得到了扩展。下面给出以“information”“design”为关键词进行扩展语义的检索统计信息，并用统计分析的方法判断程序的结果覆盖率，结果如表1所示。

从表1可以看到，加入语义扩展后，检索返回的文档覆盖率都在95%以上，基于同义词集合的语义扩展查询收到了较好效果，能更好地领会用户意图。耗时方面，使用语义扩展检索虽然耗时增加18%左右，但本身检索耗时的基数不大，为毫秒级别，且从扩展后查询的关键词数量来看，数量增加到4倍，而耗时并没有成4倍增加。可见，该算法下时间开销的增加幅度是可以接受的。

4.2　双索引多属性的检索测试分析

使用语义扩展技术建立不同数量的关键词，从建索速度、检索效率、查准率三项参数方面，对比传统线性检索和多属性双索引检索，结果如表2所示。

从表2数据可见，MRDI方案的建索时间明显要大于传统方案，随着关键字数量增加，MRDI的建索耗时时间增加幅度变小；检索时间方面，MRDI方案耗时明显少于传统方案，在关键词数量很多时，检索效率明显高于传统方案；查准率方面，二者的查准率都能保持在98%以上，当关键词较少时，传统方案占优，关键词数量增多时，MRDI查准率高于传统方案。整体而言，MRDI方案在建立索引时耗时较多，而一旦索引建立，检索时的效率便大大提高，其查准率也能得到保障，且随着关键词数量的增加，MRDI方案的优势愈加明显。

5　结　语

本文借助云平台的分布式计算能力加快建索速度，将系统的开销尽量集中在索引建立时而不是检索时，争取做到“一次建索，多次高效”。在检索时扩展查询关键词，争取做到“合理扩展，有效返回”，降低检索中对关键词的依赖，提高查准率。从实验结果分析来看，该方案具有一定的高效性和可用性。

但是，本文方案也存在不足：（1）语义扩展仅针对单个关键词，未考虑多个关键词的联合语义扩展，使得根据不同关键词生成的扩展集具有重复元素，拉低了系统效率；（2）多属性权值的分配尚没有合理的选择算法，使得检索结果未必真正符合用户期望；（3）在单机环境下测试，利用云平台的并行计算能力来提高建索效率的初衷尚未实现。以上问题是本文继续研究的方向，希望能够继续从索引建立和关键词检索两部分对密文检索系统进行改进研究，以期将该技术能更好地运用于云环境中。

参考文献：

[1] Song D X,Wanger D,Perrig A.Practical Techniques for Searches on Encrypted Data[C].Proceedings of 2000 IEEE Symposium on Security and Privacy,2000:44-55.

[2] Eu-Jin G.IACR Cryptology ePrint Archive [EB/OL].(2003-07-10)[2017-08-06].http://eprint.org/2003/216.pdf.

[3] Mehmet U.Searching on Encrypted Data[D].MD:University of Maryland College Park,2005:1-18.

[4] Wang C,Cao N,Li J,et al.Secure Ranked Keyword Search over Encrypted Cloud Data[C].2010 IEEE 30th International Conference on Distributed Computing System,2010:253-262.

[5] Zinger S,Millet C,Mathieu B,et al.Extracting an ontology of Portrayable Object from WordNet[J].Muscle,2005:17-23.

[6] 尚新丽.国外本体构建方法比较分析饥[J].图书情报工作,2012,56(04):116-119.

[7] Miller G A,Fellbaum C.WordNet Then and Now[J].Language Resources & evaluation,2007,41(02):209-214.

作者：涂俊亮，雷　波

单位：中国电子科技集团有限公司第三十研究所，四川 成都 610041

作者简介：涂俊亮，男，硕士，助理工程师，主要研究方向为信息安全、密码技术应用；