lucene PriorityQueue 优先队列
如何把lucene索引放在内存中提供查询服务2008/01/02 18:27
转：http://www.lucene.org.cn/read.php?tid=65
<搜索引擎的典型周期: 搜集数据->建立索引->应答搜索请求>
无 论有多少精彩的应用, 这个印刷时代就诞生的公式都不会作废, 公式中最关键的成分是 1. 数据, 2.算法. 虽然二者中谁对结果质量更重要依然引起争论, 我的精力并未放在这两者上. 关于spider已有数本出名的专著, 算法原理的本质也早不是秘密, 这是搜索引擎必备的条件, 是基础设备而不是制胜的杀手锏. 面对一个活生生的搜索引擎, 研究这两者就像面对解剖台上的小白鼠, 却放下手术刀去查上课用的内脏图解. 我只注意实现, 实现是商业效率的体现, 这才是真刀真枪狼烟四起的地方.
抛开数据采集, 上边的周期分成两个相(phase), 1. Indexing(建立索引), 2.Searching(搜索). 还有一个现在看来显得古怪的词-检索, 图书馆系统大多用这个词. 中国人的词汇总是显得睿智, “索”本有求取寻找的意思, "索引"原本就是为搜索创造的. 那些题目是"倒排索引原理"大篇幅对索引和模式匹配进行比较的文章, 因此有些让人哭笑不得. 上述的两个phase正是lucene覆盖的范围(Lucene核心不提供crawler), 这两个phase一个用于生成索引(index), 一个用于从index取出数据, 可以看出Lucene的一切行为都和index有关. 幸好Lucene官方指南 Lucene in Action 在附录中用浅显的语言介绍了index的结构, 这让人了解Lucene怎么把一片片文档塞进去, 就像绞肉机把一片片五花肉里脊肉搅成肉酱. 但是有点遗憾的感觉: 搜索过程怎么把index中支离破碎的数据记录(index的结构用法着实很像数据库)恢复成检索结果? 就像主妇们怎么用屠夫的肉酱作出香喷喷的肉丸?
我从Query 的构造开始, 详细检验了Lucene处理Query的过程. 这种努力使我了解到index中的记录(就是数据库中的record概念), 如何在检索过程中起作用. 这是深入把握Lucene实现的基础, 若要对Lucene作基础的调整和改动, 自然缺不了这一步(这是我的动机之一). 这种探索也帮助我了解原始文档资料的各种属性如何决定搜索结果, 进一步的研究可以揭示出文档各属性的重要性以及文档对查询条件的敏感性, 从这里出发可以提炼出更普遍的原理, 再结合通用的Search Engine原理, 把"Search Engine是什么, 长什么样"深深地刻在脑海中. 这对我是一次很好的搜索引擎进阶的途径. 接下来的就是所谓SE优化( Search Engine Optimizing ), 不敢讲这种天怒人怨的话题...
查询机制
TAG：framework_lucene
Searching with TermQuery 查询机制
任 何用户, 包括系统开发者, 使用搜索引擎的共同方式只有一个: 查询(query). 整个搜索过程的目的是为了满足查询要求, 搜索过程是由查询贯穿的. 若没有指定查询, 而是从索引(index)的内容出发, "搜索"将是漫无目的且毫无意义的过程. 搜索过程的起点只能是索引.
以下引用自Lucene in Action 的入门章节, 在其中能看到Query是如何用来启动查询的.
CODE:
public class BasicSearchingTest extends LiaTestCase {
public void testTerm() throws Exception {
IndexSearcher searcher = new IndexSearcher(directory);
Term t = new Term(“subject”, “ant”);
Query query = new TermQuery(t);
Hits hits = searcher.search(query);
assertEquals(“JDwA”, 1, hits.length());
t = new Term(“subject”, “junit”);
hits = searcher.search(new TermQuery(t));
assertEquals(2, hits.length());
searcher.close();
}
}
被 称为面向对象设计经典范例的Lucene, 其架构确实能反映"查询"行为在真实世界模式, 这不愧是OOA/OOD方法带来的成熟设计. 这也让我对Lucene设计者的软件设计能力产生充足的敬佩, 要知道人家可是研究算法的. 通常搞学术和搞工程的人思想极不统一, 我同学在微软工作时曾经为研究院和工程院的代码差异头疼不已. Lucene的设计者们能把算法和代码集合得如此完美, 可以说是牛中之牛了.
我真正关心的是搜索算法如何依据Query导出查询结果. 上面的代码给我一些启示, 我知道了起点, 从searcher.search(query)开始, 我可以一步步了解Query在搜索过程里的作用机制.
为 了满足真实世界的语义, Lucene提供了众多Query. 上面代码中的TermQuery是最简单的Query, 日常搜索有许多直接或间就由TermQuery组合而成. search(termQuery)的构造最基础, 不经过繁琐的转换. 所以我从TermQuery出发, 一步步考察搜索的核心机制.
进入search 方法前, 我了解了这些限制条件: TermQuery的语义中每一个Term指一个(field, keyword)对, 其描述的查询条件是: "在指定的字段(标题、作者、内容...)中出现指定的keyword"; 高级的search方法可以处理自定义的Filter, Sort, 此处的考察对象是不假这些自定义选项的最简单的search.
有了以上的限制, 我考察的对象--TermQuery查询过程已经被彻底简化了. 但在他和更复杂的重载方法中, 开发人员应用了相同的思路, 举一反三是我们可以期望做到的.
CODE:
public class IndexSearcher extends Searcher {
public TopDocs search(Query query, Filter filter, final int nDocs)
throws IOException {
Scorer scorer = query.weight(this).scorer(reader);
if (scorer == null)
return new TopDocs(0, new ScoreDoc[0]);
final BitSet bits = filter!=null?filter.bits(reader):null;
final HitQueue hq = new HitQueue(nDocs);
final int[] totalHits = new int[1];
scorer.score(new HitCollector() {
public final void collect(int doc, float score) {
if (score > 0.0f &&
(bits==null || bits.get(doc))) {
totalHits[0]++;
hq.insert(new ScoreDoc(doc, score));
}
}
});
ScoreDoc[] scoreDocs = new ScoreDoc[hq.size()];
for (int i = hq.size()-1; i >= 0; i--)
scoreDocs[i] = (ScoreDoc)hq.pop();
return new TopDocs(totalHits[0], scoreDocs);
}
...
}
主干流程是:1.获取scorer对象
CODE:
Scorer scorer = termQuery.weight.scorer(indexReader)
2.调用这个Scorer对象(此处是TermScorer)的score (Collector)方法.
scorer.score(new HitCollector() {
...
});
这 两步之后, collector就把hq用查询结果填满了, 而用户得到的结果就是从hq中一个一个取出的. 这段代码中, indexReader用于读取index数据, 以供查询使用, Scorer负责用查询结果把Collector填满. 问题是,scorer的'查询结果'从哪里来? 如果IndexReader向Scorer提供数据, 数据内容是如何从索引文件中选取的?
Scorer 用一个匿名类Collector来收集满足TermQuery的Doc, 但Scorer怎么能够知道哪些文档符合Query? 真实查询并非在score()方法中进行, 从数据提取的角度来说, 现代搜索引擎都是从inverted index中提取的满足Term的文档列表. 是个人都知道inverted index里有什么, 由指定的keyword得到所有对应的文档就是利用inverted index数据结构完成的, 这也是搜索过程的核心--一个延续了数百年的索引方法. 我要考察的是, 在这个新式的OO搜索引擎框架中, 谁(哪个对象/类)负责提取term对应的记录, 他怎样把结果交给Scorer?
读取inverted index是IndexReader的责任, 这时已经提到过的. 关于这一点的知识来自于Lucene手册中星星点点的暗示和大量的代码阅读, 此处不纠缠这个问题, 现在关心的是Scorer和IndexReader怎样发生联系? 回忆一下上边的代码中TermQuery创建Scorer时用的参数, 正是IndexReader对象, 动动脚趾头也猜得出来TermQuery利用"创建"这种特权对score秘密动了手脚. 现在瞄一眼weight在构造scorer时玩了什么花样. 代码是这样写的
CODE:
public scorer weight#scorer(IndexReader reader){
TermDocs termDocs = reader.termDocs(term);
if (termDocs == null)
return null;
return new TermScorer(this, termDocs, getSimilarity(searcher),
reader.norms(term.field()));
}
class Scorer{
...
public void score(HitCollector hc) throws IOException {
while (next()) {
hc.collect(doc(), score());
}
}
...
public boolean next() throws IOException {
pointer++;
if (pointer >= pointerMax) {
pointerMax = termDocs.read(docs, freqs); // refill buffer
if (pointerMax != 0) {
pointer = 0;
} else {
termDocs.close(); // close stream
doc = Integer.MAX_VALUE; // set to sentinel value
return false;
}
}
doc = docs[pointer];
return true;
}
...
}
可以看出, 上面的问题唯一可能的答案是: weight在构造Scorer时已经为Scorer决定了查询内容就在那个termDocs里. Scorer的代码也表明, 它在遍历所有合法文档时,背后的查询动作是在穷举一个数组:doc[], 而这个数组的来源就是TermDocs. 剩下的问题是,TermDoc在整个查询中扮演何种角色--它是怎么读数据的
看看TermDoc是个虾米东东
reader 创建好TermDoc后调用TermDoc.seek(term). 这个方法在硬盘索引文件中找到term所对应的所有文档记录, 每条记录包含文档id和term在文档中出现的次数tf. 这些文档信息是编制索引时就建好的, 索引文件中每个term对应的文档记录按顺序紧密排列在一起, seek方法能找到这些记录在索引中的开始位置及满足term的文档总数. 以后, TermDoc在scorer中的作用就是读入每个符合term的文档及term在该文档中的tf, 由于建好了索引只需在索引文件中遍历即可, termDoc包含的df将用于此过程的遍历计数.就是说scorer接收到的那个termDoc是调用过seek的, 已经定位到了term对应的数据位置,这便让scorer能遍历termQuery中所有包含那个term的Doc.
scorer怎样遍历全部doc
读 数据又是另一门学问, 感兴趣的人也许研究过读一个100M文件,与读1000个1K byte文件有何区别,结果当然是震撼的.只要有可能,尽量读取整块数据而不是零碎地读取小数总不会让人失望，然而同样没有人会在构造一个对象时就去对一 个未知大小(可能真的包含100万个文档)的数据.只要没收到必要请求,任何人都会尽力避免这种冗长的操作. Lucene的设计者同样只是让在scorer在需要读入数据即第一次调用next()方法时调用termDoc的read方法读数据(代码中黑体部 分).为了避免零碎读取降低硬盘效率,termDoc.read()会一次性读入所有合法文档(当然仅包括文档id和tf, 建立索引的过程中,这两个数据一组组的放在专门的文件中,每个term对应的全部文档在这个文件里连续排列以避免零碎读取),scorer调用next ()语句,遍历read()返回的文档id数组,整个遍历过程只需把读出来的doc里的i进行++便万事大吉.
遍历过程中发生什么 事情大家心里应该很清楚,无非是把这些doc(这就是搜索结果)一个个添加到Collector中. 查询结束后, 我们将得到一个int数组, 里面保存着每个结果文档的id. 要使用这些查询结果,用户还需要从按照每篇文档的id文档库中取出结果, 这些只需调用searcher.doc(id)即可完成的事务性过程不在本"技术"文章讨论范围中.
所谓搜索原来如此简单...
面向对象
OO In Lucene Search 面向对象的Lucene
Nutch 正式立项以后, Apache 基金会的incubator里现存Lucene相关项目还有一个: Lucene4C. 顾名思义, 这是一个完完全全用C做成的搜索引擎, 很多对用Java做SE有意见的哥们热烈盼望这个东东快点孵化出来. 不过我担心已经已经用惯Lucene Java的同志们对Lucene4C的热情纯属叶公好龙, 理由很简单, 就像Lucene4C的说明中提到的, Lucene4C和Lucene Java的兼容是"底层兼容"即算法和索引格式的兼容, Lucene4C只是为那些惯于C代码的程序员而专门设计. 换言之, 虽然我们可以用Lucene4C搜索LuceneJava的索引或反过来用, 但绝对别指望Doug Cutting们会提供一个类似Java的接口API. 即使不提编程风格的差异, 那些只会把继承后的对象扔给API的家伙们怎么能在没有类的世界中生存呢, 没有了对象封装, 没有OCP/SRP, 还要处理种种指针, 光是调用memset/strcpy就够他们抓狂了.
从top level来讲, 将OOD的作品移植到C, 不仅是个浩大的工程, 还是个没法预期结果的定时炸弹. 不过我还是很盼望看到Lucene4C的成品, 我想抓住它的代码一行一行的读. 两种截然不同的设计理念生出一对双胞胎, 我要瞧瞧它们有什么不同, 相信Apache的天才们能让我在对比中学到很多.
所以要先搞清楚OO在Lucene中如何体现.
在 利用TermQuery这个最基本的Query研讨查询机制后, 细心观察就会发现, 本来满以为用来实现查询机制的那个类Searcher, 其实和检索机制几乎毫无瓜葛, 就算有, 也不过是调用各参数的方法, 把这个作为那个的参数, 再把那个传给另外的某某. 诸如此类. Searcher是个指挥家, 负责调度各功能使之协调, 用OO的话说, 就是对象间的协作. 各对象的功能被Searcher的操作过程利用了, 至于这些功能如何实现, Searcher全然不知.
OO的一大强项是业务逻辑层面的简洁表达, 清晰的语义甚至可以用优雅来形容. 这可以视为高内聚低耦合设计的副产品. Searcher.search()方法描述的逻辑是, Query把满足查询条件的文档ID结果放到Scorer中, Scorer把结果塞进Collector. 这里还有个暗示的语义: 无论输入顺序是什么Collector中的结果总是按照score排序的. 从上述语义出发, 很容易分辨出职责的内聚以及类间的耦合关系.
具体 考察一下TermQuery, 才更好理解内聚和耦合度. 在TermQuery的查询中, 对文档是否符合Term条件的判断由TermQuery负责, 而评分则由TermScorer负责. 单一职责原则SRP体现得非常明显, 而正是由于SRP被满足, Query/Scorer的耦合才得以解开.
设计的过程中, 职责内聚和抽象往往是同时完成. 所以在了解了Query/Scorer的职责后, Lucene的类结构显示出另一个十分重要的特性: 这就是开头提到的, Searcher与Query的查询过程无关. Searcher所要面对的查询是无类型的, 它需要处理各种查询. 查询的共同外部特征(在这里就是Searcher能访问的那些成员)抽象成了Query接口, Searcher与Scorer的关系也是这样. 由于使用了面向对象技术中至关重要的多态性, Searcher只面对接口(依赖倒置原则DIP), 这样就把查询的业务逻辑同各查询类型的算法逻辑有效的隔离开(解耦合)了. 这是职责内聚的结果, 同时也是把"查询"概念高度抽象的结果.
于 是我们看到Searcher实现了针对"查询"的业务逻辑的描述, 对任何种类的查询, 这一业务流程都适用(抽象), 而如何实现查询的算法(结果提取和评分), 则是Query/Searcher各实现类负责(内聚). 这么做的好处不言而喻——OCP, 对扩展来说, Lucene是完全开放的, 而对更改则是封闭因而是安全的.
设想现在需要查询连续出现的Term, 单个TermQuery当然不够用, 检索算法已经变了. 但我们不需要改变现存任何一个类, 只要构建新的Query/Scorer实现类, 比如PhraseQuery/Scorer. 目前Lucene 1.4.3版已经提供这样一个检索类型.
当然, Lucene是OOD方法的杰作, 不止上述几点, 在各个实现层次上都能找到类似的设计痕迹, 这为整个软件包的扩展和应用提供了强大的架构保证. 相信这也是Lucene得以流行的深层原因.
Index in Practice 索引: 按图索骥
TermDoc从哪读取数据,自然是硬盘上已经建好的某个index, 具体说, 是从index中的某个文件读取. 要了解TermDoc读了什么东东,怎么读这些东东,必要时得考察Lucene index的细部结构.
TermDoc是个抽象类,这很好,以后可以创建自己的index结构,建立自己的搜索算法.不过这之前先要了解Lucene是怎么干的,而这个抽象类并不包含这个信息,所以,我们首先要找到TermQuery使用哪个TermDoc实现.
回想一下scorer中的TermDoc从哪里来.
public class TermQuery extends Query {
private class TermWeight implements Weight {
public Scorer scorer(IndexReader reader) throws IOException {
TermDocs termDocs = reader.termDocs(term);
if (termDocs == null)
return null;
return new TermScorer(this, termDocs, getSimilarity(searcher),
reader.norms(term.field()));
}
...
}
...
}
从这段代码能找到真正创建TermDocs的那个类: IndexReader
用 哪个TermDocs实现并不是TermQuery说了算,而是IndexReader的权利. TermQuery得到怎样一个TermDocs, 全由我们传递给TermQuery.weight.scorer()的那个IndexReader决定. 将这个TermDocs定位到指定的Term也完全由IndexReader负责。很遗憾,IndexReader也是抽象类. 想知道内幕?先找找IndexReader实现类。
如果按照用户手册的方法进行搜索, IndexReader的一个静态方法将被调用,它返回我们需要的一个IndexReader实现:SegmentReader, 这是整个查询中用到的reader。
顺藤摸瓜,很容易找到SegmentTermDocs这个类,也就是默认查询中SegmentReader使用的TermDocs,大部分查询结果通过这个类的实例来遍历.现在是时候翻它老底了,看看它怎么遍历数据,这些数据又从哪来.
class IndexReader{
public TermDocs termDocs(Term term) throws IOException {
TermDocs termDocs = termDocs();
termDocs.seek(term);
return termDocs;
}
...
}
class SegmentReader extends IndexReader{
public final TermDocs termDocs() throws IOException {
return new SegmentTermDocs(this);
}
...
}
从已经列出的代码中, 能清晰地看到SegmentTermDocs从创建到传递给scorer前进行的一系列动作:
1. SegmentTermDocs构造: 根据parent设定自己的属性
2. IndexReader调用TermDocs.seek(term); 实现类中这一步具体化为SegmentReader调用SegmentTermDocs.seek(term)
第二步中, SegmentTermDocs进行了实际对index文件的读取. 而为了进行这些IO操作, 像前边说的, 必须依靠IndexReader才能完成, 这就是SegmentTermDocs构造是需要参数SegmentReader的原因.
seek (term)方法中SegmentTermDocs利用构造函数的唯一参数IndexReader(也就是创建它的那个reader, 称作parent"), 在硬盘索引文件中定位指定的term, 读入相关信息:df(包含term的文档数), 以及满足该term的文档集合在index文件中的位置. 这个位置后面, 是创建索引时就已排好的包含这个term的文档信息.
seek 完成后, TermDoc已经准备好读取数据了, 只要一声令下, TermDoc.read方法立刻能把每一篇文档的id和该term在这篇文档中的次数tf. 前面的记载是, scorer对象调用read方法, 尔后遍历其返回的全部文档, 把他们一个个塞到Collector中
精妙繁复的步骤: seek如何完成?
这要涉及索引结构, 现在可以掀开索引文件的一个角, 偷窥下.
tis文件: Term InformationS
frq文件: FReQuency
必 须注意到IO动作一定是在IndexReader的几个成员中作的, 所有其他类中的IO要么用这些成员的Clone来完成, 要么直接代理给IndexReader. SegmentTermDocs.seek(term)动作是通过IndexReader进行的, SegmentTermDocs把创建他的IndexReader尊为parent, 在seek这种关键时刻利用IndexReader来读取索引数据. 没办法, 索引文件的读取(输入流的建立和定位)全由IndexReader负责.
seek方法中为了实现定位而利用了IndexReader一个负责 Term定位的成员tis, 从他的类名TermInfoReader看就知道有什么用途. 这个tis从.tis文件中找到我们指定的term, 读出一切我们需要的信息: 这个term在多少个文档中出现过(df)/这些文档记录在frq文件的什么位置(起始位置) 等等.
得到这 些信息后, TermDoc再自己seek, 这一步很简单, 除了几个加法和赋值, 唯一有特色的是对.frq文件的输入流(FileInputStream)进行seek(), seek()的数量正好是tis返回的"文档记录在frq文件中的位置". 这个流是IndexReader初始化时创建的, 专门从frq文件读数据. IndexReader创建TermDoc时, TermDoc把这个输入流Clone()了一下, 赋给自己的成员. 这一seek()把.frq文件的输入指针定位好, 以后真正需要这个流的地方只有从frq文件读文档数据那一阵. 读数据的过程就发生在屡次提到过的termDoc.read()里, 现在我知道这个方法的实现是SegmentTermDocs.read().
read ()的实现是简单的顺序读取文件流, 具体过程涉及Lucene索引文件的二进制结构, 我不想这时候过多地纠缠. 大致了解termDoc如何定位数据, 心中的疑惑就能解开一半. 关于索引文件结构、各文件的关系、程序如何厘清这些关系, 还值得更多的讨论.
到这一步, 结合已熟知的scorer调用TermDoc的方式, 查询过程的基本途径已经隐约呈现出来了.
<搜索引擎的典型周期: 搜集数据->建立索引->应答搜索请求>
无 论有多少精彩的应用, 这个印刷时代就诞生的公式都不会作废, 公式中最关键的成分是 1. 数据, 2.算法. 虽然二者中谁对结果质量更重要依然引起争论, 我的精力并未放在这两者上. 关于spider已有数本出名的专著, 算法原理的本质也早不是秘密, 这是搜索引擎必备的条件, 是基础设备而不是制胜的杀手锏. 面对一个活生生的搜索引擎, 研究这两者就像面对解剖台上的小白鼠, 却放下手术刀去查上课用的内脏图解. 我只注意实现, 实现是商业效率的体现, 这才是真刀真枪狼烟四起的地方.
抛开数据采集, 上边的周期分成两个相(phase), 1. Indexing(建立索引), 2.Searching(搜索). 还有一个现在看来显得古怪的词-检索, 图书馆系统大多用这个词. 中国人的词汇总是显得睿智, “索”本有求取寻找的意思, "索引"原本就是为搜索创造的. 那些题目是"倒排索引原理"大篇幅对索引和模式匹配进行比较的文章, 因此有些让人哭笑不得. 上述的两个phase正是lucene覆盖的范围(Lucene核心不提供crawler), 这两个phase一个用于生成索引(index), 一个用于从index取出数据, 可以看出Lucene的一切行为都和index有关. 幸好Lucene官方指南 Lucene in Action 在附录中用浅显的语言介绍了index的结构, 这让人了解Lucene怎么把一片片文档塞进去, 就像绞肉机把一片片五花肉里脊肉搅成肉酱. 但是有点遗憾的感觉: 搜索过程怎么把index中支离破碎的数据记录(index的结构用法着实很像数据库)恢复成检索结果? 就像主妇们怎么用屠夫的肉酱作出香喷喷的肉丸?
我从Query 的构造开始, 详细检验了Lucene处理Query的过程. 这种努力使我了解到index中的记录(就是数据库中的record概念), 如何在检索过程中起作用. 这是深入把握Lucene实现的基础, 若要对Lucene作基础的调整和改动, 自然缺不了这一步(这是我的动机之一). 这种探索也帮助我了解原始文档资料的各种属性如何决定搜索结果, 进一步的研究可以揭示出文档各属性的重要性以及文档对查询条件的敏感性, 从这里出发可以提炼出更普遍的原理, 再结合通用的Search Engine原理, 把"Search Engine是什么, 长什么样"深深地刻在脑海中. 这对我是一次很好的搜索引擎进阶的途径. 接下来的就是所谓SE优化( Search Engine Optimizing ), 不敢讲这种天怒人怨的话题...
查询机制
TAG：framework_lucene
Searching with TermQuery 查询机制
任 何用户, 包括系统开发者, 使用搜索引擎的共同方式只有一个: 查询(query). 整个搜索过程的目的是为了满足查询要求, 搜索过程是由查询贯穿的. 若没有指定查询, 而是从索引(index)的内容出发, "搜索"将是漫无目的且毫无意义的过程. 搜索过程的起点只能是索引.
以下引用自Lucene in Action 的入门章节, 在其中能看到Query是如何用来启动查询的.
CODE:
public class BasicSearchingTest extends LiaTestCase {
public void testTerm() throws Exception {
IndexSearcher searcher = new IndexSearcher(directory);
Term t = new Term(“subject”, “ant”);
Query query = new TermQuery(t);
Hits hits = searcher.search(query);
assertEquals(“JDwA”, 1, hits.length());
t = new Term(“subject”, “junit”);
hits = searcher.search(new TermQuery(t));
assertEquals(2, hits.length());
searcher.close();
}
}
被 称为面向对象设计经典范例的Lucene, 其架构确实能反映"查询"行为在真实世界模式, 这不愧是OOA/OOD方法带来的成熟设计. 这也让我对Lucene设计者的软件设计能力产生充足的敬佩, 要知道人家可是研究算法的. 通常搞学术和搞工程的人思想极不统一, 我同学在微软工作时曾经为研究院和工程院的代码差异头疼不已. Lucene的设计者们能把算法和代码集合得如此完美, 可以说是牛中之牛了.
我真正关心的是搜索算法如何依据Query导出查询结果. 上面的代码给我一些启示, 我知道了起点, 从searcher.search(query)开始, 我可以一步步了解Query在搜索过程里的作用机制.
为 了满足真实世界的语义, Lucene提供了众多Query. 上面代码中的TermQuery是最简单的Query, 日常搜索有许多直接或间就由TermQuery组合而成. search(termQuery)的构造最基础, 不经过繁琐的转换. 所以我从TermQuery出发, 一步步考察搜索的核心机制.
进入search 方法前, 我了解了这些限制条件: TermQuery的语义中每一个Term指一个(field, keyword)对, 其描述的查询条件是: "在指定的字段(标题、作者、内容...)中出现指定的keyword"; 高级的search方法可以处理自定义的Filter, Sort, 此处的考察对象是不假这些自定义选项的最简单的search.
有了以上的限制, 我考察的对象--TermQuery查询过程已经被彻底简化了. 但在他和更复杂的重载方法中, 开发人员应用了相同的思路, 举一反三是我们可以期望做到的.
CODE:
public class IndexSearcher extends Searcher {
public TopDocs search(Query query, Filter filter, final int nDocs)
throws IOException {
Scorer scorer = query.weight(this).scorer(reader);
if (scorer == null)
return new TopDocs(0, new ScoreDoc[0]);
final BitSet bits = filter!=null?filter.bits(reader):null;
final HitQueue hq = new HitQueue(nDocs);
final int[] totalHits = new int[1];
scorer.score(new HitCollector() {
public final void collect(int doc, float score) {
if (score > 0.0f &&
(bits==null || bits.get(doc))) {
totalHits[0]++;
hq.insert(new ScoreDoc(doc, score));
}
}
});
ScoreDoc[] scoreDocs = new ScoreDoc[hq.size()];
for (int i = hq.size()-1; i >= 0; i--)
scoreDocs[i] = (ScoreDoc)hq.pop();
return new TopDocs(totalHits[0], scoreDocs);
}
...
}
主干流程是:1.获取scorer对象
CODE:
Scorer scorer = termQuery.weight.scorer(indexReader)
2.调用这个Scorer对象(此处是TermScorer)的score (Collector)方法.
scorer.score(new HitCollector() {
...
});
这 两步之后, collector就把hq用查询结果填满了, 而用户得到的结果就是从hq中一个一个取出的. 这段代码中, indexReader用于读取index数据, 以供查询使用, Scorer负责用查询结果把Collector填满. 问题是,scorer的'查询结果'从哪里来? 如果IndexReader向Scorer提供数据, 数据内容是如何从索引文件中选取的?
Scorer 用一个匿名类Collector来收集满足TermQuery的Doc, 但Scorer怎么能够知道哪些文档符合Query? 真实查询并非在score()方法中进行, 从数据提取的角度来说, 现代搜索引擎都是从inverted index中提取的满足Term的文档列表. 是个人都知道inverted index里有什么, 由指定的keyword得到所有对应的文档就是利用inverted index数据结构完成的, 这也是搜索过程的核心--一个延续了数百年的索引方法. 我要考察的是, 在这个新式的OO搜索引擎框架中, 谁(哪个对象/类)负责提取term对应的记录, 他怎样把结果交给Scorer?
读取inverted index是IndexReader的责任, 这时已经提到过的. 关于这一点的知识来自于Lucene手册中星星点点的暗示和大量的代码阅读, 此处不纠缠这个问题, 现在关心的是Scorer和IndexReader怎样发生联系? 回忆一下上边的代码中TermQuery创建Scorer时用的参数, 正是IndexReader对象, 动动脚趾头也猜得出来TermQuery利用"创建"这种特权对score秘密动了手脚. 现在瞄一眼weight在构造scorer时玩了什么花样. 代码是这样写的
CODE:
public scorer weight#scorer(IndexReader reader){
TermDocs termDocs = reader.termDocs(term);
if (termDocs == null)
return null;
return new TermScorer(this, termDocs, getSimilarity(searcher),
reader.norms(term.field()));
}
class Scorer{
...
public void score(HitCollector hc) throws IOException {
while (next()) {
hc.collect(doc(), score());
}
}
...
public boolean next() throws IOException {
pointer++;
if (pointer >= pointerMax) {
pointerMax = termDocs.read(docs, freqs); // refill buffer
if (pointerMax != 0) {
pointer = 0;
} else {
termDocs.close(); // close stream
doc = Integer.MAX_VALUE; // set to sentinel value
return false;
}
}
doc = docs[pointer];
return true;
}
...
}
可以看出, 上面的问题唯一可能的答案是: weight在构造Scorer时已经为Scorer决定了查询内容就在那个termDocs里. Scorer的代码也表明, 它在遍历所有合法文档时,背后的查询动作是在穷举一个数组:doc[], 而这个数组的来源就是TermDocs. 剩下的问题是,TermDoc在整个查询中扮演何种角色--它是怎么读数据的
看看TermDoc是个虾米东东
reader 创建好TermDoc后调用TermDoc.seek(term). 这个方法在硬盘索引文件中找到term所对应的所有文档记录, 每条记录包含文档id和term在文档中出现的次数tf. 这些文档信息是编制索引时就建好的, 索引文件中每个term对应的文档记录按顺序紧密排列在一起, seek方法能找到这些记录在索引中的开始位置及满足term的文档总数. 以后, TermDoc在scorer中的作用就是读入每个符合term的文档及term在该文档中的tf, 由于建好了索引只需在索引文件中遍历即可, termDoc包含的df将用于此过程的遍历计数.就是说scorer接收到的那个termDoc是调用过seek的, 已经定位到了term对应的数据位置,这便让scorer能遍历termQuery中所有包含那个term的Doc.
scorer怎样遍历全部doc
读 数据又是另一门学问, 感兴趣的人也许研究过读一个100M文件,与读1000个1K byte文件有何区别,结果当然是震撼的.只要有可能,尽量读取整块数据而不是零碎地读取小数总不会让人失望，然而同样没有人会在构造一个对象时就去对一 个未知大小(可能真的包含100万个文档)的数据.只要没收到必要请求,任何人都会尽力避免这种冗长的操作. Lucene的设计者同样只是让在scorer在需要读入数据即第一次调用next()方法时调用termDoc的read方法读数据(代码中黑体部 分).为了避免零碎读取降低硬盘效率,termDoc.read()会一次性读入所有合法文档(当然仅包括文档id和tf, 建立索引的过程中,这两个数据一组组的放在专门的文件中,每个term对应的全部文档在这个文件里连续排列以避免零碎读取),scorer调用next ()语句,遍历read()返回的文档id数组,整个遍历过程只需把读出来的doc里的i进行++便万事大吉.
遍历过程中发生什么 事情大家心里应该很清楚,无非是把这些doc(这就是搜索结果)一个个添加到Collector中. 查询结束后, 我们将得到一个int数组, 里面保存着每个结果文档的id. 要使用这些查询结果,用户还需要从按照每篇文档的id文档库中取出结果, 这些只需调用searcher.doc(id)即可完成的事务性过程不在本"技术"文章讨论范围中.
所谓搜索原来如此简单...
面向对象
OO In Lucene Search 面向对象的Lucene
Nutch 正式立项以后, Apache 基金会的incubator里现存Lucene相关项目还有一个: Lucene4C. 顾名思义, 这是一个完完全全用C做成的搜索引擎, 很多对用Java做SE有意见的哥们热烈盼望这个东东快点孵化出来. 不过我担心已经已经用惯Lucene Java的同志们对Lucene4C的热情纯属叶公好龙, 理由很简单, 就像Lucene4C的说明中提到的, Lucene4C和Lucene Java的兼容是"底层兼容"即算法和索引格式的兼容, Lucene4C只是为那些惯于C代码的程序员而专门设计. 换言之, 虽然我们可以用Lucene4C搜索LuceneJava的索引或反过来用, 但绝对别指望Doug Cutting们会提供一个类似Java的接口API. 即使不提编程风格的差异, 那些只会把继承后的对象扔给API的家伙们怎么能在没有类的世界中生存呢, 没有了对象封装, 没有OCP/SRP, 还要处理种种指针, 光是调用memset/strcpy就够他们抓狂了.
从top level来讲, 将OOD的作品移植到C, 不仅是个浩大的工程, 还是个没法预期结果的定时炸弹. 不过我还是很盼望看到Lucene4C的成品, 我想抓住它的代码一行一行的读. 两种截然不同的设计理念生出一对双胞胎, 我要瞧瞧它们有什么不同, 相信Apache的天才们能让我在对比中学到很多.
所以要先搞清楚OO在Lucene中如何体现.
在 利用TermQuery这个最基本的Query研讨查询机制后, 细心观察就会发现, 本来满以为用来实现查询机制的那个类Searcher, 其实和检索机制几乎毫无瓜葛, 就算有, 也不过是调用各参数的方法, 把这个作为那个的参数, 再把那个传给另外的某某. 诸如此类. Searcher是个指挥家, 负责调度各功能使之协调, 用OO的话说, 就是对象间的协作. 各对象的功能被Searcher的操作过程利用了, 至于这些功能如何实现, Searcher全然不知.
OO的一大强项是业务逻辑层面的简洁表达, 清晰的语义甚至可以用优雅来形容. 这可以视为高内聚低耦合设计的副产品. Searcher.search()方法描述的逻辑是, Query把满足查询条件的文档ID结果放到Scorer中, Scorer把结果塞进Collector. 这里还有个暗示的语义: 无论输入顺序是什么Collector中的结果总是按照score排序的. 从上述语义出发, 很容易分辨出职责的内聚以及类间的耦合关系.
具体 考察一下TermQuery, 才更好理解内聚和耦合度. 在TermQuery的查询中, 对文档是否符合Term条件的判断由TermQuery负责, 而评分则由TermScorer负责. 单一职责原则SRP体现得非常明显, 而正是由于SRP被满足, Query/Scorer的耦合才得以解开.
设计的过程中, 职责内聚和抽象往往是同时完成. 所以在了解了Query/Scorer的职责后, Lucene的类结构显示出另一个十分重要的特性: 这就是开头提到的, Searcher与Query的查询过程无关. Searcher所要面对的查询是无类型的, 它需要处理各种查询. 查询的共同外部特征(在这里就是Searcher能访问的那些成员)抽象成了Query接口, Searcher与Scorer的关系也是这样. 由于使用了面向对象技术中至关重要的多态性, Searcher只面对接口(依赖倒置原则DIP), 这样就把查询的业务逻辑同各查询类型的算法逻辑有效的隔离开(解耦合)了. 这是职责内聚的结果, 同时也是把"查询"概念高度抽象的结果.
于 是我们看到Searcher实现了针对"查询"的业务逻辑的描述, 对任何种类的查询, 这一业务流程都适用(抽象), 而如何实现查询的算法(结果提取和评分), 则是Query/Searcher各实现类负责(内聚). 这么做的好处不言而喻——OCP, 对扩展来说, Lucene是完全开放的, 而对更改则是封闭因而是安全的.
设想现在需要查询连续出现的Term, 单个TermQuery当然不够用, 检索算法已经变了. 但我们不需要改变现存任何一个类, 只要构建新的Query/Scorer实现类, 比如PhraseQuery/Scorer. 目前Lucene 1.4.3版已经提供这样一个检索类型.
当然, Lucene是OOD方法的杰作, 不止上述几点, 在各个实现层次上都能找到类似的设计痕迹, 这为整个软件包的扩展和应用提供了强大的架构保证. 相信这也是Lucene得以流行的深层原因.
Index in Practice 索引: 按图索骥
TermDoc从哪读取数据,自然是硬盘上已经建好的某个index, 具体说, 是从index中的某个文件读取. 要了解TermDoc读了什么东东,怎么读这些东东,必要时得考察Lucene index的细部结构.
TermDoc是个抽象类,这很好,以后可以创建自己的index结构,建立自己的搜索算法.不过这之前先要了解Lucene是怎么干的,而这个抽象类并不包含这个信息,所以,我们首先要找到TermQuery使用哪个TermDoc实现.
回想一下scorer中的TermDoc从哪里来.
public class TermQuery extends Query {
private class TermWeight implements Weight {
public Scorer scorer(IndexReader reader) throws IOException {
TermDocs termDocs = reader.termDocs(term);
if (termDocs == null)
return null;
return new TermScorer(this, termDocs, getSimilarity(searcher),
reader.norms(term.field()));
}
...
}
...
}
从这段代码能找到真正创建TermDocs的那个类: IndexReader
用 哪个TermDocs实现并不是TermQuery说了算,而是IndexReader的权利. TermQuery得到怎样一个TermDocs, 全由我们传递给TermQuery.weight.scorer()的那个IndexReader决定. 将这个TermDocs定位到指定的Term也完全由IndexReader负责。很遗憾,IndexReader也是抽象类. 想知道内幕?先找找IndexReader实现类。
如果按照用户手册的方法进行搜索, IndexReader的一个静态方法将被调用,它返回我们需要的一个IndexReader实现:SegmentReader, 这是整个查询中用到的reader。
顺藤摸瓜,很容易找到SegmentTermDocs这个类,也就是默认查询中SegmentReader使用的TermDocs,大部分查询结果通过这个类的实例来遍历.现在是时候翻它老底了,看看它怎么遍历数据,这些数据又从哪来.
class IndexReader{
public TermDocs termDocs(Term term) throws IOException {
TermDocs termDocs = termDocs();
termDocs.seek(term);
return termDocs;
}
...
}
class SegmentReader extends IndexReader{
public final TermDocs termDocs() throws IOException {
return new SegmentTermDocs(this);
}
...
}
从已经列出的代码中, 能清晰地看到SegmentTermDocs从创建到传递给scorer前进行的一系列动作:
1. SegmentTermDocs构造: 根据parent设定自己的属性
2. IndexReader调用TermDocs.seek(term); 实现类中这一步具体化为SegmentReader调用SegmentTermDocs.seek(term)
第二步中, SegmentTermDocs进行了实际对index文件的读取. 而为了进行这些IO操作, 像前边说的, 必须依靠IndexReader才能完成, 这就是SegmentTermDocs构造是需要参数SegmentReader的原因.
seek (term)方法中SegmentTermDocs利用构造函数的唯一参数IndexReader(也就是创建它的那个reader, 称作parent"), 在硬盘索引文件中定位指定的term, 读入相关信息:df(包含term的文档数), 以及满足该term的文档集合在index文件中的位置. 这个位置后面, 是创建索引时就已排好的包含这个term的文档信息.
seek 完成后, TermDoc已经准备好读取数据了, 只要一声令下, TermDoc.read方法立刻能把每一篇文档的id和该term在这篇文档中的次数tf. 前面的记载是, scorer对象调用read方法, 尔后遍历其返回的全部文档, 把他们一个个塞到Collector中
精妙繁复的步骤: seek如何完成?
这要涉及索引结构, 现在可以掀开索引文件的一个角, 偷窥下.
tis文件: Term InformationS
frq文件: FReQuency
必 须注意到IO动作一定是在IndexReader的几个成员中作的, 所有其他类中的IO要么用这些成员的Clone来完成, 要么直接代理给IndexReader. SegmentTermDocs.seek(term)动作是通过IndexReader进行的, SegmentTermDocs把创建他的IndexReader尊为parent, 在seek这种关键时刻利用IndexReader来读取索引数据. 没办法, 索引文件的读取(输入流的建立和定位)全由IndexReader负责.
seek方法中为了实现定位而利用了IndexReader一个负责 Term定位的成员tis, 从他的类名TermInfoReader看就知道有什么用途. 这个tis从.tis文件中找到我们指定的term, 读出一切我们需要的信息: 这个term在多少个文档中出现过(df)/这些文档记录在frq文件的什么位置(起始位置) 等等.
得到这 些信息后, TermDoc再自己seek, 这一步很简单, 除了几个加法和赋值, 唯一有特色的是对.frq文件的输入流(FileInputStream)进行seek(), seek()的数量正好是tis返回的"文档记录在frq文件中的位置". 这个流是IndexReader初始化时创建的, 专门从frq文件读数据. IndexReader创建TermDoc时, TermDoc把这个输入流Clone()了一下, 赋给自己的成员. 这一seek()把.frq文件的输入指针定位好, 以后真正需要这个流的地方只有从frq文件读文档数据那一阵. 读数据的过程就发生在屡次提到过的termDoc.read()里, 现在我知道这个方法的实现是SegmentTermDocs.read().
read ()的实现是简单的顺序读取文件流, 具体过程涉及Lucene索引文件的二进制结构, 我不想这时候过多地纠缠. 大致了解termDoc如何定位数据, 心中的疑惑就能解开一半. 关于索引文件结构、各文件的关系、程序如何厘清这些关系, 还值得更多的讨论.
到这一步, 结合已熟知的scorer调用TermDoc的方式, 查询过程的基本途径已经隐约呈现出来了.
