算法高级（31） |
您所在的位置：网站首页 › 错字这个词的拼音 › 算法高级（31） |
算法高级（31）
|
一、Word中的拼写检查功能
拼写检查程序是指将输入的每个字词与存储器里的字典比较，检查其正确性并在屏幕上显示差异的计算机程序。如果在字典中没有这个单词，用户就会被警告可能拼写错误，同时经常提供几个纠正错误建议。拼写检查程序不能识别不常用的人或专用术语，但是它容许你生成自己的个人字典，把自己常用的词语加进去。 二、拼写纠错功能的实现在使用搜索引擎时，当我们输入错误的关键词时，当然这里的错误是拼写错误，搜索引擎的下拉框中仍会显示以正确关键词为前前辍的提示，当你直接回车搜索错误的关键词时，搜索引擎的结果中仍包括正确关键词的结果。你有没有想过它是如何实现的呢?
这个的实现可以有多种方案，常见的方法就是我们前面学习过的最长公共子序列和今天要讲的莱文斯坦距离方式。 最长公共子序列可以查看我前面的博文程序员的算法课（6）-最长公共子序列（LCS）。 这两种方案都需要跟正确的词典进行对照，计算编辑距离或者最长公共子序列，将编辑距离最小或子序列最长的单词，作为纠正之后的单词，返回给用户。 三、莱文斯坦距离【百度百科】莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 如单词three，我不小心手误打成了ethre，可以看到ethre只需要把首字母e移动到末尾即可变成正确的单词three。此时ethre相对于three的编辑距离就是1。 莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。 莱文斯坦距离和最长公共子串长度，从两个截然相反的角度，分析字符串的相似程度。莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。 四、Lucene、Solr、ES中的拼写纠错原理其实比较简单，无非就是通过算法进行计算得出一个最贴切的单词返回给用户，网上也有很多这样的案例讲解。既然是实战，那我们就分别来看看Java领域中鼎鼎大名的几个开源搜索框架对于拼写纠错是如何实现的吧。 1.Lucene中通过Suggest模块下的SpellChecker功能来实现拼写纠错。源码中，定义了两个public的静态成员变量， DEFAULT_ACCURACY表示默认的最小分数，SpellCheck会对字典里的每个词与用户输入的搜索关键字进行一个相似度打分，默认该值是0.5，相似度分值范围是0到1之间，数字越大表示越相似，小于0.5会认为不是同一个结果。F_WORD是对于字典文件里每一行创建索引时使用的默认域名称，默认值为：word。 几个重要的API： getAccuracy： accuracy是精确度的意思，这里表示最小评分，评分越大表示与用户输入的关键字越相似suggestSimilar：这个方法就是用来决定哪些word会被判定为比较相似的然后以数组的形式返回，这是SpellChecker的核心；setComparator：设置比较器，既然涉及到相似度问题，那肯定有相似度大小问题，有大小必然存在比较，有比较必然需要比较器，通过比较器决定返回的建议词的顺序，因为一般需要把最相关的显示在最前面，然后依次排序显示；setSpellIndex：设置拼写检查索引目录的setStringDistance：设置编辑距离看到了setStringDistance这个方法，想都不用想，Lucene肯定也是使用编辑距离的方式进行匹配的。 源码中还有两个私有属性，分别代表前缀和后缀的权重，前缀要比后缀大。 private float bStart = 2.0f; private float bEnd = 1.0f;几个重要的方法： formGrams：对输入的字符串按指定长度分割，返回分割后的数组。indexDictionary：将字典文件里的词进行ngram操作后得到多个词然后分别写入索引。 suggestSimilar：用来计算最后返回的建议词。有三种建议模式： SUGGEST_WHEN_NOT_IN_INDEX：意思就是只有当用户提供的搜索关键字在索引Term中不存在我才提供建议，否则我会认为用户输入的搜索关键字是正确的不需要提供建议。SUGGEST_MORE_POPULAR：表示只返回频率较高的词组，用户输入的搜索关键字首先需要经过ngram分割，创建索引的时候也需要进行分词，如果用户输入的词分割后得到的word在索引中出现的频率比索引中实际存在的Term还要高，那说明不需要进行拼写建议了。SUGGEST_ALWAYS：永远进行建议，只是返回的建议结果受numSug数量限制即最多返回几条拼写建议。最终返回用户输入关键字和索引中当前Term的相似度，这个取决于你Distance实现，默认实现是LevenshteinDistance （莱文斯坦距离）即计算编辑距离。采用三个一维数组代替了一个二维数组，一个数组为上一轮计算的值，一个数组保存本轮计算的值，最后一个数组用于交换两个数组的值。核心源码如下： package org.apache.lucene.search.spell; public class LevenshteinDistance implements StringDistance { @Override public float getDistance (String target, String other) { char[] sa; int n; int p[]; //上一行计算的值 int d[]; //当前行计算的值 int _d[]; //用于交换p和d sa = target.toCharArray(); n = sa.length; p = new int[n+1]; d = new int[n+1]; final int m = other.length(); if (n == 0 || m == 0) { if (n == m) { return 1; } else { return 0; } } int i; // target的索引 int j; // other的索引 char t_j; //other的第j个字符 int cost; //初始化，将空字符串转换为长度为i的target字符串的操作次数 for (i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |