使用Burkhard-Keller tree优化近似串匹配

Approximate string matching

近似字符串匹配问题。

Levenshtein edit distance

在metric space中衡量两个字符串差异程度的一个指标,即通过一系列单字符的编辑操作把字符串A变成字符串B所需的最小编辑次数,其中的编辑操作可以是插入字符、删除字符以及修改字符。

计算编辑距离有个经典的Wagner-Fischer算法,使用了动态规划,用d(i,j)表示把字符串A的前i个字符变成字符串B的前j个字符所需的最小编辑次数(即子串的编辑距离)。

下面给出Ruby实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
def levenshtein a, b
m, n = a.size, b.size
d = [(n+1).times.to_a, [0]*(n+1)]
1.upto m do |i|
pre, cur = d[i-1 & 1], d[i & 1]
cur[0] = i
1.upto n do |j|
diff = a[i-1] == b[j-1] ? 0 : 1
cur[j] = [cur[j-1]+1, pre[j]+1, pre[j-1]+diff].min
end
end
d[m & 1][n]
end

另外,编辑距离是个metric,也就是说三个字符串间满足三角不等式:

dist(a, b) + dist(b, c) >= dist(a, c)

可以这样理解,把a变成b的最少修改操作和b变成c的最少修改操作拼起来就得到了把a变成c的一个可行修改操作,编辑次数为dist(a,c),而最小编辑次数肯定不会比这个数大。

Burkhard-Keller tree

给定一个字符串集合S,有若干询问。每个询问的输入是一个字符串a,输出是字符串集合S
中和a的编辑距离在某个阈值内的所有字符串,即:{b | levenshtein(a,b) <= k},其中k是阈值。

直观想法就是枚举S中的每个串,一一和 a 求编辑距离,若在阈值内则输出。对于长为mn的两个串,朴素的Wagner-Fischer算法时间复杂度是O(m*n),又要对集合中每个串都做这样的操作,比较慢。

于是就有两个优化策略:

优化编辑距离的计算

对于k为常数的情况,可以利用性质d(a, b) >= abs(len(a)-len(b)),动态规划表格中很多格子的值必然大于k,而我们计算编辑距离的意图是判断是否在阈值内,所以对于这些值必然大于k的格子我们是不感兴趣的,可以避免计算。我们只需要只计算一条diagonal band,这样可以把时间复杂度优化到O((m+n)*k)

另外对于这样的unit-cost Levenshtein edit distance问题,还可以采用一些bit-parallel方法进行常数优化。

减少字符串集合中的字符串枚举次数

a为字符串集合中任意一个字符串,对于询问字符串b,计算出它们的编辑距离dist(a, b)。对于每一个我们感兴趣的字符串c,都满足dist(c,b) <= k,而根据三角不等式,我们知道:

<= dist(c,b)="" <="dist(a,b)+k```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
注意到所有的`c`都满足这个不等式,也就是说我们不需要考虑整个字符串集合,只需要考虑和`a`的编辑距离在某个特定区间内的所有字符串。
如何获取和枢轴`a`的编辑距离在某个特定区间内的所有字符串呢?只需要对于所有不同的编辑距离分类,令`a`有若干棵子树,分别表示和`a`编辑距离为0的字符串的集合、和`a`编辑距离为1的字符串集合……而这些子树的任务是:在子树内找出所有和询问串的编辑距离在阈值内所有字符串,和原问题形式相同,不难想到对子树用同样方法递归构建Burkhard-Keller树。
然后考虑如何处理询问。先测试根节点的字符串`a`和询问串`b`的编辑距离是否在阈值`k`内,是则输出。接着根据三角不等式得到一个区间`[dist(a,b)-k .. dist(c,b)-k]`,得到一系列可能有候选字符串的子树,递归处理。
下面给出Ruby实现:
```ruby
class BKTree
attr_accessor :root, :child
def insert s
if @root.nil?
@root = s
@child = Hash.new {|h,k| h[k] = BKTree.new }
else
d = levenshtein @root, s
@child[d].insert s
end
end
def query k, s, &block
return unless @root
d = levenshtein s, @root
yield @root if d <= k
([d-k, 0].max .. d+k).each do |i|
if t = @child.fetch(i, nil)
t.query k, s, &block
end
end
end
end
strs = ['cinnabar', 'cinnabaric', 'cinnabarine']
tree = BKTree.new
strs.each {|s| tree.insert s }
puts '--0--'
tree.query 0, 'cinnabaric', &method(:puts)
puts '--1--'
tree.query 1, 'cinnabaric', &method(:puts)
puts '--2--'
tree.query 2, 'cinnabarine', &method(:puts)