Lucene 算法介绍 IR-Lab 胡晓光
Lucene 的主要算法 单个索引的构建 多个索引的增量归并 查找定位 快速排序算法 增量算法 归并算法 分级查找机制 如何判断当前的索引中是否有需要合并的段 归并算法 如果有，如何合并这些段 查找定位 分级查找机制 二分查找和顺序查找相结合
增量算法 数据结构 栈 主要参数 合并因子 Merge Factor 用于决定合并的频度
增量算法
增量算法 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; } }
增量算法 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)
增量算法 对于N篇文档 N=1M, b=2 gives just 20 indexes 索引中包含的文档数很不均匀，大致等比数列 插入文档的速度较快，查询速度稍慢
归并算法 已知各个段内的Term都是已排序的 用一个小根堆来表示存储各个段 堆中的顺序由段中当前第一个Term决定 取出当前堆中最小的元素写入新的索引段 从最小元素所在的段中删除该元素 重新调整堆
归并算法 例子 为简单起见用一个整数来表示Term 并且不含有相等的整数 Seg1: 1,4,5 Seg2: 2,9,10,12 合并后结果为：1,2,3,4,5,6,7,8,9,10,11,12
Step1 输入各个段并建立堆
Step2 弹出最小段 把最后一个节点放到根节点 调整成堆
Step3 从Seg1中输出整数1 把Seg1插回到堆的最后 调整成堆
查找算法 查找算法 分级查找 二分查找和顺序查找相结合
查找算法 把.tii文件调入内存 在内存中用二分查找找到相应的Block 把.tis文件中相应的Block调入内存 在Block中顺序找到相应的Term
查找算法 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;
小结 快速排序 增量归并算法 二分查找算法
谢谢！