使用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 求编辑距离，若在阈值内则输出。对于长为m和n的两个串，朴素的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，而根据三角不等式，我们知道：

dict(a,b)-k <= dist(c,b) <= dist(a,b)+k

注意到所有的c都满足这个不等式，也就是说我们不需要考虑整个字符串集合，只需要考虑和a的编辑距离在某个特定区间内的所有字符串。

如何获取和枢轴a的编辑距离在某个特定区间内的所有字符串呢？只需要对于所有不同的编辑距离分类，令a有若干棵子树，分别表示和a编辑距离为0的字符串的集合、和a编辑距离为1的字符串集合……而这些子树的任务是：在子树内找出所有和询问串的编辑距离在阈值内所有字符串，和原问题形式相同，不难想到对子树用同样方法递归构建Burkhard-Keller树。

然后考虑如何处理询问。先测试根节点的字符串a和询问串b的编辑距离是否在阈值k内，是则输出。接着根据三角不等式得到一个区间[dist(a,b)-k .. dist(c,b)-k]，得到一系列可能有候选字符串的子树，递归处理。

下面给出Ruby实现：

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
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)