22、介绍一下你们的个性化搜索方案？
SEE 基于 word2vec 和 Elasticsearch 实现个性化搜索
23、是否了解字典树？
常用字典数据结构如下所示：
第 98 页 共 485 页Trie 的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以
达到提高效率的目的。它有 3 个基本性质：
1、根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3、每个节点的所有子节点包含的字符都不相同。
第 99 页 共 485 页1、可以看到，trie 树每一层的节点数是 26^i 级别的。所以为了节省空间，我们
还可以用动态链表，或者用数组来模拟动态。而空间的花费，不会超过单词数×单
词长度。
2、实现：对每个结点开一个字母集大小的数组，每个结点挂一个链表，使用左儿
子右兄弟表示法记录这棵树；
3、对于中文的字典树，每个节点的子节点用一个哈希表存储，这样就不用浪费太
大的空间，而且查询速度上可以保留哈希的复杂度 O(1)。
24、拼写纠错是如何实现的？
1、拼写纠错是基于编辑距离来实现；编辑距离是一种标准的方法，它用来表示经
过插入、删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数；
2、编辑距离的计算过程：比如要计算 batyu 和 beauty 的编辑距离，先创建一个
7×8 的表（batyu 长度为 5，coffee 长度为 6，各加 2），接着，在如下位置填入
黑色数字。其他格的计算过程是取以下三个值的最小值：
如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字
+1。（对于 3,3 来说为 0）
左方数字+1（对于 3,3 格来说为 2）
上方数字+1（对于 3,3 格来说为 2）
最终取右下角的值即为编辑距离的值 3。
第 100 页 共 485 页对于拼写纠错，我们考虑构造一个度量空间（Metric Space），该空间内任何关
系满足以下三条基本条件：
d(x,y) = 0 -- 假如 x 与 y 的距离为 0，则 x=y
d(x,y) = d(y,x) -- x 到 y 的距离等同于 y 到 x 的距离
d(x,y) + d(y,z) >= d(x,z) -- 三角不等式
1、根据三角不等式，则满足与 query 距离在 n 范围内的另一个字符转 B，其与 A
的距离最大为 d+n，最小为 d-n。
2、BK 树的构造就过程如下：每个节点有任意个子节点，每条边有个值表示编辑
距离。所有子节点到父节点的边上标注 n 表示编辑距离恰好为 n。比如，我们有棵
第 101 页 共 485 页第 102 页 共 485 页
树父节点是”book”和两个子节点”cake”和”books”，”book”到”books”
的边标号 1，”book”到”cake”的边上标号 4。从字典里构造好树后，无论何
时你想插入新单词时，计算该单词与根节点的编辑距离，并且查找数值为
d(neweord, root)的边。递归得与各子节点进行比较，直到没有子节点，你就可
以创建新的子节点并将新单词保存在那。比如，插入”boo”到刚才上述例子的树
中，我们先检查根节点，查找 d(“book”, “boo”) = 1 的边，然后检查标号为
1 的边的子节点，得到单词”books”。我们再计算距离 d(“books”
, “boo”)=2，
则将新单词插在”books”之后，边标号为 2。
3、查询相似词如下：计算单词与根节点的编辑距离 d，然后递归查找每个子节点
标号为 d-n 到 d+n（包含）的边。假如被检查的节点与搜索单词的距离 d 小于 n，
则返回该节点并继续查询。比如输入 cape 且最大容忍距离为 1，则先计算和根的
编辑距离 d(“book”, “cape”)=4，然后接着找和根节点之间编辑距离为 3 到
5 的，这个就找到了 cake 这个节点，计算 d(“cake”, “cape”)=1，满足条件
所以返回 cake，然后再找和 cake 节点编辑距离是 0 到 2 的，分别找到 cape 和
cart 节点，这样就得到 cape 这个满足条件的结果。
