试论互关联后继树模型扩展研究

《试论互关联后继树模型扩展研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学硕士学位论文互关联后继树模型扩展研究姓名：袁天宇申请学位级别：硕士专业：计算机软件与理论指导教师：胡运发20070520论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成采。论文中除了特掰加以标注和致谢的地方矫，不包含其谴入或其它梳鞫注经发表或撰写过鹃耩究戒莱。萁镌霞恚辩奉磷究懿翁发移掰徽貔爨菰鹭避在论文率俸了鞠确嚣声氍并表示了谢意。作者签粥：埠嘶珥剑论文使用授权声明本人完全了解复旦大学有关保留、使用学袋论文的规定，即：学校有权保爨送交论文的复印件，允许论文被煮阗和供阅；学校可以公布论文

2、的全部或部分内容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密尉遵守此规定。撂者签襄；参誊导蜂签名：—：li匮趁毽翅：¨71}1摘要随着人类社会进入“信息时代”，信息记录的形式已由纸张演变为电子形式，而对于信息的检索也由计算机代替了人工方式。在存储、检索和更新结构化数据时，传统的关系数据库(RDBMS)作为一种成熟的技术足以胜任。但是随着非结构化数据的日益膨胀，特别是占所有信息量的比重增加，如何有效的管理非结构化数据已成为信息检索领域的一个重要课题。在关系数据库处理非结构化数据比较低效的情况下，全文

3、检索技术应运而生。全文检索技术针对非结构化数据中的文本数据，通过精心设计的文本数据存储结构，提供高效、多样化的文本数据检索界面和更新界面。本文在互关联后继树这一全文检索模型现有的研究基础上，对其优缺点进行了分析。对如何进一步提高互关联后继树的文本检索速度和解决在处理海量文本数据时存储和检索效率下降的问题上做出了努力。本文的重点和取得的创新性成果主要包含以下几个方面：1)分析全文检索的一些主流模型的索引结构、检索算法和各自的优缺点，并对它们的适用性进行了探讨。2)介绍互关联后继树模型的基本概念、索引创建和检索算法，

4、包括其索引结构，精简的互关联后继树模型，三元互关联后继树模型和基于区间的检索算法。3)提出并实现了后继字符和后继编号都有序的双排序互关联后继树模型。借助于另一种全文索引模型PAT数组来创建双排序互关联后继树。检索算法利用后继字符和后继编号都升序排列的特点，使用折半查找代替原有的顺序查找，大大优化了检索算法的时间复杂度。4)将原限于字索引领域的互关联后继树模型扩展到词领域。互关联后继树在处理海量的原始文本数据时，需要用更多的字节来保存后继编号。这使索引的膨胀比增加，索引创建过程和检索过程都因为频繁的内外存交换而变得

5、低效。本文选择按词来组织索引结构来解决这一问题。通过将互关联后继树的特点和分词算法相结合，对词表预先建立索引，去除了分词失败时需要多次回溯这一缺陷。显著提高了索引的创建效率和检索效率，同时大大降低了索引的膨胀比。并成功地将这一创新性成果应用到了上海电信黄页搜索引擎系统中。关键词：全文检索全文索引互关联后继树双排序词索弓AbstractSteppingintoInformationEra,paper-baseddataisreplacedbyelectronicdataandmanualinformationret

6、rievalisreplacedbycomputer-basedretrieval．RelationalDBisfullcapableofdealingwithstructureddata．However,underthecircumstancesofexplosivenon-structureddata,howtoreachnon-structuredonanorganizedformatandefficientretrievalbecomesanemergingissue．Especially,Relatio

7、nalDBisprovedtobeinefficientofmanagingnon-structureddata．Tosolvethisproblem,Full-TextRetrieval．whichaimsatstoringnon-structureddatathroughmeasureddatastructureandprovidingefficientretrievinginterfaces，hasbeencomeupwith．BasingoncurrentresearchingoutcomeofInter

8、-RelatedSuccessiveTrees(msD，theadvantagesanddisadvantagesofIRSTareanalyzedandsummarized．HowtoimprovetheretrievalefficiencyofIRSTfurtherandhowtoovercomethelowstoringandretrievalefficiencyo