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