搜索引擎(lucene及周边) 涉及的一些算法总结

一)分词

1)正向/逆向最大匹配算法

典型:IKAnalyzer采用的是正向迭代最细粒度切分算法

IKAnalyzer源码简单分析:

http://www.cnblogs.com/huangfox/p/3282003.html

2)字典树(trieTree)

trieTree实现

http://www.cnblogs.com/huangfox/archive/2012/04/27/2474185.html

中文分词遇到的问题:

a)标准trieTree节点采用数组存储指针,如果是英文a-z用26长度的数组表示,但是中文不能用这种存储方式,节点数组长度等于中文字数。(内存撑不住!)

b)如何节点内部查询?采用数组进行二分查找,或者采用map。(ik结合了这两种方式)

具体还可以参考:

http://hxraid.iteye.com/blog/618962

3)消歧算法

4)新词识别算法(机构名、品牌名、专业名词、缩略语、网络新词等)

具体参考:

http://www.programmer.com.cn/12276/

二)索引

1)压缩算法

前缀后缀规则、差值规则

2)跳跃表

为了提高查找的性能,Lucene在很多地方采取的跳跃表的数据结构。

跳跃表(Skip List)是如图的一种数据结构,有以下几个基本特征:

  • 元素是按顺序排列的,在Lucene中,或是按字典顺序排列,或是按从小到大顺序排列。
  • 跳跃是有间隔的(Interval),也即每次跳跃的元素数,间隔是事先配置好的,如图跳跃表的间隔为3。
  • 跳跃表是由层次的(level),每一层的每隔指定间隔的元素构成上一层,如图跳跃表共有2层。

搜索引擎(lucene及周边) 涉及的一些算法总结

节选自:http://forfuture1978.iteye.com/blog/546824

三)检索

1)文本相关性算法(tfIdf)

tfIdf的详细解释:

http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html

lucene打分过程:

http://www.cnblogs.com/huangfox/archive/2012/07/02/2573333.html

2)字段排序过程中——优先级队列

请参考:

http://www.cnblogs.com/huangfox/archive/2012/07/11/2586232.html

相关知识:

a)堆排序

http://www.cnblogs.com/huangfox/archive/2012/06/30/2571216.html

四)扩展

1)相似检索(MoreLikeThis)

关键步骤:

a)字频统计

b)去噪(黑名单、词条长度)

c)计算词权(tfIdf)

d)构建query

F)检索

具体参考:

http://www.cnblogs.com/huangfox/archive/2012/07/05/2578179.html

2)拼写检查(SpellingChecker)

关键算法:

a)N-gram

b)编辑距离

具体参考:

http://www.cnblogs.com/huangfox/archive/2012/02/14/2350349.html

3)电商排序模型

多因子综合排序(略)

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

其他

1)自动关键词的应用(牵涉到相似检索)

2)同义词、近义词的应用

上一篇:Viewer.js 是一款强大的 jQuery 图像浏览插件。


下一篇:Maven提高篇系列之五——处理依赖冲突