k-前缀树全文搜索方法及其应用

《k-前缀树全文搜索方法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、厦门大学硕士学位论文K-前缀树全文搜索方法及其应用姓名：陈金桥申请学位级别：硕士专业：系统工程指导教师：吉国力20090501摘要在科学技术高速发展和信息爆炸式膨胀的时代，如何快速和有效的从海量信息中获取有用信息是信息检索技术主要的研究课题。当前应用广泛的后缀树和后缀数组全文搜索方法在搜索速度和计算空间方面各有特点和局限，本文正是针对此问题提出了K．前缀树全文搜索方法。K．前缀树全文搜索方法是一种基于前缀树且能够对内容长度不大于K的字串进行搜索的文本全文搜索方法，其主要特点是使用K子串来构建前缀树，使得最大空间复杂度为o(zk+1)，并具有折中后缀数和后缀数组在计算空间和搜索速度上的优点。

2、通过与广泛应用的后缀树和后缀数组两种全文搜索方法的计算比较，说明了K．前缀树全文搜索方法在计算空间和搜索速度上具有良好的综合性能。载体识别是生物信息学中一项基础而重要的任务，对去除EST序列中的污染和提取cDNAinset具有重要作用。本文针对植物EST序列的载体识别问题，基于EST序列期望结构给出了EST序列的载体结构描述，由此结合K-前缀树全文搜索方法提出了基于K．前缀树的EST序列载体识别方法，其主要特点是基于EST序列载体结构来构建K_前缀树，并以K．前缀树进行K子串的匹配、扩展和合并。通过对172229条松树EST序列的载体识别，说明了基于K．前缀树的EST载体识别方法的可行性和

3、有效性。关键词：K-前缀树；信息搜索；载体识别AbstractWiththerapiddevelopmentofscienceandtechnology,howtofastdrivemostusefulinformationfromthefloodofinformationisthemostimportantresearchsubjectofmessageretrieval．Thefulltextretrievalwhichisoneofthemajorsearchcontentofmessageretrieval，istoresolvetheissuethathowtodriveinfo

4、rmationapacefrequentlyandchangefullyfrommassiveinformation．Thecurrentwidelyusedsuffixtreeandsuffixarrayfull-textsearchmethodhavet11eirowncharacteristicsandlimitationsinsearchspaceandcomputingspeed．Astoresolvethisproblem，thispaperdescribesanfull—textsearchmethodcalledK-PrefixTreefull-textsearchmeth

5、od．K．PrefixTreefull．textsearchmethodiSa伽1．textsearchmethodwhichiSbasedonprefixtreeandCallsearchthetextwithlengthnotgreaterthanIcThemaincharacteristicofK-PrefixTreeiscreatingprefixtreewimk-substring．So，it’SmaximumspacecomplexityisO(Zk+1)anditcompromisethesearchspaceandcomputingtimeadvantagesofsuffi

6、xtreeandsuffixarray．ToavoidlargeoccupationspacelikeSuffixTree，thismethodimportstheSuffixArray’SpracticeofreducingtheinsidenodeofSuffixTree，andusetheK—substringtoconstructtreeinsteadofsuffix，SOcomparetoSuffix，itoverwhelminglysaveslargespaceofTree．．Bycomparisonwiththewidespreadusefull—textmethodsofs

7、uffixtreeandsuffixarray,itisverifiedthatK-PrefixTreefull．textsearchmethodhaswellcombinationpropertyinsearchandcomputingtime．Asoneofthebasicandimportantmissionofbioinformatics，vectorrecognitionplaysanimportantpart