一个朴素的搜索引擎实现

2019-09-11 16:52:18 浏览数 (1)

今天我们要使用 Lucene 来实现一个简单的搜索引擎,我们要使用上一节爬取的果壳网语料库来构建索引,然后在索引的基础上进行关键词查询。

上一节果壳网的语料库放在了 Redis 中如下,有一个有效的文章 ID 集合,对于每一篇文章都会有一个 hash 结构存储了它的标题和 HTML 内容。

代码语言:javascript复制
valid_article_ids => set(article_id)

article_${id} => hash(title=>${title}, html=>${html})

Lucene 需要将构建的索引库放在一个指定的目录中,在这个目录里会存放很多种不同功用的文件。构建索引的目标就是生成倒排索引,在本例中,会建立一个 title 标题的倒排索引和一个 html 内容的倒排索引,这是两个不同的倒排索引。

倒排索引就是分词词汇和文档 ID 列表的映射。如果是英文,那么就是一个个的英文单词,如果是中文,就需要中文分词词库来切分标题和内容来得到一个个的中文词语。这里的「文档 ID」 不是指文章 ID,而是 Lucene 内部的 Document 对象的唯一 ID。我们通过调用 Lucene 的 addDocument 方法添加进去的每一篇文章在 Lucene 内部都会有一个 Document 对象。

代码语言:javascript复制
class InvertedIndex {
  Map<String, int[]> mappings; //  word => docIds
}

class Documents {
  Map<int, Document> docs;  // docId => document
}

有了这个倒排索引,就可以很快定位出一个关键词出现在哪些文档 ID 中。有了这个文档 ID,就可以定位出相关的文档标题和内容。

在 Lucene 中,文档 ID 是一个 32bit 的「有符号整数」,按顺序添加进来的文档其 ID 也是连续递增的。因为它是 32bit,这也意味着 Lucene 的单个索引最多能存储 1<<31 -1 篇文档。文档 ID 之间可能会有空隙,因为 Lucene 的文档是支持删除操作的。

Elasticsearch 为了支持海量的文档存储,它内部对索引进行了分片存储(Sharding)。在内部实现中,它会使用到多个 Lucene 的索引来聚合处理。

好,下面我们来看看文档索引的构建是如何使用代码来完成的。首先导入 Lucene 依赖库

代码语言:javascript复制
<dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-core</artifactId>
    <version>8.2.0</version>
</dependency>

因为是中文搜索,所以还需要导入中文分词分析库,这里有多种选择,我就随意挑选了一个

代码语言:javascript复制
<dependency>
    <groupId>com.hankcs.nlp</groupId>
    <artifactId>hanlp-lucene-plugin</artifactId>
    <version>1.1.6</version>
</dependency>

构造一个 IndexWriter 对象,它是构建索引的关键对象。

代码语言:javascript复制
// 中文分词分析器
var analyser = new HanLPAnalyzer();
// 指定索引的存储目录
var directory = FSDirectory.open(Path.of("./guokr"));
// 构造配置对象
var config = new IndexWriterConfig(analyser);
// 构造 IndexWriter 对象
var indexWriter = new IndexWriter(directory, config);

有了这个 IndexWriter,接下来我们使用它来添加 Redis 中爬到的所有文档。

代码语言:javascript复制
var redis = new JedisPool();
// 首先拿到所有的文章ID
var db = redis.getResource();
var articleIds = db.smembers("valid_article_ids");
db.close();
// 挨个添加
for(var id : articleIds) {
    // 取文章的标题和内容
    db = redis.getResource();
    var key = String.format("article_%s", id);
    var title = db.hget(key, "title");
    var html = db.hget(key, "html");
    var url = String.format("https://www.guokr.com/article/%s/", id);
    db.close();
    if(title != null && html != null) {
        // 干掉内容中所有的 HTML 标签只剩下纯文本
        var content = Jsoup.parse(html).text();
        // 构造文档
        var doc = new Document();
        doc.add(new TextField("title", title, Field.Store.YES));
        doc.add(new TextField("content", content, Field.Store.YES));
        doc.add(new StoredField("url", url));
        // 这里添加文档
        indexWriter.addDocument(doc);
    }
}

