（系统工程专业论文）K前缀树全文搜索方法及其应用.pdf

摘要 摘要 在科学技术高速发展和信息爆炸式膨胀的时代，如何快速和有效的从海量信 息中获取有用信息是信息检索技术主要的研究课题。当前应用广泛的后缀树和后 缀数组全文搜索方法在搜索速度和计算空间方面各有特点和局限，本文正是针对 此问题提出了k 前缀树全文搜索方法。 k 前缀树全文搜索方法是一种基于前缀树且能够对内容长度不大于k 的字 串进行搜索的文本全文搜索方法，其主要特点是使用k 子串来构建前缀树，使 得最大空间复杂度为o ( z k + 1 ) ，并具有折中后缀数和后缀数组在计算空间和搜索 速度上的优点。通过与广泛应用的后缀树和后缀数组两种全文搜索方法的计算比 较，说明了k 前缀树全文搜索方法在计算空间和搜索速度上具有良好的综合性 能。 载体识别是生物信息学中一项基础而重要的任务，对去除e s t 序列中的污染 和提取c d n ai n s e t 具有重要作用。本文针对植物e s t 序列的载体识别问题，基 于e s t 序列期望结构给出了e s t 序列的载体结构描述，由此结合k - 前缀树全文 搜索方法提出了基于k 前缀树的e s t 序列载体识别方法，其主要特点是基于 e s t 序列载体结构来构建k _ 前缀树，并以k 前缀树进行k 子串的匹配、扩展和 合并。通过对1 7 2 2 2 9 条松树e s t 序列的载体识别，说明了基于k 前缀树的e s t 载体识别方法的可行性和有效性。 关键词：k - 前缀树；信息搜索；载体识别 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , h o wt of a s td r i v em o s t u s e f u li n f o r m a t i o nf r o mt h ef l o o do fi n f o r m a t i o ni st h em o s ti m p o r t a n tr e s e a r c h s u b j e c to fm e s s a g er e t r i e v a l t h ef u l lt e x tr e t r i e v a lw h i c hi so n eo ft h em a j o r s e a r c h c o n t e n to fm e s s a g er e t r i e v a l ，i st or e s o l v et h ei s s u et h a th o wt od r i v ei n f o r m a t i o n a p a c ef r e q u e n t l ya n dc h a n g e f u l l yf r o mm a s s i v ei n f o r m a t i o n t h ec u r r e n tw i d e l yu s e d s u f f i xt r e ea n ds u f f i xa r r a yf u l l - t e x ts e a r c hm e t h o dh a v et 1 1 e i ro w nc h a r a c t e r i s t i c sa n d l i m i t a t i o n si ns e a r c hs p a c ea n dc o m p u t i n gs p e e d a st or e s o l v et h i sp r o b l e m ，t h i s p a p e rd e s c r i b e sa nf u l l t e x t s e a r c hm e t h o dc a l l e dk - p r e f i xt r e ef u l l - t e x ts e a r c h m e t h o d k p r e f i xt r e ef u l l t e x ts e a r c hm e t h o di sa 伽1 t e x ts e a r c hm e t h o dw h i c hi sb a s e d o np r e f i xt r e ea n dc a l ls e a r c ht h et e x tw i t hl e n g t hn o tg r e a t e rt h a ni ct h em a i n c h a r a c t e r i s t i co fk - p r e f i xt r e ei sc r e a t i n gp r e f i xt r e ew i mk - s u b s t r i n g s o ，i t s m a x i m u ms p a c ec o m p l e x i t yi so ( z k + 1 ) a n di tc o m p r o m i s et h es e a r c hs p a c ea n d c o m p u t i n gt i m ea d v a n t a g e so fs u f f i xt r e ea n ds u f f i xa r r a y t oa v o i dl a r g eo c c u p a t i o n s p a c el i k es u f f i xt r e e ，t h i sm e t h o di m p o r t st h es u f f i xa r r a y sp r a c t i c eo fr e d u c i n gt h e i n s i d en o d eo fs u f f i xt r e e ，a n du s et h ek s u b s t r i n gt oc o n s t r u c tt r e ei n s t e a do fs u f f i x ， s oc o m p a r et os u f f i x ，i to v e r w h e l m i n g l ys a v e sl a r g es p a c eo ft r e e b yc o m p a r i s o n w i t ht h ew i d e s p r e a du s ef u l l t e x tm e t h o d so fs u f f i xt r e ea n ds u f f i xa r r a y , i ti sv e r i f i e d t h a tk - p r e f i xt r e ef u l l t e x ts e a r c hm e t h o dh a sw e l lc o m b i n a t i o np r o p e r t yi ns e a r c h a n dc o m p u t i n gt i m e a so n eo ft h eb a s i ca n di m p o r t a n tm i s s i o no fb i o i n f o r m a t i c s ，v e c t o rr e c o g n i t i o n p l a y sa ni m p o r t a n tp a r ti ns e q u e n c e s c o n t a m i n a t er e m o v i n ga n df i n d i n gt h ee d n a i n s e t a p p l y i n gk - p r e f i xt r e et ov e c t o rr e c o g n i t i o ni sv e r yi m p o r t a n ta n dm e a n i n g f u l t ob i o l o g i s t t h i sp a p e rd e s c r i b e st h ev e c t o rs t r u c t u r eo fe s ts e q u e n c ew h i c hb a s e d o nt h ee s te x p e c t e ds t r u c t u r e c o m b i n e dt h ev e c t o rs t r u c t u r eo fe s ts e q u e n c ea n d k p r e f i xt r e ef u l l t e x ts e a r c hm e t h o d ，av e c t o ri d e n t i f i c a t i o nm e t h o do fe s t s e q u e n c ew h i c hb a s e do nk - p r e f i xt r e ei sp r o p o s e d t h em a i nc h a r a c t e r i s t i c so ft h i s i i i k - 前缀树全文搜索方法及其应用 m e t h o da l ec r e a t i n gk - p r e f i xt r e eb a s e do nv e c t o rs t r u c t u r eo fe s t s e q u e n c ea n d m a t c h i n g ，e x t e n d i n g ，m e r g i n gk - s u b s t r i n gu s i n gk - p r e f i xt r e e i tw a sa p p r o v e dt h a t t h ek p r e f i xt r e ev e c t o rr e c o g n i t i o nm e t h o di sf e a s i b l ea n de f f e c t i v e b yt h ee x p e r i m e n ta n da n a l y s i so ft h er e p r e s e n t a t i o n ，k - p r e f i xt r e ei sn o to n l y d o i n gw i t hl e s st i m eb u ta l s od o i n gw i t hl e s ss p a c e ，a n dw i l lb eh e l p f u li ns t u d yo f m e s s a g er e t r i e v a le s p e c i a l l yf u l lt e x tr e t r i e v a l k e yw o r d s ：k - p r e f i xt r e e ；s u f f i xt r e e ；v e c t o rr e c o g n i t i o n i v 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。本人 在论文写作中参考其他个人或集体已经发表的研究成果，均在文中以适当 方式明确标明，并符合法律规范和厦门大学研究生学术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的资助， 在() 实验室完成。( 请在以上括号内填写课题或课题组 负责人或实验室名称，未有此项声明内容的，可以不作特别声明。) 声明人( 签名) ： 陈岔析 矽夕年月2 1 e i 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等 规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文( 包 括纸质版和电子版) ，允许学位论文进入厦门大学图书馆及其数据库被查 阅、借阅。本人同意厦f - 1 ) k 学将学位论文加入全国博士、硕士学位论文共 建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、 缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文，于 年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文应是 已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审 定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论 文，均适用上述授权。) p r i m a ( 签名) ：防各桷 卯罗年月力日 第一章绪论 1 1 研究背景 第一章绪论 进入2 0 世纪以后，科学技术以爆炸式的速度向前发展，各学科领域，特别 是物理学、生物学、化学、天文学、地理学领域都进行了深刻的革命，取得了惊 人的进展，尤其是随着各物种基因测序的相继完成，基因数据正急剧膨胀，目前 仅登录在美国g e n e b a n k 数据库中的d n a 序列总量已超过7 0 亿碱基。随着计算 机越来越普及的今天，信息的产生速度进一步加快，已经大大超出人们手工处理 的能力，迫切的需要能够更加快速的进行信息检索。 信息检索是指将信息按照一定的方式组织和存储起来，并根据信息用户的需 要找出有关信息的过程【。而在当今计算机普及的时代，信息检索是以计算机为 工具，按照一定的数据结构组织和存储数据，根据信息用户输入信息找出用户关 心信息的过程( 图1 1 ) ，而信息存储的数据结构是信息检索速度的最大影响因素。 信息检索在信息管理中具有重要的作用，主要包含增强决策的科学性、缩短获取 信息的时间、有利于在大量的信息中获取所需的全部信息以及提高科研工作的能 力。 图1 - 1 信息检索过程示意图 信息检索按照能否对信息全文进行构建索引和搜索可分为关键字信息检索 和全文信息检索。关键字信息检索是通过能够概括信息数据全文的一些关键字进 行信息检索，顺排文档和倒排文档是其中典型实例，都是通过对待检索数据的关 k - 前缀树全文搜索方法及其应用 键字建立索引，从而能够快速的进行数据搜索。全文信息搜索是以被搜索的数据 全文作为对象建立数据结构，从而能够使用户搜索任何数据而不仅仅是特定的关 键字。 全文检索的核心是将源数据中所有的数据信息建立索引库，从而快速搜索关 键字。建立全文索引库的关键是底层的数据存储结构，优秀的数据存储结构不仅 能够保证全文索引占用较小的空间，也能够为快速搜索关键字提供算法基础。在 数据结构基础上开发的优秀创建算法和搜索算法，能够极大的改善全文搜索方法 的创建时间和搜索时间。 1 2 研究现状 信息检索从产生到现在可以大致分成三个阶段【1 1 。第一阶段称为手工信息检 索阶段，从1 8 世纪中叶到2 0 世纪中叶2 0 0 多年间，科学技术不断发展，各种数 据信息急剧增加，为了有效利用大量的数据信息，逐渐形成了传统的手工检索工 具一目录、索引和文摘。第二阶段为机械信息检索阶段，是2 0 世纪5 0 年代开始 使用各种机械装置进行信息检索的机械系统，主要包含两种基本类型，即机电信 息检索系统和光电信息检索系统。第三阶段为计算机检索阶段，计算机的发明为 信息检索注入了强劲的动力，成为了信息检索不可或缺的工具。利用计算机的快 速计算能力以及信息网络的全球性，信息检索出现了前所未有的检索速度和处理 大量数据的能力以及能够全球性的处理数据。 关键字信息检索是信息搜索中的一个重要部分，需要对数据全文进行良好的 提炼，关键字选取的不合适将导致信息数据部分内容不能检索或者检索错误。当 前关键字信息检索中顺排文档应用较广，顺排文档通过对各文档的关键字建立索 引，从而实现快速的信息检索。近年来，由于前缀树具有信息搜索速度快、占用 空间小等优点，正受到人们的关注和使用，特别是在生物信息学领域。 全文检索是信息检索中重要和复杂的领域，与关键字检索不一样，全文检索 需要对信息数据全文进行搜索，而对于当前大量的信息，简单的对信息全文进行 检索需要大量的时间和空间，这都促使全文检索研究和发现新的数据结掏。目前 流行的全文索引模型有倒排索引、署名文件、位图和p a t 数组【2 】。倒排索引由于 其综合性能较好、应用成熟，成为当前许多主流全文检索系统使用的模型。 2 第一章绪论 后缀树和后缀数组由于其良好的搜索性能已经取得了广泛的应用，但是这两 种方法在计算空间和搜索速度上都存在各自的有点和局限。后缀树是基于前缀树 结构存储后缀，其搜索速度与被搜索的数据量无关，但计算空间为o ( n i 1 ) ；后 缀数组是基于数组存储后缀，其搜索速度与被搜索的数据量有关，但计算空间为 o ( 。 1 3 本文的主要工作 本文的主要工作体现在以下三个方面： 1 ) 提出了k - 前缀树全文搜索方法。本文提出了一种基于前缀树且能够搜索 长度不大于k 字串的文本全文搜索方法，其主要特点是使用k 子串来构建前缀 树，使得最大空间复杂度为o ( z k + 1 ) ，并具有折中后缀数和后缀数组在计算空间 和搜索速度上的优点。 2 ) 对比k - 前缀树全文搜索方法与后缀树、后缀数组两种全文搜索方法的计 算空间和搜索速度。通过在长度均为1 0 0 0 0 0 的随机数据和d n a 序列中搜索的 结果，后缀树的搜索时间小于后缀数组的1 5 ，而后缀数组占用的空间小于后缀 树的l 7 ，k - 前缀树具有与后缀树差不多的搜索时间，并且占用的空间是后缀树 的1 5 ，小于后缀数组的2 倍。相对于后缀树和后缀数组，k - 前缀树在占用空间 和搜索时间上得到了较好的平衡。 3 ) 提出了e s t 序列载体结构，由此结合k - 前缀树全文搜索方法得到了基于 k - 前缀树的e s t 序列载体识别方法。针对植物e s t 序列载体识别的特点，基于 e s t 序列期望结构给出了e s t 序列的载体结构，并由此结合k - 前缀树全文搜索 方法提出了的基于k 前缀树的e s t 序列载体识别方法。通过对1 7 2 2 2 9 条松树 e s t 序列的载体识别，说明了基于k 前缀树的e s t 载体识别方法的可行性和有 效性。 1 4 本文的组织结构 本文共分成六章，除第一章以外其它章的组织内容如下： 第2 章：基于前缀树的搜索方法。介绍了前缀树的基础概念以及基于前缀树 的后缀树全文搜索方法，并对两者进行了比较研究。 3 k - 前缀树全文搜索方法及其应用 第3 章：k - 前缀树全文搜索方法。详细的阐述了k 前缀树全文搜索方法内 容，主要包含创建k _ 前缀树和基于k 前缀树搜索的两个过程，并总结了k - 前缀 树的优点。 第4 章：与后缀树和后缀数组全文搜索方法的比较。文章概述了全文搜索和 后缀数组方法，并通过实验来对比k 前缀树和后缀树、后缀数组在全文搜索中 的计算空间和搜索速度。 第5 章：k - 前缀树在载体识别中的应用。介绍了载体识别的背景和通过e s t 序列的期望结构提出的e s t 序列载体结构，并描述了结合e s t 序列载体结构和 k - 前缀树全文搜索方法的基于k _ 前缀树的e s t 序列载体识别方法，最后给出了 对1 7 2 2 2 9 条松树e s t 序列的载体识别实验结果及分析。 第6 章：总结与展望。对全文工作进行总结，并提出了把k - 前缀树应用到其 他领域的工作展望。 4 第二章基于前缀树的搜索方法 2 1 基本概念 第二章基于前缀树的搜索方法 定义2 1 ( 字符集) 字符集是一个有序的元素集合，在中的任意两个不 同的元素q 和1 3 都可以比较大小，要么q 1 3 ，要么1 3 1 3 ) 。字 符集中的元素称为字符。 定义2 2 ( 字符串) 长度为n 的字符串s 是将n 个字符顺次排列形成的字符序 列，n 称为s 的长度，表示为l e n ( s ) 。s 的第i 个字符表示为s 嘲。 定义2 - 3 ( 子串) 字符串s 的子串s i j 】，i j ，表示s 串中从位置i 至i j j 的字 符序列，也就是顺次排y u s i ，s 【i + 1 】，s u 形成的字符串。 定义2 - 4 ( 后缀) 后缀s u f f i x ( s ，i ) 是指从字串s 的某个位置i 开始到整个串末尾 结束的一个特殊子串，也就是s u f f i x ( s ，i ) = s i 1 e n ( s ) 。 定义2 5 ( k 子串) 字符串s 的k 子串s k i 】，表示s 字符串中从i 开始的k 个字符， 也就是s k i = s i i + k - 1 】。 定义2 6 ( 字符比较) 字符比较通常是指按照字符的字典顺序比较，也就是 对于两个字符串u 、v ，令i 从l 开始顺次比较u 【i 】和v i 】，如果u i - - v i 贝j j 令i 加1 ， 否则若u i 】 v ( 也就是v l e n ( u ) 或者i l e n ( v ) 仍未比较出结果，那么若l e n ( u ) v 。 2 2 前缀树与后缀树 前缀树( p r e f i xt r e e ，或t i r e ) 是一种有序树数据结构，通常被存储在一个以 字符串为关键字的联合数组中【3 1 。与二叉搜索树不同，在树罩没有结点存储与结 点相关联的关键字，而是用在树中的位置展示与其相关的关键字。任何一个结点 的所有子结点有一个字符串前缀与结点相关联，根与空字符串相关联。值通常跟 每个结点不关联，只是叶结点和一些内部的结点与感兴趣的关键字相关。具体前 缀树结构参见图2 1 。 5 k - 前缀树全文搜索方法及其应用 图2 1 关键字a ，t r e e ，t r i e 和i n 构成的前缀数 后缀树( s u f f i xt r e e 、s u f f i xt i r e 、p a tt r e e 或p o s i t i o nt r e e ) 是一种特殊的前缀树， 是把待搜索文本的所有后缀作为关键字的一种能够进行全文检索的前缀树。方法 由w e i n e r 在19 7 3 年提出，并最初命名为p o s i t i o nt r e e l 4 】，并随后被d o n a l dk n u t h 描述为 a l g o r i t h mo f t h ey e a r1 9 7 3 ”。一个具有n 个词的字元串s 的后缀树t ，就 是一个包含一个根节点并具有n 个叶子节点的有向树。该树的每一个内部节点， 除了根节点以为，都至少有两个用s 的一个非空字串来标识的子节点。对于任何 叶子i ，沿根到叶子i 的边标签的串联就表示从位置i 开始的s 的后缀1 9 l 。具体后 缀树的结构参见图2 2 。 亩由 图2 2t r e e 字串构成的后缀树 前缀树或后缀树的创建过程就是依次往前缀 对中增加关键字的过程，按照待 增加关键字中的字符，从根结点出发，依次往下延伸，如果碰到节点中不存在相 应的前缀边，则增加叶子节点和相应的前缀节点边，并使的增加的边指向增加的 叶子节点。如果碰到节点边的字符串也待搜索关键字w 前缀某些字符一致，但 是整体不一致，则分裂该边，增加一个内节点和叶子节点，分别由公共部分和差 异部分字符指向。 6 $ l l 一 倘由 、 $ 小哭 第二章基于前缀树的搜索方法 基于前缀树或后缀树查找字符串s 时，只需依次枚举s 的每个字符，同时从 树的根节点开始选择相应的边往下走。如果枚举完的同时到达树的叶子节点，说 明s 存在于树中。如果未到达叶子节点或者枚举中途发现没有任何对应的边，说 明s 没有被包含在树中。 2 3 前缀树与后缀树的比较 2 2 3 1 前缀树与后缀树的共同点 前缀树基于关键字的前缀建立树，并且树的节点中不保存待搜索的文本数据 而是相应的位置信息，后缀树是一种特殊的前缀树，所以两者底层都是采用前缀 树作为其数据结构，具有一些共同的的优点。 1 ) 快速的搜索关键字。对于给定的长度为m 的关键字p ，能够在o ( m ) 时间 内搜索完毕。由于搜索时间仅仅依赖于搜索的关键字p ，而与被搜索的数据无关， 所以在大量的数据中，能够快速搜索并且能够保搜索的持稳定性。这对于应付当 今社会中大量数据的检索具有重大意义，并且能够很好的适应继续快速膨胀的数 据。 2 ) 对于大量的数据，需要更少的存储空间。由于前缀树不是把关键字保存 在树的节点中，而只是通过关键字的字符作为前缀保存在树的边中，并且相同关 键字前缀是通过共享同一个节点而不是创建不同的节点，所以前缀树需要更少的 空间来保存大量的关键字信息。目前大量的数据，虽然具有庞大的数据量，但是 这些数据的字符集是固定的，并且往往相对于数据量来说是很少的，这给由字符 集大小决定存储空间的前缀树方法带来了广阔的应用空间。 3 ) 可以通过前缀树来查找关键字在数据中的最长前缀。基于d 矿缀树进行搜 索关键字w ，如果关键字w 没有出现在前缀树中，即在前缀耐由根节点通过前 缀往下延伸时某一个节点没有出现相应的前缀节点，则由当d 才节点回溯到根结 点，则是被查找关键字在前缀树中的最长前缀。这给前段模糊查询提供了便捷的 实现。 7 k - 前缀树全文搜索方法及其应用 2 3 2 前缀树与后缀树的差异 后缀树是使用所有后缀构建而成的前缀树，其构建目的是为了进行全文检 索，具有前缀数不具备的优点。 1 ) 能够进行全文检索。由于后缀树是由所有后缀构成，故能够在整个被搜 索数据中进行搜索，而不仅仅是像前缀树只能搜索特定的关键字。这在数据量庞 大，而人们需要在数据量中频繁的进行搜索的今天，是具有非常大的意义的。 2 ) 对字符串进行大量的操作。后缀树能够在o ( n i + n i ) 时间内查找字串s i 和 s 的最长相同子串；在o ( n ) 时间内找到最长重复子串等等。 3 ) 线性时间内构建树。由于后缀之间的关系，所以可以在o ( n ) 时间内构建 好后缀树，这使得后缀树能够适用于大型的文本数据，而不会随着数据的膨胀过 度膨胀。 前缀树是基于用户给定的关键字构建而成，相比后缀树固定由后缀构成，具 有后缀树不具有的优点。 1 ) 前缀树具有更好的可塑性。后缀树是采用所有后缀作为关键字而构建的， 而前缀树是基于用户给定的关键字进行构建，从而前缀树可以根据用户不同的需 求采用不同的关键字构建，能够更加贴近用户使用的需求。 2 ) 前缀树相对后缀树更省存储空间。后缀树使用的关键字是所有的后缀， 而前缀树使用的是用户给定的关键字，从而相对后缀树需要对数据全文进行构 建，前缀树可以只针对特定的关键字构建按，能够节省大量的空间。 2 4 前缀树与后缀树的应用与研究 前缀树和后缀树作为优秀的数据搜索方法，都得到了广泛的应用和研究。在 方法的应用方面，前缀树自从e d w a r df r e d k i n 以来就得到了广泛的关注，目前已 经应用到不同的领域，取得了不错的成果：在字符串搜索方面，基于前缀树的字 符串搜索算法能够使用更少的内存【5 j 。在数据挖掘方面，前缀树也体现了优异的 性能，汪红等【6 】提出的基于前缀讨的t i u a 算法，算法摆脱了传统算法多次迭代的 不足，并利用挖掘出的结果，只需扫描一次数据库，就能满足各种要求，通过以空间 换时间，达到提高挖掘效率的目的。张坤等【_ 7 】提出了一种增量序列模式挖掘算法， 8 第二章基于前缀树的搜索方法 算法构造了前缀树表示序列模式，并用广度剪枝和深度剪枝维护该前缀树的结 构。朱光喜等【8 】提出一种基于前级树的新算法，算法通过引入前级树( p r e f i x t r e e ) 用来压缩存放数据所相关信息，并通过调整前级树中节点信息和节点桩立接在 p r e f i x t r e e 上采用深度优先的策略抢掘频繁模式，而不常要任何附加的数据结构， 从而大大提高了花扭效率。前缀树不仅仅在数据搜索和挖掘方面取得了应用，并 且在其他方面也得到了很好的应用。r a m k i s h o r eb h a t t a c h a r y y a 9 把前缀树应用到 数据编码上，从而能够创建压缩率更高和空间优化利用的前缀树编码方案。 利用后缀树处理不同领域的问题一直是人们关注的问题。a p o s t o l i c o 在1 9 8 5 的调查论文中提到后缀树已经在论文中引用了超过4 0 次【1 0 l 。后缀树在其提出来 的时候就被应用在字符串中查找最长的重复子引4 1 ，随后应用到在字符串中查找 所有的重复子串f 】j 】以及字符串比较f 1 甜。不仅在字符串中得到应用，后缀树也在 其他领域得到了很好的应用。r o d e h 把后缀树应用到了文本压缩领域【l3 1 ，c a r d e n a s 应用倒排索引中【1 4 1 ，c l i f f 在基因数据分析中应用了后缀树【1 5 】。 后缀树由于使用后缀构建树，因此如何利用后缀的特点从而快速和省空间构 建后缀树一直是研究的热点。自w e i n e r 提出后缀树以来，后缀树的构建算法一 直在创新，尽量占用更少的空间和时间。w e i n e r 最初提出了一种对被搜索字串 从右到左，首先加入最短的后缀，然后依次增加长度，不断地增加后缀树的长度 【4 】。该算法不仅复杂难以理解，并且没有充分考虑到后缀之间的相同点，从而达 到需要。州l o g y ) 的空间负责度。随后m c c r e i g h t 与1 9 7 6 年提出了与w e i n e r 相 反的构建算法，不是从最短后缀开始构建，而是从最长后缀构建，并且利用前后 两个后缀之间只相差一个碱基的特点，从而实现了使用o ( n ) 空间就能够构建后 缀树，并且相对于w e i n e r 算法，算法简单易实现【l6 1 。e s k ou k k o n e n 于1 9 9 5 年 提出了一种线性的实时后缀树构建算法【1 7 1 。 9 k - 前缀树全文搜索方法及其应用 3 1k 一前缀树 第三章k - 前缀树全文搜索方法 k - 前缀树全文搜索方法是以k 子串和长度小于k 的后缀建立的前缀树为结 构，能够对内容长度不大于k 的字串进行搜索的文本全文搜索方法。在包含z 个字符的的字符集中，树的最大深度为k ，最多包含z k + 1 + 1 个节点，每个叶 子节点记录着k 子串在s 中的位置，如有相同的k 子串则记录多个位置信息。 由字串a b c b c a c a b 生成的所有k 子串( 1 0 3 ) 如图3 1 所示，由这些k 子串构 成的k - 前缀树( k - 3 ) 的结构图如图3 2 。 o ，一一一一。一一一一一一一一一一一一”。一一一一4 一一一一。一一一一。一。一一、 ： k 子串： l 子串； ；网阑圆圈圆圈固； 、。一- j p ，一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一、 ； 长度小于k 的后缀： i l l圈囡 ，： a 0 卜c b 尺c争- $文a 少c一4 , 、 s 寻，穗手曳 1 、 1 0 第三章k - 前缀树全文搜索方法 k - 前缀树采用k 子串和长度小于k 的后缀建树，使得树的最大深度为k ， 所以用包含z 个字符的字符集构建的k 前缀树，其最多包含z k + 1 + 1 个结点， 且每个非叶子结点最多需要保存z 个指针指向子结点，每个叶子节点需要保存 相应的位置信息，从而k - 前缀树最大需空间z k + 1 + z k + k 一1 ，即k - 前缀树的最大 空间复杂度为o ( z k + 1 ) 。 k - 前缀树方法同前缀树和后缀树，包含树的创建过程和使用树进行关键字搜 索过程。创建树的过程包含找出所有的k 子串和使用k 子串构建k - 前缀树，同 后缀树一样可以利用后缀之间的关系从而快速和简单的构建后缀树，k - 前缀树也 可以利用前后k 子串之间相差一个字符的差异，也可以得到简化的k 一前缀树构 建方法。使用k - 前缀树搜索关键字同前缀树相同，可以再o ( m ) 时间内搜索完毕。 3 2 创建 创建k - 前缀树是使用k - 前缀树的前提，而对字串p 创建k 前缀树，包含分 割字串得到包含的所有k 子串和长度小于k 的后缀以及依次添加这些子串到k 前缀树中，从而形成最终的k 前缀树。 3 2 1 简单的创建方法 对于长度为n 的字串p ，简单的构建k 前缀树方法可以通过提取k 子串和使 用k 字串建树两个步骤来实现。首先使用长度为k 的滑动窗口依次向前移动1 个字符，从而得到所有的n 1 ( + 1 个k 子串，然后使用建立前缀树的方法，把得 到的k 字串作为关键字来创建k 前缀树。 步骤i ：提取k 字串 对于长度为n 的字串p ，采用长度为k 的滑动窗口，每次向前滑动一个字符， 从而得到所有的k 子串。滑动窗口的长度为k ，于是每一个窗口里面的字串就 是所需要的k 子串，通过每一次在字串p 中向右移动一个字符，从而得到下一 个k 子串，总共移动n k 次，从而得到所有的n k + 1 个k 子串。方法的伪代码 见伪代码3 1 ，图示见图3 3 。 k s t r i n g a r r a y = s t r i n g ； f o r ( i 一0 ，n k + 1 ) k s t r i n g = s u b k s t r i n g ( p ，i ) ； k s t r i n g a r r a y a d d ( k s t r i n g ) ； k - 前缀树全文搜索方法及其应用 e n d f o r f 0 砸 1 ，k - 1 ) k s u f f l x = s u b l a s t c o n t s t r i n g ( p ，j ) ； k s t r i n g a r r a y a d d ( k s u f f i x ) ； e n d f o r 伪代码3 - 1 ：霹把觚；e 纛黜t a l 颞了附弩l 翩匝黼磊j g ： i 。- 一。j 一一一一一o 向右移动个字符施工 ，一m 一一一“。一。一。- 。一。一。_ ”。一_ 。一。一。一。一”。一1 ia l 磊勰囟g 弼 t a r j 醵= ，r 弘：静”- ”一”“”l c 冱强z 簟n 3 礴毒g： i 一。? 一。4 一。，。，。i 髯改向右移动个字符毒彩上 移秘到最左逡i c 个字符o ：嘉1 直；c i g ；g 瑶 f 直t s c l d c ：玎；1 ：撇矗墨鬟a 髓袅蠢缓： w、#“#o# 图3 3 使用长度为8 的滑动窗口提取8 子串 步骤2 ：利用k 子串建树 对于步骤1 得到的所有k 子串，采用逐步加入的方式进行构建k - 前缀树。 采用k 子串的前缀作为根节点到子结点的映射方向，并且把去除父节点字串的 子字串作为以子节点作为根节点的开始字串。当要插入的字串与当前某节点具有 相同的前缀但是不完全相同时，则提取出相同的部分作为它们的父节点，而两者 去除前缀不同的部分作为该父节点的两个子结点。在k - 前缀树的叶子节点中记 录相应的信息，如该k 联子的序列名称和起止位置。通过依次加入所有的k 联 子，最终得到的树就是k 前缀树。算法伪代码见3 2 f o “i c h i l d ( k s t r i n g p o s i t i o n ) 节点。 跳出f o r 。 1 2 第三章k 前缀树全文搜索方法 e n d i f e n d f o r e n d f o r 伪代码3 2 简单的k 一前缀树创建方法，把创建过程分成两个步骤，在计算算法的时间 复杂度和空间复杂度时需要考虑两者之和。在步骤1 提取k 子串的过程中，得 到所以k 子串需要一个k 子串数组来保存得到的所有k 子串，并且需要一个 k s t r i n g 来保存每一个循环中的k 子串，共需要k 枣( n k + 1 ) + k 的空间，需要循环 n k 十1 次。然后在得到长度小于k 的后缀需要保存( k - 1 ) + ( k - 2 卜+ l 字符，故需 要( k 2 + k ) 2 空间，循环k - 1 次。所以在步骤1 中需要k * n g ? 2 + 3 k 2 的空间和 n 的时间。 在步骤2 使用k 子串建树过程中，外层循环需要循环n 次，里层循环最多 需要循环k 次，所以最多共需要循环n * k 次，需要n * k 时间。在循环过程中只 需要循环量k s t r i n g ，占k 个字符空间，加上k - 前缀树所占用的空间，所以使用 k 子串生成k - 前缀树共需要空间为k 。 综合步骤1 和步骤2 ，简单的创建方法共需要k 的空间和n + n * k 的时间， 即方法的空间复杂度和时间复杂度为o ( 1 ) 和o ( k 宰n ) 。由于k 是固定的值，所以 创建过程中都是线性的，需要线性的空问和线性的时间。然而创建过程中把得到 k 子串和使用k 子串建树分裂开，从而导致两次扫描子串p ，并且在扫描过程中 没有考虑到前后k 子串只相差一个字符的特点，从而本文引入优化的创建方法。 3 2 2 优化的创建方法 s k i 子串是字串s 中从i 位置开始k 个相连的字符组成，s k i + 1 与s k i 相差 一个字符，即s k i + 1 的最后一个字符与s k i 的首个字符不同，而两者中间的字 符是相同的。若用s k i 】( j ) 表示s k 【i 】中的第j 个字符，则s k i + 1 与s k i 的关系可 以用公式3 1 表示。 蹦i + 1 】( j ) = s x i u + 1 ) = 1 , 2 一定一1 公式3 1 字串s 中的k 子串共享s 同一位置的字符，所以在m ( k = m - - n k ) 位置的字 符s ，共同属于s k m k + l 】，s k m - l 针2 】，s k m 子串，用公式3 - 2 表示。 以【朋一足+ 1 】( 固= s 置陋一足+ 2 】( 芷一d = = s 工e r a ( 1 ) = 瓤神足= 聊 - 稽一足 1 3 k - 前缀树全文搜索方法及其应用 公式3 2 从公式3 2 可以得到，扫描子串s 的时候，任一个字符至多跟k 个子串相关， 从而只要再扫描子串s 时，使用k 的变量保存于当前子串相关的k 子串，就可 以一次扫描字串s 就可以建立k - 前缀树，而避免对字符扫描k 遍。并且把提取 k 子串和使用k 子串建树合并成一个步骤，即边扫描边建树，不但避免了循环 过程中保存k 子串的数组空间，并且不用重复扫描。算法实现伪代码见伪代码 3 - 3 。 k n o d e a r r a y = n o d e k ；保存与字符s 相关的k 的子串当前的节点 f o r ( i 一0 ，l e n g t h ( s ) 一k 十1 ) p = = r o o t ； i f ( i k ) 处理与字符s ( i ) 相关的i 个子串。 e l s e 处理与字符s ( i ) 相关的k 个子串。 e n d i f n o d en o d e = n e wn o d e o ；仓, j 建以当前字符开始的k 子串。 k n o d e a r r a y k - 1 = n o d e ；把当前新建的k 子串加入进去。 e n d f o r 伪代码3 - 3 优化的创建方法只需要循环子串s 一遍，从而只需要n 时间，与简单的创建 方法n + n * k 得到了很大的改善。由于创建方法把提取k 子串和使用k 子串建树 合并成一个过程，从而省却了k 子串的保存数组，虽然增加了保存与当前字符s 相关的k 个节点，算法循环过程需要的空间为k + 1 ，所以优化的创建算法需要 k + i 的空| 日j 。优化的k 前缀树创建方法的空间复杂度和时间复杂度为o ( 1 ) 和 o ( n ) ，相对简单的创建方法时间复杂度得到了较大的改善。 3 3 搜索 k 前缀耐同前缀树和后缀树相同，方法提出来就是为了进行快速的文本数据 搜索。前缀树只能针对特定的关键字搜索，后缀树能够进行全文搜索，两者针对 特定的长度为m 的搜索字串p ，都能够在o ( m ) 时间内搜索完毕。k - 前缀树基于 1 4 第三章k 前缀树全文搜索方法 广一 暑c睾罗 彳$ 亨蛋警手? x oo 1 5 k - 前缀树全文搜索方法及其应用 3 4 方法特点 k 前缀树基于前缀树和后缀树的思想，底层数据结构采用前缀树，基本具有 前缀树和后缀树的优点，并在一定程度上避免了前缀树和后缀树的缺陷。k 前缀 树方法具体具有以下优点： 1 ) 快速的搜索数据。k - 前缀树底层采用前缀树的结构，所以具有了前缀树 能够在o ( m ) 时间复杂度内完成对长度为m 的p 字串的搜素。 2 ) 能够进行全文检索。k - 前缀树不像前缀树只是采用特定的关键字构建树， 而是像后缀树一样采用字串的全部文本进行建树，所以k 前缀树能够进行全文 检索，这对于如今多变的世界，往往是必须的。 3 ) 相同的关键字只保存一次，从而更省空间。k - 前缀树同前缀树一样对于 一样的k 子串只保存一次，并且对于不同的