月度归档:2015年04月

Boyer-Moore 子字符串查找算法

前一篇博文中讨论了子字符串查找的问题,并给出了一个能高效地解决这个问题的算法:KMP 算法。我们知道,KMP 算法仅需在被查找字符串中顺序访问其中每个字符一次,便能找到其中匹配指定模式的子字符串。然而令人惊讶的事实是,KMP 并不是解决子字符串查找问题最快的算法,这意味着有时并不需要完整地扫描被查找字符串中的每一个字符便能完成子字符串查找。

Bob Boyer 和 J Strother Moore 在 1977 年设计了一个比 KMP 更快的字符串查找算法[1]。与 KMP 算法一样,这个算法也以设计者的名字命名,得名 Boyer-Moore 算法。Boyer-Moore 算法的主要思想是,在比对被查找字符串与模式中的字符时,启发式地跳过一些不事实上不需要比较的字符,大大减少了查找过程中比较的次数。更难得的是,Boyer-Moore 算法非常容易理解,实现也很简洁。

为了理解 Boyer-Moore 算法,先考察如下的例子:在字符串 S = “http://luodichen.com/blog/” 中查找模式 R = “luodichen”。像之前讨论过的暴力查找算法一样,先从被查找的字符串 0 索引处开始查找;但匹配字符的方向与暴力查找相反——自右向左匹配模式中的字符。如下图所示,在这个例子中当查找索引 i = 0 时,右边首先匹配的是被查找字符串中的字符 S[8] = ‘u’ 与 模式中的字符 R[8] = ‘n’,结果是这两个字符不相匹配。按照暴力查找的做法,当出现了不匹配的情况时,需要做的是将查找索引的值加 1,重新进行匹配,此时不妨也这样做,将查找索引 i 的值加 1,此时 i = 1。现在应该比较哪两个字符呢?比较 S[8] = ‘u’ 与 R[7] = ‘e’,同样不匹配,重复增加 i 的值,直到 i = 7 时,S[8] = ‘u’ 与 R[1] = ‘u’ 匹配。接着逐字向左匹配剩下的字符,最后会发现子字符串匹配成功了。

bm-ani1图 1  暴力算法的小改动——先匹配右边的字符

然而这并没有比暴力算法更快(与暴力算法一样慢)。仔细回想一下上面的操作,实质上是在不断增加查找索引 i 的同时检查 S[8] 与 R[8 – i] 是否匹配,换句话说,就是在 R 中自右向左寻找第一个字符 S[8]。如果在字符串查找开始之前就对模式 R 做一些处理,记住 R 中每一个字符自右向左第一次出现的位置(上例中 ‘u’ 第一次出现的位置是 R[1]),就可以在发生不匹配的情况时直接推算出 i 应当增加的数值,而不必每次只加 1 地尝试。如下图。

bm-ani2图 2 查表并推算出 i 需要增加的值,直接设置 i

以上的例子便是运用了 Boyer-Moore 算法的思想。将这个思路推广到一般情形,为了描述方便,先假设被查找的字符串为 S 假定 S 足够长,匹配模式为 R,R 的长度为 l;查找索引为 i,i 的初始值是 0;函数 m(c) 表示 R 中自右向左第一次出现字符 c 时 R 的索引,若 c 从未在 R 中出现过,返回 -1。Boyer-Moore 算法由以下几个步骤组成:

  1. 找到模式 R 最右匹配的字符 S[i + l – 1] 与 R[l – 1];
  2. 如果匹配,则继续向左检查,直到找到 S[i + l – n] 与 R[l – n] 不匹配或全部字符都匹配成功;
  3. 如果全部字符匹配成功,则子字符串查找到一个结果;否则调用 j = m(S[i + l – n]),得到 j 表示 S 中不匹配的那个字符在 R 中自右向左第一次出现的索引,然后查找索引向右移动 (l – j – 1),重复步骤 1。

Boyer-Moore 算法在应用中通常能跳过大部分字符,因此具有非常快的速度。并且模式相对越长,查找速度越快。以下的图片演示了 Boyer-Moore 算法的一个经典示例:在 “HERE IS A SIMPLE EXAMPLE” 中查找 “EXAMPLE”。

bm-ani3图 3 在 “HERE IS A SIMPLE EXAMPLE” 中查找 “EXAMPLE”

本文所提到的所有算法均以 Java 实现,代码托管于 GitHub,查看