最后不要忘记关闭 IndexWriter 和 Directory 对象

代码语言:javascript复制
indexWriter.close();
directory.close();

如果严格来说,上面的代码其实编写的并不严谨,至少应该使用 try{} finally{} 语句来确保资源关闭,这里为了代码阅读的简单性就不去计较这些了。

上面的代码最关键的地方在于 Document 对象的构造

代码语言:javascript复制
var doc = new Document();
doc.add(new TextField("title", title, Field.Store.YES));
doc.add(new TextField("content", content, Field.Store.YES));
doc.add(new StoredField("url", url));

这个文档定义了三个字段,分别是 title、content 和 url。其中 Lucene 会为 title 和 content 字段建立两个倒排索引,因为它们被定义成了 TextField 类型,Lucene 默认会为 TextField 类型的字段建立倒排索引。

注意到 TextField 对象的最后一个参数指明是否存储字段的内容,如果这个字段设置为 Field.Store.NO,那么 Lucene 就不存储这个字段的值,但是还是会将这个值的文本进行切词后放入倒排索引中。在关键词查询阶段,我们可以根据关键词搜索到文档 ID,进一步得到这个文档的具体内容,但是文档的内容会缺失这个字段,因为 Lucene 没有存它。简单的说这个字段是隐身的,它在搜索时会起到作用,但是最终的搜索结果里却看不见它。之所以提供这个选项,很明显这是为了可以节约存储空间。

同时我们还注意到 url 字段使用了 StoreField,这是啥意思?它的意思和 Field.Store.NO 正好相反。它只存储字段的值,不参与检索,相当于文档的附加字段。通俗点讲它就是个「搭便车」字段 —— 老司机带带我。

现在让我们跑一跑这个程序,跑完之后打开 ./guokr 目录,看看里面都有些啥。

代码语言:javascript复制
bash> ls -l

total 13824
-rw-r--r--  1 qianwenpin  staff   299B  9  4 14:22 _0.cfe
-rw-r--r--  1 qianwenpin  staff   6.7M  9  4 14:22 _0.cfs
-rw-r--r--  1 qianwenpin  staff   383B  9  4 14:22 _0.si
-rw-r--r--  1 qianwenpin  staff   137B  9  4 14:22 segments_1
-rw-r--r--  1 qianwenpin  staff     0B  9  4 14:22 write.lock

哇,里面有一个 6.7M 的大文件,这毫无疑问肯定存储了文档内容和倒排索引。其它文件都很小,应该只是一些元文件。还有一个 write.lock 文件,这个是用来防止多进程同时对这个目录进行写操作。我们可以尝试并发运行这个程序两次,看看会发生什么

图片

Lucene 虽然不允许多进程同时写,但是可以单进程写多进程读,也就是单写多读。好接下来我们开始尝试 Lucene 的读操作 —— 关键词查询。

查询操作需要构造一个关键对象 IndexSearcher,它的构造方式比 IndexWriter 简单很多。

代码语言:javascript复制
var directory = FSDirectory.open(Path.of("./guokr"));
var reader = DirectoryReader.open(directory);
var searcher = new IndexSearcher(reader);

然后再构造一个关键词查询对象,所谓「关键词」就是指不可分割的整体,查找时会直接拿这个词去匹配倒排索引。

代码语言:javascript复制
var query = new TermQuery(new Term("title", "动物"));

上面的查询目标是文章标题,如果要查询内容,将 title 改成 content 就行。好,接下来进入最重要的一步 —— 查询。

代码语言:javascript复制
var hits = searcher.search(query, 10).scoreDocs;
for(var hit : hits) {
    var doc = searcher.doc(hit.doc);
    System.out.printf("%s=>%sn", doc.get("url"), doc.get("title"));
}

search方法的参数指定了只返回 10 个结果,这些结果会按照匹配程度 score 进行倒排。代码里面的 hit.doc 就是前面提到的 docId,查询操作只返回 docId,需要使用 doc 方法来获取整个文档内容。完事之后不要忘记关闭相关资源哦。

代码语言:javascript复制
reader.close();
directory.close();

我们看看上面的代码运行效果

图片

