/* */

分布式搜索引擎中关键词倒排索引方法仿真

2019-10-07| 发布者: admin| 查看: |

1 引言

当前多数信息检索引擎有着相同的结构, 即集中式结构, 此种结构存在稳定性差和扩展性能弱的缺陷, 利用此种结构中索引方式得到的检索结果不是十分理想[1,2]。为了使信息搜索系统性能更强, 分布式搜索引擎顺势而生。作为结合分布式计算与全文检索的新型信息数据检索系统, 改变了大众获取数据的渠道, 使大众更加高效地获取数据, 被称作上网的第一站。该引擎中的各子系统均能够通过物理资源独立而又相互合作完成用户任务, 容错性和实时性较强[3]。为进一步提升分布式搜索引擎性能, 利用倒排索引的方式检索用户提供的关键词是信息检索领域发展的必然趋势。以目前应用范围比较广的信息检索方法为例, 分析当前相关检索方法。

江宇[4]等人利用分析检索文档的自查询结构, 构建倒排链表自检索结构。该结构将定长元组当作单位, 根据迭代方式设计数据段同步自索引框架;以设计结果为依据, 构建数据压缩与查询体系。利用TREC GOV2数据集验证该方法, 实验结果表明, 该方法运行复杂度较低, 但检索结果准确性较差。陈亚杰[5]等人提出基于ElasticSearch的数据检索方法, 利用River机制构建当前FITS数据索引结构, 以此实现海量FITS数据查询, 并分析了数据检索过程中的关键技术。实验结果表明, 该方法运行能耗低, 但存在检索过程安全性较差的问题。陈远[6]等人提出基于DKASR的信息数据检索方法。过程中, 以分布式平台为依据, 实现海量数据并行检索。结合RDF本体信息设计并构建本体子图, 根据语义评价函数实现本体子图的排序, 利用MapReduce计算模型完成信息数据的并行搜索, 同时返回Top-k结果;假设所得结果未达到Top-k, 那么扩展本体子图, 以此得到近似本体子图, 通过语义的相似度函数给出近似本体子图的排序结果, 依据MapReduce计算模型完成信息数据的并行搜索, 一直到得到Top-k结果。仿真结果表明, 该方法检索结果用户满意度高, 但是却存在检索效率较低的问题。

信息数据检索相关方法较多, 但性能相对完善的却比较少。为了解决上述问题, 提出分布式搜索引擎中关键词倒排索引方法, 以完善当前相关方法性能。

2 分布式搜索引擎中关键词倒排索引方法

2.1 倒排索引分析

倒排索引作为典型且高效的信息数据检索结构, 是全文索引中的核心单元[7]。其对数据库各条记录中所有字段或部分字段属性分析并提取其中的词干, 同时将数据库中表的主键当作索引记录的唯一标识。各个索引项将排列出一系列带有该索引项的标识, 利用查找索引项, 就能检索出相应的索引结果, 其中最为关键的两个步骤则为构建词典和词干特征提取。

2.2 关键词倒排索引体系和索引关键技术分析

综合倒排索引特性, 构建的分布式搜索引擎中关键词倒排索引体系如图1所示。

图1 分布式搜索引擎中关键词倒排索引体系

图1 分布式搜索引擎中关键词倒排索引体系  

 

根据分布式搜索引擎中关键词倒排索引体系的构建, 对其中的词典构建和词干特征提取两个关键部分进行分析。

为了充分反映分布式搜索引擎中各种类型信息文档特性, 采用多种特征向量构建的超向量当作文档特征, 其中包含时域特征和频域特征等。各种特征均能够描述文档信息数据某一个方面的特征, 以充分表征文档内容为目的, 将超向量当作特征充分表征各种文档的特性。因为各维特征在取值上存在很大差异, 因此要将各维特征进行归一化, 进而提升关键词倒排索引时的效率[8,9]。提取特征之后, 将各维特征均值与标准差作为规整向量, 并利用该规整向量按照式 (1) 规整分布式搜索引擎中文档特征

fd=fdmdsdDε(1)

式 (1) 中, f ′d代表规整后的特征, fd代表规整前的特征, md代表规整过程中的均值, sd代表规整过程中用到的标准差, D代表特征总维数, ε代表归一化系数。

依据式 (1) 可将各维特征规整到均值为0、且方差为1的空间分布中。

在信息检索中, 关键词为文档索引项目, 所有索引项组成的集合叫作索引项词表。在此, 将分布式搜索引擎中关键词进行组合, 构成词典。

关键词中字的数量会影响查询结果:假设关键词中的字数太多, 在极限情况下会将每个字的特征视为一个关键词, 这样一方面会生成尺寸比较大的词典, 另一方面会将比较相似的关键字或者词内容判定成不同的关键字或者词, 这样则会造成比较相似的关键字或者词有着完全不同的序列;反之, 关键词字数太少, 会使得关键词对文档项目内容的判别能力下降, 出现多个序列完全相同的情况。

在此, 根据文档类型数量确定词典大小。为防止将不同项目判定为同一个关键词或者字, 每个文档项目至少要具有一个关键词或者字表征, 且每个文档项目因存在的形式可能不唯一, 所以应该对每个文档项目使用多个关键词或者关键字表征, 进而提高关键词索引结果的精确性。训练词典过程中, 假设每个文档项目采集i个样本, 根据上述的特征提取技术, 利用模糊K均值聚类法将所有样本特征聚成K个类别, 所有文档项目共生成C个聚类中心。将各聚类中心当作一个文档项目wi, 以此产生的词典可表示为

Wi=fd{w1,w2,,wΚ}C(2)

式 (2) 中, Wi代表分布式搜索引擎中的词典。

2.3 关键词倒排索引与检索

