关于算法:一个提升英文单词拼写检测性能-1000-倍的算法

小明同学上一次在产品经理的忽悠下，写好了一个中英文拼写纠正工具：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 间隔。

这种算法是最容易想到的，然而实时计算的代价十分低廉。个别不作为工业实现。

从查问词生成具备编辑间隔（删除 + 转置 + 替换 + 插入）的所有可能词，并在字典中搜寻它们。

对于长度为 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 个术语）和语言相干（因为字母表用于生成术语，这在许多方面都不同）。

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

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

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

那么，世间安得双全法？

让咱们一起来看一下本篇的配角。

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

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

生成与输出术语具备编辑间隔（仅删除）的术语并在字典中搜寻它们。

对于长度为 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)

仅替换和转置须要最初一个比拟类型。

然而咱们须要查看倡议的字典术语是否真的是输出术语的替换或相邻转置，以避免更高编辑间隔的误报（bank==bnak 和 bank==bink，然而 bank!=kanb 和 bank!= xban 和银行！=baxn）。

备注 3：咱们应用的是搜索引擎索引自身，而不是专用的拼写字典。

这有几个益处：

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

因为咱们无论如何都须要搜寻索引，因而拼写更正简直不须要额定的老本。

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

备注 4：咱们以相似的形式实现了查问倡议 / 实现。

这是首先避免拼写错误的好办法。

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

因为咱们提供了即时搜寻性能，因而查找倡议也简直不须要额定费用。多个术语按存储在索引中的后果数排序。

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

咱们能够生成与查问词条编辑间隔 < 2 的所有词条（试图扭转查问词条谬误）并依据所有字典词条查看它们，

咱们能够生成与每个字典术语的编辑间隔 < 2 的所有术语（尝试创立查问术语谬误），并依据它们查看查问术语。

通过将正确的字典术语转换为谬误的字符串，并将谬误的输出术语转换为正确的字符串，咱们能够将两者联合起来并在两头相遇。

因为在字典上增加一个字符相当于从输出字符串中删除一个字符，反之亦然，所以咱们能够在两边都限度转换为仅删除。

这一段读的让小明有些云里雾里，于是这里举一个例子，便于大家了解。

比方用户输出的是：goox

正确的词库只有：good

对应的编辑间隔为 1。

那么通过删除，good 预处理存储就会变成：{good = good, ood=good; god=good; goo=good;}

判断用户输出的时候：

（1）goox 不存在

（2）对 goox 进行删除操作

oox gox goo

能够找到 goo 对应的是 good。

读到这里，小伙伴必定曾经发现了这个算法的奇妙之处。

通过对原有字典的删除解决，实际上根本曾经达到了原来算法中删除 + 增加 + 批改的成果。

咱们正在应用变体 3，因为仅删除转换与语言无关，并且成本低三个数量级。

速度从何而来？

预计算，即生成可能的拼写错误变体（仅删除）并在索引时存储它们是第一个前提条件。

通过应用均匀搜寻工夫复杂度为 O(1) 的哈希表在搜寻时进行疾速索引拜访是第二个前提条件。

然而，只有在此之上的对称删除拼写纠正能力将这种 O(1) 速度带到拼写查看中，因为它能够极大地缩小要事后计算（生成和索引）的拼写错误候选者的数量。

将预计算利用于 Norvig 的办法是不可行的，因为预计算所有可能的删除 + 转置 + 替换 + 插入所有术语的候选将导致微小的工夫和空间耗费。

SymSpell 算法是常数工夫（O(1) 工夫），即独立于字典大小（但取决于均匀术语长度和最大编辑间隔），因为咱们的索引基于具备均匀搜寻工夫复杂度的哈希表的 O(1)。

光说不练假把式。

看完之后，小明就连夜把本人原来的算法实现进行了调整。

以前针对上面的词库：

the,23135851162
of,13151942776
and,12997637966

只须要构建一个单词，和对应的频率 freqMap 即可。

当初咱们须要对单词进行编辑间隔 = 1 的删除操作：

/**
 * 对称删除拼写纠正词库
 * <p>
 * 1. 如果单词长度小于 1，则不作解决。* 2. 对单词的长度减去 1，顺次移除一个字母，把余下的局部作为 key，* value 是一个原始的 CandidateDto 列表。* 3. 如何去重比拟优雅？* 4. 如何排序比拟优雅？* <p>
 * 如果不思考自定义词库，是能够间接把词库预处理好的，然而只是缩小了初始化的工夫，意义不大。*
 * @param freqMap    频率 Map
 * @param resultsMap 后果 map
 * @since 0.1.0
 */