所有的文章标题里确实都有「动物」这个词。下面我们改变一下查询的输入,改为从内容查询,并且必须同时包含「动物」和 「世界」两个词汇。这是一个复合查询,复合查询需要使用到一个关键的类 BooleanQuery,它可以对多个子 Query 进行逻辑组合来融合查询结果。

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query2 = new TermQuery(new Term("content", "世界"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.MUST)
        .add(query2, BooleanClause.Occur.MUST)
        .build();

运行程序,得到结果如下,可以看出查询的结果相关性还是比较明显的。

图片

我们可以点开链接看看文章的内容进行验证一下。

图片

下面我们继续改变查询条件,还是从内容查询,但是条件变为包含「动物」但是不得有「世界」这个词汇,估计满足这样条件的文章会非常多。

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query2 = new TermQuery(new Term("content", "世界"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.MUST)
        .add(query2, BooleanClause.Occur.MUST_NOT)
        .build();

代码中的 BooleanClause.Occur 参数就是控制逻辑的关键,Occur 有「出现」之意。除了 MUST 和 MUST_NOT 两个选项之外,它还有 SHOULD 和 FILTER 两个值,那这两个值有什么特别的含义呢?上面的两个复合查询案例都是逻辑与,那么有了 SHOULD 我们就可以实现逻辑或的功能。

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query2 = new TermQuery(new Term("content", "经济"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.SHOULD)
        .add(query2, BooleanClause.Occur.SHOULD)
        .build();

上面这段查询逻辑的意思是文章的内容要包含「动物」或者「经济」。虽然看起来 SHOULD 是用来进行逻辑或查询的,但是在本质上它并非如此。比如上面的查询如果将第一个 SHOULD 改成 MUST 如下,那么这个查询又是什么含义呢,运行起来确实可以得到结果,说明这不是非法的查询?但是很明显这是无法直接使用简单的逻辑与或解释清楚的。

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query2 = new TermQuery(new Term("content", "经济"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.MUST)
        .add(query2, BooleanClause.Occur.SHOULD)
        .build();

这个查询的真正含义是文章内容里必须包含「动物」,但是如果同时还包含了「经济」,那么它的匹配程度(score)会高一些,SHOULD 会影响排序结果而不会影响命中。

前面提到 MUST 表示必须包含,MUST_NOT 表示必须不包含。但是如果将两个 MUST_NOT 组合你得到的将会是空查询。为什么会这样呢?

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query2 = new TermQuery(new Term("content", "经济"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.MUST_NOT)
        .add(query2, BooleanClause.Occur.MUST_NOT)
        .build();

这个我们要从查询效率上来进行解释。MUST 查询好办,直接可以命中倒排索引中的关键词从而直接得到与之相关的文档列表,而 MUST_NOT 却需要遍历所有的文档,我们无法直接使用倒排索引,这明显会严重影响查询效率。所以即使你只是使用单个 MUST_NOT 得到的查询结果也会是空的。

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.MUST_NOT)
        .build();

上面的查询结果将会是空集,所以 MUST_NOT 也不单单是个「非」运算。但是如果已经有了一个 MUST,后面再跟一个 MUST_NOT 就可以起到「非」运算的效果,因为它不会有查询效率问题,可以直接利用前一个 MUST 关键词匹配的倒排索引来进行「非」运算过滤。

最后我们再看一下 FILTER 选项的作用,它和 SHOULD 正好相反。SHOULD 不影响查询结果,但是会影响排序,而 FILTER 会影响查询结果但是不影响排序,它只起到过滤的作用,就好比数据库查询里的 Where 条件。

代码语言:javascript复制
var query1 = new TermQuery(new Term("content", "动物"));
var query2 = new TermQuery(new Term("content", "经济"));
var query = new BooleanQuery.Builder()
        .add(query1, BooleanClause.Occur.FILTER)
        .add(query2, BooleanClause.Occur.FILTER)
        .build();

上面的查询表示文章内容必须包含「动物」和「经济」,但是命中关键词的数量对排序没有影响,最终呈现出来的结果将是随机的,查询结果的顺序可能只是倒排索引中文档列表的存储遍历的顺序。

关于 Lucene 查询语句的更多奥秘,在后面的文章中我们会继续深入探讨。

0 人点赞