资讯专栏INFORMATION COLUMN

实现拼写检查器(spell check)

Harriet666 / 1929人阅读

摘要:本文同时发在我的博客上,欢迎在百度或者搜索的时候,有时会小手一抖,打错了个别字母,比如我们想搜索,错打成了,但神奇的是,即使我们敲下回车,搜索引擎也会自动搜索而不是,这是怎么实现的呢本文就将从头实现一个版的拼写检查器基础理论首先,我们要确定

本文同时发在我的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的代码,传送门

首先是构造函数:

</>复制代码

  1. function SpellCheck(priorList) {
  2. //to do trie
  3. this.priorList = priorList;
  4. this.priorHash = {};
  5. priorList.forEach(item => {
  6. !this.priorHash[item] && (this.priorHash[item] = 0);
  7. this.priorHash[item]++;
  8. });
  9. }

priorList是语料库,在构造函数中我们对priorList中的单词进行了出现次数的统计,这也就可以被我们看作是先验概率P(O)

接下来是check函数,用来检测这个单词是否在语料库中出现

</>复制代码

  1. SpellCheck.prototype.check = function(word) {
  2. return this.priorList.indexOf(word) !== -1;
  3. };

然后我们需要获取单词指定编辑距离内的所有可能性:

</>复制代码

  1. SpellCheck.prototype.getWordsByMaxDistance = function(wordList, maxDistance) {
  2. if (maxDistance === 0) {
  3. return wordList;
  4. }
  5. const listLength = wordList.length;
  6. wordList[listLength] = [];
  7. wordList[listLength - 1].forEach(item => {
  8. wordList[listLength].push(...this.getWordsByOneDistance(item));
  9. });
  10. return this.getWordsByMaxDistance(wordList, maxDistance - 1);
  11. };
  12. SpellCheck.prototype.getWordsByOneDistance = function(word) {
  13. const alphabet = "abcdefghijklmnopqrstuvwxyz";
  14. let result = [];
  15. for (let i = 0; i < word.length + 1; i++) {
  16. for (let j = 0; j < alphabet.length; j++) {
  17. //插入
  18. result.push(
  19. word.slice(0, i) + alphabet[j] + word.slice(i, word.length)
  20. );
  21. //替换
  22. if (i > 0) {
  23. result.push(
  24. word.slice(0, i - 1) +
  25. alphabet[j] +
  26. word.slice(i, word.length)
  27. );
  28. }
  29. }
  30. if (i > 0) {
  31. //删除
  32. result.push(word.slice(0, i - 1) + word.slice(i, word.length));
  33. //前后替换
  34. if (i < word.length) {
  35. result.push(
  36. word.slice(0, i - 1) +
  37. word[i] +
  38. word[i - 1] +
  39. word.slice(i + 1, word.length)
  40. );
  41. }
  42. }
  43. }
  44. return result.filter((item, index) => {
  45. return index === result.indexOf(item);
  46. });
  47. };

wordList是一个数组,它的第一项是只有原始单词的数组,第二项是存放距离原始单词编辑距离为1的单词数组,以此类推,直到到达了指定的最大编辑距离maxDistance

以下四种情况被视为编辑距离为1:

插入一项,比如ab->abc

替换一项,比如ab->ac

删除一项,比如ab->a

前后替换,比如ab->ba

获取了所有在指定编辑距离的单词候选集,再比较它们的先验概率:

</>复制代码

  1. SpellCheck.prototype.getCorrections = function(word, maxDistance = 1) {
  2. const candidate = this.getWordsByMaxDistance([[word]], maxDistance);
  3. let result = [];
  4. candidate
  5. .map(candidateList => {
  6. return candidateList
  7. .filter(item => this.check(item))
  8. .map(item => {
  9. return [item, this.priorHash[item]];
  10. })
  11. .sort((item1, item2) => item2[1] - item1[1])
  12. .map(item => item[0]);
  13. })
  14. .forEach(item => {
  15. result.push(...item);
  16. });
  17. return result.filter((item, index) => {
  18. return index === result.indexOf(item);
  19. });
  20. };

最后得到的就是修正后的单词

我们来测试一下:

</>复制代码

  1. const spellCheck = new SpellCheck([
  2. "apple",
  3. "apples",
  4. "pear",
  5. "grape",
  6. "banana"
  7. ]);
  8. spellCheck.getCorrectionsByCalcDistance("appel", 1); //[ "apple" ]
  9. 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)