static synchronized void initSymSpellMap(Map<String, Long> freqMap,
                                         Map<String, List<CandidateDto>> resultsMap) {if (MapUtil.isEmpty(freqMap)) {return;}

    for (Map.Entry<String, Long> entry : freqMap.entrySet()) {String key = entry.getKey();
        Long count = entry.getValue();
        // 长度判断
        int len = key.length();
        // 后续能够依据编辑间隔进行调整
        if (len <= 1) {continue;}
        char[] chars = key.toCharArray();
        Set<String> tempSet = new HashSet<>(chars.length);
        for (int i = 0; i < chars.length; i++) {String text = buildString(chars, i);
            // 跳过反复的单词
            if (tempSet.contains(text)) {continue;}
            List<CandidateDto> 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<String, List<CandidateDto>> entry : resultsMap.entrySet()) {String key = entry.getKey();
        List<CandidateDto> list = entry.getValue();
        if (list.size() > 1) {
            // 排序
            Collections.sort(list);
            resultsMap.put(key, list);
        }
    }
}

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

/**
 * 构建字符串
 *
 * @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 < chars.length; i++) {if (i == excludeIndex) {continue;}
        stringBuilder.append(chars[i]);
    }
    return stringBuilder.toString();}

这里有几个点须要留神下：

（1）单词如果小于等于编辑间隔，则不须要删除。因为就删除没了 ==

（2）要留神跳过反复的词。比方 good，删除的后果会有 2 个 god。

（3）对立排序，这个还是有必要的，能够晋升实时查问时的性能。

当然，小明心想，如果词库是固定的，能够间接把预处理的词库也解决好，大大晋升加载速度。

不过这个聊胜于无，影响不是很大。

外围算法获取备选列表，间接依照给定的 4 种状况查问即可。

freqData 正确字典的频率信息。

symSpellData 删除后字典的信息。

/**
 * dictionary entry==input entry,
 * delete(dictionary entry,p1)==input entry  // 预处理
 * dictionary entry==delete(input entry,p2)
 * delete(dictionary entry,p1)==delete(input entry,p2)
 *
 * 为了性能思考，这里做疾速返回。前期能够思考能够配置，临时不做解决。*
 * @param word    单词
 * @param context 上下文
 * @return 后果
 * @since 0.1.0
 */
@Override
protected List<CandidateDto> getAllCandidateList(String word, IWordCheckerContext context) {IWordData wordData = context.wordData();
    Map<String, Long> freqData = wordData.freqData();
    Map<String, List<CandidateDto>> symSpellData = wordData.symSpellData();

    //0. 原始字典蕴含
    if (freqData.containsKey(word)) {
        // 返回原始信息
        CandidateDto dto = CandidateDto.of(word, freqData.get(word));
        return Collections.singletonList(dto);
    }
    // 如果长度为 1
    if(word.length() <= 1) {CandidateDto dtoA = CandidateDto.of("a", 9081174698L);
        CandidateDto dtoI = CandidateDto.of("i", 3086225277L);
        return Arrays.asList(dtoA, dtoI);
    }

    List<CandidateDto> resultList = new ArrayList<>();
    //1. 对称删减蕴含输出的单词
    List<CandidateDto> symSpellList = symSpellData.get(word);
    if(CollectionUtil.isNotEmpty(symSpellList)) {resultList.addAll(symSpellList);
    }
    // 所有删减后的数组
    Set<String> 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<String> edits = edits(word);
    for(String edit : edits) {if(freqData.containsKey(edit)) {CandidateDto dto = CandidateDto.of(edit, freqData.get(edit));
            resultList.add(dto);
        }
    }
    return resultList;
}

有上面几点须要留神：

（1）如果原字典曾经蕴含，则间接返回。阐明是拼写正确。

（2）如果长度为 1，则固定返回 I、a 即可。

（3）其余每一种场景，如果处于性能思考的话，也能够疾速返回。

你的服务器性能永远不可能晋升 1000X 的配置，然而算法能够，然而工资不能够。

好的算法，对程序的晋升是十分显著的。

当前还是要继续学习。

文中的代码为了便于大家了解，做了大量精简，感兴趣的小伙伴能够本人去看源码：

https://github.com/houbb/word-checker

我是老马，期待与你的下次重逢。

关于算法:一个提升英文单词拼写检测性能-1000-倍的算法

序言

单词拼写算法思路

实时计算编辑间隔

Peter Norvig 的拼写算法

性能晋升的一种思路

对称删除拼写纠正（SymSpell）

算法形容

一些备注

推理

例子

编辑间隔

计算复杂度

代码实现

词库预处理

外围算法的调整

小结