2.4 查询
查询一个词时，将直接把对应的文档编号列表找出来，然后按相关度返回文档列表。如果内存不能完全存下所有的文档列表，可以把用户最经常查询的词的文档列表放到内存中，不常查询的词的文档列表放到文件中。
查询两个词“NBA视频”时，则对“NBA”这个词对应的文档编号列表和“视频”这个词对应的文档编号列表做交集(Intersection)运算后返回。例如，在倒排索引表中检索出包含“NBA”一词的文档列表为docList(“NBA”)=(1, 5, 9, 12)，表示这4个文档编号的文档含有“NBA”这个词。包含“视频”的文档列表为docList(“视频”)= (5, 7, 9, 11)。这样同时包含“NBA”和“视频”这两个词的文档为docList(“NBA”)∩docList(“视频”)=(5, 9)。这里的“∩”表示文档列表集合求交集运算。
计算过程类似归并排序，如图2-5所示。
图2-5 文档列表集合求交集
多文档列表求交集计算的示例代码如下。
public ArrayList<Integer> intersection(int[] docListA, int[] docListB) {
ArrayList<Integer> ret = new ArrayList<Integer>();
int aindex = 0;
int bindex = 0;
while (aindex < docListA.length && bindex < docListB.length) {
if (docListA[aindex] == docListB[bindex]) {
// 找到在两个数组中都出现的值
ret.add(docListA[aindex]);
aindex++;
bindex++;
} else if (docListA[aindex] < docListB[bindex]) {
aindex++;
} else {
bindex++;
}
}
return ret;
}
使用构建好的倒排索引和文档索引执行搜索。
public class IndexSearcher {
InvertedIndex index; //倒排索引
DocumentIndex docIndex; //文档索引
}
根据一个或者多个查询词执行搜索，可以指定最多返回的搜索结果数量。如果不指定返回结果数量，则返回全部相关的文档。
只需要使用浮点数就能够区分相关文档和不太相关的文档，所以把score定义成float类型。
/** 用于搜索的辅助类。支持对文档按相关度排序 */
public class ScoreDoc implements Comparable<ScoreDoc> {
DocumentData doc; //文档相关的信息，包括文档编号等
public float score; //表示这个文档和查询词有多相关
public ScoreDoc(DocumentData d, float b) { //构造方法
doc = d;
score = b;
}
public int compareTo(ScoreDoc other) { // 按相关度排序
// 返回值并不重要，保证需要的顺序就行
ScoreDoc o = other;
return (o.score == score) ? (0) : ((score > o.score) ? (-1) : (1));
}
public String toString() { //格式化输出
return doc.filename + ":\t" + doc.docid + "\n" + score;
}
}
如果要对一个大的索引库排序，而且一个词有很多结果，则对所有这些结果排序然后分页显示会很慢。
搜索时要排序，但实际上并不需要对所有的结果排序。如果只要第1页，就只对前10个结果排序。排序是和显示页相关的。前10个结果是怎么得到的呢？是用最小堆得到的，须先构建最小堆。
按相关度排序简介如下。
用优先队列记录前n 个评分最高的文档。优先队列用最小堆实现。把前n 个评分最高的文档放到一个最小堆中。堆虽然是一个二叉树，但是一般使用数组实现，不需要元素之间的指针，如图2-6所示。
图2-6 二叉堆
heap[0]左边的子元素是heap[1]，右边的子元素是heap[2]。heap[1]左边的子元素是heap[3]，右边的子元素是heap[4]。heap[2]左边的子元素是heap[5]，右边的子元素是heap[6]。则heap[i]左边的子元素是heap[2i+1]，右边的子元素是heap[2i+2]。
如果要简化计算，第一个位置可以不用，则根节点位于heap[1], heap[1]左边的子元素是heap[2]，右边的子元素是heap[3]。则heap[i]左边的子元素是heap[2i]，右边的子元素是heap[2i+1]。
因为没有使用第0个位置，所以数组要多分配一个位置。
private final T[] heap;
public PriorityQueue(int maxSize) {
int heapSize = maxSize + 1;
heap = (T[]) new Object[heapSize]; // 没有用heap[0]
}
建立容量为n的最小堆，记录前n个评分最高的文档。对于每个和查询词相关的文档，如果它比堆顶文档的相关度更高，则删除堆顶元素，把当前文档插入堆中，然后自顶向下调节，维护最小堆。如果它比堆顶文档相关度低，则直接扔掉。遍历完整个相关文档集合，堆中的文档就是最相关的n个文档了。
public T insertWithOverflow(T element) {
if (size < maxSize) {
add(element);
return null;
} else if (size > 0 && ! lessThan(element, heap[1])) {
//堆中最小的元素用更大的元素替换了
T ret = heap[1];
heap[1] = element;
updateTop();
return ret;
} else {
return element;
}
}
要在堆中增加一个元素，必须执行一个upHeap。可以用add(element) 方法调用upHeap。要从最小堆中取得最小的元素就需要从堆中删除根节点，这叫作downHeap。可以用pop()方法调用downHeap。
最后把最小堆中的文档放入ScoreDoc。
final ScoreDoc[] scoreDocs = new ScoreDoc[hq.size()];
for (int i = hq.size() -1; i >= 0; i--) // 把最相关的文档放入数组
scoreDocs[i] = hq.pop(); //先取出来最不相关的文档