11

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

 3 years ago
source link: http://maskray.me/blog/2013-02-10-bk-tree
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

Approximate string matching

近似字符串匹配问题。

Levenshtein edit distance

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

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

下面给出Ruby实现：

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
d[m & 1][n]

另外，编辑距离是个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，而根据三角不等式，我们知道：

<= 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实现：
```ruby
class BKTree
attr_accessor :root, :child
def insert s
if @root.nil?
@root = s
@child = Hash.new {|h,k| h[k] = BKTree.new }
d = levenshtein @root, s
@child[d].insert s
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
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)

Share Comments


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK