数据结构与算法(Java描述)


数据结构与算法(Java 描述) 邓俊辉 著 机械工业出版社 目录 i / xii 目录 目录 ____________________________________________________________________________________________________ i 前言 ___________________________________________________________________________________________________ x 第一章 算法及其复杂度 1 §1.1 计算机与算法 _____________________________________________________________________________________ 2 1.1.1 过指定垂足的直角边....................................................................................................................................................2 1.1.2 三等分线段 .....................................................................................................................................................................3 1.1.3 排序...................................................................................................................................................................................4 1.1.4 算法的定义 .....................................................................................................................................................................7 §1.2 算法性能的分析与评价_____________________________________________________________________________ 8 1.2.1 三个层次..........................................................................................................................................................................8 1.2.2 时间复杂度及其度量....................................................................................................................................................8 1.2.3 空间复杂度 ...................................................................................................................................................................10 §1.3 算法复杂度及其分析 ______________________________________________________________________________ 11 1.3.1 O(1)⎯⎯取非极端元素................................................................................................................................................11 1.3.2 O(logn)⎯⎯进制转换....................................................................................................................................................11 1.3.3 O(n)⎯⎯数组求和.........................................................................................................................................................12 1.3.4 O(n2)⎯⎯起泡排序........................................................................................................................................................13 1.3.5 O(2r)⎯⎯幂函数 ............................................................................................................................................................13 §1.4 计算模型 _________________________________________________________________________________________ 14 1.4.1 可解性............................................................................................................................................................................14 1.4.2 有效可解........................................................................................................................................................................14 1.4.3 下界.................................................................................................................................................................................15 §1.5 递归 _____________________________________________________________________________________________ 15 1.5.1 线性递归........................................................................................................................................................................16 1.5.2 递归算法的复杂度分析 .............................................................................................................................................20 1.5.3 二分递归........................................................................................................................................................................21 1.5.4 多分支递归 ...................................................................................................................................................................24 第二章 栈与队列 27 §2.1 栈________________________________________________________________________________________________ 28 2.1.1 栈ADT..............................................................................................................................................................................29 目录 ii / xii 2.1.2 基于数组的简单实现..................................................................................................................................................31 2.1.3 Java虚拟机中的栈 ........................................................................................................................................................35 2.1.4 栈应用实例 ...................................................................................................................................................................37 §2.2 队列 _____________________________________________________________________________________________ 41 2.2.1 队列ADT .........................................................................................................................................................................42 2.2.2 基于数组的实现 ..........................................................................................................................................................44 2.2.3 队列应用实例...............................................................................................................................................................47 §2.3 链表 _____________________________________________________________________________________________ 48 2.3.1 单链表............................................................................................................................................................................48 2.3.2 基于单链表实现栈......................................................................................................................................................52 2.3.3 基于单链表实现队列..................................................................................................................................................54 §2.4 位置 _____________________________________________________________________________________________ 56 2.4.1 位置ADT .........................................................................................................................................................................56 2.4.2 位置ADT接口 ................................................................................................................................................................56 §2.5 双端队列 _________________________________________________________________________________________ 57 2.5.1 双端队列的ADT............................................................................................................................................................57 2.5.2 双端队列的接口 ..........................................................................................................................................................58 2.5.3 双向链表........................................................................................................................................................................59 2.5.4 基于双向链表实现的双端队列................................................................................................................................60 第三章 向量、列表与序列 67 §3.1 向量与数组_______________________________________________________________________________________ 68 3.1.1 向量ADT .........................................................................................................................................................................68 3.1.2 基于数组的简单实现..................................................................................................................................................71 3.1.3 基于可扩充数组的实现 .............................................................................................................................................73 3.1.4 java.util.ArrayList类和java.util.Vector类 ..........................................................................................................................77 §3.2 列表 _____________________________________________________________________________________________ 78 3.2.1 基于节点的操作 ..........................................................................................................................................................78 3.2.2 由秩到位置 ...................................................................................................................................................................78 3.2.3 列表ADT .........................................................................................................................................................................79 3.2.4 基于双向链表实现的列表.........................................................................................................................................83 §3.3 序列 _____________________________________________________________________________________________ 90 3.3.1 序列ADT .........................................................................................................................................................................90 3.3.2 基于双向链表实现序列 .............................................................................................................................................91 3.3.3 基于数组实现序列......................................................................................................................................................93 §3.4 迭代器 ___________________________________________________________________________________________ 93 3.4.1 简单迭代器的ADT........................................................................................................................................................94 目录 iii / xii 3.4.2 迭代器接口 ...................................................................................................................................................................95 3.4.3 迭代器的实现...............................................................................................................................................................96 3.4.4 Java中的列表及迭代器................................................................................................................................................98 第四章 树 101 §4.1 术语及性质______________________________________________________________________________________ 102 4.1.1 节点的深度、树的深度与高度..............................................................................................................................103 4.1.2 度、内部节点与外部节点.......................................................................................................................................104 4.1.3 路径...............................................................................................................................................................................104 4.1.4 祖先、后代、子树和节点的高度..........................................................................................................................105 4.1.5 共同祖先及最低共同祖先.......................................................................................................................................106 4.1.6 有序树、m叉树..........................................................................................................................................................106 4.1.7 二叉树..........................................................................................................................................................................106 4.1.8 满二叉树与完全二叉树 ...........................................................................................................................................107 §4.2 树抽象数据类型及其实现 ________________________________________________________________________ 109 4.2.1 父亲-长子-弟弟”模型 .............................................................................................................................................109 4.2.2 树ADT............................................................................................................................................................................110 4.2.3 树的Java接口..............................................................................................................................................................111 4.2.4 基于链表实现树 ........................................................................................................................................................111 §4.3 树的基本算法 ___________________________________________________________________________________ 113 4.3.1 getSize()⎯⎯统计(子)树的规模..........................................................................................................................113 4.3.2 getHeight()⎯⎯计算节点的高度...............................................................................................................................114 4.3.3 getDepth()⎯⎯计算节点的深度................................................................................................................................114 4.3.4 前序、后序遍历 ........................................................................................................................................................114 4.3.5 层次遍历......................................................................................................................................................................116 4.3.6 树迭代器......................................................................................................................................................................117 §4.4 二叉树抽象数据类型及其实现 ____________________________________________________________________ 119 4.4.1 二叉树ADT...................................................................................................................................................................119 4.4.2 二叉树类的Java接口.................................................................................................................................................120 4.4.3 二叉树类的实现 ........................................................................................................................................................123 §4.5 二叉树的基本算法 _______________________________________________________________________________ 131 4.5.1 getSize()、getHeight()和getDepth() ..............................................................................................................................131 4.5.2 updateSize() ....................................................................................................................................................................131 4.5.3 updateHeight().................................................................................................................................................................132 4.5.4 updateDepth() .................................................................................................................................................................132 4.5.5 secede()...........................................................................................................................................................................133 4.5.6 attachL()和attachR().......................................................................................................................................................134 4.5.7 二叉树的遍历.............................................................................................................................................................135 4.5.8 直接前驱、直接后继的定位算法..........................................................................................................................136 目录 iv / xii §4.6 完全二叉树的Java实现 ___________________________________________________________________________ 137 4.6.1 完全二叉树类的Java接口........................................................................................................................................137 4.6.2 基于向量的实现 ........................................................................................................................................................138 第五章 优先队列 143 §5.1 优先级、关键码、全序关系与优先队列 ___________________________________________________________ 144 §5.2 条目与比较器 ___________________________________________________________________________________ 145 5.2.1 条目...............................................................................................................................................................................145 5.2.2 比较器..........................................................................................................................................................................147 5.2.3 Comparator接口及其实现...........................................................................................................................................147 §5.3 优先队列ADT及Java接口 __________________________________________________________________________ 149 5.3.1 ADT描述.........................................................................................................................................................................149 5.3.2 Java接口........................................................................................................................................................................150 5.3.3 基于优先队列的排序器 ...........................................................................................................................................151 §5.4 用向量实现优先队列 _____________________________________________________________________________ 152 §5.5 用列表实现优先队列 _____________________________________________________________________________ 153 5.5.1 基于无序列表的实现及分析 ..................................................................................................................................153 5.5.2 基于有序列表的实现及分析 ..................................................................................................................................155 §5.6 选择排序与插入排序 _____________________________________________________________________________ 157 5.6.1 选择排序......................................................................................................................................................................157 5.6.2 插入排序......................................................................................................................................................................157 5.6.3 效率比较......................................................................................................................................................................158 §5.7 堆的定义及性质 _________________________________________________________________________________ 158 5.7.1 堆结构..........................................................................................................................................................................159 5.7.2 完全性..........................................................................................................................................................................160 §5.8 用堆实现优先队列 _______________________________________________________________________________ 160 5.8.1 基于堆的优先队列及其实现 ..................................................................................................................................160 5.8.2 插入与上滤 .................................................................................................................................................................163 5.8.3 删除与下滤 .................................................................................................................................................................166 5.8.4 改变任意节点的关键码 ...........................................................................................................................................168 5.8.5 建堆...............................................................................................................................................................................168 §5.9 堆排序 __________________________________________________________________________________________ 170 5.9.1 直接堆排序 .................................................................................................................................................................170 5.9.2 就地堆排序 .................................................................................................................................................................171 §5.10 Huffman树 _______________________________________________________________________________________ 173 5.10.1 二叉编码树 ...............................................................................................................................................................173 目录 v / xii 5.10.2 最优编码树 ...............................................................................................................................................................174 5.10.3 Huffman编码与Huffman编码树.................................................................................................................................176 5.10.4 Huffman编码树的构造算法......................................................................................................................................180 5.10.5 基于优先队列的Huffman树构造算法...................................................................................................................182 第六章 映射与词典 183 §6.1 映射 ____________________________________________________________________________________________ 184 6.1.1 映射的ADT描述..........................................................................................................................................................185 6.1.2 映射的Java接口..........................................................................................................................................................186 6.1.3 判等器..........................................................................................................................................................................187 6.1.4 java.util包中的映射类..................................................................................................................................................188 6.1.5 基于列表实现映射类................................................................................................................................................189 §6.2 散列表 __________________________________________________________________________________________ 191 6.2.1 桶及桶数组 .................................................................................................................................................................191 6.2.2 散列函数......................................................................................................................................................................191 6.2.3 散列码..........................................................................................................................................................................192 6.2.4 压缩函数......................................................................................................................................................................194 6.2.5 冲突的普遍性⎯⎯生日悖论 ..................................................................................................................................194 6.2.6 解决冲突......................................................................................................................................................................195 6.2.7 基于散列表实现映射类 ...........................................................................................................................................199 6.2.8 装填因子与重散列....................................................................................................................................................202 §6.3 无序词典 ________________________________________________________________________________________ 203 6.3.1 无序词典的ADT描述 .................................................................................................................................................203 6.3.2 无序词典的Java接口.................................................................................................................................................204 6.3.3 列表式无序词典及其实现.......................................................................................................................................205 6.3.4 散列表式无序词典及其实现 ..................................................................................................................................208 §6.4 有序词典 ________________________________________________________________________________________ 211 6.4.1 全序关系与有序查找表 ...........................................................................................................................................211 6.4.2 二分查找......................................................................................................................................................................211 6.4.3 有序词典的ADT描述 .................................................................................................................................................213 6.4.4 有序词典的Java接口.................................................................................................................................................213 6.4.5 基于有序查找表实现有序词典..............................................................................................................................214 第七章 查找树 219 §7.1 二分查找树______________________________________________________________________________________ 221 7.1.1 定义...............................................................................................................................................................................221 7.1.2 查找算法......................................................................................................................................................................222 7.1.3 完全查找算法.............................................................................................................................................................225 目录 vi / xii 7.1.4 插入算法......................................................................................................................................................................226 7.1.5 删除算法......................................................................................................................................................................229 7.1.6 二分查找树节点类的实现.......................................................................................................................................231 7.1.7 二分查找树类的实现................................................................................................................................................232 7.1.8 二分查找树的平均性能 ...........................................................................................................................................235 §7.2 AVL树 ____________________________________________________________________________________________ 236 7.2.1 平衡二分查找树 ........................................................................................................................................................236 7.2.2 等价二分查找树 ........................................................................................................................................................237 7.2.3 等价变换......................................................................................................................................................................237 7.2.4 AVL树 .............................................................................................................................................................................239 7.2.5 插入节点后的重平衡................................................................................................................................................240 7.2.6 节点删除后的重平衡................................................................................................................................................245 7.2.7 AVL树的Java实现.........................................................................................................................................................250 §7.3 伸展树 __________________________________________________________________________________________ 253 7.3.1 数据局部性 .................................................................................................................................................................253 7.3.2 逐层伸展......................................................................................................................................................................254 7.3.3 双层伸展......................................................................................................................................................................256 7.3.4 分摊复杂度 .................................................................................................................................................................258 7.3.5 伸展树的Java实现 .....................................................................................................................................................260 7.3.6 插入...............................................................................................................................................................................264 7.3.7 删除...............................................................................................................................................................................265 §7.4 B-树 _____________________________________________________________________________________________ 267 7.4.1 分级存储......................................................................................................................................................................267 7.4.2 B-树的定义 ...................................................................................................................................................................268 7.4.3 关键码的查找.............................................................................................................................................................268 7.4.4 性能分析......................................................................................................................................................................270 7.4.5 上溢节点的处理 ........................................................................................................................................................271 7.4.6 关键码的插入.............................................................................................................................................................272 7.4.7 下溢节点的处理 ........................................................................................................................................................276 7.4.8 关键码的删除.............................................................................................................................................................277 第八章 排序 279 §8.1 归并排序 ________________________________________________________________________________________ 280 8.1.1 分治策略......................................................................................................................................................................280 8.1.2 时间复杂度 .................................................................................................................................................................281 8.1.3 归并算法......................................................................................................................................................................282 8.1.4 Mergesort的Java实现 ...................................................................................................................................................284 §8.2 快速排序 ________________________________________________________________________________________ 285 目录 vii / xii 8.2.1 分治策略......................................................................................................................................................................285 8.2.2 轴点...............................................................................................................................................................................285 8.2.3 划分算法......................................................................................................................................................................286 8.2.4 Quicksort的Java实现 ....................................................................................................................................................287 8.2.5 时间复杂度 .................................................................................................................................................................288 §8.3 复杂度下界______________________________________________________________________________________ 290 8.3.1 比较树与基于比较的算法.......................................................................................................................................290 8.3.2 下界...............................................................................................................................................................................291 第九章 串 293 §9.1 串及其ADT ______________________________________________________________________________________ 294 §9.2 串模式匹配______________________________________________________________________________________ 296 9.2.1 概念与记号 .................................................................................................................................................................296 9.2.2 问题...............................................................................................................................................................................297 9.2.3 算法效率的测试与评价 ...........................................................................................................................................298 §9.3 蛮力算法 ________________________________________________________________________________________ 298 9.3.1 算法描述......................................................................................................................................................................298 9.3.2 算法实现......................................................................................................................................................................299 9.3.3 算法分析......................................................................................................................................................................300 §9.4 Knuth-Morris-Pratt算法 ______________________________________________________________________________ 301 9.4.1 蛮力算法的改进 ........................................................................................................................................................301 9.4.2 next[]表的定义及含义.................................................................................................................................................302 9.4.3 KMP算法描述...............................................................................................................................................................303 9.4.4 next[]表的特殊情况 .....................................................................................................................................................303 9.4.5 next[]表的构造..............................................................................................................................................................304 9.4.6 next[]表的改进..............................................................................................................................................................304 9.4.7 KMP算法的Java实现...................................................................................................................................................306 9.4.8 性能分析......................................................................................................................................................................308 §9.5 BM算法 __________________________________________________________________________________________ 309 9.5.1 坏字符策略 .................................................................................................................................................................310 9.5.2 好后缀策略 .................................................................................................................................................................312 9.5.3 BM算法 ..........................................................................................................................................................................313 9.5.4 BM算法的Java实现 .....................................................................................................................................................314 9.5.5 性能...............................................................................................................................................................................318 第十章 图 321 §10.1 概述 ___________________________________________________________________________________________ 322 目录 viii / xii 10.1.1 无向图、混合图及有向图.....................................................................................................................................322 10.1.2 度.................................................................................................................................................................................323 10.1.3 简单图........................................................................................................................................................................323 10.1.4 图的复杂度 ...............................................................................................................................................................324 10.1.5 子图、生成子图与限制子图 ................................................................................................................................325 10.1.6 通路、环路及可达分量 .........................................................................................................................................325 10.1.7 连通性、等价类与连通分量 ................................................................................................................................326 10.1.8 森林、树以及无向图的生成树............................................................................................................................327 10.1.9 有向图的生成树 ......................................................................................................................................................328 10.1.10 带权网络..................................................................................................................................................................329 §10.2 抽象数据类型 __________________________________________________________________________________ 330 10.2.1 图.................................................................................................................................................................................330 10.2.2 顶点.............................................................................................................................................................................331 10.2.3 边.................................................................................................................................................................................333 §10.3 邻接矩阵 _______________________________________________________________________________________ 334 10.3.1 表示方法....................................................................................................................................................................334 10.3.2 时间性能....................................................................................................................................................................335 10.3.3 空间性能....................................................................................................................................................................336 §10.4 邻接表 _________________________________________________________________________________________ 337 10.4.1 顶点表和边表...........................................................................................................................................................337 10.4.2 顶点与邻接边表 ......................................................................................................................................................338 10.4.3 边.................................................................................................................................................................................340 10.4.4 基于邻接表实现图结构 .........................................................................................................................................343 §10.5 图遍历及其算法模板 ____________________________________________________________________________ 346 §10.6 深度优先遍历 __________________________________________________________________________________ 348 10.6.1 深度优先遍历算法..................................................................................................................................................348 10.6.2 边分类........................................................................................................................................................................349 10.6.3 可达分量与DFS树....................................................................................................................................................350 10.6.4 深度优先遍历算法模板 .........................................................................................................................................352 10.6.5 可达分量算法...........................................................................................................................................................354 10.6.6 单强连通分量算法..................................................................................................................................................355 10.6.7 强连通分量分解算法..............................................................................................................................................356 10.6.8 浓缩图与弱连通性..................................................................................................................................................356 §10.7 广度优先遍历 __________________________________________________________________________________ 358 10.7.1 广度优先遍历算法..................................................................................................................................................358 10.7.2 边分类........................................................................................................................................................................359 10.7.3 可达分量与BFS树....................................................................................................................................................359 10.7.4 广度优先遍历算法模板 .........................................................................................................................................360 目录 ix / xii 10.7.5 最短距离算法...........................................................................................................................................................361 §10.8 最佳优先遍历 __________________________________________________________________________________ 363 10.8.1 最佳优先遍历算法..................................................................................................................................................363 10.8.2 最佳优先遍历算法模板 .........................................................................................................................................364 10.8.3 最短路径....................................................................................................................................................................366 10.8.4 最短路径序列...........................................................................................................................................................368 10.8.5 Dijkstra算法..................................................................................................................................................................371 10.8.6 最小生成树 ...............................................................................................................................................................374 10.8.7 Prim-Jarnik算法 ...........................................................................................................................................................376 附录 i DSA类关系图___________________________________________________________________________________________ ii 插图索引_______________________________________________________________________________________________ v 表格索引_______________________________________________________________________________________________ ix 算法索引_______________________________________________________________________________________________ xi 代码索引______________________________________________________________________________________________ xiii 定义索引______________________________________________________________________________________________ xvi 观察结论索引 _________________________________________________________________________________________ xix 推论索引______________________________________________________________________________________________xxii 引理索引_____________________________________________________________________________________________ xxiii 定理索引_____________________________________________________________________________________________ xxiv 关键词索引 __________________________________________________________________________________________xxvii 前言 x / xi 前言 关于计算机教育规范,最有权威、影响最大的莫过于 ACM 与 IEEE-CS 联合制订的 Computing Curricula。比如,Computing Curricula 1991(CC1991)就曾对我国高校的计算机教育产生深刻的 影响。 正在制订中的 CC2001(后改称 CC2004)认为,随着近年来计算概念的快速发展,计算学 科已经发展成为一个内涵繁杂的综合性学科,至少可以划分为计算机工程(CE)、计算机科学(CS)、 信息系统(IS)、信息技术(IT)和软件工程(SE)等五个领域,而且不同领域的人才所应具备的知 识结构与能力侧重也不尽相同。尽管如此,从目前已经完成的部分来看,数据结构与算法在各领域 的知识体系中仍然占据着重要的位置。比如在 CE 分卷(草案)中,Programming Fundamentals 共 39 个核心学时,其中 Algorithms and Problem Solving 占 8 个学时,Data Structures 占 13 个学 时;在 CS 分卷(正式稿)中,Programming Fundamentals 共 38 个核心学时,其中 Algorithms and Problem Solving 占 6 个学时,Data Structures 占 14 个学时。 为什么长期以来,数据结构与算法会一直受到如此重视?数据结构和算法是一对孪生兄弟,数 据结构研究的问题包括数据在计算机中存储、组织、传递和转换的过程及方法,这些也是构成与支 撑算法的基础。我们在编写计算机程序来解决应用问题时,最终都要归结并落实到这两个问题上。 正因为此,N. Wirth 早在 70 年代就曾指出“程序 = 数据结构 + 算法”。近年来,随着面向对象技 术的广泛应用,从数据结构的定义、分类、组成,到设计、实现与分析的模式与方法都有了长足的 发展,现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、简洁性和安全性。为遵 循上述原则,本书选择 Java 作为描述语言,因为相对于其它语言,Java 语言比较完整、彻底地体 现了面向对象的设计思想,这也是目前国际上同行们的一个主要取向。不过,关于 Java 语言本身的 介绍与交待,本书并未花费多少笔墨,而是直接假定读者已经熟练掌握了该语言。这既能缩减本书 篇幅,也符合此领域教学今后的规范。比如,CC2001 的 CS 分卷将 Data Structures and Algorithms 课程编号为 CS103 ,并明确指出该课程是 Programming Fundamentals (CS101) 和 The Object-Oriented Paradigm (CS102)的后续课程。 在内容选取、剪裁与体例结构上,作者力图突破现成的模式。这里并未对各种数据结构面面俱 到,而是通过分类和讲解典型结构,力图使读者形成对数据结构的宏观认识;结合各部分的具体内 容,书中都穿插了大量的问题,把更多的思考空间留给读者。 本书可以作为计算机专业本科生的教材,对于辅修计算机专业的学生,也有一定的参考价值。 根据内容侧重,本书分为以下具体部分。 第一章是全书的基础,重点在于介绍算法与数据结构的关系,以及算法时间、空间复杂度的概 念及其度量方法。 第二至四章覆盖了基本的数据结构,既有传统的栈与队列,也有更为抽象和通用的向量和列表。 面向对象技术在现代数据结构理论中的重要地位在此得到体现,我们利用接口实现数据结构的封装, 抽象出位置的概念,在向量和列表的基础上定义并实现序列结构,引入迭代器概念并针对上述结构 具体实现。通过结合数组与链表结构的优点,第四章自然地导出了树结构的概念、实现及算法。 前言 xi / xi 第五、六和七章介绍了若干高级数据结构。通过在一般性队列中引入优先级概念,导出了优先 队列结构;面向实际问题中的查找需求,导出了映射和词典结构;针对全序集的查找问题,引入了 查找数结构,并结合 AVL 树、伸展树和 B-树的实例介绍了平衡查找树结构的原理及其实现。面向对 象的思想在这里继续得到贯彻,普遍采用了抽象、封装及继承等技术。 这一部分的侧重点逐渐转向算法,并结合具体问题介绍其应用与实现,包括堆结构的生成及调 整算法、Huffman 编码树算法、散列算法以及二路或多路平衡查找树的生成、插入、删除算法。在 这三章中,读者也将对算法复杂度的各种分析方法有所了解。 第八、九和十章的论述重点完全转向算法。第八章对此前各章中陆续介绍过的排序算法作了归 纳与分类,着重介绍了归并排序算法与快速排序算法,并给出了此类算法的复杂度下界。结合串结 构的应用,第九章着重讨论了串匹配问题,从蛮力算法出发,采用不同的启发式加速策略,分别介 绍了 KMP 算法及 BM 算法。 关于图结构,第十章将重点放在相关算法上,并力图使初学者从各种图算法中梳理出清晰的脉 络。为此,这里尝试通过一条主线⎯⎯遍历⎯⎯将各种算法串接起来。在这里,面向对象技术的魅 力再次得以展现:基于统一的图遍历算法模版,分别实现了深度优先、广度优先和最佳优先三大类 遍历算法。实际上,这三类算法本身仍然以模版形式实现,包括边分类、可达分量、连通分量、最 短路径以及最小生成树在内的各种具体算法,都进而基于这三个模版分别得到了实现。 书中涉及的所有代码,都符合 J2SDK-1.4.1 规范,并构成一个名为 dsa(Data Structures & Algorithms)的包;所有类之间的扩展、继承关系,都在书后的“DSA 类关系图”部分统一介绍。 为获取本书中的代码及相关教学资料,欢迎访问:http://vis.cs.tsinghua.edu.cn/~deng/dsaj.htm。 从本书的筹划、撰写、审订到定稿发行,其间跨越三个年头,在此漫长的过程中,我的父母和 妻子给了我巨大的支持,就这个意义而言,他们也是本书的完成者。年幼的女儿总是以她独有的方 式,不时将我从写作和调试的苦海中解救出来,她让我体会了禁用 PowerOff 按钮的妙用(尽管除了 拔除接头外我还没有找到更好的办法,使得在她恶作剧地按下 Reset 按钮后依然能够继续写作)。我 的确需要感谢她,她让我养成了及时备份的良好习惯,更使我意识到在离开电脑后自己依然能够而 且更好地思考。 经过在清华大学的多年执教,我日益深刻地体会到教育的伟大和神圣,是我的同事、我的学生 使我懂得了如何忘却劳动的艰辛,并从教育的过程中获得乐趣。 我还要特别感谢机械工业出版社的温莉芳女士,在我一次次地推迟交稿时,她表现出的耐心与 理解都令我既钦佩又惭愧,正是这非凡的宽容激励着我不断追求完美。 虽反复斟酌,在本书即将出版之际,内心依然惶恐。“丑媳妇终要见公婆”,恳请读者批评指正。 邓俊辉 2005 年仲夏初笔 2005 年岁末定稿 第一章 算法及其复杂度 第二章 栈与队列 第三章 向量、列表与序列 第四章 树 第五章 优先队列 第六章 映射与词典 第七章 查找树 第八章 排序 第九章 串 第九章 串 §9.1 串及其 ADT 296 计算机已经成为我们日常学习、办公不可或缺的工具,反过来,为了提高学习和工作的效率, 对计算机信息处理能力的要求也越来越高,其中文本处理的能力就是极其重要的一个方面。今天, 越来越多的文档、资料开始以数字化的形式出现,互联网所提供的信息总量也在以惊人的速度膨胀, 因此在文本处理方面,目前的一个突出问题就是如何高效地处理海量的文本数据,而串(String)则 是最常见的一种文本形式。 相对于此前介绍的数据结构,串中各元素的内容相对简单,分别称作一个字符。所有字符排成 一个线性结构,它们都来自于某个集合,称作字符表。字符表的规模往往不大,以最常见的 ASCII 字符表为例,只有 128 个元素。然而,就其规模而言,串结构一般都远远超过其它结构,故我们也 把串的规模称作其“长度”。因此,串中字符的重复率一般非常高。串作为一种数据结构的存在意义 与价值,正体现在这一结构的这些特点。 鉴于串结构的特点,本章虽然也会提及该结构的 ADT 描述,但不再对其实现进行讨论,而是直 接利用 Java 本身提供的 String 类。本章的重点,将放在串匹配算法上面。 §9.1 串及其 ADT „ 串 我们今天所面对的文本数据,大多是以串的形式出现。串是由有限个字符组成的一种线性结构, 其中每个字符都来自某个字符表(Alphabet)Σ,比如 ASCII 字符集或 Unicode 字符集。 „ ADT 串 ADT 的主要操作可以归纳为如下: 表九.1 串ADT支持的操作 操作方法 功能描述 length(): 查询串的长度 输入:无 输出:非负整数 charAt(i): 返回第 i 个字符 输入:一个非负整数 输出:一个字符 substr(i, k): 返回从第 i 个字符起、长度为 k 的子串 输入:两个非负整数 输出:一个字符串 prefix(k): 返回长度为 k 的前缀 输入:一个非负整数 输出:一个字符串 第九章 串 §9.1 串及其 ADT 297 操作方法 功能描述 suffix(k): 返回长度为 k 的后缀 输入:一个非负整数 输出:一个字符串 equals(T): 判断 T 是否与当前字符串相等 输入:一个字符串 输出:一个布尔标志 concat(T): 将 T 串接在当前字符串之后 输入:一个字符串 输出:一个字符串 indexOf(P): 若 P 是当前字符串的一个子串,则返回该子串的起始位置;否则返回-1 输入:一个字符串 输出:一个非负整数 比如,从串 S = "data structures"开始,依次执行如下操作,相应的结果如所示: 表九.2 串操作实例 操作 输出 字符串 S length() 15 "data structures" charAt(5) 's' "data structures" prefix(4) "data" "data structures" suffix(10) "structures" "data structures" concat("and algorithms") "data structures and algorithms" "data structures and algorithms" equals("data structures") false "data structures and algorithms" equals("data structures and algorithms") true "data structures and algorithms" indexOf("string") -1 "data structures and algorithms" indexOf("algorithm") 20 "data structures and algorithms" „ 特点 串具有两个突出的特点:结构简单,规模庞大。所谓结构简单,是指字符表规模不大,在某些 应用问题中,字符表的规模甚至可能极小。以生物信息序列为例,组成蛋白质(文本)的氨基酸(字 符)只有约 20 种,而组成DNA序列(文本)的碱基(字符)则只有 4 种。既然文本串也是线性结 构,当然可以直接利用 第三章所介绍的向量或列表等序列结构来实现,因此就数据结构本身而言, 串没有太多问题需要讨论。这里我们将直接采用Java本身提供的String类。 然而,这类文本的规模往往很大,其中每个字符都大量重复地出现。在处理这样的数据时,时 间效率就成为了一个特出的问题,需要仔细研究。本章将集中讨论 indexOf()方法的高效算法。 第九章 串 §9.2 串模式匹配 298 §9.2 串模式匹配 9.2.1 概念与记号 在展开后续的讨论之前,有必要对与串相关的若干概念与记号做一介绍。一般地, 定义九.1 由 n 个字符构成的串记作 S = "a0 a1 … an-1",其中 ai ∈Σ。这里的Σ是所有可用字符的集 合,称作字母表(Alphabet)。 比如,对于通常的文本处理,Σ就是 ASCII 字符集或者 Unicode 字符集。又如,在生物信息学 中,Σ则可能是所有的碱基(DNA 序列),或者所有的氨基酸(蛋白质序列)。再如,若串是以二进 制文件形式给出的,则字母表Σ={0, 1}。 定义九.2 n 称为 S 的长度,记作|S| = n。 我们只考虑长度有限的串,即 n < ∞。特别地, 定义九.3 长度为零的串称为空串(Null string)。 在对串进行处理时,经常需要取出其中连续的某一片段。 定义九.4 所谓 S 的子串( Sub-string),就是起始于任一位置 i 的连续 k 个字符,记作 substr(S, i, k) = "ai ai+1 ... ai+k-1",0 ≤ i < n,0 ≤ k。 有两种特殊的子串。 定义九.5 起始于位置 0、长度为 k 的子串称为前缀(Prefix),记作 prefix(S, k) = substr(S, 0, k)。 定义九.6 终止于位置 n-1、长度为 k 的子串称为后缀( suffix),记作 suffix(S, k) = substr(S, n-k, k)。 根据上述定义,可以得出以下结论: 观察结论九.1 空串是任何串的子串,也是任何串的前缀、后缀。 观察结论九.2 任何串都是自己的子串,也是自己的前缀、后缀。 因此,空串与串本身都需要特殊指称: 定义九.7 空串以及串本身亦称作平凡子串(前缀、后缀)。 定义九.8 空串以及非平凡子串(前缀、后缀)称作真子串(前缀、后缀)。 最后,我们给出两个串相等的条件: 定义九.9 串 S = "a0 a1 a2 ... an-1"和 T = "b0 b1 b2 ... bm-1"称作相等,当且仅当二者长度相等,且对应 的字符分别相同,即 n = m 且对任何 0 ≤ i < n 都有 ai = bi。 第九章 串 §9.2 串模式匹配 299 9.2.2 问题 „ 应用与定义 在串文本的众多应用问题中,会反复涉及到一项非常基本的判断性操作:给定串 T(称作主串) 和串 P(称作模式串),T 中是否存在的某个子串与 P 相同?如果存在,找到该子串在 T 中的起始位 置。 比如,Unix Shell中的命令grep和DOS中的命令find,功能与此类似 ㈠。又如在生物信息的处理 过程中,也经常需要在蛋白质序列中寻找特定的氨基酸模式,或者在DNA序列中寻找特定的碱基模 式。再如,邮件过滤器会扫描电子邮件的地址、标题及正文,并根据事先定义的特征串判定是否为 垃圾邮件。还有,反病毒系统也会对下载的或将要执行的程序进行扫描,根据事先提炼出的特征串 判定是否含有病毒。 这类操作,都属于串模式匹配(String pattern matching)的范畴,简称串匹配。比如,若主串 和模式串分别是 T = "Now is the time for all good people to come" P = "people" 则匹配的位置应该是 29。 记主串 T 的长度为|T| = n,记模式串的长度|P| = m。通常,m 和 n 都是很大的整数,而且相对 来说 n 更大,即满足 2 ≪ m ≪ n。比如,n = 100,000,m = 100。 „ 分类 实际上,根据具体应用的不同,串匹配问题有多种形式。有些场合属于串匹配检测(Pattern detection)问题:我们只关心是否存在匹配,而不关心具体的匹配位置。有些场合则属于定位(Pattern location)问题:若经判断的确存在匹配,则还需要确定具体的匹配位置。有些场合属于计数(Pattern counting)问题:倘若有多处匹配,统计出这些匹配子串的总数。有些场合则属于枚举(Pattern enumeration)问题:在有多处匹配时,报告出所有匹配的具体位置。 比如,以上邮件过滤器的例子就属于检测型问题:一旦特征匹配,即可判定为垃圾邮件,从而 直接删除,或者将其隔离以待用户确认,此时我们并不关心特征串的具体位置。然而,反病毒系统 的任务则属于枚举型问题:不仅必须在二进制代码中找出所有的病毒特征串,还需要报告它们的具 体位置,以便修复。 ㈠ 这两个命令的格式分别是: % grep c:\> find "pattern" 可见,二者都是通过文件形式来指定待查找的主串。 第九章 串 §9.3 蛮力算法 300 9.2.3 算法效率的测试与评价 串匹配是一个经典的问题,有名字的算法不下三十余种。由于串结构自身的特点,在设计和分 析此类算法时也需做特殊的考虑,其中首先需要回答的一个问题就是:如何评估某一串匹配算法的 性能? 多数读者首先会想到,能否采用通常评估算法性能的策略,假设主串 T 和模式串 P 都是随机生 成的,然后分析它们的各种组合所需的时间呢?很遗憾,答案是否定的。 以基于字母表Σ={0, 1}的二进制串为例。在长度为 n 的主串中,长度为 m 的子串的数目为 n-m+1,当 m ≪ n时,这个数目将接近于 n;另一方面,长度为 m 的二进制串数目为 2m。因此, 如果模式串也是随机选取的,则匹配成功的概率为 n/2m。以 n = 100,000、m = 100 为例,这一概率 只有 100,000/2100 < 10-25。对于更长的模式串、更大的字母表,这一概率还将更低。因此,这一策 略无法对算法的性能作出客观的评价。 可行的一种策略是,随机选取主串 T,但仅仅测试那些匹配成功的情况。为此,可以从 T 中随 机取出长度为 m 的子串作为 P。这也是本书将采用的评价标准。 §9.3 蛮力算法 9.3.1 算法描述 蛮力串匹配算法是最直接、直观的方法。我们想象着将主串和模式串分别写在两条印有等间距 方格的纸带上,主串对应的纸带固定,模式串的首字符与主串的首字符对齐,沿水平方向放好。如 图九.1 所示,主串的前m个字符将与模式串的m个字符两两对齐。接下来,自左向右检查对齐的每 一对字符:如果匹配,则转向下一对字符;如果失配,则说明在这个位置主串与模式串无法匹配, 于是将模式串对应的纸带右移一个字符,然后从首字符开始重新对比。若经过检查,当前的m个字 符对都是匹配的,则匹配成功,并返回匹配子串的位置。 第九章 串 §9.3 蛮力算法 301 图九.1 串模式匹配:蛮力算法 模式串中,黑色方格为经检查与主串匹配的字符,灰色方格为失配的字符,白色 方格为无需检查的字符 9.3.2 算法实现 代码九.1 给出了蛮力算法的具体实现。 /* * 串模式匹配:蛮力算法 * 若返回位置i > length(T) - length(P),则说明失配 * 否则,i为匹配位置 */ import dsa.*; import java.io.*; public class PM_BruteForce { ////////////////////////////////////////////////////////////////////////// // T: 0 1 . . . i i+1 . . . i+j . . n-1 // --------------------|-------------------|------------ // P: 0 1 . . . j . . // |-------------------| ////////////////////////////////////////////////////////////////////////// public static int PM(String T, String P) { int i;//模式串相对于主串的起始位置 int j;//模式串当前字符的地址 for (i=0; i <= T.length()-P.length(); i++) {//主串从第i个字符起,与 for (j=0; j= P.length()) break;//找到匹配子串 } return(i); } } 代码九.1 蛮力串匹配算法的实现 9.3.3 算法分析 „ 正确性 我们首先来证明蛮力算法的正确性。首先,只有在某一轮的 m 次比较全部成功后,蛮力算法才 会报告“发现匹配”,故该算法不会误报。另一方面,在发现匹配子串之前,蛮力算法会逐一尝试每 一个可能匹配的位置,因此只要主串中存在与模式串匹配的子串,蛮力算法必然迟早会将其中最靠 前的匹配子串报告出来,也就是说,该算法也不会漏报。 „ 运行时间 接下来分析该算法的时间复杂度。 我们注意到,从理论上讲,该算法至多需要迭代 n-m+1 轮,而且每一轮至多需要进行 m 次比 较,也就是说,至多只需进行(n-m+1)×m 次比较。那么,这种最坏情况的确会发生吗? 图九.2 蛮力算法的最坏情况 0 0 0 0 00 0 0 0 0 10 0 T P: 0 P: 1 P: 2 . . . P: n-m-1 P: n-m 0 … 00 0 0 0 0 0 0 10 0 0 0 0 0 10 0 0 0 0 0 1 00 0 0 0 0 1 00 … 第九章 串 §9.4 Knuth-Morris-Pratt 算法 303 如 图九.2 所示的实例给出了肯定的回答。如果主串由n个'0'组成,而模式串除末字符为'1'外其 它字符也都是'0',那么的确需要进行n-m+1 轮迭代,而且每一轮都需要比较m对字符(m-1 次成功, 1 次失败)。考虑到m≪n,故蛮力串匹配算法的时间复杂度为O(n×m)。 §9.4 Knuth-Morris-Pratt 算法 9.4.1 蛮力算法的改进 上一节的分析表明,在最坏情况下蛮力算法的运行时间为主串、模式串长度的乘积,因此只适 用于小规模的串匹配应用。对最坏情况稍加观察即可发现,之所以需要大量的时间,是因为存在大 量的局部匹配(每一轮的 m 次比较中,只有最后一次是失败的),而且一旦失配,主串、模式串的 字符指针都要回退,并从头开始下一轮尝试。实际上,绝大部分的这类字符比较操作都是不必要的, 因为关于主串中此前曾经比较成功过的字符,我们已经掌握了它们的所有信息。只要充分利用这些 信息,就可以大大提高匹配算法的效率。 图九.3 利用以往的成功比较所提供的信息,可以避免主串字符指针的回退 如 图九.3 所示,用T[i]和P[j]分别表示当前正在接受比较的一对字符。当本轮比较进行到最后一 对字符并发现失配后,蛮力算法将会让这两个字符指针回退(即令i = i-j+1 和j = 0),然后从这一位 置继续比较。事实上,指针i完全不必回退⎯⎯因为通过前一轮比较我们已经清楚地知道,主串的子 串T[i-j..i-1]完全是由字符'0'组成的。因此,在回退之后紧接下来的一轮迭代中,前j-1 次比较将注定 会成功。既然如此,完全可以让指针i保持不动并且令j = j-1,然后继续比较。请注意,如此将可以 省去j-1 次比较! 上述“i 保持不动并且令 j = j-1”的含义,可以理解为“将 P 相对于 T 向右移动一个单元,然后 从刚才失配的位置继续比较”。实际上,利用以往的成功比较所提供的信息,不仅可以避免主串字符 指针的回退,而且有可能使模式串尽可能大跨度地右移。 0 00 0 00 0 0 0 0 10 0 T P: 0 P: 1 0 … 00 0 0 0 0 10 0 i j j-1 … i - j 0 0 i - j + 1 第九章 串 §9.4 Knuth-Morris-Pratt 算法 304 图九.4 利用以往的成功比较所提供的信息,有可能使模式串大跨度地右移 再来考察如 图九.4 所示的例子。当本轮比较中发现T[i] ≠ P[7]失配后,应该将模式串P右移多少 个单元呢?有必要逐个单元地右移吗? 稍加观察即可发现,在这一情况下,移动一个、两个或三个单元都是徒劳的。事实上,根据以 往的比较结果,必然有 T[i-7..i] = P[0..7] = "CHINCHI"。如果在此局部能够实现匹配,则至少在 T[i] 左侧的那些字符应该是匹配的⎯⎯比如,当 P[0]与 T[i-3]对齐时,就属于这样的情况。如果再注意到 i-3 是能够如此匹配的最靠左位置,就可以放心地将模式串右移 7-3 = 4 个单元,使 i 保持不变,令 j = 3,然后继续比较。 9.4.2 next[]表的定义及含义 图九.5 利用以往的成功比较所提供的信息,在安全的前提下尽可能大跨度地 右移模式串 一般地,如 图九.5 所示,假设前一轮迭代终止于T[i] ≠ P[j]。根据上面的分析,指针i可以不用回 退,并且接下来的一轮迭代将从T[i]与P[t]的比较开始。现在的问题是,t应该等于多少呢? 如 图九.5 所示,前一轮迭代中经过比较匹配的范围为: P[0..j-1] = T[i-j..i-1] 即 … … I N C H IH C T P: 0 i 7 ALL I N C H IH C M I N C H IHCP: 1 3 A LL i - 7 0 0 i - 3 … … T P: 0 i j … P: 1 t i - j 0 0 i - t prefix(prefix(P, j), t) … suffix(prefix(P, j), t) prefix(prefix(P, j), t) 右移量 = j - t j - t suffix(prefix(P, j), t) 第九章 串 §9.4 Knuth-Morris-Pratt 算法 305 prefix(P, j) = substr(T, i-j, j) 如果模式串 P 经右移之后能够与 T 的某一(包含 T[i]在内的)子串完全匹配,一个必要条件就 是: prefix(prefix(P, j), t) = T[i-t..i-1] = suffix(prefix(P, j), t) 也就是说,在串 P 中,长度为 t 的真前缀与长度为 t 的真后缀完全匹配。更准确地,值得试探的 t 必然来自集合: N(P, j) = { t | prefix(prefix(P, j), t) = suffix(prefix(P, j), t), 0 ≤ t < j} 请注意,集合 N(P, j)只取决于模式串 P 本身以及前一轮迭代失配的位置 j,而与主串 T 无关。 从 图九.5 也可以看出,如果下一轮迭代从T[i]与P[t]的比较开始,其效果相当于将模式串P右移 了j-t个单元。因此,为了不至于遗漏可能的匹配,需要在集合N(P, j)中挑选最大的t⎯⎯也就是说, 当有多个值得试探的右移方案时,我们总是保守地选择其中移动距离最短者。因此,只要令 next[j] = max(N(P, j)) 则一旦发现 P[j]与 T[i]失配,就可以转而用 P[next[j]]与 T[i]继续比较。 9.4.3 KMP 算法描述 上述处理方法可以描述为 算法九.1,即著名的KMP算法 ㈠。该算法的具体实现参见 代码九.2 中 的PM()方法。 算法:串匹配算法KMP(P, T) 输入:模式串P和主串T 输出:若P与T的某一子串匹配,则输出第一个匹配位置i;否则返回值i > |T|-|P| { 构造next[]表; j = i = 0; //将P和T的首字符对齐 while (P仍然在T的范围内) { //设P和T的字符指针分别为j和i if (0>j || P[j]==T[i]) { //若匹配,或P已移出最左侧 i++; j++; //则转到下一对字符 } else //否则 j = next[j]; //P右移,T不用回退 } return(i-j); //返回最终P相对T的位置 } 算法九.1 KMP算法 ㈠ 根据三位发明者名字 Knuth、Morris 和 Pratt 的首字母命名。 第九章 串 §9.4 Knuth-Morris-Pratt 算法 306 9.4.4 next[]表的特殊情况 既然空串是任何非空串的真子串(前缀、后缀),故只要 j > 0,就必有 0 ∈ N(P, j)。在这种情况 下,N(P, j)必然非空,故“在其中取最大值”这一操作才有意义。然而反过来,倘若 j = 0,则前缀 prefix(P, j)本身就是空串,它没有任何真子串,于是集合 N(P, j) = ∅。在这种情况下,又应该如何定 义 next[0]呢? 按照串匹配算法的构思,倘若某一轮迭代在比较第一对字符时就失配,我们就应该将模式串直 接右移一个字符,然后从模式串的首字符起继续下一轮比较。这一处理方法可以等效为令 next[0] = -1。 我们也可以通过一个假象的处理方法来理解关于next[0]的定义:如 表九.3 所示,在P[0]的左侧 “附加”一个通配符P[-1],这个字符与任何字符都是匹配的。 表九.3 next[]表实例:假想地附加一个通配符P[-1] -1 0 1 2 3 4 5 6 7 8 9 * C H I N C H I L L A -1 0 0 0 0 1 2 3 0 0 9.4.5 next[]表的构造 需要特别指出的是,如上定义的 next[]表,只取决于模式串 P 以及失配的位置 j,而主串无关。 因此,next[]表的构造可以作为预处理,只需进行一次即可。 幸运的是,next[]表的构造算法与 KMP 算法本身几乎一样。如果注意到集合 N(P, j)中的每一元 素 t 都对应于串 prefix(P, j)自己与自己的一个匹配,就不会对此感到奇怪了。 next[]表构造算法的具体实现,参见 代码九.2 中的BuildNext()方法。 9.4.6 next[]表的改进 利用以上的 next[]表,KMP 算法可以避免大量不必要的比较操作。然而在某些情况下,依然存 在进一步提高效率的可能。 试考察模式串P = "0000010",按照第 9.4.2 节的定义,其对应的next[]如 表九.4 所示。 表九.4 next[]表仍有待优化的实例 -1 0 1 2 3 4 5 6 * 0 0 0 0 0 1 0 -1 0 1 2 3 4 0 如 图九.6 所示,假设前一轮迭代终止于T[i] = '1' ≠ '0' = P[4]。 第九章 串 §9.4 Knuth-Morris-Pratt 算法 307 图九.6 根据前一节所定义的next[]表,仍有可能进行多次不必要的比较操作 于是,接下来KMP算法将按照这一next[]表,依次用P[3]、P[2]、P[1]和P[0]与T[i]做比较。从 图 九.6 可以看出,这四次比较都是失败的。 实际上,如果说 P[4]与 T[i]的比较还算必要的话,那么后续的这四次比较都是多余的,因为它 们注定会失败。为了看出这一点,我们只需注意到 P[4] = P[3] = P[2] = P[1] = P[0] = '0'。既然经过 比较已经发现 T[i] ≠ P[4],为什么还要徒劳地用与 P[4]相同的字符去“重蹈覆辙”呢? 从算法策略的层次来看,第 9.4.2 节所定义的next[]表可以帮助我们充分利用以往成功..的比较所 提供的信息,这正是KMP算法得以加速的根本原因。然而实际上,此前已经进行过的比较还不止这 些,确切地说,还有那些失败..的比较⎯⎯它们同样可以向我们提供信息,但却被忽略了。依然以 图 九.6 为例,以往失败的比较已经提供了一条重要的信息⎯⎯T[i] ≠ P[4]⎯⎯而我们却未能加以利用。 之所以会进行后续四次不必要的比较,原因正在于此。 为了在next[]表中引入这类信息,需要将第 9.4.2 节所定义的集合N(P, j)修改为: N(P, j) = { t | prefix(prefix(P, j), t) = suffix(prefix(P, j), t) 且 P[j] ≠ P[t], 0 ≤ t < j} 相应地,算法九.1 也需稍作修改。如 代码九.2 中的BuildNextImproved()方法所示,在P[0..j-1] 中发现长度为t的匹配前缀和后缀之后,还需判断P[j]是否等于P[t]。只有当P[j] ≠ P[t]时,才能采用t 作为next[j];否则,需要转而用next[t]作为next[j]。 … … 0 0 00 T P: 0 i 010 0 0 00 1 P: 1 4 i - 4 0 0 0 0 0 0 0 01 P: 2 0 0 0 0 010 3 0 P: 3 0 0 0 010 2 0 0 P: 4 0 0 010 1 00 0 P: 5 * 0 0 10000 -1 第九章 串 §9.4 Knuth-Morris-Pratt 算法 308 表九.5 改进后的next[]表 -1 0 1 2 3 4 5 6 * 0 0 0 0 0 1 0 -1 -1 -1 -1 -1 4 -1 表九.4 中的next[],经改进之后如 表九.5 所示。读者可以参照 图九.6,对next[]表两个版本的效 率做一对比。 9.4.7 KMP 算法的 Java 实现 /* * 串模式匹配:KMP算法 * 若返回位置i > length(T) - length(P),则说明失配 * 否则,i为匹配位置 */ import dsa.*; import java.io.*; public class PM_KMP { ////////////////////////////////////////////////////////////////////////// // T: 0 1 . . . i i+1 . . . i+k . . n-1 // --------------------|-------------------|------------ // P: j j+1 . . . j+k . . // |-------------------| ////////////////////////////////////////////////////////////////////////// public static int PM(String T, String P) {//KMP算法 int[] next = BuildNextImproved(P);//构造next[]表 int i = 0;//主串指针 int j = 0;//模式串指针 while(jj || T.charAt(i) == P.charAt(j)) {//若匹配,或P已移出最左侧(提问:这两个条件能 否交换次序?) i++; j++;//则转到下一对字符 } else//否则 j = next[j];//模式串右移(注意:主串不用回退) }//while return(i-j); } protected static int[] BuildNext(String P) {//建立模式串P的next[]表 int[] next = new int[P.length()];;//next[]表 第九章 串 §9.4 Knuth-Morris-Pratt 算法 309 int j = 0;//“主”串指针 int t = next[0] = -1;//“模式”串指针 while (j < P.length()-1) if (0 > t || P.charAt(j) == P.charAt(t)) {//匹配 j++; t++; next[j] = t;//此句可以改进... } else//失配 t = next[t]; for (j=0; j t || P.charAt(j) == P.charAt(t)) {//匹配 j++; t++; next[j] = (P.charAt(j) != P.charAt(t)) ? t : next[t];//注意此句与未改进之前的区别 } else//失配 t = next[t]; for (j=0; j k都有pattern[i] ≠ c) -1 (若pattern[]中不含字符c) 需要强调的是,对于给定的字符表,函数BC[]的取值只取决于具体的模式串P,而与主串T无关。 因此与KMP算法中的next[]表一样,也可以通过预处理计算出BC[]表,并将其组织为一张查询表 (Look-up table),供匹配算法使用。BC[]表的构造过程可以描述为 算法九.2: 算法:BC[]表构造算法BuildBC(P) 输入:模式串P ㈠ BC 是 Bad Character 的缩写。⎯⎯作者 匹配的后缀 a b 不含'b' 右移量 = j - k j b i+j i k 第九章 串 §9.5 BM 算法 313 输出:P对应的BC[]表 { 对于字母表Σ中的每一字符c,令BC[c] = -1; //首先假设该字符没有在P中出现 自左向右扫描P中的各个字符 如果当前字符为P[j] = c,则令BC[c] = j; //更新各字符的BC[]值 return(BC[]); } 算法九.2 BC[]表构造算法 算法九.2 的具体实现,参见 代码九.3 中的BuildBC()方法。 „ 正确性 请注意,这里是按照从左到右(即下标递增)的次序对模式串进行扫描,故只要某个字符 c 在 P 中出现过,则在算法结束时 BC[c]中记录的就是最靠右的 c 的位置。由此可得如下结论: 观察结论九.4 算法 BuildBC(P)能够正确地构造出模式串 P 对应的 BC[]表。 „ 预处理时间 算法九.2 所需时间可以划分为两部分,分别消耗于其中的两个循环。前一个循环是对字符表Σ 中的每个字符分别做初始化,故需要O(|Σ|)时间。后一循环对模式串进行扫描,由于每个字符的处理 只需O(1)时间,故共需O(m)时间。由此可得如下结论: 定理九.2 BC[]表可以在 O(|Σ|+m)时间内构造出来,其中|Σ|为字符表的规模,m 为模式串的长度。 „ 特殊情况 图九.8 坏字符策略:T[i+j]在P中未出现,或者右移量为负数 还有些特殊情况需要处理。如 图九.8 所示,有时P串中根本就不含字符'b',此时可以直接将该 串整体移过,用P[0]对准T[i+j+1],然后自右向左继续比较。 匹配的后缀 a j 不含'b' 右移量 = j b 不含'b' b i+j i 负右移 = 左移 第九章 串 §9.5 BM 算法 314 另外,即使 P 串中含有字符'b',却也有可能出现的位置太靠右,使得 k = BC['b'] ≥ j。在这一情 况下,j-k 将不再是正数,若以此距离进行右移,实际效果将是左移⎯⎯显然,这是不必要的。因此, 为处理这一情况,只需简单地将 P 串右移一个字符,然后重新自右向左扫描比较。 9.5.2 好后缀策略 „ 好后缀 BM 算法的思想,是尽可能地利用此前已进行过的比较所提供的信息,以加速模式串的移动。 上述坏字符策略,就很好地体现了这一构思:既然已经发现 P[j]与 T[i+j]不匹配,就应该从 P 中找出 一个与 T[i+j]匹配的字符,将二者对齐之后,重新自右向左开始比较。 然而,仔细分析后我们可以发现,坏字符策略只利用了此前(最后一次)失败的比较所提供的 信息。实际上,在失败之前往往还会有一系列成功的比较,它们也能提供大量的信息,对此我们能 否加以利用呢? 在 图九.9 中,假设前一轮自右向左的比较终止于T[i+j] ≠ P[j]。如果分别记 ⎩ ⎨ ⎧W = substr(T, i+j+1, m-j-1) U = suffix(P, j+1, m-j-1) 于是只要 j ≤ m-2,则后缀 U 必非空,而且满足: U = W 正如我们马上就要看到的,利用后缀 U 所提供的信息可以加速模式串的右移,因此我们将这样的后 缀称作“好后缀”。 „ 好后缀策略 如 图九.9 所示,假设经过右移使T[i+j]与P[k]相互对齐之后,模式串P能够与主串T的某一(包 含T[i+m-1]在内的)子串匹配,即 P = substr(T, i+j-k, m) 既然如此,如果记 U' = substr(P, k+1, m-j-1) 则必然有: U' = W = U 也就是说,在模式串 P 中,存在某一长度为 m-j-1 的子串与 P 自己的后缀匹配⎯⎯只有在满足这一 条件的位置,才有可能使 P 得到匹配。当然,这只是模式串 P 与主串 T 匹配的一个必要条件,在将 这两段匹配的子串对齐之后,还需要重新自右向左进行比较。 此外,还要加上另一个必要条件:P[k] ≠ P[j]。否则,与第 9.4.6 节关于KMP算法中next[]表的 改进同理,这一对齐位置注定不会出现P的整体匹配。 若模式串 P 中存在多个满足上述必要条件的子串,我们不妨取其中最靠右者,以避免此后 P 串 的左移。 第九章 串 §9.5 BM 算法 315 如果满足上述必要条件的子串 U'起始于 P[k+1],则对应的右移量就是 j-k。请注意,这个右移 量只取决于 P 串以及失配的位置 j,因此与 KMP 算法中的 next[]表一样,也可以通过预处理在事先 计算出来,并将结果保存为一张查找表 GS[0..m-1]。 „ 特殊情况 图九.9 好后缀策略 有一种特殊情况需要处理:如 图九.9 所示,有的时候,模式串P中没有任何子串与好后缀U完 全匹配。此时,我们可以从模式串P的所有前缀中,找出一个尽可能长的、与U的(真)后缀匹配的 前缀V。如果V的长度为t,则取GS[j] = m-t。 查找表GS[]的具体构造算法,参见 代码九.3 中的BuildGS()方法。这里,ComputeSuffixSize() 方法的作用,是计算P的各前缀与P的各后缀的最大匹配长度,即对于P的每一前缀X = prefix(P, j+1), 计算出 SS[j] = max{s | suffix(X, s) = suffix(P, s)} 9.5.3 BM 算法 综上所述,BM算法可以描述为 算法九.3: 算法:串匹配算法BoyerMoore(P, T) 输入:模式串P和主串T 输出:若P与T的某一子串匹配,则输出第一个匹配位置i;否则返回值i > |T|-|P| { 构造BC[]表; 构造GS[]表; i = 0; //将P和T的首字符对齐 while (P仍然在T的范围内) { //设P和T的字符指针分别为j和i+j j = |P|-1; //从最右侧的字符开始 while (P[j] == T[i+j]) //自右向左逐一比较各对字符,直至发现失配或者 if (0 > --j) break; //所有字符对经过比较都获成功 k j 0 m 0 0 m m 匹配的后缀 U = P[j+1..m-1] a 右移量 GS[j] = j-k b 成功的比较:W = T[i+j+1..i+m-1] i+j i 最靠右的匹配子串 U' = P[k+1..m+k-j-1] ≠a 与 U 后缀匹配的最长前缀 V 右移量 GS[j] = m-t 长度 = t i+j-k i+m 第九章 串 §9.5 BM 算法 316 if (所有比较都成功) return(i); //返回匹配位置 else i += MAX(GS[j], j - BC[T[i+j]]; //在位移量BC和GS中选择大者,右移模式串 } //执行至此,说明P已经移出T的范围,即T中不存在与P匹配的子串 return(i); //注意,此时的返回值i满足i > |T|-|P|,可依此判断是否存在匹配 } 算法九.3 BM算法 请注意,这里同时采用了坏字符、好后缀两种启发策略,并在它们给出的右移量中取大者。该 算法的具体实现,参见 代码九.3 中的PM()方法。 9.5.4 BM 算法的 Java 实现 /* * 串模式匹配:Boyer-Moore算法 * 若返回位置i > length(T) - length(P),则说明失配 * 否则,i为匹配位置 */ import dsa.*; import java.io.*; public class PM_BM { final static int CARD_CHAR_SET = 256;//字符集规模 ////////////////////////////////////////////////////////////////////////// // T: 0 1 . . . i i+1 . . . i+j . . n-1 // --------------------|-------------------|------------ // P: 0 1 . . . j . . // |-------------------| ////////////////////////////////////////////////////////////////////////// public static int PM(String T, String P) { //预处理 int[] BC = BuildBC(P); int[] GS = BuildGS(P); //查找匹配 int i = 0;//模式串相对于主串的起始位置(初始时与主串左对齐) while (T.length()-P.length() >= i) {//在到达最右端前,不断右移模式串 int j = P.length() - 1;//从模式串最末尾的字符开始 while (P.charAt(j) == T.charAt(i+j))//自右向左比较 if (0 > --j) break; 第九章 串 §9.5 BM 算法 317 ShowProgress(T, P, i, j); System.out.print("\n"); if (0 > j)//若极大匹配后缀 == 整个模式串(说明已经完全匹配) break;//返回匹配位置 else//否则 i += MAX(GS[j], j - BC[T.charAt(i+j)]);//在位移量BC和GS之间选择大者,相应地移动模式 串 } return(i); } /* * 构造Bad Charactor Shift表BC[] * * 0 BC['X'] m-1 * | | | * ........................X**************************************** * |<------------ 不含字符'X' ------------>| * * 复杂度 = O(m + CARD_CHAR_SET) ************************************************************************/ protected static int[] BuildBC(String P) { //初始化 int[] BC = new int[CARD_CHAR_SET];//BC[]表 int j; for (j = 0; j < CARD_CHAR_SET; j++) BC[j] = -1;//首先假设该字符没有在P中出现 //自左向右迭代:更新各字符的BC[]值 for (j = 0; j < P.length(); j++) BC[P.charAt(j)] = j;//P[j]曾出现在位置j——鉴于这里的扫描次序是从左到右(即下标递增),故 只要某个字符ch在P中出现过,BC[ch]就会记录下其中的最靠右的出现位置 System.out.println("-- BC[] Table ---------------"); for (j = 0; j < CARD_CHAR_SET; j++) if (0 <= BC[j]) System.out.print("\t"+(char)j); System.out.println(); for (j = 0; j < CARD_CHAR_SET; j++) if (0 <= BC[j]) System.out.print("\t"+BC[j]); System.out.println("\n"); return(BC); } /* * 计算P的各前缀与P的各后缀的最大匹配长度 * 对于P的每一前缀P[0..j],SS[j] = max{s | P[j-s+1..j] = P[m-s..m-1]} * * 0 m-SS[j] m-1 * | | | 第九章 串 §9.5 BM 算法 318 * ........................************************* * | | * <-------- SS[j] --------> * | | * ............*************************.................. * | | | | * 0 j-SS[j]+1 j m-1 * * 复杂度 = O(m) ************************************************************************/ protected static int[] ComputeSuffixSize(String P) { int m = P.length(); int[] SS = new int[m];//Suffix Size Table int s, t;//子串P[s+1, ..., t]与后缀P[m+s-t, ..., m-1]匹配 int j;//当前字符的位置 // 对最后一个字符而言,与之匹配的最长后缀就是整个P串,故... SS[m-1] = m; // 从倒数第二个字符起,自右向左扫描P,依次计算出SS[]其余各项 s = m-1; t = m-2; for (j = m-2; j >= 0; j--) { if ((j > s) && (j-s > SS[(m-1-t)+j])) SS[j] = SS[(m-1-t)+j]; else { t = j;//与后缀匹配之子串的终点,就是当前字符 s = MIN(s, j);//与后缀匹配之子串的起点 while ((0 <= s) && (P.charAt(s) == P.charAt((m-1-t)+s))) s--;//似乎是二重循环,难道复杂度是平方量级? SS[j] = t-s;//与后缀匹配之最长子串的长度 } } System.out.println("-- SS[] Table -------"); for (j=0; j<------ GS Shift ------> * | <---- SS[j] = j+1 ----><-------- m-j-1 -------> * | | | | * ***********************........................ * | | | * 0 j m-1 * <--<--<--<--<--<--< 自右向扫描 <--<--<--<--<--< * ************************************************************************/ int i = 0; for (j = m-1; j >= -1; j--)//提问:反过来(自左向右)扫描可以吗?为什么? if (-1 == j || j+1 == SS[j])//若定义SS[-1] = 0,则可统一为:if (j+1 == SS[j]) for (; i < m-j-1; i++)//似乎是二重循环,难道复杂度是平方量级? if (GS[i] == m) GS[i] = m-j-1; /* * m-SS[j]-1(失配位置) * | * 0 |m-SS[j] m-1 * | || | * ....................A********************** * || | * |<--- Suffix Size ----><-- GS Shift -> * |<------- SS[j] ------><--- m-j-1 ---> * || | | * .....B**********************............... * | | | | * 0 j-SS[j]+1 j m-1 * >-->-->-->-->--> 自左向右扫描 --->-->-->--> * ************************************************************************/ for (j = 0; j < m-1; j++)//提问:反过来(自右向左)扫描可以吗?为什么? GS[m-SS[j]-1] = m-j-1; System.out.println("-- GS[] Table ---------------"); for (j=0; jb) ? a : b; } protected static int MIN(int a, int b) { return (a
还剩79页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享pdf获得金币 ] 7 人已下载

下载pdf

pdf贡献者

1985lili

贡献于2012-05-03

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf