如何在含拼写错误的文本中匹配查找列表内的字符串

• 预过滤阶段用N-gram相似度筛除无效候选：不需要对所有拆分出来的词组都算全量编辑距离，先对目标关键词和候选词组提取相同长度的N元文法（通常选2-gram即可），计算两者N元集合的交集占比，低于预设阈值（比如0.7）的直接判定不匹配，这一步可以筛掉90%以上的无效候选，仅剩下少量高相似的候选再做精确的相似度计算，大幅减少运算量。
• 先做目标文本拼写校正再匹配：提前准备对应语言的常用词词典，先对目标文本做批量拼写校正，解决单词拼写错误、意外拆分（比如示例中的th eforest、broww）这类问题，校正后的文本直接做精确关键词匹配即可，运算效率远高于逐次计算相似度。拼写校正阶段也可以做优化，仅对词典中不存在的词，和长度差在±2以内的候选词典词计算编辑距离，不用全量匹配。
• 优化编辑距离计算逻辑：如果你要求匹配度超过90%才判定相同，那两个字符串长度差如果超过总长度的10%，可以直接跳过计算，不需要算完整的Levenshtein距离。另外可以替换为专门用于模糊子串匹配的Bitap算法，该算法用位运算做了优化，支持直接设置允许的最大错误数，运算速度是普通Levenshtein算法的3~10倍。
• 多关键词场景用改造版AC自动机：如果待匹配的关键词数量较多，可以把所有关键词建成AC自动机，在遍历文本的过程中直接做模糊匹配，不需要提前拆分所有单字词、双字词组合，把候选遍历的时间复杂度从O(2n)降到O(n)，文本越长、关键词越多，效率提升越明显。

内容的提问来源于stack exchange，提问作者XIAA