标签归档:数据结构

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 )

红黑树:自平衡的二叉查找树(二)

前一篇博文展示了红黑树在二叉查找树基础上的改进,讨论了红黑树结点的几种变换以及实现了红黑树的插入算法。本文继续红黑树的话题,谈一谈红黑树结点的删除方法并在最后以测试用例对比红黑树和普通二叉查找树在性能上的差异。

在讨论红黑树的删除算法之前,先回顾一下在《键-值查找的基础——二叉查找树(Binary Search Tree)》一文中提到的二叉查找树的删除方法。在二叉查找树中删除一个典型的结点,要先通过查找操作找到被删的结点 N,然后再找到 N 的右子树中最小的结点 Nrmin,把 Nrmin 从原来的位置删出,替换到 N 的位置。那么,如果在红黑树中也用这样的方法实现删除是否可行呢?显然地,如果 Nrmin 在红黑树中恰好是一个红色结点,那么把它从红黑树中删出,再替换到 N 的位置是没有问题的。但如果 Nrmin 不巧是一个黑色结点,把它从红黑树中删出就会导致和在红黑树中插入一个黑色结点一样的问题:Nrmin 所在的子树的所有叶子结点与整棵树其他的叶子结点到树根的路径长度不相等了。

既然删去一个红结点不会影响红黑树的平衡,那么找到一种方法保证在删除操作发生的时候,最终被删去的结点一定是红色,是解决这个问题的一条思路。在研究红黑树插入算法的时候,提到了对结点左旋、右旋和颜色翻转等三种基本变换,可以发现一个规律,除了在根结点处外,红结点似乎不会凭空产生也不会凭空消失,它只会从一个子树旋到另一个子树,或者从左右子结点“汇聚”到父结点。上一篇博文中一幅向红黑树插入一个新红结点的动画很直观地展示了红链接从树的底端向树根传递的过程,可以看到,树底端的红结点通过一步一步的旋转、颜色翻转最终把根结点染红,后根结点重新被置黑,插入操作完成。如果把这个过程倒过来执行,先把根结点染红,再通过与颜色翻转相反的操作以及适当地左旋和右旋就可以把红色结点一步步下推到需要删除的地方,保证被删去的是一个红色的结点。

在一个典型的删除操作中,一共有两个查找步骤。一个是从根结点出发,找到要删除的目标结点 N;另一个是从 N 的右子结点出发,找到这棵子树中键最小的那个结点 Nrmin。这个查找的路径正好也是根结点通往 Nrmin 的路径,于是在红黑树删除的具体实现中,可以一边查找一边“调运”红色结点。典型情形下,要使 Nrmin 在删出时是红色结点,只需要确保这个原则成立:查找过程中保持查找的后继结点或后继结点的左子结点是红色,直至查找到 Nrmin。这是一个递归的条件,只要查找开始时在根结点处保证了这个条件成立,那么后续每一步查找都可以通过有限次的左旋、右旋及“反颜色翻转”使这个条件成立。特别地,在当 N 的右子结点是空结点的情形下,查找操作查到 N 即停止,也能保证 N 本身或 N 的左子结点是红色结点。

假设正在进行红黑树删除结点过程中的查找操作,当前结点是 Ncur,那么分以下几种情形分别执行不同的变换来维持上文中原则的成立。

(一)Ncur 是根结点且根结点的左右两个子结点都是黑色的,先把根结点染红。然后把根结点当作一般结点继续以下的流程。

(二)Ncur 的查找后继 Nnext 是它的左子结点

  1. Nnext 是红色的或 Nnext 的左子结点是红色的,后继满足原则,无需操作,继续查询后继;
  2. Nnext 不满足原则,但 Ncur 的右子结点是红色的,对 Ncur 执行左旋操作,继续查询后继;
  3. Nnext 不满足原则,而且 Ncur 的右子结点是黑色的,此时由于有原则约束, Ncur 一定是红色的(请思考为什么),对 Ncur 执行反颜色翻转操作,Ncur 的左右子结点都变成红色。这时检查 Ncur 的右子结点的左子结点是否也是红色,如果是,则先右旋 Ncur 的右子结点,再左旋 Ncur 以避免在查找路径之外的地方出现双红父子的问题,然后继续查询后继。

(三)Ncur 的查找后继 Nnext 是它的右子结点

  1. Nnext 是红色的或 Nnext 的右子结点是红色的,后继满足原则,无需操作,继续查询后继;
  2. Nnext 不满足原则,但 Ncur 的左子结点是红色的,对 Ncur 执行右旋操作,继续查询后继;
  3. Nnext 不满足原则,而且 Ncur 的左子结点也是黑色的,同样可得出 Ncur 一定是红色的。先对 Ncur 执行反颜色翻转操作,Ncur 的左右子结点都变成红色。这时检查 Ncur 的左子结点的左子结点是否是红色,如果是,则右旋 Ncur 以避免查找路径之外的地方出现双红父子,然后继续查询后继。

(二)和(三)的第 3. 种情形分别图示如下。

rbt-remove-1图1 左右子结点都为黑,查找后继是左子结点时的颜色变换

rbt-remove-2图2 左右子结点都为黑,查找后继是右子结点时的颜色变换

当删出、替换操作完成后,还需要从查找的终点开始沿查找路径向上回溯,清除之前操作遗留下来的双红父子结点以及右红子结点。这个操作与上篇博文中讲到的红黑树插入新结点后向上回溯恢复红黑树性质的操作非常相似,不再赘述。

至此,一棵完整的红黑树就已经可以实现了。为了检验算法的正确性,同时比较红黑树与一般的二叉查找树在不同的输入条件下的性能差异,我用 Java 分别实现了一个一般二叉查找树的符号表和一个红黑树的符号表。编写了一个测试用例,分别用一组相同的随机乱序数据和一组相同的有序递增数据测试两个符号表实现,并测试各自在进行插入、查询和删除操作中的耗时。另外还选择了一个使用类似技术实现的 Java 容器类 TreeMap 作为对照组,在同等条件下执行这个测试。

测试内容包括了:

(一)一个由 0~1,000,000 范围内的随机乱序整数(可能重复)组成的数组作为输入数据,数组长度为 100,000。

  1. 测试这十万个整数分别插入各符号表实现所花费的时间,以毫秒计;
  2. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮查找操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计;
  3. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮删除操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计。

(二)一个由 0~99,999 范围内的顺序排列的连续整数组成的数组作为输入数据,数组长度为 100,000。

  1. 测试这十万个整数分别插入各符号表实现所花费的时间,以毫秒计;
  2. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮查找操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计;
  3. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮删除操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计。

测试三次取平均值后的数据如下:

表1 随机乱序数据测试结果(单位为 ms)

Put Get Remove
Basic BST 170.7 53.3 62.7
RBT 171.0 72.3 221.7
Java TreeMap 139.0 88.0 65.3

表2 连续递增数据测试结果(单位为 ms)

Put Get Remove
Basic BST 42,475.7 84,783.0 42,424.3
RBT 122.7 33.7 158.7
Java TreeMap 67.3 26.0 18.0

结果显示,在测试数据随机分散的情况下,普通二叉查找树和红黑树的性能接近,甚至普通二叉查找树性能稍优于红黑树;而当用连续有序的测试数据测试时,普通二叉查找树的性能变得极差,操作耗时增加了数千倍,同时红黑树仍然保持了稳定的性能,耗时没有明显的变化。

本文中提到的全部算法和测试用例均已用 Java 实现,GitHub 版本库地址:查看

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