(允许转载文本,转载请注明出处:http://luodichen.com/blog/?p=298

参考文献
[1] Wikipedia. Boyer-Moore字符串搜索算法[EB/OL]. http://zh.wikipedia.org/wiki/Boyer-Moore%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95.

KMP 算法:实现高效的子字符串搜索

在计算机日常应用中,我们经常会遇到需要在一篇文章中搜索某个字词的情形,这就是子字符串查找算法运用的实例。例如在字符串 “http://luodichen.com/blog/” 中找出子字符串 “luodichen.com” 第一次出现的位置(索引),通过观察可以很轻松地得到答案是 7。在子字符串查找中,期望查找的子字符串是以“字符串某一部分与期望查找的子字符串完全相同”的规则存在的,这个以子字符串表示的匹配规则称为“模式(Pattern)”。上面查找 “luodichen.com”的例子中,模式就是 “luodichen.com”。

如何编程实现子字符串查找呢?假设有长度为 l 字符串 S,需要在 S 中寻找长度为 m 的子字符串 R 第一次出现的位置(m < l)。粗看起来,这个问题似乎并不难回答。一个直观的做法就是依次设查找索引 i = 0, 1, 2, …, l – m,每次都检查 S 在索引 i 处长度为 m 的子字符串是否与 R 完全相等,如果相等,则说明查找成功,i 就是要找的答案;否则就尝试下一个 i 的值,如果尝试了每一个 i 的值都没有找到答案,说明查找失败,S 中不存在要找的子字符串。这是一种简单粗暴的方法,下文称其为“暴力算法”。

考察“检查在索引 i 处长度为 m 的子字符串是否与 R 完全相等”的实现过程,我们会逐一比较字符 S[i + j] 与 R[j](0 <= j < m)是否相等,会发现这个操作实质上可以看作一个确定有限状态自动机。这个状态机在每比较一个字符时发生一次状态转移:如果比较的两个字符相等,则进入下一个状态,否则匹配失败停机,直到比较完所有的字符,转入成功停机状态。状态机停机之后,只要判断当前的状态是成功还是失败就能得出此次匹配的结果。假设要查找的字符串是 “LUODC”,状态机的图示如下。

图1 在字符串中查找 “LUODC” 时的状态机表示

对于每个 i 的取值,这个操作最少需要 1 次字符比较,最多需要做 m 次字符比较。因此,这种字符串搜索算法在最差的情况下的时间复杂度是 O(ml – m2)。当然,在实际应用中碰到较差的情况是比较罕见的,因为在通常情况下,大部分匹配尝试都会在前几个字符的比较中就会转到失败状态,暴力算法在一般的情形下性能还是可以接受的。

然而,1970 年,S.Cook 在理论上证明一个关于某种特定类型的抽象计算机的结论,该结论暗示了一种在最坏情况下用时也只是与 m + l 成正比的解决子字符串查找问题的算法[1]。D.E.Knuth 与 V.R.Pratt 在这些基础上做了一些改进,提出了一个相对简单而实用的算法。另外,J.H.Morris 也独立发明了相似的子字符串查找算法。后来,这个算法取发明者三人名字的首字母,得名 KMP 算法

考虑以下问题:在字符串 S[] = “AAAAAAAAAB” 中搜索模式 R[] = “AAAAB”。按上文中提到的暴力算法,先测试 S[0…4] 与 R[] 是否相等,直到比较到字符 S[4] 与 R[4] 时,才发现 S[4] 的值是 ‘A’ 而 R[4] 的值是 ‘B’,此时子串 s[0…4] 测试失败,下一步应当测试 S[1…5] 与 R[] 是否相等。在下一轮测试中,又需要依次比较 S[i + 1] 与 R[i](1 <= i <= 5)的值是否相等,并最终以 S[5] 与 R[4] 不相等而匹配失败收场。

等等——我们注意到,在第一轮测试中,其实已经可以知道 S[1…4] 的值是 “AAAA”,与 R[0…3] 的四个字符是完全吻合的,实际上只需要比较 S[5] 与 R[4] 两个字符是否相等就行了,接下来的几轮比较也是如此。这样,通过这个小的改进,省下了多次不必要的字符比较,节省了操作时间。

以上是一个特殊的例子,KMP 算法将这种思路推广到了一般情形,对于任意模式的查找操作都能最大限度地省去不必要的字符比较。

在暴力算法的状态机描述中,假设某一轮测试将 a[i], a[i+1] ,…, a[i+m-1] 依次输入状态机中后,发生了失败停机,则下一轮需要将 a[i+1], a[i+2], …, a[i+m] 输入状态机中重新测试。在最坏的情形下,每轮测试都不得不输入 m – 1 个与上次重复的字符。KMP 算法最大的优势在于,如果把它也用状态机来描述,KMP 状态机是没有失败状态的,它可以连续地接收被查找字符串中的所有字符,直到找到一个匹配的子字符串才停机。在这个过程中,被查找的字符串中竟没有任何重复扫描的字符!下面是一个用 KMP 算法在只由 ‘A’、’B’ 和 ‘C’ 构成的字符串中查找子字符串 “ABABAC” 的状态机的例子。

kmp-fsm-2图2 用 KMP 算法在字符串中查找子字符串 “ABABAC” 时的状态机

KMP 算法按顺序连续(而不回头)地读取被查找字符串中的字符,每读取一个字符都会改变一次状态机的状态,自发地根据当前的状态“决策”最适合的下一个状态以达到找出子字符串的目的。如上图所示,KMP 算法为每一个匹配进度都设置了一个状态,假定要查找的模式 R[] 的长度是 m,那么状态机 DFA 就有 S0, S1, …, Sm-1 一共 m 个状态,其中每个状态都根据不同的输入对应一个转移路径。例如上图中的例子,假设当前的状态为匹配进度 “ABABA_”,那么如果下一个输入正好是 ‘C’,毫无疑问此时子字符串匹配成功,转移到 succeed 状态;如果下一个输入是 ‘B’,意味着当前匹配到了一个 “ABABAB” 的字符串,最佳的决策是丢掉前面两个字符 “AB”,再期望输入一个 ‘A’ 和一个 ‘C’ 即可达到子字符串匹配的目的,因此转移到匹配进度为 “ABAB_” 的状态;如果下一个输入是 ‘A’,意味着当前匹配到了一个 “ABABAA”,的字符串,显然地,这时只能丢掉前五个字符 “ABABA”,只留下字符 “A”,并期望输入 “BABAC” 来达到匹配的目的,因此转移到匹配进度为 “A_” 的状态。

可见,KMP 算法高效的原因是有一个“聪明的”状态机总能根据当前的匹配进度为每种可能的输入选择最佳的匹配方案。那么,现在的问题是如何构建一个任意的模式 R[] 对应的状态机。假设 R 的长度为 m,那么 R 所有可能的匹配进度有匹配前 0 个字符、匹配前 1 个字符、匹配前 2 个字符……匹配前 m 个字符,每个匹配进度对应状态机一个状态,记作 S0, S1, S2, …, Sm。另设构成被查找字符串的字符集为 E,则构成确定有限自动机 DFA 的 5-元组要素如下:

  • 状态集合 Q = {S0, S1, S2, …, Sm}
  • 输入字母表 ∑ = E
  • 开始状态 s = S0
  • 接受状态集合 F = {Sm}

接下来要做的是构造自动机的转移函数。设当前状态为 S,输入的字符为 c 时的状态转移函数为 f(S, c),另设模式 R[0…m-1] 的字符分别为 c0, c1, …, cm-1,显然地,当状态机处于 Si 状态时,说明已经完成了 c0-ci-1 共 i 个字符的匹配,此时如果输入的字符正好与 ci 相等,那么状态机一定会再次完成一次匹配,进入 Si+1 状态。于是可以得出下式:

f(Si, ci) = Si+1    ①
特别地:f(S0, c0) = S1    ②

再考虑状态机处于 S0 状态时,显然只有当输入的字符与 c0 相等时才会进入下一个状态 S1,其他输入都是不匹配的,只会让状态机回到原地。因此对 S0 的其他非 c0 输入又可以得到下式:

f(S0, c) = S0 (c ≠ c0)    ③

那么,在非 S0 状态时的不匹配输入,应当怎样处理呢?显然,状态机不匹配时应当回到当前状态之前某个状态,这正是 KMP 算法的精妙之处。再回过头来看图 2 中的例子,假设当前状态是已匹配 “ABABA_”,已经匹配了 5 个字符,也就是当前的状态是 S5。当输入 c ≠ ‘C’ 时,状态机需要回退到之前某个状态,目前已知的是如果向状态机中依次输入 (‘A’, ‘B’, ‘A’, ‘B’, ‘A’, c) 一定是不匹配的,在输入 c 后能获得最佳匹配结果的状态是将 (‘B’, ‘A’, ‘B’, ‘A’, c) 依次输入重新初始化过的状态机,最终得到的状态,这个状态即是要求的 S5 转换函数 f(S5, c)。因为 5 个输入最多能使状态机转换到 S5,所以使用上述方法推导 S5 的转换函数时,只需要已知 S0-S4 各个状态的转换函数即可!换言之,如果要推导 Sn (n > 0) 的转换函数,最多只需已知 S0, S1, …, Sn-1 即可,有了这个递推关系之后,竟可以只已知 S0 的全部转换函数而推导出其他所有状态的非匹配转换函数!总结以上的方法,当需要求 Sn (n > 0) 的转换函数时,只需将当前已经匹配过的字符,跳过第一个后(即 c1, c2, …, cn)依次输入到已初始化的状态机中,状态机给出的状态即 Sn

设函数 g(Si, cm, cn) = f(f(f(…f(Si, cm), cm+1), cm+2), …, cn) (n > m),则有
f(Si, c) = f(g(S0, c0, ci-1), c) (i > 0, c ≠ ci)   ④

至此就可以从 S1 开始,依次根据已知的状态函数推导出状态机所有状态对全部输入的转换函数了。下面是一个由模式 mPattern 生成 KMP 算法状态机转换函数表的 Java 实现。

KMP 算法的 Java 完整实现包括测试用例已经托管于我的 GitHub,查看

参考文献
[1] Sedgewick R, Wayne K. Algorithms[M]. 人民邮电出版社, 2012.

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=272 )

