当前课程知识点:Data Structures and Algorithm Design Part II >  11.String I >  C6.Kmp.improvement >  11C6-5

返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表

11C6-5在线视频

下一节:11D1-1

返回《Data Structures and Algorithm Design Part II》慕课在线视频列表

11C6-5课程教案、知识点、字幕

在告别KMP算法之前

我们不妨以一种可视的形式

将其与蛮力算法作一对比

我们此前曾经指出

对于串匹配算法的评判与对比

需要分成功和失败两种情况分别进行

因此这里 我们不妨只针对失败的情况

对二者的最好与最坏性能作一对比

在这个图中 我们用这条线来表示文本串

它相对而言更长

而模式串的长度m则相对更小

在蛮力算法中 如果我们将文本串固定于此

然后将模式串在各次迭代中的快照记录下来

并按照与文本串相应的对齐位置 如此排列

就会得到这样一个相对比较窄

同时非常高的平行四边形

当然 既然是失败情况 所以 每一轮的比对过程都类似

具体来说 都是在经过了一系列的成功比对之后

最终失败于某个位置

而一旦失败之后 算法都会将模式串右移一个字符 并重新开始一轮比对

而且同样地 接下来也会经过一系列的成功比对 并最终失败于某个位置

这样的故事会反复地发生

直到最终模式串试图越过文本串的右侧边界

从这个图中 我们可以清晰地看到

在每一个对齐位置所消耗的计算成本

都可相应地由深色区间的宽度来度量

整个算法累计所消耗的时间

应该也就是这些深色区间的宽度总和

那么这一总和的变化范围是多大呢

首先我们注意到有最坏情况

也就是在某一个对齐位置

可能会持续地经过m-1次成功的比对

而最终失败于第m次比对

而整体的最坏情况

莫过于每次都出现这样的最坏情况

关于这一点 我们在此前曾经举过一个具体的实例

既然在数量级上 m要小于n

所以这个平行四边形的高度 也就可以直接度量为n

因此 平行四边形的面积 也自然就是n*m

这也是蛮力算法在最坏情况下的性能

再来看看KMP算法

我们同样地可以将所有潜在的和实在的对齐位置

按照刚才的方式排列起来

从而同样得到这样一个平行四边形

然而幸运的是

因为KMP算法的智能性

它所消耗的时间

要远远地小于这个平行四边形的面积

来看右侧这个局部放大图

在这里我们可以清晰地看到KMP的两种优化效果

你应该记得 KMP首先能够令模式串得以快速地滑动

也就是说 它有可能会直接越过一些潜在的对齐位置

在每一次快速的滑动之后

它也不必继续从头开始比较

而事实上 它只需从刚才失败的那个位置出发

继续开始下一轮的比对

如果有必要 在经过下一次的快速移动之后

它依然会从新的失败位置开始

启动下一轮的比对

以致再下一轮

以及再再下一轮比对

同样地 在这样的一个计算过程中

我们所花费的时间也可以用这些深色的区间来表示

它们的宽度之和

也就给出了KMP算法总体的计算时间

为了统计出所有这些深色区间的宽度之和

我们不妨回到左侧这幅总览图

不难看出 如果将所有这些深色的区间 都沿着垂直方向投影到文本串上

我们就会发现 任何两段深色的区间

除了在端点处之外 绝不会有任何的重叠

因此 既然文本串的长度为n

我们也可以由这个图直接推知

整个KMP算法所消耗的时间总量

也不会超过2n

这与我们此前的分析完全一致

在学习过KMP算法之后

如果我们回过头来再看看蛮力算法

你或许会对它不屑一顾

是的 就最坏情况下的效率而言

这个算法的确不值一提

然而在此 我们也不妨为蛮力算法作些辩护

如果还不是平反的话

事实上 即使是在失败情况下

蛮力算法也有最好的情形

你能想到吗

是的 在总体失败的情况下

蛮力算法依然需要在每一个对齐位置作一轮比对

然而在最好的情况下

每一步迭代 可能只牵涉到常数 甚至只有一次比对

是的 只经过一次比对

就可排除掉一个对齐的位置

你应该不难构造出这样的实例

因此在这种情况下

为了排除掉所有的O(n)个对齐位置

蛮力算法所消耗的时间 累计也不过是线性的

当然 你有可能会质疑这种最好情形所发生的概率

