- 自己动手写分布式搜索引擎
- 罗刚
- 601字
- 2020-11-28 15:52:42
第2章 自己动手写全文检索
很多软件系统都需要对应的数据结构。信息检索中最常用的数据结构是倒排索引。全文索引如图2-1所示。
图2-1 以词为基础的全文索引
倒排索引就是一个词到文档列表的映射。用HashMap实现的一个简单的倒排索引代码如下。
public class InvertedIndex {
Map<String, List<Tuple>> index =
new HashMap<String, List<Tuple>>(); //词和这个词在文档中出现的位置信息
// 索引文档
public void indexDoc(String docName, ArrayList<String> words) {
int pos = 0;
for (String word : words) {
pos++; // 位置
List<Tuple> idx = index.get(word);
if (idx == null) {
idx = new LinkedList<Tuple>();
index.put(word, idx);
}
idx.add(new Tuple(docName, pos));
System.out.println("indexed " + docName + " : " + pos + " words");
}
}
// 搜索
public void search(List<String> words) {
for (String word : words) {
Set<String> answer = new HashSet<String>();
List<Tuple> idx = index.get(word);
if (idx ! = null) {
for (Tuple t : idx) { //找到了一些文档
answer.add(t.docName);
}
}
System.out.print(word);
for (String f : answer) {
System.out.print(" " + f); //输出文件名
}
System.out.println("");
}
}
private class Tuple { //<文档名，位置>元组
private String docName; // 文档名
private int position; // 位置
public Tuple(String d, int position) {
this.docName = d;
this.position = position;
}
}
}
如果用户的查询中包含多个词，需要统计这些词在文档中出现的区间大小。区间越小的文档相关度越高。
public class Span {
public int start; // 开始位置
public int end; // 结束位置
public Span(int s, int e) {
start = s;
end = e;
}
public int length() {
return end - start + 1;
}
public String toString() {
return start + "-" + end;
}
}
建立索引往往很耗时，所以应把建立好的倒排索引保存到文件。查询之前先读入建立好的索引。
倒排索引由两个文件组成：一是文件存储倒排列表；另外一个是B树(Btree)存储词到倒排列表的映射。
索引的实现接口如下。
/** 一个索引应该实现的功能模板 */
public interface Index {
/** 使用数据库统计类构建索引 */
public void build(DatabaseStatistics s);
/** 从文件加载倒排索引 */
public void read(String filename) throws IOException;
/** 把内存中建好的倒排索引存入文件 */
public void flush(String filename) throws IOException;
}
可以把创建索引和读入索引的方法分到不同的类实现，分别为IndexWriter和IndexReader类。