纠错利器 BK树

缘起

有木有对搜狗拼音输入法中的自动纠错功能感到神奇? 这种功能的实现就和本文要讲解的BK树有关.

分析

BK树（Burkhard-Keller），是一种基于树的数据结构，被设计于快速查找近似字符串匹配，比方说拼写纠错，或模糊查找，当搜索”aeek”时能返回”seek”和”peek”。BK树在1973年由Burkhard和Keller第一次提出.

在定义BK树之前，我们需要预先定义一些操作。为了索引和搜索字典，我们需要一种比较字符串的方法。编辑距离（ Levenshtein Distance）是一种标准的方法，它用来表示经过插入、删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数。

BK树是多路平衡搜索树. 它（记为parent）的子节点集合是一个Map，键是子节点到parent的距离(所以parent到各个子节点的距离是各不相同的)，值就是子节点本身. 然后往BK树中添加节点的话，就是从根节点中加入，如果发现和当前节点的距离为0的话，表明BK树中已经存在了此节点，就不必再加入了. 否则的话，看看有没有当前节点的子节点与待加入的单词和当前节点的距离相等（因为已经说过了——parent的所有孩子到parent的距离各不相同.）,如果有的话，则递归将其加入到孩子节点为根的BK子树中去（所以子节点为根的BK子树上所有的节点到当前节点的距离和子节点到当前节点的距离相等），否则的话，将其加入当前节点的BK树(依旧维护了当前节点的所有子节点到当前节点的距离各不相同这一特点).

综上所述，BK树的特点有

  1. 节点P的任何子节点C到P的距离都不相等， 而且严格大于0
  2. 节点C的父节点为P,则C为根的BK子树上的任何一个节点到P的距离和C到P的距离相等.

讲完了BK树的构建，下面讲BK树的查询. 如果当前节点和待查询的单词的距离小于BK树配置的查询范围的话，就将当前节点加入到结果集中去，否则的话就不加，然后搜索其子节点, 等等！ 如果遍历所有子节点的话，则就是搜索整棵树了，效率就太低了，BK树的效率就无从谈起了. 所以这里利用了距离的三角不等式——算出有可能的节点距离当前节点距离的范围, 然后只需要搜索这些子树就可以了，极大的缩减了搜索的范围，试验表明，编辑距离=1要搜索的节点数不会超过整棵BK树节点个数的5-8%，编辑距离=2不会超过树的17-25%，这可比检查每个节点改进了一大步啊！

至于编辑距离如何计算? 这是经典的DP问题了. 看看下面的代码就明白了了.

下面给出BK树的java实现（唉，用java写封装就是方便）

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
package com.yfs.bk;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * BK树, 对外仅仅暴露 1. 构造器 2. 追加（put） 3. 查询（query） 4. 设置BK树的查找范围
 * 
 * 上述4个接口
 * 
 * 
 * @author yfs
 *
 */
public class BKTree {

	/**
	 * 使用words集合进行BK树的初始化
	 * 
	 * @param words
	 */
	public BKTree(Collection<String> words) {
		for (String word : words) {
			put(word);
		}
	}

	/**
	 * 追加接口（有可能初始化完毕之后，用户觉得还不够，还得往里面加一些单词）
	 * 
	 * @param word
	 */
	public void put(String word) {
		if (root == null) {
			this.word = word;
			root = new BKTree(word);
		} else {
			add(word, root); // 根节点已经存在了, 就直接从根节点加入到BK树中去了
		}
	}

	/**
	 * 查询接口
	 * 
	 * @param target
	 *            要找的单词(即用户通过输入法输入的单词)
	 * @return 返回相似的单词（即词库中纠错的单词），这些单词保存在results中
	 */
	public void query(String target, Set<String> results, BKTree root) {
		if (root == null) {
			return;
		}
		int distance = LevensteinMetricSpace.distance(target, root.word); // 计算用户输入的单词和当前节点的单词的编辑距离
		if (distance <= radius) { // 如果在查找范围之内
			results.add(root.word);
		}
		// 开始查询子节点
		for (int i = Math.max(1, distance - radius); i <= distance + radius; i++) { // 根据编辑距离的三角不等式,
																					// target距离root有distance距离，而待加入results中的单词距离target<=radius的距离，所以待加入results的单词离root的距离<=radius+distance，但是>=abs(distance-radius)，
																					// 但是既然是root的子节点, 所以距离都是>=1的,
																					// 所以这里取max
			BKTree child = root.children.get(i);
			if (child != null) {
				query(target, results, child); // 递归子节点
			}

		}
	}

	/**
	 * 设置当前BK树的查找范围，这算是BK树的配置项
	 * 
	 * @param radius
	 */
	public void setRadius(int radius) {
		this.radius = radius;
	}

	/** 根节点 */
	private BKTree root;

	/** 当前节点代表的字符串 */
	private String word;

	/** BK树查找的范围，即编辑距离多近的时候会被列入纠错单词 默认值是1 */
	private int radius = 1;