优先队列与堆排序

队列(Queues)是应用中常见的数据结构,一个队列至少有“入队”和“出队”两个基本操作。队列具有“先入先出(First In First Out, FIFO)”性质,就像排队一样,入队会将新元素插入到队列的末尾,而出队会取出队列中排在最前的(也是最早入队的)一个元素。

优先队列(Priority Queues)的接口与基本队列一样,至少有“入队”和“出队”两个基本操作。与基本队列不同的是,优先队列的出队顺序不是先入先出,而是以队列中元素的健作为优先级出队,键最大(或最小)的元素最先出队,其次是键次大(或次小)的元素。键大优先出队的优先队列称为面向大元素的优先队列;键小优先出队的优先队列称为面向小元素的优先队列。为了方便,在没有特别说明的情况下,下文所有提到的优先队列均指面向大元素的优先队列。

要实现一个高效的优先队列并不十分容易,一个直观而简易的实现方式是使用有序链表。设 L 是一个按从大到小顺序排列的链表,使用这个链表充当优先队列。当有一个元素 N 需要入队时,只需从头到尾遍历队列,找到插入 N 之后不会破坏链表有序性的位置,将 N 插入链表;当需要出队一个元素时,因为链表的有序性保证了第一个元素一定是最大的元素,因此只需直接取出链表中第一个元素返回,并删除这个元素。