事实情况是 在通常的情况下 这个概率并不像你想象的那么低

而且 随着字符集规模的增大

这个概率也会急速地提高

也就是说 在这类情况下

KMP算法相对于蛮力算法的优势 也就不那么明显了

或者反过来等效地

只有在字符集规模相对很小时

KMP在性能上的优势

才能充分得以展示

你或许已经注意到了

在介绍KMP算法的诸多教材中

绝大多数的实例都是基于二进制串

如果你能够领会到我们刚才所说的那个现象

你就应该能够更好地理解那些作者的良苦用心了

Data Structures and Algorithm Design Part II课程列表:

07.Binary Search Tree

-A.introduction

--07A-1

--07A-2

--07A-3

--07A-4

--07A-5

-A.introduction--Homework

-B1.BST : search

--07B1-1

--07B1-2 查找:算法

--07B1-3 查找:理解

--07B1-4 查找:实现

--07B1-5 查找:语义

-B1.BST : search--Homework

-B2.BST : insertion

--07B2-1

--07B2-2

-B2.BST : insertion--Homework

-B3.BST : removal

--07B3-1

--07B3-2

--07B3-3

--07B3-4

-B3.BST : reomval--Homework

-C.balance+equivalence

--07C-1

--07C-2

--07C-3

--07C-4

--07C-5

-C.balance+equivalence--Homework

-D1.AVL : rebalance

--07D1-1

--07D1-2

--07D1-3

--07D1-4

--07D1-5

-D1.AVL : rebalance--Homework

-D2.AVL : insertion

--07D2-1

--07D2-2

--07D2-3

-D2.AVL : insertion--Homework

-D3.AVL : removal

--07D3-1

--07D3-2 删除:双旋

--07D3-3 删除:实现

-D3.AVL : removal--Homework

-D4.AVL : (3+4)-construction

--07D4-1

--07D4-2

--07D4-3

--07D4-4

-D4.AVL : (3+4)-construction--Homework

-Homework

--Homework

08.ABST I

-A1.Splay_Tree.splay1

--08A1-1

--08A1-2

--08A1-3

--08A1-4

--08A1-5

--08A1-6

--08A1-7

--Homework

-A2.Splay_Tree.splay2

--08A2-1

--08A2-2

--08A2-3

--08A2-4

--08A2-5

--08A2-6

--08A2-7

--Homework

-A3.Splay_Tree.implementation

--08A3-1

--08A3-2

--08A3-3

--08A3-4

--08A3-5

--08A3-6

--08A3-7

--Homework

-B1.B-Tree.motivation

--08B1-1

--08B1-2

--08B1-3

--08B1-4

--08B1-5

--08B1-6

--Homework

-B2.B-Tree.structure

--08B2-1

--08B2-2

--08B2-3

--08B2-4

--08B2-5

--08b2-6

--08B2-7

--08B2-8

--Homework

-B3.B-Tree.search

--08B3-1

--08B3-2

--08B3-3

--08B3-4

--08B3-5

--08B3-6

--Homework

08.ABST II

-B4.B-Tree.insertion

--08B4-1

--08B4-2

--08B4-3

--08B4-4

--08B4-5

--Homework

-B5.B-Tree.removal

--08B5-1

--08B5-2

--08B5-3

--08B5-4

--08B5-5

--Homework

-XA1.Red-Black.motivation

--08XA1-1

--08XA1-2

--08XA1-3

--08XA1-4

--Homework

-XA2.Red-Black.structure

--08XA2-1

--08XA2-2

--08XA2-3

--08XA2-4

--08XA2-5

--08XA2-6

--08XA2-7

--Homework

-XA3.Red-Black.insertion

--08XA3-1

--08XA3-2

--08XA3-3

--08XA3-4

--08XA3-5

--08XA3-6

--Homework

-XA4.Red-Black.removal

--08XA4-1

--08XA4-2

--08XA4-3

--08XA4-4

--08XA4-5

--08XA4-6

--08XA4-7

--08XA4-8

--08XA4-9

-Homework

--Homework

09.Dictionary

-B.hashing.principle

--09B-1

--09B-2

--09B-3

--09B-4

--09B-5

--09B-6

--Homework

-C.Hashing.Hash-Function

--09C-1

--09C-2

--09C-3

--09C-4

--09C-5

--09C-6

--09C-7

--09C-8

--09C-9

--09C-A

