2015-08-22

字符串算法之——BK树

前言
基于前缀树的搜索
基于编辑距离树的算法
1. 编辑距离（Edit Distance）
2. 编辑距离树
总结

前言

　　有关于字符串的算法有很多应用场景，诸如：搜索，生物工程，基因序列等等。本文所涉及的算法是和字符串搜索相关的。假设有一系列的字符串集合dist[]，需要从中找出任意给定字符串A最相似的TopN字符串。

基于前缀树的搜索

　　前缀树：trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。trie树实际上是一个DFA（有穷状态向量机），通常用转移矩阵表示。行表示状态，列表示输入字符，(行, 列)位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移，但由于要线性查询，会造成效率低下。
　　缺点：只有前缀完全匹配的字符串才能匹配到。

基于编辑距离树的算法

编辑距离（Edit Distance）

　　又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）

编辑距离树

编辑距离的性质

　　假设有串A,B,C,dist[i,j]表示串i和j之间的编辑距离，则有三角不等式：
dist[A,B] + dist[B,C] >= dist[A,C]

建树规则

　　根据三角不等式，按照如下规则建立编辑距离树，树的数据结构为

public class BKTreeNode<T>{
	private T data;//数据节点
	private HashMap<Integer,BKTreeNode<T>> children;//孩子节点：key为与父节点的编辑距离，value为子树。
	private int distance;//与父节点的编辑距离
	...
}

　　以词典中的任意单词作为根节点，然后依次从dict[]中取单词dict[i]，计算与根节点的编辑距离K，将该节点加入到其子树，并设置边的权重为K。如果存在以边为K的子节点child，则用该单词dict[i]在意该子节点上进行迭代插入。一个单词key插入树过程如下：

0.初始化BKTree，树根为root，令：iterator <- root
1.将key插入iterator。如果iterator的data域为空，goto 2。如果iterator的data域不为空，goto 3;
2.将key置入iterator的data域，并计算key与iterator父节点的编辑距离，设置到iterator的distance域（如果iterator为根节点设置distance为0,则结束。否则goto 4）
3.计算key和iterator中data的编辑距离k，如果iterator.getChildren().get(k)为空，则创建一个BKTreeNode，将BKTreeNode的data域设置为key,如果不为空，则：iterator<-iterator.getChildren().get(k),并goto 1
4.结束
查找规则
　　假设需要返回最大的编辑距离为m的匹配的串，待查询字符串为key，字典为dict[],可以有如下推导：
计算key以root的编辑距离为d
key到root子节点的距离最大为m，则可以知道我们需要遍历：|d - m| < distance域的值 < d + m
将满足条件的节点加入队列，并继续深度遍历。不满足条件的则不再向下搜索（分支限界）。
　　问题：当字符串长度小于m的时候，则返回的列表可能不具备参考依据。所以这里，对满足条件的进行相似度判断
相似度的定义如下为：|dist-max(a.length()-b.length())|/max(a.length()-b.length()),当相似度达到一定阈值的时候才会被加入到返回列表。
总结
　　编辑距离树的查找是一个基于分支限界的多路搜索算法，并以编辑距离为搜索依据，并以相似度作为返回依据。对于返回的值按照相似度从大到小的顺序排列即可。

前言