Download presentation
Presentation is loading. Please wait.
1
Lucene 算法介绍 IR-Lab 胡晓光
2
Lucene 的主要算法 单个索引的构建 多个索引的增量归并 查找定位 快速排序算法 增量算法 归并算法 分级查找机制
如何判断当前的索引中是否有需要合并的段 归并算法 如果有，如何合并这些段 查找定位 分级查找机制 二分查找和顺序查找相结合
3
增量算法 数据结构 栈 主要参数 合并因子 Merge Factor 用于决定合并的频度
4
增量算法
5
增量算法 let b=3 be the merge factor; M=∞ for (size = 1; size < M; size *= b) { if (there are b indexes with size docs on top of the stack) { pop them off the stack; merge them into a single index; push the merged index onto the stack; } else { break; } }
6
增量算法 Step1 Step2 Step3 Step4 Step5 indexWriter.add(doc1)
SegmentInfos(_0,1) maybeMerge = false Step2 indexWriter.add(doc2) SegmentInfos(_0,1;_1,1) Step3 indexWriter.add(doc3) SegmentInfos( _0,1;_1,1;_2,1) maybeMerge = true Merge() SegmentInfos(_3,3) Step4 IndexWriter.add(doc4) SegmentInfos(_3,3;_4,1) maybeMerge=false Step5 indexWriter.close() flushRamSegments() SegmentInfos(_5,4)
7
增量算法 对于N篇文档 N=1M, b=2 gives just 20 indexes 索引中包含的文档数很不均匀，大致等比数列
插入文档的速度较快，查询速度稍慢
8
归并算法 已知各个段内的Term都是已排序的 用一个小根堆来表示存储各个段 堆中的顺序由段中当前第一个Term决定
取出当前堆中最小的元素写入新的索引段 从最小元素所在的段中删除该元素 重新调整堆
9
归并算法 例子 为简单起见用一个整数来表示Term 并且不含有相等的整数 Seg1: 1,4,5 Seg2: 2,9,10,12
合并后结果为：1,2,3,4,5,6,7,8,9,10,11,12
10
Step1 输入各个段并建立堆
11
Step2 弹出最小段 把最后一个节点放到根节点 调整成堆
12
Step3 从Seg1中输出整数1 把Seg1插回到堆的最后 调整成堆
13
查找算法 查找算法 分级查找 二分查找和顺序查找相结合
14
查找算法 把.tii文件调入内存 在内存中用二分查找找到相应的Block 把.tis文件中相应的Block调入内存
在Block中顺序找到相应的Term
15
查找算法 Term在索引里是有序排列的 采用二分查找机制来定位索引里的Term 在Index包TermInfosReader类中的实现代码
private final int getIndexOffset(Term term) throws IOException { int lo = 0; // binary search indexTerms[] int hi = indexTerms.length - 1; while (hi >= lo) { int mid = (lo + hi) >> 1; int delta = term.compareTo(indexTerms[mid]); if (delta < 0)hi = mid - 1; else if (delta > 0) lo = mid + 1; else return mid; } return hi;
16
小结 快速排序 增量归并算法 二分查找算法
17
谢谢！
Similar presentations
