字符串查找算法
15 Oct 2016字符串查找是很常见的功能, 但是实现一个高效的查找算法还是挺不容易的. 这两天花了点时间理解了几种常见的算法 (KMP, BM, BMH a.k.a Horspool), 这里记录一下, 方便以后查找.
约定
Pat: 模式字符串, Str: 待搜索的字符串.
Brute-force
先介绍最容易理解的暴力破解法. 这算法比较直观, 就是将 Pat 与 Str 的字符一个个比较, 如果匹配失败就将 Pat 向右移动一位再进行比较, 直到匹配完成.
直接上算法
public int bruteForce(String str, String pat) {
int m = pat.length();
int n = str.length();
int i = 0, j = 0;
while (j < m && i < n) {
if (str.charAt(i) == pat.charAt(j)) {
i++;
j++;
continue;
}
i = i - j + 1;
j = 0;
}
if (j == m) {
return i - j;
}
return -1;
}Knuth–Morris–Pratt
Brute-force 算法之所以不够高效是因为, 当匹配失败时, 部分匹配的字符会在 Pat 右移一位后再次比较, 这就带来了不必要的开销. KMP 算法就是在此基础上改进的.
Knuth DFA 版本
Knuth 最开始的算法实现是基于 DFA (有限状态机) 的, 假如 Pat 的长度为 M, 那么 DFA 的状态共有 M + 1
Pat: abc
DFA: (0) --a--> (1) --b--> (2) --c--> (3)
我们顺序读取 Str 的每个字符, 每读取一个就会改变 DFA 的状态, 当 DFA 处于 (3) 状态时就表示字符串匹配完成.
假如 DFA 构造完成了, 那么我们该如何利用改造出来的 DFA 来搜索呢?
class KMP {
publiv int[][] initDfa(String pat) {
// TODO
}
public int search(String pat, String str) {
int[][] dfa = this.initDfa(pat);
int j = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
j = dfa[c - 'a'][j];
if (j == pat.length()) {
return i - j + 1;
}
}
return -1;
}
}有了 DFA 搜索就很简单了, 只用依次读取字符, 再从 DFA 里获取下一个状态就行了.
如何构造 DFA
KMP 算法最核心的问题就在于构造 DFA. 我们用一个矩阵来表示 DFA, 矩阵的行数为所有的可输入字符, 列数为 DFA 的状态数
以 aba 为例 (假设我们需要匹配的字符串只可能由 abc 组成), 我们会得到下面的 DFA
| 可输入字符\Pat | a | b | a |
|---|---|---|---|
| a | 1 | 1 | 3 |
| b | 0 | 2 | 0 |
| c | 0 | 0 | 0 |
假如 Str 为 acaba, 那么依次读取字符, DFA 的状态变化为
DFA[0][0]: 1
DFA[1][2]: 0
DFA[0][0]: 1
DFA[1][1]: 2
DFA[2][0]: 3
我们先考虑 DFA 的第一列 (状态 0), 只有当输入字符和 Pat 的第一个字符相同, DFA 才会进入 (1) 状态 (即匹配了一个字符),
其它任何字符都不会匹配, 所以 DFA 会停留在 (0) 状态 (即没有字符匹配)
下面我们考虑第二列 (状态 1), 只有当输入字符合 Pat 的第二个字符相同时, DFA 才会进入 (2) 状态, 那其它不匹配的字符呢?
可以这样思考, 当输入字符不匹配时, Pat 如果按照暴力破解法会右移一位, 此时 DFA 会进入 (0) 状态, 那么 (2)
状态在不匹配的时候的跳转情况和 (0) 状态是一样的.
最后考虑第三列 (状态 2), 同上, 只有匹配的时候才会进入 (3) 状态. 不匹配的时候, Pat 会右移一位, 此时 DFA 进入 (0),
但是此时我们知道, 即将和 Pat 匹配的字符是 Pat 的第二个字符 (因为刚才匹配了), 所以 DFA 会进入 DFA[0][Pat[1]] 状态,
用上面的例子来说明就是, DFA[0][1] (b 在 Pat 中的 index 是 1), 即状态 (0), 所以第三列不匹配的情况和状态里 (0)
是一样的.
总结下就是, 当在某个状态不匹配时, DFA 会进入 (0) 状态 (右移一位), 这时我们可以根据已经匹配的字符 (除去第一个字符,
因为 Pat 右移了一位) 来推断当匹配到当前字符时 DFA 会处于哪个状态. 本质也是一种递归的思想,
我们可以根据之前状态的跳转规则来计算出当前状态的跳转规则.
最后构造 DFA 的算法实现如下:
class KMP {
private static final String ALPHABETS = "abc";
private int[][] initDfa(String pat) {
int m = pat.length();
int r = KMP.ALPHABETS.length();
int[][] dfa = new int[r][m]; // init with 0
dfa[pat.charAt(0) - 'a'][0] = 1; // init first column
int x = 0; // previous state
for (int i = 1; i < pat.length(); i++) {
for (int j = 0; j < r; j++) { // copy x state to current
dfa[j][i] = dfa[j][x];
}
int ci = pat.charAt(i) - 'a';
dfa[ci][i] = i + 1; // mached
x = dfa[ci][x]; // update x
}
return dfa;
}
public int search(String pat, String str) {
int[][] dfa = this.initDfa(pat);
int j = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
j = dfa[c - 'a'][j];
if (j == pat.length()) {
return i - j + 1;
}
}
return -1;
}
}算法里的 x 是比较重要的, 按照之前的描述我们是需要每次都回溯的, 但是因为 Pat 的字符串是不变的, 也就是说, 每次回溯时前面的部分都是一样的, 所以用 x 记录一下省得每次都回溯.
这个就是 Knuth DFA 版的 KMP 算法, 我觉得这个版本是比较好理解的. 但这个版本有一个缺点就是, 需要使用 MR (Pat 的长度乘以可输入字符的长度) 的额外空间. Pratt 在 Knuth 的 DFA 版本上改进了下, 只需要额外使用 M 的空间 (即和可输入字符长度无关, 当然效率会低点), 于是就有了现在通常所说的 KMP 算法. (Morris 在 KMP 算法里做了什么? 呃, Wiki 的说法是, 他是独立完成这个算法的. 总结就是, Knuth 完成了 DFA 版本的, Pratt 改进了, Morris 独立完成了)
Pratt 改进版
发现用 Java 写算法不利于表现算法的本质, 所以之后还是用 Python 写算法吧.
在暴力破解算法中我们用指针 i 指向 Str 中待匹配的字符, j 指向 Pat 中待匹配的字符.
现在回过头来看暴力破解法, 当 i 和 j 指向的字符不匹配时, i 移动到 i - j + 1 位置,
j 重置为 0, 然后继续匹配. 仔细想想我们可以发现, Str 中 i - j + 1 到 i 之间的字符我们是知道的,
所以当暴力破解法中 i 再次走到现在这个位置时, j 所处的位置我们是可以提前算出来了.
跳转表
假如我们现在有张跳转表 jump, jump[j] 表示当 Pat[j] != Str[i] 时 j 的下一个值应该是多少.
那么我们便可以利用 jump 来完成搜索算法
jump = []
def pratt(pat, s):
m = len(pat)
if m == 0:
return 0
j = 0
i = 0
for c in s:
while j > 0 and c != pat[j]:
j = jump[j]
if c == pat[j]:
i += 1
j += 1
else: # j == 0 and c != pat[j]
i += 1
if j == m:
return i - j
return -1构造跳转表
下面我们来构造跳转表, 我们先考虑 jump 的前两项, 当 j 等于 0, 1 时, 显然 j 需要重置为 0.
那么当 j 大于 1 时呢? 等于用 Pat 去匹配 Pat[1:], 看匹配到当前位置时 j 等于多少.
def initJump(pat):
m = len(pat)
jump = [0, 0]
if m < 3:
return jump
j = 0
for c in pat[1:-1]:
while j > 0 and c != pat[j]:
j = jump[j]
if c == pat[j]:
j += 1
jump.append(j)
return jumpBoyer-Moore
KMP 可以说是 Brute-Force 的改进版. BM 算法也差不多, 不过是基于反向的 Brute-Force 的算法:
def bruteForceRev(s, pat):
m = len(pat)
n = len(s)
i = m - 1
j = m - 1
while i < n and j > -1:
if s[i] == pat[j]:
i -= 1
j -= 1
else:
i += m - j
j = m - 1
return i + 1 if j == -1 else -1Boyer-Moore-Horspool
完整的 BM 算法实现起来比较麻烦, BMH 是它的简化版本, 不过匹配起来依旧很快.
BMH 是根据当前不匹配的字符来决定pat 的位移的. 比如说, 我们从右向左的匹配, 匹配第一个字符就失败了,
同时这个字符也没有在 pat 中出现过, 那么我们可以放心大胆的将 pat 直接向右位移 len(pat) 个距离.
可以看到决定位移的距离的关键在于当前不匹配的那个字符是否在 pat 中出现过, 出现的位置是多少.
这就是所谓的坏字符表.
坏字符表
我们用一个字典来表示坏字符表, 每一个在 pat 中出现的字符都在这个字典里, 对应的值为这个字符在 pat
中最后一次出现的位置. 比如 pat = 'aba' 那么坏字符表就等于 {'a': 2, 'b': 1}
我们先看假如我们现在有了坏字符表, 我们应该怎么匹配呢?
bad = {}
def BMH(s, pat):
m = len(pat)
n = len(s)
i = m - 1
j = m - 1
while i < n and j >= 0:
b = s[i]
if b != pat[j]:
if b in bad:
inc = m - 1 - bad[b]
inc = m - j if inc < m - j else inc # 在反向 BF 中 i 至少会增加 m - j
else:
inc = m
i += inc
j = m - 1
else:
i -= 1
j -= 1
return i + 1 if j == -1 else -1需要注意的地方已经在代码中注释了. 剩下的就是构造坏字符表了, 根据定义我们很容易就可以实现如下的代码:
def initBad(pat):
bad = {}
for i, v in enumerate(pat):
bad[v] = i
return bad完整 BM 算法
完整的 BM 算法不单单利用了不匹配的字符的信息还利用了已经匹配的字符的信息来决定位移的距离. 也就是所谓的好字符表. 乍看下觉得好字符表的构造应该和 KMP 的差不多, 然而, 因为匹配的顺序 (从右向左) 和位移的方向 (从左向右) 不一样, 导致好字符表的构造的远比 KMP 的跳转表的构造复杂. Algorithm 一书中作者 Robert Sedgewick 直接一句:
In general, the pattern at the end might appear elsewhere, so we need an array of restart positions as for Knuth-Morris-Pratt. We will not explore this approach in further detail because it is quite similar to our implementation of the Knuth-Morris-Pratt method.
就这么一笔带过了! 果然境界不一样啊.
这里我也不打算详细的叙述 (这文章已经断断续续的写了好多天了), 我就贴个代码好了:
def BM(s, pat):
n = len(s)
m = len(pat)
jump = self.initJump(self.initBorder(pat))
i = m - 1
j = m - 1
while i < n and j >= 0:
if s[i] != pat[j]:
i += jump[j]
j = m - 1
else:
i -= 1
j -= 1
return i + 1 if j == -1 else -1
def initBorder(pat):
m = len(pat)
border = [m] * m # last one will always equal to `m`
for j in range(m - 1)[::-1]:
prev = border[j + 1]
while prev != m:
if pat[j] == pat[prev - 1]:
border[j] = prev - 1
break
prev = border[prev]
else:
border[j] = m - 1 if pat[j] == pat[m - 1] else m
return border
def initJump(border):
m = len(border)
if m == 0:
return []
jump = [0] * m
jump[m - 1] = 1
j = border[0]
for i in range(m):
b = border[i]
if b != m:
jump[b - 1] = m - i
if jump[i] != 0:
continue
while i >= j:
j = border[j]
jump[i] = j + m - i - 1
return jump总结
不管 KMP 还是 BM 都是在 Brute-Force (不管是从左往右还是从右往左比较) 的基础上, 利用已经匹配的和当前不匹配的字符来优化位移移动的距离.
将近一个礼拜断断续续的把这篇文章写完了, 并且把文中的算法都自己实现了一遍. 实现的过程中各种 +1 -1 搞的头都大了.
写算法的过程中感觉 大局观 很重要, 不能一开始就陷入细枝末节中. 比如, 可以先假设跳转表实现了, 先利用跳转表实现搜索算法.
ps. 在 LeetCode 上分别跑了下 KMP, BM, BF 算法, 最后发现, KMP 最慢, BF 最快. 没错, Brute-Force 算法最快!