共计 4226 个字符，预计需要花费 11 分钟才能阅读完成。
本文同时发在我的 github 博客上，欢迎 star
在百度或者 Google 搜索的时候，有时会小手一抖，打错了个别字母，比如我们想搜索 apple，错打成了 appel，但神奇的是，即使我们敲下回车，搜索引擎也会自动搜索 apple 而不是 appel，这是怎么实现的呢？本文就将从头实现一个 JavaScript 版的拼写检查器
基础理论
首先，我们要确定如何量化敲错单词的概率，我们将原本想打出的单词设为 origin(O)，错打的单词设为 error(E)
由贝叶斯定理我们可知：P(O|E)=P(O)*P(E|O)/P(E)
P(O|E)是我们需要的结果，也就是在打出错误单词 E 的情况下，原本想打的单词是 O 的概率
P(O)我们可以看作是 O 出现的概率，是先验概率，这个我们可以从大量的语料环境中获取
P(E|O)是原本想打单词 O 却打成了 E 的概率，这个可以用最短编辑距离模拟概率，比如原本想打的单词是 apple，打成 applee(最短编辑距离为 1)的概率比 appleee(最短编辑距离为 2)自然要大
P(E)由于我们已知 E，这个概念是固定的，而我们需要对比的是 P(O1|E)、P(O2|E)…P(On|E)的概率，不需要精确的计算值，我们可以不用管它
具体实现
这部分的实现我参考了 natural 的代码，传送门
首先是构造函数：
function SpellCheck(priorList) {
//to do trie
this.priorList = priorList;
this.priorHash = {};
priorList.forEach(item => {
!this.priorHash[item] && (this.priorHash[item] = 0);
this.priorHash[item]++;
});
}
priorList 是语料库，在构造函数中我们对 priorList 中的单词进行了出现次数的统计，这也就可以被我们看作是先验概率 P(O)
接下来是 check 函数，用来检测这个单词是否在语料库中出现
SpellCheck.prototype.check = function(word) {
return this.priorList.indexOf(word) !== -1;
};
然后我们需要获取单词指定编辑距离内的所有可能性：
SpellCheck.prototype.getWordsByMaxDistance = function(wordList, maxDistance) {
if (maxDistance === 0) {
return wordList;
}
const listLength = wordList.length;
wordList[listLength] = [];
wordList[listLength – 1].forEach(item => {
wordList[listLength].push(…this.getWordsByOneDistance(item));
});
return this.getWordsByMaxDistance(wordList, maxDistance – 1);
};
SpellCheck.prototype.getWordsByOneDistance = function(word) {
const alphabet = “abcdefghijklmnopqrstuvwxyz”;
let result = [];
for (let i = 0; i < word.length + 1; i++) {
for (let j = 0; j < alphabet.length; j++) {
// 插入
result.push(
word.slice(0, i) + alphabet[j] + word.slice(i, word.length)
);
// 替换
if (i > 0) {
result.push(
word.slice(0, i – 1) +
alphabet[j] +
word.slice(i, word.length)
);
}
}
if (i > 0) {
// 删除
result.push(word.slice(0, i – 1) + word.slice(i, word.length));
// 前后替换
if (i < word.length) {
result.push(
word.slice(0, i – 1) +
word[i] +
word[i – 1] +
word.slice(i + 1, word.length)
);
}
}
}
return result.filter((item, index) => {
return index === result.indexOf(item);
});
};
wordList 是一个数组，它的第一项是只有原始单词的数组，第二项是存放距离原始单词编辑距离为 1 的单词数组，以此类推，直到到达了指定的最大编辑距离 maxDistance
以下四种情况被视为编辑距离为 1:
插入一项，比如 ab->abc
替换一项，比如 ab->ac
删除一项，比如 ab->a
前后替换，比如 ab->ba
获取了所有在指定编辑距离的单词候选集，再比较它们的先验概率：
SpellCheck.prototype.getCorrections = function(word, maxDistance = 1) {
const candidate = this.getWordsByMaxDistance([[word]], maxDistance);
let result = [];
candidate
.map(candidateList => {
return candidateList
.filter(item => this.check(item))
.map(item => {
return [item, this.priorHash[item]];
})
.sort((item1, item2) => item2[1] – item1[1])
.map(item => item[0]);
})
.forEach(item => {
result.push(…item);
});
return result.filter((item, index) => {
return index === result.indexOf(item);
});
};
最后得到的就是修正后的单词
我们来测试一下：
const spellCheck = new SpellCheck([
“apple”,
“apples”,
“pear”,
“grape”,
“banana”
]);
spellCheck.getCorrectionsByCalcDistance(“appel”, 1); //[‘apple’]
spellCheck.getCorrectionsByCalcDistance(“appel”, 2); //[‘apple’, ‘apples’]
可以看到，在第一次测试的时候，我们指定了最大编辑距离为 1，输入了错误的单词 appel，最后返回修正项 apple；而在第二次测试时，将最大编辑距离设为 2，则返回了两个修正项
语料库较少的情况
上面的实现方法是先获取了单词所有指定编辑距离内的候选项，而在语料库单词较少的情况下，这种方法比较耗费时间，我们可以改成先获取语料库中符合指定最短编辑距离的单词
计算最短编辑距离是一种比较经典的动态规划(leetcode:72)，dp 即可。这里的计算最短编辑距离与 leetcode 的情况略有不同，需要多考虑一层临近字母左右替换的情况
leetcode 情况下的状态转换方程：
dp[i][j]=0 i===0,j===0
dp[i][j]=j i===0,j>0
dp[i][j]=i j===0,i>0
min(dp[i-1][j-1]+cost,dp[i-1][j]+1,dp[i][j-1]+1) i,j>0
其中当 word1[i-1]===word2[j-1]时，cost 为 0，否则为 1
考虑临近字母左右替换的情况，则需要在 i >1,j>1 且 word1[i – 2] === word2[j – 1]&&word1[i – 1] === word2[j – 2]为 true 的条件下，再作 min(dp[i-1][j-1]+cost,dp[i-1][j]+1,dp[i][j-1]+1,dp[i-2][j-2]+1)
拿到语料库中符合指定最短编辑距离的单词在对先验概率作比较，代码如下：
SpellCheck.prototype.getCorrectionsByCalcDistance = function(
word,
maxDistance = 1
) {
const candidate = [];
for (let key in this.priorHash) {
this.calcDistance(key, word) <= maxDistance && candidate.push(key);
}
return candidate
.map(item => {
return [item, this.priorHash[item]];
})
.sort((item1, item2) => item2[1] – item1[1])
.map(item => item[0]);
};
SpellCheck.prototype.calcDistance = function(word1, word2) {
const length1 = word1.length;
const length2 = word2.length;
let dp = [];
for (let i = 0; i <= length1; i++) {
dp[i] = [];
for (let j = 0; j <= length2; j++) {
if (i === 0) {
dp[i][j] = j;
continue;
}
if (j === 0) {
dp[i][j] = i;
continue;
}
const replaceCost =
dp[i – 1][j – 1] + (word1[i – 1] === word2[j – 1] ? 0 : 1);
let transposeCost = Infinity;
if (
i > 1 &&
j > 1 &&
word1[i – 2] === word2[j – 1] &&
word1[i – 1] === word2[j – 2]
) {
transposeCost = dp[i – 2][i – 2] + 1;
}
dp[i][j] = Math.min(
replaceCost,
transposeCost,
dp[i – 1][j] + 1,
dp[i][j – 1] + 1
);
}
}
return dp[length1][length2];
};
最后
这份代码还有很多可以优化的地方，比如 check 函数使用的是 indexOf 判断单词是否在语料库中出现，我们可以改用单词查找树 (Trie) 或者 hash 的方式加速查询