	/** 子节点，BK树是多路平衡查找树 map的key是本节点的子节点与本节点的编辑距离， value就是子节点本身 */
	private Map<Integer, BKTree> children = new HashMap<>();

	private BKTree(String word) {
		this.word = word;
	}

	private void add(String word, BKTree root) { // root是当前根节点,word是要加入的单词
		int distance = LevensteinMetricSpace.distance(root.word, word); // 计算加入的单词和当前根节点的编辑距离
		if (distance == 0) { // 已经存在，不需要加入了
			return;
		}
		BKTree child = root.children.get(distance);
		if (child == null) { // 如果不存在和word一样和root距离相等的子节点的话
			root.children.put(distance, new BKTree(word)); // 直接加入,成为root的新的子节点
		} else { // 存在的话，就递归地将该节点加入到child下面，所以我们知道了BK树任何节点的直接子节点们和它的距离都是不相等的
			add(word, child);
		}
	}

	/**
	 * 两个单词wordA和wordB之间的编辑距离（老外叫 Levenstein 距离，
	 * 下简称距离）指的就是wordA最少需要通过几步合法操作能变成wordB. 其中所谓的合法操作指的是将一个字符替换成另一个字符，插入一个字符，删除一个字符
	 * 但是这些合法操作的代价（cost）不一样.
	 * 
	 * @author yfs
	 *
	 */
	private static class LevensteinMetricSpace {

		private static final int INSERTCOST = 1;
		private static final int DELETECOST = 1;
		private static final int SUBSTITUDECOST = 2; // 这里的代价其实可以做更细致的处理, 这里认为替换的代价比删除或者新增更加高昂

		private static int distance(String a, String b) { // 从单词a变到单词b的Levenstein距离, 使用DP， 算法复杂度是O(n*m)
			int n = a.length();
			int m = b.length();
			int[][] cost = new int[n + 1][m + 1]; // cost[n][m] 就是a[0,...,n-1] 和 b[0,..,m-1]的距离, 下面使用dp计算
			cost[0][0] = 0;
			for (int i = 1; i <= n; i++) {
				cost[i][0] = i * INSERTCOST; // a[0,...,i-1] 和 空串之间的距离
			}
			for (int j = 0; j <= m; j++) {
				cost[0][j] = j * INSERTCOST; // 空串与 b[0,...,j-1]之间的距离
			}
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= m; j++) { // 开始dp计算 cost[i][j], 即a[0,...,i-1]和b[0,....,j-1]之间的距离
					// 我们想想 a[0,...,i-1]变化到 b[0,...,j-1] 有几种手段呢? 在这些手段中取小即可
					// 1. a[0,...,i-2]变化到 b[0,...,j-1] 然后删掉a[i-1]
					// 2. a[0,...,i-1]变化到 b[0,...,j-2] 然后新增b[j-1]
					// 3. 如果a[i-1]=b[j-1]的话，a[0,...,i-2]变化到 b[0,..,j-2]即可
					// 4. 如果a[i-1]!=b[j-1]的话, a[0,...,i-2]变化到 b[0,..,j-2] 然后a[i-1]替换为b[j-1] 即可
					// 总共就这4种, 注意，a[i-1]=b[j-1] 未必cost[i][j]就是 cost[i-1][j-1],
					// 因为有的时候还不如从一个短的变化到长的，然后删掉呢!
					int first = cost[i - 1][j] + DELETECOST; // 第一种
					int second = cost[i][j - 1] + INSERTCOST; // 第二种
					int third = cost[i - 1][j - 1]; // 第三种
					int fourth = cost[i - 1][j - 1] + SUBSTITUDECOST; // 第四种
					cost[i][j] = first; // 预设第一种
					if (cost[i][j] > second) {
						cost[i][j] = second;
					}
					if (a.charAt(i - 1) == b.charAt(j - 1)) {
						if (cost[i][j] > third) {
							cost[i][j] = third;
						}
					} else {
						if (cost[i][j] > fourth) {
							cost[i][j] = fourth;
						}
					}
				}
			}
			return cost[n][m];
		}

	}

	public static void main(String[] args) {
		List<String> words = new ArrayList<>();
		words.add("hello");
		words.add("shell");
		words.add("holl");
		words.add("helliii");
		BKTree bkTree = new BKTree(words);
		Set<String> results = new HashSet<>(); // 其实可以使用带排序功能的集合，这样可以类似于搜狗输入法那样将更为相似的单词放在前面
		bkTree.query("helli", results, bkTree.root); // helli 是待纠错的单词, 注意，根据add，其实bk树的根节点在bkTree.root
														// 而不在bkTree，即这里的bkTree.children是空的，bkTree.root.children才不空,
														// 所以这里要传入bkTree.root而不是bkTree作为入参
		System.out.println(results); // 范围默认为1，太小，搜不到
		bkTree.setRadius(2); // 加大范围, 搜到了
		bkTree.query("helli", results, bkTree.root);
		System.out.println(results); // 搜到了

	}
}

其实不得不说，BK树的实现并不复杂，但是能实现的功能比较酷~ 自动纠错，很智能哦！