拿到语料库中符合指定最短编辑距离的单词在对先验概率作比较,代码如下:

</>复制代码

  1. SpellCheck.prototype.getCorrectionsByCalcDistance = function(
  2. word,
  3. maxDistance = 1
  4. ) {
  5. const candidate = [];
  6. for (let key in this.priorHash) {
  7. this.calcDistance(key, word) <= maxDistance && candidate.push(key);
  8. }
  9. return candidate
  10. .map(item => {
  11. return [item, this.priorHash[item]];
  12. })
  13. .sort((item1, item2) => item2[1] - item1[1])
  14. .map(item => item[0]);
  15. };
  16. SpellCheck.prototype.calcDistance = function(word1, word2) {
  17. const length1 = word1.length;
  18. const length2 = word2.length;
  19. let dp = [];
  20. for (let i = 0; i <= length1; i++) {
  21. dp[i] = [];
  22. for (let j = 0; j <= length2; j++) {
  23. if (i === 0) {
  24. dp[i][j] = j;
  25. continue;
  26. }
  27. if (j === 0) {
  28. dp[i][j] = i;
  29. continue;
  30. }
  31. const replaceCost =
  32. dp[i - 1][j - 1] + (word1[i - 1] === word2[j - 1] ? 0 : 1);
  33. let transposeCost = Infinity;
  34. if (
  35. i > 1 &&
  36. j > 1 &&
  37. word1[i - 2] === word2[j - 1] &&
  38. word1[i - 1] === word2[j - 2]
  39. ) {
  40. transposeCost = dp[i - 2][i - 2] + 1;
  41. }
  42. dp[i][j] = Math.min(
  43. replaceCost,
  44. transposeCost,
  45. dp[i - 1][j] + 1,
  46. dp[i][j - 1] + 1
  47. );
  48. }
  49. }
  50. return dp[length1][length2];
  51. };
最后

这份代码还有很多可以优化的地方,比如check函数使用的是indexOf判断单词是否在语料库中出现,我们可以改用单词查找树(Trie)或者hash的方式加速查询

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/102271.html

相关文章

  • java 英文单词拼写纠正框架(Word Checker)

    Word Checker word checker 本项目用于单词拼写检查。 Github 地址 项目简介 本项目用于单词拼写检查。 特性说明 支持 i18n 错误提示支持 i18N 支持英文的单词纠错 可以迅速判断当前单词是否拼写错误 可以返回最佳匹配结果 可以返回纠正匹配列表,支持指定返回列表的大小 后续将会添加的新功能 英文单词支持自行定义 中文单词的拼写是否正确功能添加 快速开始 ...

    amc 评论0 收藏0
  • JavaScript是如何工作的:Web Workers的构建块+ 5个使用他们的场景

    摘要:最后,提供个正确使用的场景。异步编程的一个很好的用例就请求。这意味着异步函数只能解决一小部分语言单线程中的局限性问题。中有类似的集群子进程概念,他们也是多线程但是和还是有区别。可用的特性由于的多线程特性,工作者只能访问特性的一个子集。 showImg(https://segmentfault.com/img/bVblS8J?w=400&h=298); 这是专门探索 JavaScript...

    ningwang 评论0 收藏0
  • sublime text3配置<python篇>

    摘要:选中一个后,按此快捷键可以同时选中另一个,同时多了另一个光标在下面新开一行在上面新开一行删除整行。向左单位性地移动光标,快速移动光标。开启关闭侧边栏。插件能为提供括号,引号这类高亮功能。用来安装其官网上的所有主题。 古语有云,工欲善其事必先利其器。选择一个好的工具,往往事半功倍。因为个人电脑原因,用 pycharm 太卡,所以想起了 sublime text,配置了一下,觉得挺好用。 ...

    陈江龙 评论0 收藏0
  • vscode常用插件【全了】

    摘要:插件集待补充。。。同时,它还包含了用于转换为格式和生成数据模式的选项用于压缩合并和文件的应用程序。它提供了大量自定义的设置,以及自动压缩保存并导出为文件的选项。修改文本的更多命名格式,包括驼峰命名下划线分隔命名,命名以及命名等切换漂亮的主题 插件集 待补充。。。 20180903 文件 【Path Intellisense】 自动补全路径 浏览器 【Open-In-Browser】在...

    kyanag 评论0 收藏0

发表评论

0条评论

Harriet666

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<