最近在做楼盘搜索的时候遇到一个问题，用户在查询楼盘的时候回出现楼盘名称输入有误的情况，一般会出现一个或多个错字，其中同义词可以根据词典和拼音的方式进行处理，但是如果用户输入的字不是同音字用拼音的方式就无能为力了，这就和一个场景类似：给一个单词和一个字典，找出字典中所有和给定单词编辑距离不大于 k 的词。

一个常见的思路是遍历一遍，求单词和字典中每一项的编辑距离。我们知道编辑距离是二维 DP，时间复杂度为 $O(L^2)$，其中 L 为每个单词平均长度，则总时间复杂度为$O(NL^2)$， N 为字典中词的个数。

这个方法的问题在于，一旦查询单词变多，性能会很糟糕。基于[黄振大神的算法实现] (http://norvig.com/spell-correct.html) ，可以通过构造 Trie， 结合 DFS，来解决这个问题。

解决思路

  • 1.根据字典中的单词构造前缀树，标记每个单词结束时的结束为 None。
  • 2.设计函数 API 为check_fuzzy(trie, word, path, tol)。trie是在树中当前走到的节点，word 表示走到当前节点剩余需要处理的查询单词，path表示走到当前节点已经记录的字典单词前缀，tol 表示剩余可容忍的编辑距离。然后定义一个set，不断找到可能的单词并入这个set，直到结束。

匹配当前字符，有两种情况：匹配，那么直接递归下一层；不匹配，可能是字母不一致或者是 word 已经结束（这个情况很容易被忽略），需要 tol 减一后递归下一层。 增加任意字母（字典单词比查询单词多字母）。这里和知乎回答里的不一样，那里是枚举了26个字母，其实只要枚举当前 tree 的所有节点字母就行了（Jayxon 大牛想到的）。 删除字符。word 向后移一个字母，tol 减一

第一步. 构造Trie（用dict登记结点信息和维持子结点集合）：

对词典中的每个单词，逐词逐字母拓展Trie，单词完结处的结点用None标识。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def make_trie(words):
    trie = {}
    for word in words:
        t = trie
        for c in word:
            if c not in t: t[c] = {}
            t = t[c]
        t[None] = None
    return trie

第二步. 容错查找（容错数为tol）：

实质上是对Trie的深度优先搜索，每一步加深时就消耗目标词的一个字母。当搜索到达某个结点时，分为不消耗容错数和消耗容错数的情形，继续搜索直到目标词为空。搜索过程中，用path记录搜索路径，该路径即为一个词典中存在的词，作为纠错的参考;最终结果即为诸多搜索停止位置的结点路径的并集。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def check_fuzzy(trie, word, path='', tol=1):
    if word == '':
        return {path} if None in trie else set()
    else:
        p0 = set()
        if word[0] in trie:
            p0 = check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
        p1 = set()
        if tol > 0:
            for k in trie:
                if k is not None and k != word[0]:
                    p1.update(check_fuzzy(trie[k], word[1:], path+k, tol-1))
        return p0 | p1

测试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

words = ['hello', 'hela', 'dome']
t = make_trie(words)

check_fuzzy(t, 'hellu', tol=0)
{}
check_fuzzy(t, 'hellu', tol=1)
{'hello'}

check_fuzzy(t, 'healu', tol=1)

{}

check_fuzzy(t, 'healu', tol=2)

{'hello'}
## 来个中文的
check_fuzzy(t, '豪方箐圆', tol=2)
{'豪方天际', '豪方花园', '豪方菁园', '豪方卉园', '豪方东园'}

代码整体处理速度还是比较快的，在词典中词的数量是40万+的时候，处理速度是40毫秒左右，当然这种算法还有提升空间，有兴趣的朋友们可以自己尝试优化。 另外这种方法不但可以实现错别字检查，还可以实现相近词扩展的功能，这样在楼盘搜索上就可以尽可能的为用户找到目标楼盘。

更多信息参见

https://www.zhihu.com/question/29592463