使用链表构建的优先队列入队效率比较低,假设队列长度是 n 那么入队平均需要遍历 n / 2 个结点;而它的出队效率又非常高,显然,它出队的时间复杂度是常数 1。造成链表优先队列入队效率底的根本原因是搜索的效率低,在一个有序的数据结构中逐个元素顺序搜索是不明智的。以往的经验告诉我们,在有序的数据集合中进行查找,高效的做法是用二分的思想。而链表不支持随机访问,在数组中运用的二分法查找在链表中是无效的。

实现优先队列,另一个更聪明的办法是用二叉树来组织数据。维护一棵始终满足以下条件的二叉树,就能实现一个较高效的优先队列:

  1. 是一棵完全二叉树;
  2. 每个结点的键都比它的非空子结点的键大。

通常的二叉树是以链式结构组织的,树各个结点的物理存储位置是离散的,每个结点通过保存该结点的两个子结点以及父结点的引用(或“指针”)来彼此关联。而为了实现优先队列,我们按从上到下、从左到右的顺序将一棵二叉树组织到数组里,所有结点都在数组中连续存放,形成一个二叉堆。按习惯,二叉堆又简称“”,下文也遵循习惯使用简称“堆”指二叉堆。之所以用堆的形式来组织优先队列而不是通常的链式结构,是因为堆能更快更容易地实现优先队列入队和出队的操作,具体的理由总结如下:

  1. 完全二叉树除了底部外所有结点的子结点全都非空,且生长点只能在树的底部,用数组来存放它既没有空位,又无需在插入之后移动元素;
  2. 数组支持随机访问,访问效率优于链式结构的二叉树;
  3. 无需每个结点都保存其子结点或父结点的引用,只需对自身的索引进行简单的运算即可找到子结点或父结点;
  4. 插入新元素时,能非常容易地找到插入点。

