一个提升英文单词拼写检测性能 1000 倍的算法？

老马啸西风2020年1月20日大约 12 分钟

小明同学上一次在产品经理的忽悠下，写好了一个中英文拼写纠正工具：https://github.com/houbb/word-checker。

本来以为可以一劳永逸了，直到昨天闲来无事，发现了另一个开源项目，描述简要如下：

Spelling correction & Fuzzy search: 1 million times faster through Symmetric Delete spelling correction algorithm

The Symmetric Delete spelling correction algorithm reduces the complexity of edit candidate generation and dictionary lookup for a given Damerau-Levenshtein distance. 

It is six orders of magnitude faster (than the standard approach with deletes + transposes + replaces + inserts) and language independent.

小明以为自己眼睛花了，100W 倍，这牛吹得厉害了。

秉着不信谣，不传谣的原则，小明开始了算法的学习之旅。

单词拼写算法思路

针对英文单词拼写，有下面几种算法：

实时计算编辑距离

给定两个字符串 $s_1$ 和 $s_2$，它们之间的编辑距离是将 $s_1$ 转换为 $s_2$ 所需的最小编辑操作次数。

最常见的，为此目的所允许的编辑操作是： (i) 在字符串中插入一个字符； (ii) 从字符串中删除一个字符和 (iii) 用另一个字符替换字符串中的一个字符；对于这些操作，编辑距离有时称为 Levenshtein 距离。

这种算法是最容易想到的，但是实时计算的代价非常昂贵。一般不作为工业实现。

Peter Norvig 的拼写算法

从查询词生成具有编辑距离（删除 + 转置 + 替换 + 插入）的所有可能词，并在字典中搜索它们。

对于长度为n的单词，字母大小为a，编辑距离d=1，会有n次删除，n-1次换位，a*n 次改变，a*(n+1) 次插入，总共2n次搜索时 2n+2an+a-1 个词。

这种算法就是小明一开始选择的算法，性能比上一个算法要好很多。

但在搜索时仍然很昂贵（n=9、a=36、d=2 的 114,324 个术语）和语言相关（因为字母表用于生成术语，这在许多方面都不同）。

性能提升的一种思路

如果让小明来提升这个算法，那有一个思路就是用空间换时间。

把一个正确单词的删除 + 转置 + 替换 + 插入提前全部生成好，然后插入到字典中。

但是这里存在一个很大的问题，这个预处理生成的字典数太大了，有些不能接受。

那么，世间安得双全法？

让我们一起来看一下本篇的主角。

对称删除拼写纠正（SymSpell）

算法描述

从每个字典术语生成具有编辑距离（仅删除）的术语，并将它们与原始术语一起添加到字典中。

这必须在预计算步骤中仅执行一次。

生成与输入术语具有编辑距离（仅删除）的术语并在字典中搜索它们。

对于长度为 n 的单词、字母大小为 a、编辑距离为 1 的单词，将只有 n 个删除，在搜索时总共有 n 个术语。

这种方法的代价是每个原始字典条目x次删除的预计算时间和存储空间，这在大多数情况下是可以接受的。

单个字典条目的删除次数 x 取决于最大编辑距离。

对称删除拼写校正算法通过仅使用删除而不是删除 + 转置 + 替换 + 插入来降低编辑候选生成和字典查找的复杂性。它快了六个数量级（编辑距离=3）并且与语言无关。

一些备注

为了便于大家理解，原作者还写了一点备注。

备注1：在预计算过程中，字典中不同的词可能会导致相同的删除词：delete(sun,1)==delete(sin,1)==sn。

虽然我们只生成一个新的字典条目 (sn)，但在内部我们需要将两个原始术语存储为拼写更正建议 (sun,sin)

备注 2：有四种不同的比较对类型：

dictionary entry==input entry,
delete(dictionary entry,p1)==input entry  // 预处理
dictionary entry==delete(input entry,p2)
delete(dictionary entry,p1)==delete(input entry,p2)

仅替换和转置需要最后一个比较类型。

但是我们需要检查建议的字典术语是否真的是输入术语的替换或相邻转置，以防止更高编辑距离的误报（bankbnak 和bankbink，但是bank!=kanb 和bank!= xban 和银行！=baxn）。

备注 3：我们使用的是搜索引擎索引本身，而不是专用的拼写字典。

这有几个好处：

它是动态更新的。每个新索引的词，其频率超过某个阈值，也会自动用于拼写校正。

