首页 > 代码库 > 超酷算法-BK树

超酷算法-BK树

前几天无意间遇到一个博客,觉得写得挺好的,自己之前的时候有个不好的习惯,那就是遇到了好资源第一反应就是收藏起来然后却很少再看!!这是坏习惯,要改!于是今天就开始通读了,读的第二篇是BK树。觉得有点意思,于是乎就萌发了写个博客啥的,但是呢,我发现已经有人翻译了。那还干嘛重复发明轮子呢,鉴于原作者声明禁止转载,那就算了吧,想看原文的来这里。

下面简单说明一下这个算法,确实不难,只是思路有点巧妙。

BK树解决一个什么问题呢,简单而言就是找相似字符串,比如说"book"跟"boon"是不是只差一个字母,很相似了吧。

我们先来定义相似:采用编辑距离来度量两个字符串之间的相似程度。字符串A和字符串B的编辑距离就是至少需要几次操作(删除一个字母,插入一个字母,更换一个字母)才能使得A变成B。上面提到的"book"以及"boon"的编辑距离就是1,因为只需要将字母‘k‘更新为‘n‘就可以达到目的了。

接下来我们来看编辑距离的一个性质,我们用L(A,B)来表示字符串A和字符串B之间的编辑距离。那么我们为了找到与A距离不超过m的字符串C,那么它与字符串B的距离为多少呢?答案是L(A,B)-m <= L(B,C) <= L(A,B)+m。为什么?m步之内A、C可以相互转换,而L(B,C)步之内B、C可以相互转换,于是乎m+L(B,C)步之内,A、B之间必然可以转换,于是有L(A,B) <= L(B,C)+m;同理可知 L(B,C) <= L(A,B)+m。

那么这样一来的话,BK树就可以出场了。BK树的边是有编号的,编号值就是边的两个节点直接的编辑距离。

我们先在字符串集合中任选一个字符串Z作为根节点,然后每次从集合中取出一个字符串X,将其插入树中。插入规则是这样的,首先计算X与根节点Z的编辑距离L(X,Z),然后将这个节点插入到Z的编号为L(X,Z)的孩子那边;递归直到到达X可以成为叶子节点。

我们查找字符串A的相似字符串的时候(假设编辑距离为2以内就算相似),那么从根节点开始寻找,先计算L(Z,A),这个时候我们就知道了与A编辑距离为2的字符串只可能存在于Z的编号为L(Z,A)-2到编号为L(Z,A)+2之间的那些子树里面,于是乎就递归查找去吧。

 

超酷算法-BK树