本书介绍了分布式搜索引擎开发的原理与Java实现，主要包括全文检索的原理与实现、分布式算法与代码实现、SolrCloud和ElasticSearch的使用与原理等内容，并着重介绍了一种实现分布式中文搜索引擎的方法。

本书适合有Java程序设计基础的开发人员或者对分布式搜索引擎技术感兴趣的从业人员使用

前    言

搜索引擎成为人们获取信息不可或缺的工具。大数据技术的发展推动了多机集群的分布式搜索引擎技术走向成熟。普通的机器就可以搭建分布式搜索引擎。一些开源的分布式搜索引擎系统在数据存储、数据分析等方面的功能越来越强大。本书希望用通俗易懂的语言，让任何对分布式搜索引擎技术感兴趣的读者都能够有所收获。

本书的很多内容来源于搜索引擎、自然语言处理、金融等领域的项目开发和教学实践。在此感谢开源软件的开发者们，他们无私的工作丰富了本书的内容。

本书的第1章介绍开发分布式搜索引擎所需要的基本算法；第2章介绍如何从头开始自己动手写一个简单的全文检索软件包；第3章介绍Lucene的基本使用方法及其原理；第4章介绍使用JSP或者Struts 2开发搜索引擎用户界面，以及用户界面常用的Taglib；第5章介绍Solr实现分布式搜索引擎的解决方案——SolrCloud，以及它对SQL查询的支持；第6章介绍如何使用基于Lucene的ElasticSearch实现分布式搜索引擎。

鉴于ElasticSearch处于快速发展中，一些新版本的具体使用情况可以加入QQ群460405445，进行讨论。

本书配套的光盘中提供了相关的源代码，有的来源于猎兔搜索多年的开发经验积累，有的是经典算法实现。其中很多源代码都可以直接用于项目实践。

本书适合需要具体实现搜索引擎的程序员使用，对于信息检索等相关领域的研究人员也有一定的参考价值，同时猎兔搜索技术团队已经开发出以本书为基础的专门培训课程和商业软件。目前的一些分布式搜索引擎软件仍然有很多功能有待完善，作者真诚地希望通过本书把读者带入分布式搜索引擎开发的大门并认识更多的朋友。

感谢早期合著者、合作伙伴、员工、学员的支持，给我们提供了良好的工作基础。在将来，希望我们的分布式搜索引擎代码和技术能够像雨后春笋一样快速生长。

本书由罗刚、崔智杰编著，另外参与本书编写的还有张晓斐、石天盈、张继红、张进威、刘宇、何淑琴、任通通、高丹丹、徐友峰、孙宽，在此一并表示感谢。

编
者  

第2章  自己动手写全文检索

很多软件系统都需要对应的数据结构。信息检索中常用的数据结构是倒排索引。全文索引如图2-1所示。

图2-1  以词为基础的全文索引

　　倒排索引就是一个词到文档列表的映射。用HashMap实现的一个简单的倒排索引代码如下。

public class InvertedIndex {

         Map> index =

      
new HashMap>(); //词和这个词在文档中出现的位置信息

         //
索引文档

         public
void indexDoc(String docName, ArrayList words) {

                  int
pos = 0;

                  for
(String word : words) {

                          pos ;
// 位置

                          List
idx = index.get(word);

                          if
(idx == null) {

                                   idx
= new LinkedList();

                                   index.put(word,
idx);

                          }

                          idx.add(new
Tuple(docName, pos));

                          System.out.println(“indexed
” docName ” : ” pos ” words”);

                  }

         }

         //
搜索

