全文索引技术中索引归并算法的研究与分析

《全文索引技术中索引归并算法的研究与分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要索引的动态维护与更新是全文检索与全文索引技术中的一个重要研究和应用方向，当随着Intemet的迅速发展，互联网上信息数据在急剧地增长，而在这种海量数据的情况下，新的数据在不断增长，同时过时的数据就要被淘汰，这就需要对信息数据频繁的插入和删除，因此，索引的动态维护中的归并算法的研究也就处于了一个十分重要的地位。本论文主要针对常见的索引归并算法进行改良，并对改良的算法在时间效率以及可行性上进行了研究论述。索引的过程就是把原始的数据处理成一个有利于高效检索的数据形式，因此索引的基本结构关系到动态索引维护与更新的效率，包括建立索引的过程，索引的组织方式，正排表，倒排文件及倒排索引的

2、建立，本文介绍了构造倒排索引的过程，并分析静态索引技术的优缺点以及增量索引知识，还有索引动态更新对信息检索技术的重要性。本文比较了各种索引更新策略，包括原地更新策略，重建策略，重新归并更新策略，并且分析了这些策略的成本代价，在此基础上研究了基于归并策略的各种不同的索引归并算法，包括有立即归并算法，对数归并算法，几何划分归并算法，类哈夫曼索引归并算法，同时分析了他们的优缺点，提出了各自的改良算法，其中本文的重点是在详细分析几何划分归并算法的基础上，针对原有的几何归并算法在索引过程中没有对文档删除，提出了带有索引垃圾碎片的回收的新的几何归并算法，其中新算法采用了极限值的方法对删除的

3、文档进行处理。最后通过一个开源的全文检索与全文索引平台测试了立即归并算法，对数归并算法及改进算法的索引合并过程和时间，验证了在相同条件下使用改进的算法进行合并，时间上得到了提高。测试了几何归并删除文档索引碎片回收的可行性。关键词：全文检索，倒排索引，索引合并，重新归并ABSTRACTInrecentyear,themaintenanceandupdateofon-lineindexbecomethehotisSueiIltlleresearchofmll—textretrieval，aStherapiddevelopmentofIntemet，da舾onⅡ1eInternet1

4、Salsoexplodingrapidly,however,nomatterthehugedataexiSted．newdatecontlnuetogrow,outdateddateneedtobeeliminatedaSwell，whichrequiresthefrequentmsertionanddeletionofdata,therefore，accordingly,indexmergera删1111etic1sputonthecentralarena·Inthispaper,wemainlyaimattheanalysisofindexmer￡e2Llgorithmin

5、thefull_textretrievalandprovideimprovedalgorit王mlintenIlsoftimeconsumption．Thefundamentalofindexisconvertoriginaldatetoflexibledatastructuret0makese抓．nmoreeffective，baseonanalysisofthebaSicstructurewhichdoesimpactel-IiciencYofindexupdate，includehowtoconstructindex，structllresofindexandinvert

6、edfiletogetherwithhowtoconstructinvertedindex，wealsomentiontheadVantageSanddisadvantagesofstaticindex，andintroduceincrementi11dexandtheimportanceofdynamicupdateattheendofthissession．2．Inthethesis，weresearch3indexmaintenancestrategies，In．placeIndeXupdate，Merge·BasedIndexupdateandRe—BuildIndex

7、update，wKch岛cusoncostconsulllptloninthedifferentstrategies，accordingly,weanalyzethemerge—basedindeXmaIntellancestrategies，includedimmediatemergealgorithm，logarithmicmerge，geometricpartitioninganddynamicbalancingtreemergeralgorithmtogetherwiththeira