假设用数组 a[] 来组织上面说到的堆,为了方便,元素 a[0] 置空不用,从 a[1] 开始存放堆的所有元素。这样,堆的根结点即是 a[1],假设存在某个结点 a[n] (n > 1),那么它的父结点就是 a[n / 2],它的左子结点是 a[2 * n],它的右子结点是 a[2 * n + 1]。

实现对优先队列的入队就是当向堆插入一个元素,先将新的元素插入到堆的尾部成为一个新结点。此时,这个结点很可能并不比它的父结点小,因此堆的性质之一“每个结点的键都比它的非空子结点的键大”可能会遭到破坏,必须做一些处理使堆重新满足这个条件。

这些处理称为结点的“上浮”。结点上浮的目的是将新插入的结点移动到合适的位置,使这个结点既大于它所有的子结点,又小于它的父结点。结点上浮的操作算法很简单:比较被上浮的结点与它的父结点的大小,如果当前结点大于父结点,则交换它们的位置;然后重复上述操作,直到当前结点不大于父结点或者当前结点已经是根结点。下面的 Java 代码实现了堆结点上浮的操作。

实现对优先队列的出队就是读出堆顶部的结点,然后删除它。删除一般二叉树的一个结点,就有可能留下两个孤立的子树,此时需要在树中删出一个没有非空子结点或只有一个非空子结点的结点来填补到删除结点后产生的空缺中。删除堆顶的一个结点,同样需要找一个结点来填补空缺,最容易的办法是删出堆底的结点,填补到堆顶空缺的位置,然后堆大小减 1。这时填补到堆顶的结点几乎一定是会比它的左右子结点都小的,不满足优先队列堆要求的条件,需要做一些处理使堆重新满足条件。

这些处理称为结点的“下沉”。结点下沉的目的是将处于堆顶部的小结点向堆底移动,使这个结点既大于它所有的非空子结点,又小于它的父结点。像结点的上浮操作一样,结点的下沉操作也很容易实现。先从结点的左右子结点中找出非空且较大的那一个,被下沉的结点与之交换,重复这个过程,直到当前结点大于它的所有非空子结点或者它的所有子结点均为空。下面的 Java 代码实现了堆结点的下沉操作。

如果将一串乱序数据全部入队到一个优先队列中,然后从优先队列中出队所有的数据,数据出队时将是有序的,这无疑提供了一个新的排序思路。

堆排序就是利用了上述优先队列思想的排序算法。对一个乱序的数组进行堆排序时,分为两个阶段,第一阶段称为建堆,将数组原地组织成一个符合上文中描述的条件的堆;另一个阶段把这个堆当作优先队列,不断地出队元素,并把出队的元素填到因出队而空缺的位置。当堆逐步缩小直至为空时,堆排序完成,数组变成了有序数组。

如何对一个数组实现原地建堆是一个值得思考的问题,为了讨论问题方便,先定义“堆有序”指一个堆满足上文提到的优先队列堆的所有条件。显然,一个大小为 1 的堆一定是堆有序的。如果一个堆 H 的左右两个子堆都是堆有序的,只要对这个堆的根结点做一次下沉操作,堆 H 也一定会转化为一个堆有序的堆。设有一个乱序数组 a[1…n],把它看作一个堆,Hi 表示以 a[i] 为堆顶的子堆,则可以得出 Hn/2+1, Hn/2+2, …, Hn 均是大小为 1 的子堆,换言之,这些子堆都是堆有序的,数组 a 中有半数子堆是堆有序的。为了使整个数组都成为堆有序的堆,只要先后对 a[n/2], a[n/2-1], …, a[1] 执行下沉操作即可。

建堆完成后,就可以开始第二步骤了。将数组当作一个优先队列,出队一个元素 N1,此时 a[n] 处因出队产生了一个空缺,将 N1 填补到 a[n] 处,继续出队 N2,填补到 a[n-1] 处,直到出队 Nn,填补到a[1] 处,数组 a 排序完成。

值得注意的是,在实际运用中,大部分程序设计语言的数组第一个元素的索引并不是 1 而是 0,但只要在上述算法的基础上对索引稍作处理即可实现堆排序。

堆排序无需额外的空间,时间复杂度也能达到比较理想的 O(nlogn) 的级别,是一种优秀的排序算法。

本文提到的全部算法均已用 Java 实现,代码托管于 GitHub,查看

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=250 )