         public
void search(List words) {

                  for
(String word : words) {

                          Set
answer = new HashSet();

                          List
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类。

2.1  构 建 索 引

　　为了按词建立索引，需要对文档分词。把这个分词类叫作Analyzer。文档内容作为输入流Reader的实例传入。

public class Analyzer {

         String[]
split(Reader reader) {

                  //对文档内容分词，并返回分词后的词数组

         }

}

　　首先建立文档索引，也就是正排索引，然后建立倒排索引。

　　正排索引用到的DocConsumer类如下。

public class DocConsumer {

         public
int docid; //文档编号

   
//词到频率的映射，频率存在长度是1的整数数组中

         HashMap frequencyList;

         int
words;  //文档长度，也就是这个文档包含多少个词

}

　　然后建立倒排索引。倒排索引用到的Posting类如下。

public class Posting implements
Serializable {

         public
int docid; //文档编号

         public
int freq; //这个词在文档中出现了多少次

         Posting(int
doc, int freq) {

                  this.docid
= doc;

                  this.freq
= freq;

         }

}

　　这里把文档作为一个字符串，如果有多列，可以把文档作为一个自定义的对象。

public class Document {

                  public
String title; //标题列

                  public
String content; //内容列

}

　　为了更灵活地定义文档的结构，可以专门定义一个Field类。

public class Field {

  /**
列名  */

 
public final String name;

  /**
列值 */

 
public String fieldsData;

}

　　一个Document类的实例中可以包含多个Field类的实例。

　　在真正的信息检索中，都是有多个列的，而且很多列有同等重要的地位。对于多个列的检索，简单的方法是：给每个倒排列附加一个bit-map，假设有N列，则Bitmap长度是N。例如，title出现，则第1位为1，content没出现，则第2位为0。实际的做法是：把一个列中所有的词连续存放到一起，一个专门的列定义文件中包括某个列中这些词信息的开始位置，如图2-2所示。

图2-2  多列索引

2.2  生成索引文件

　　词表是类似这样的数据结构：SortedMap。如果词表很小，内存能够放下，则可以使用折半查找算法来查询一个词对应的文档序列。如果内存不能完全放下倒排索引中的词表，如何利用索引文件查找？理论上，可以采用B树存储词表。为了简化实现，Lucene 3以前的版本使用了跳表。跳表把词组织成固定大小的块，例如每32个词放入一个新的块，然后在块上建立一个索引。记住每个块的开始词在文件中的位置。

　　但是，更好的分块方式是根据词共享了哪些前缀。按前缀组织词产生的词块大小是变化的。把相同前缀的词放到一起比按顺序放更好，这样在每个区块内，可化共享前缀的词，并且减少了产生的词索引。

　　这样做也可以加速词密集的查询。因为词索引成为了前缀Trie树。如果词典中不包含这个词，可以快速报告：“没有找到。”不需要在查找某一个词块之后才能确定没有。

　　这种方法叫作BlockTree。例如，词表中包含如下一些词。

able

above

apple

perfect

preface

prefecture

prefix

previous

profit

programmer

project

zoo

　　把a开头的3个词组织成一个词块：{able,above,apple}。p开头的词有8个，超过4个。把pre开头的4个词组织成一个词块：{ preface, prefecture, prefix , previous }。把pro开头的3个词组织成一个词块：{
profit, programmer, project }。因为以z开头的词只有1个，所以zoo单独组成一个词块。BlockTree索引如图2-3所示。

图2-3  BlockTree索引

　　根据有限状态转换找到词块在文件中存放的位置，如图2-4所示。

图2-4  有限状态转换

　　BlockTreeTermsReader类用于读索引。BlockTreeTermsWriter类用于写索引。

　　对于主键列来说，可以把所有的词和postings一起存到一个FST中。把FST保存到硬盘。

　　可以利用BlockTree的结构加快排序的速度。

2.3  读入索引文件

　　如果词表太大，则只读入上面几层的索引。为了批量读入数据，把数据分页存放。参考B树索引的分页读取。

public class Page{

         public
Page() {

                  data
= new byte[MAX_SPACE];

         }

         public
Page(byte[] apage) {

                  data
= apage;

         }

         /**

          *返回数据的字节数组

          *

          * @return页面的字节数组

          */

         public
byte[] getpage() {

                  return
data;

         }

         /**

          *用给定的字节数组设置页面

          *

          * @param array

          * 页面大小的字节数组

          */

         public
void setpage(byte[] array) {

                  data
= array;

         }

         public
byte[] getData() {

                  return
this.data;

         }

         /**

          *受保护的属性:字节数组

          *

          */

         protected
byte[] data;

}