ITKeyword,专注技术干货聚合推荐

注册 | 登录

拼写检查的Lucene源码分析

duck_genuine 分享于 2010-08-11

推荐:lucene 源码分析

//org.apache.lucene.index => DocumentsWriter.java       /* Invert one occurrence of one field in the document */       public void invertField(Fieldab

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1054

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

原文出处http://lolorosa.blogbus.com/logs/45646288.html

 

1. 首先来说一个N-Gram的概念,我不知道中文里怎么称呼这个,从Lucene SpellChecker的实现来看,N-Gram是指将一个单词划分成若干等长的字串,每一个成为一个gram,n就是用来控制每个gram的长度的。

2. 对于一个单词我们往往会给不同的N做多次切割,这样便于做搜索建议和拼写检查。

3. 构建词典

        a. 对于每个词典中的单词,根据两个值minN~maxN(minN, maxN是根据单词长度由专门的函数产生的)进行分割,介于两个值之间的N都算作一种分割,伪码如下:

        for ng = minN to maxN

             for  i=0 to wordLen-ng +1 (wordLen是指当前这个单词的长度,word是当前单词内容)

                    gram = word.substr(i,i+ng);

                     add this gram as a field to the current lucene document

             end for

          end for

         b. 针对每个N,开头结尾的gram也加入索引域

举例来说:

对于three这个词,minN = 2, maxN =3(有一个很简单的函数计算,参看源码);

那么针对three这个词的对应document对象包含的Field有如下

keyword      value 

----------------------------------------------

F_WORD      three(原词)

gram2           th

推荐:owncloud源码分析8--修改json文件存储

目前owncloud的外接存储信息存放在data文件夹下的mount.json文件中,在这里我修改了这种存储方式使之成为了数据库存储方式: 一、建表: DROP TABLE IF EXISTS `

gram2           hr

gram2           re

gram2           ee

start2            th

end2             ee

gram3          thr

gram3           hre

gram3           ree

start3           thr

end3             ree

通过如上的方式将词典里的每个单词都进行了索引,但请注意上述索引的Field都不进行分词,并且只有F_WORD是存储在索引文件中的(对于这两句不理解的话请参考源码,源码链接我会在下面给出)。

4. 拼写检查

a. 根据输入word构建查询条件

    也是通过minN, maxN来讲输入进行gram化,每个对应的分割都构成一个查询Term,同时针对每种分割也有对应的起始和结束查询,过程和构建词典的过程一样。这些条件之间是或的关系。这个用BooleanQuery可以实现。

b. 开始从词典构建的索引中使用上述条件进行查询

   I. 从查询结果中过滤掉自身(如果查询结果包含自身的话)

   II. 计算查询结果中的每个单词和输入word的编辑距离,过滤掉部分距离过小的单词(源码为: if(sugWord.score<min) continue;, 我觉得应该是过滤掉距离过大的词啊,不太明白这里)

   III. 放入以编辑距离为衡量指标的优先队列中,队列长度人为确定,具体根据要查询的建议单词的多少确定

   IV. 当队列长度满之后,返回结果,注意此处的结果要是以编辑距离增序的结果(使用优先队列的函数可以达到此要求)。

5. 编辑距离解释 : 编辑距离是衡量两个字符串相似度的值,介于0和1之间,0表示两个字符串完全相同,1表示两个字符串具有最大的不相似程度。常用的编辑距离有:LevensteinDistance和JaroWinklerDistance.

6. Comments on spellchecker : 从上面的分析来看,拼写检查和搜索建议其实相差非常小(我指如果都用lucene来完成的话),唯一的差别就是多了个编辑距离的检查。

推荐:Lucene41PostingWriter源码分析

原来看lucene4.0的posting格式(http://blog.csdn.net/jollyjumper/article/details/30017581),发现这还是比较简单的VInt格式,据说VInt压缩解压都不错(medium),

原文出处http://lolorosa.blogbus.com/logs/45646288.html   1. 首先来说一个N-Gram的概念,我不知道中文里怎么称呼这个,从Lucene SpellChecker的实现来看,N-Gram是指将一个单词划分成若干等

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。