由于我们无论如何都需要搜索索引，因此拼写更正几乎不需要额外的成本。

当索引拼写错误的术语时（即未在索引中标记为正确），我们会即时进行拼写更正，并为正确的术语索引页面。

备注 4：我们以类似的方式实现了查询建议/完成。

这是首先防止拼写错误的好方法。

每个新索引的单词，其频率超过某个阈值，都被存储为对其所有前缀的建议（如果它们尚不存在，则会在索引中创建）。

由于我们提供了即时搜索功能，因此查找建议也几乎不需要额外费用。多个术语按存储在索引中的结果数排序。

推理

SymSpell 算法利用了两个术语之间的编辑距离对称的事实：

我们可以生成与查询词条编辑距离

1. 如果单词长度小于1，则不作处理。
1. 对单词的长度减去1，依次移除一个字母，把余下的部分作为 key，
value 是一个原始的 CandidateDto 列表。
1. 如何去重比较优雅？
1. 如何排序比较优雅？
如果不考虑自定义词库，是可以直接把词库预处理好的，但是只是减少了初始化的时间，意义不大。
@param freqMap 频率 Map
@param resultsMap 结果 map
@since 0.1.0
*/
static synchronized void initSymSpellMap(Map freqMap,
Map> resultsMap) {
if (MapUtil.isEmpty(freqMap)) {
return;
}
for (Map.Entry entry : freqMap.entrySet()) {
String key = entry.getKey();
Long count = entry.getValue();
// 长度判断
int len = key.length();
// 后续可以根据编辑距离进行调整
if (len tempSet = new HashSet<>(chars.length);
for (int i = 0; i candidateDtos = resultsMap.get(text);
if (candidateDtos == null) {
candidateDtos = new ArrayList<>();
}
// 把原始的 key 作为值
candidateDtos.add(new CandidateDto(key, count));
// 删减后的文本作为 key
resultsMap.put(text, candidateDtos);
tempSet.add(text);
}
}
// 统一排序
for (Map.Entry> entry : resultsMap.entrySet()) {
String key = entry.getKey();
List list = entry.getValue();
if (list.size() > 1) {
// 排序
Collections.sort(list);
resultsMap.put(key, list);
}
}
}


其中构建删除字符串的实现比较简单：

```java
/**
 * 构建字符串
 *
 * @param chars        字符数组
 * @param excludeIndex 排除的索引
 * @return 字符串
 * @since 0.1.0
 */
public static String buildString(char[] chars, int excludeIndex) {
    StringBuilder stringBuilder = new StringBuilder(chars.length - 1);
    for (int i = 0; i  getAllCandidateList(String word, IWordCheckerContext context) {
    IWordData wordData = context.wordData();
    Map freqData = wordData.freqData();
    Map> symSpellData = wordData.symSpellData();

    //0. 原始字典包含
    if (freqData.containsKey(word)) {
        // 返回原始信息
        CandidateDto dto = CandidateDto.of(word, freqData.get(word));
        return Collections.singletonList(dto);
    }
    // 如果长度为1
    if(word.length()  resultList = new ArrayList<>();
    //1. 对称删减包含输入的单词
    List symSpellList = symSpellData.get(word);
    if(CollectionUtil.isNotEmpty(symSpellList)) {
        resultList.addAll(symSpellList);
    }
    // 所有删减后的数组
    Set subWordSet = InnerWordDataUtil.buildStringSet(word.toCharArray());
    //2. 输入单词删减后，在原始字典中存在。
    for(String subWord : subWordSet) {
        if(freqData.containsKey(subWord)) {
            CandidateDto dto = CandidateDto.of(subWord, freqData.get(subWord));
            resultList.add(dto);
        }
    }
    //3. 输入单词删减后，在对称删除字典存在。
    for(String subWord : subWordSet) {
        if(symSpellData.containsKey(subWord)) {
            resultList.addAll(symSpellData.get(subWord));
        }
    }
    if(CollectionUtil.isNotEmpty(resultList)) {
        return resultList;
    }

    //4. 执行替换和修改（递归调用一次）甚至也可以不做处理。
    // 为保证编辑距离为1，只考虑原始字典
    List edits = edits(word);
    for(String edit : edits) {
        if(freqData.containsKey(edit)) {
            CandidateDto dto = CandidateDto.of(edit, freqData.get(edit));
            resultList.add(dto);
        }
    }
    return resultList;
}