--09C-B

--Homework

-D1.Hashing.Solving-Collision-1

--09D1-1

--09D1-2

--09D1-3

--09D1-4

--09D1-5

--Homework

-D2.Hashing.Solving-Collision-2

--09D2-1

--09D2-2

--09D2-3

--09D2-4

--09D2-5

--09D2-6

--09D2-7

--09D2-8

--Homework

-E.Bucketsort

--09E-1

--09E-2

--09E-3

--Homework

-Homework

--Homework

10.Priority Queue

-A1.motivation

--10A1-1

--10A1-2

--10A1-3

--Homework

-A2.Basic_Implementations

--10A2-1

--10A2-2

--10A2-3

--Homework

-B1.Complete_Binary_Heap.structure

--10B1-1

--10B1-2

--10B1-3

--10B1-4

--Homework

-B2.Complete_Binary_Heap.insertion

--10B2-1

--10B2-2

--10B2-3

--10B2-4

--Homework

-B3.Complete_Binary_Heap.removal

--10B3-1

--10B3-2

--10B3-3

--10B3-4

--Homework

-B4.Complete_Binary_Heap.heapification

--10B4-1

--10B4-2

--10B4-3

--10B4-4

--10B4-5

--Homework

-C.Heapsort

--10C-1

--10C-2

--10C-3

--10C-4

--Homework

-XA1.Leftist_Heap.structure

--10XA-1

--10XA1-2

--10XA1-3

--10XA1-4

--10XA1-5

--10XA1-6

--Homework

-XA2.Leftist_Heap.merge

--10XA2-1

--10XA2-2

--10XA2-3

--10XA2-4

--Homework

-XA3.Leftist_Heap.insertion+removal

--10XA3-1

--10XA3-2

-Homework

--Homework

11.String I

-A.ADT

--11A-1

--11A-2

--11A-3

--Homework

-B1.Pm

--11B1-1

--11B1-2

--Homework

-B2.brute-force

--11B2-1

--11B2-2

--11B2-3

--11B2-4

--Homework

-C1.Kmp.memorization

--11C1-1

--11C1-2

--11C1-3

--11C1-4

--Homework

-C2.Kmp.lookup-table

--11C2-1

--11C2-2

--11C2-3

--Homework

-C3.Kmp.understanding_next[]

--11C3-1

--11C3-2

--11C3-3

--Homework

-C4.Kmp.constructing_next[]

--11C4-1

--11C4-2

--11C4-3

--Homework

-C5.Kmp.amortization

--11C5-1

--11C5-2

--Homework

-C6.Kmp.improvement

--11C6-1

--11C6-2

--11C6-3

--11C6-4

--11C6-5

11.String II

-D1.BM_BC.begin_with_the_end

--11D1-1

--11D1-2

--11D1-3

--11D1-4

-D2.BM_BC.bad_character

--11D2-1

--11D2-2

-D3.BM_BC.constructing_bc[]

--11D3

-D4.Bm_BC.performance

--11D4-1

--11D4-2

-E1.Bm_GS.good-suffix

--11E1-1

--11E1-2

--11E1-3

-E2.Bm_GS.constructing_gs[]

--11E2

-E3.Bm_GS.performance

--11E3-1

--11E3-2

-F1.KR.fingerprint

--11F1-1

--11F1-2

--11F1-3

-F2.KR.hashing

--11F2-1

--11F2-2

--11F2-3

--11F2-4

-Homework

--Homework

12.Sorting

-A1.Quicksort.algorithm

--12A1-1

--12A1-2

--12A1-3

--12A1-4

-- 12A1-5

--Homework

-A2.Quicksort.performance

--12A2-1

--12A2-2

--12A2-3

--Homework

-A4.Quicksort.Variation

--12A4-1

--12A4-2

--12A4-3

--12A4-4

--12A4-5

-B1.Selection.mode

--12B1-1

--12B1-2

--12B1-3

--12B1-4

--12B1-5

-B2.Selection.Median

--12B3-1

--12B3-2

--12B3-3

--12B3-4

--12B3-5

--12B3-6

--Homework

-C1.Shellsort.Shell's sequence

--12C1-1

--12C1-2

--12C1-3

--12C1-4

--12C1-5

--Homework

-C2.Shellsort.Inversion

--12C2-1

--12C2-2

--12C2-3

-Homework

--Homework

11C6-5笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。