因为分布式搜索引擎中索引文档保存有明文记录信息, 入侵者会对其进行分析, 从而入侵索引词典, 导致索引安全受到威胁。为避免索引文档有信息泄露情况, 保障索引过程的安全性, 要对索引文档进行加密, 构建密文索引文档。密文索引文档生成详细流程为:

1) 分析词典Wi, 构建明文倒排索引文档;

2) 得到加密密钥, 对文档中相关记录信息实施加密操作, 生成密文文档;

3) 为密文文档构建倒排索引, 整个过程分为两部分, 一部分为根据所有关键词构成的列表, 此列表为词典Wi, 另一部分为事件表。各关键词均会与事件表的一行相对应, 事件表中各项均记录了该关键词在文档中所在位置。如果要添加关键词序列至倒排索引中, 则将要添加的关键词序列添加至事件表对应位置的末端, 以此完成索引的建立。

根据上述索引的建立, 实现信息检索。在检索关键词之前, 索引服务器根据CRC32算法对密文检索词进行处理, 并生成相应明文检索词。在检索过程中, 检索任务为接收用户指令并通过检索和排序将一个排列好顺序的文档列表返回给用户, 其中, 排名越靠前的文档和用户检索的内容相似度越高[10]

利用2.2节关键技术中的特征提取将用户检索词划分成不同段, 利用词典将其转变成字序列, 并表示为

Q={q1,q2,,qn}(3)

式 (3) 中, n代表根据用户检索词得到的第n个序列。

通过查询Q中全部关键词进行命中检测, 同时确定所有候选文档的起止位置, 最后根据全部候选文档和用户查询内容相似度排序, 将检索结果反至用户。

上述中的命中指的是某关键词不仅出现在检索中, 也出现在文档中。如果与检索Qqn相对应的关键词为wK, 那么qn的命中位置是倒排索引序列表中wK在事件表对应的所有位置。针对qn命中的随机位置 (i′, j′) , 能够确定一个候选文档。

根据上述内容检测出全部候选文档之后, 需要对候选文档和检索内容的相似度顺序进行排列, 检索和候选文档相似程度越高, 则两者应该有越多一致的关键词或字, 所以以命中关键词在每个候选文档中占据的比例当作相似度判断依据。某候选文档c={c1c2, …, cn}与检索Q相似程度利用计算命中关键词的数量比例获得, 即

RQC=n=1qncnΝQWi(4)

式 (4) 中, RQC代表某候选文档c与检索Q相似程度, 即命中关键词的数量比例值。NQ代表候选文档总长度。

根据式 (4) 计算检索与全部候选文档相似程度, 同时将计算结果依据从大到小顺序进行排列, 将排列结果返回给查询用户, 以此完成分布式搜索引擎中关键词检索。

3 实验结果与分析

为验证分布式搜索引擎中关键词倒排索引方法有效性, 将实验平台搭建在Matlab上, 实验数据来自于互联网。在某大学随机选取100名学生作为用户, 使用本文方法、文献[4]、文献[5]方法检索其所需文档。在检索过程和检索结果中分别以下列指标为依据, 验证所提方法的有效性。

1) 检索效率

2) 检索过程安全性

3) 检索结果准确性

实验结果如下:

图2 不同方法信息检索效率对比

图2 不同方法信息检索效率对比   

 

图2 不同方法信息检索效率对比

图2 不同方法信息检索效率对比   

 

由图2可知, 文献[4]和文献[5]方法整体检索耗时较高, 表示两种方法的信息检索效率较低。而分布式搜索引擎中关键词倒排索引方法考虑到检索文档各维特征在取值方面差异大的问题, 将各维特征进行了归一化, 进而有效提升了关键词倒排索引时的效率。相比文献[4]和文献[5]方法, 该方法可靠性更强。

图3 不同方法检索安全性对比

图3 不同方法检索安全性对比   

由图3可知, 文献[4]数据检索方法安全性最差, 文献[5]信息数据检索方法次之, 分布式搜索引擎中关键词倒排索引方法信息检索安全性最佳。该方法为避免索引文档有信息泄露情况, 保障信息检索安全性, 对索引文档进行加密, 并构建了密文索引文档, 有效增强了所提方法的安全性。

1中, A1代表检索次数, A2代表文献[4]方法检索准确率, A3代表文献[5]方法检索准确率, A4代表分布式搜索引擎中关键词倒排索引方法检索准确率。其中, 准确率单位为%。

表1 不同方法信息检索准确率对比

 

 


A1
A2 A3 A4

12
78 86 95

22
89 89 98

32
75 87 97

42
68 85 95

52
69 90 94

62
78 75 96

72
75 71 98

82
74 72 99

92
73 75 98
 

 

从表1可以看出, 分布式搜索引擎中关键词倒排索引方法检索准确性明显优于当前方法。所提方法采用每个文档项目使用多个关键词或者关键字予以表征策略, 提高了信息索引结果的准确性, 增强了检索方法的整体性能。

4 结束语

信息检索是信息数据利用的前提条件, 但当前相关方法无法满足现实需求, 存在效率低、检索过程安全性和准确性不高等问题, 提出分布式搜索引擎中关键词倒排索引方法。通过构建索引体系、分析索引关键技术等步骤实现信息检索, 并利用实验证明了所提方法的实用性。随着计算机网络的不断发展, 集群规模逐渐扩大, 下一步应该引入智能动态负载均衡策略, 在信息检索中充分利用检索中各个节点计算性能, 构建更好的检索体系, 进一步提升检索结果的准确率和效率, 尽可能地降低检索能耗。总之, 分布式的搜索引擎潜力巨大, 不断开发与利用该引擎, 是未来信息检索领域的重点内容。


 
QQ在线咨询
售前咨询热线
13524991327
售后服务热线
13524991327
返回顶部