Lucene系列（5）——倒排索引、Token与词向量

注：本文基于Lucene 8.2.0 版本。

上文我们对Analyzer的原理和代码进行了分析，主要偏重流程，这篇文章来分析Analyzer的输出细节——Token。对原始数据进行Analyze的终极目的是为了更好的搜索，所以还会讨论和搜索相关的倒排索引和词向量（Term Vector）。

倒排索引（Inverted Index）和正向索引（Forward Index）

我们用一个例子来看什么是倒排索引，什么是正向索引。假设有两个文档（前面的数字为文档ID）：

1. a good student.
2. a gifted student.

这两个文档经过Analyzer之后（这里我们不去停顿词），分别得到以下两个索引表：

这两个表都是key-value形式的Map结构，该数据结构的最大特点就是可以根据key快速访问value。我们分别分析以下这两个表。

表1中，Map的key是一个个词，也就是上文中Analyzer的输出。value是包含该词的文档的ID。这种映射的好处就是如果我们知道了词，就可以很快的查出有哪些文档包含该词。大家想一下我们平时的检索是不是就是这种场景：我们知道一些关键字，然后想查有哪些网页包含该关键词。表1这种词到文档的映射结构就称之为倒排索引。

表2中，Map的key是文档id，而value是该文档中包含的所有词。这种结构的映射的好处是只要我们知道了文档（ID），就能知道这个文档里面包含了哪些词。这种文档到词的映射结构称之为正向索引。

倒排索引是文档检索系统最常用的数据结构，Lucene用的就是这种数据结构。那对于检索有了倒排索引是不是就够用了呢？我们来看一个搜索结果：

这里我搜索了我年少时的偶像S.H.E，一个台湾女团，Google返回了一些包含该关键字的网页，同时它将网页中该关键字用红色字体标了出来。几乎所有的搜索引擎都有该功能。大家想一下，使用上述的倒排索引结构能否做到这一点？

答案是做不到的。倒排索引的结构只能让我们快速判断一个文档（上述例子中一个网页就是一个文档）是否包含该关键字，但无法知道关键字出现在文档中的哪个位置。那搜索引擎是如何知道的呢？其实使用的是另外一个结构——词向量，词向量和倒排索引的信息都是在Analyze阶段计算出来的。在介绍词向量之前，我们先来看一下Analyze的输出结果——Token。

Token

在《Lucene系列（3）——术语总结》一文中我们说了token除了包含词以外，还存在一些其它属性，下面就让我们来看看完整的token长什么样？看下面代码（源文件见AnalysisDebug.java）：

package com.niyanchun;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.core.WhitespaceAnalyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;

/**
 * Debug Analysis Process.
 *
 * @author NiYanchun
 **/
public class AnalysisDebug {

    public static void main(String[] args) throws Exception {
        Analyzer analyzer = new StandardAnalyzer();
//        Analyzer analyzer = new StandardAnalyzer(EnglishAnalyzer.ENGLISH_STOP_WORDS_SET);
        String sentence = "a good student, a gifted student.";
        try (TokenStream tokenStream = analyzer.tokenStream("sentence", sentence)) {
            tokenStream.reset();

            while (tokenStream.incrementToken()) {
                System.out.println("token: " + tokenStream.reflectAsString(false));
            }
            tokenStream.end();
        }
    }
}

上述代码很简单，如果你看过上篇文章《Lucene系列（4）——探秘Analyzer》的话，应该不难理解。我们借助TokenStream对象输出经过StandardAnalyzer处理的数据，程序运行结果如下：

token: term=a,bytes=[61],startOffset=0,endOffset=1,positionIncrement=1,positionLength=1,type=<ALPHANUM>,termFrequency=1
token: term=good,bytes=[67 6f 6f 64],startOffset=2,endOffset=6,positionIncrement=1,positionLength=1,type=<ALPHANUM>,termFrequency=1
token: term=student,bytes=[73 74 75 64 65 6e 74],startOffset=7,endOffset=14,positionIncrement=1,positionLength=1,type=<ALPHANUM>,termFrequency=1
token: term=a,bytes=[61],startOffset=16,endOffset=17,positionIncrement=1,positionLength=1,type=<ALPHANUM>,termFrequency=1
token: term=gifted,bytes=[67 69 66 74 65 64],startOffset=18,endOffset=24,positionIncrement=1,positionLength=1,type=<ALPHANUM>,termFrequency=1
token: term=student,bytes=[73 74 75 64 65 6e 74],startOffset=25,endOffset=32,positionIncrement=1,positionLength=1,type=<ALPHANUM>,termFrequency=1

这个输出结果是非常值得探究的。可以看到sentence字段的文本数据"a good student, a gifted student"经过StandardAnalyzer分析之后输出了6个token，每个token由一些属性组成，这些属性对应的定义类在org.apache.lucene.analysis.tokenattributes包下面，有兴趣的可以查阅。这里我们简单介绍一下这些属性：

• term：解析出来的词。注意这里的term不同于我们之前介绍的Term，它仅指提取出来的词。
• bytes：词的字节数组形式。
• startOffset, endOffset：词开始和结束的位置，从0开始计数。大家可以数一下。
• positionIncrement：当前词和上个词的距离，默认为1，表示词是连续的。如果有些token被丢掉了，这个值就会大于1了。可以将上述代码中注释掉的那行放开，同时将原来不带停用词的analyzer注释掉，这样解析出的停用词token就会被移除，你就会发现有些token的该字段的值会变成2。该字段主要用于支持"phrase search", "span search"以及"highlight"，这些搜索都需要知道关键字在文档中的position，以后介绍搜索的时候再介绍。另外这个字段还有一个非常重要的用途就是支持同义词查询。我们将该某个token的positionIncrement置为0，就表示该token和上个token没有距离，搜索的时候，不论搜这两个token任何一个，都会返回它们两对应的文档。假设第一个token是土豆，下一个token是马铃薯，马铃薯对应的token的positionIncrement为0，那我们搜马铃薯时，也会给出土豆相关的信息，反之亦然。
• positionLength：该字段跨了多少个位置。代码注释中说极少有Analyzer会产生该字段，基本都是使用默认值1.
• type：字段类型。需要注意的是这个类型是由每个Analyzer的Tokenizer定义的，不同的Analyer定义的类型可能不同。比如StandardAnalyzer使用的StandardTokenizer定义了这几种类型：<ALPHANUM>、<NUM>、<SOUTHEAST_ASIAN>、<IDEOGRAPHIC>、<HIRAGANA>、<KATAKANA>、<HANGUL>、<EMOJI>。
• termFrequency：词频。注意这里的词频不是token在句子中出现的频率，而是让用户自定义的，比如我们想让某个token在评分的时候更重要一些，那我们就可以将其词频设置大一些。如果不设置，默认都会初始化为1。比如上面输出结果中有两个"a"字段，词频都为初始值1，这个在后续的流程会合并，合并之后，词频会变为2。

除了以上属性外，还有一个可能存在的属性就是payload，我们可以在这个字段里面存储一些信息。以上就是一个完整的Token。接下来让我们看什么是词向量。

词向量（Term Vector）

Analyzer分析出来的Token并不会直接写入Index，还需要做一些转化：

• 取token中的词，以及包含该词的字段信息、文档信息（doc id），形成词到字段信息、文档信息的映射，也就是我们前面介绍的倒排索引。
• 取token中的词，以及包含该词的positionIncrement、startOffset、endOffset、termFrequency信息，组成从token到后面四个信息的映射，这就是词向量。

所以，倒排索引和词向量都是从term到某个value的映射，只是value的值不一样。这里需要注意，倒排索引是所有文档范围内的，而词向量是某个文档范围的。简言之就是一个index对应一个倒排索引，而一个document就有一个词向量。有了倒排索引，我们就知道搜索关键字包含在index的哪些document的字段中。有了词向量，我们就知道关键字在匹配到的document的具体位置。

下面让我们从代码角度来验证一下上面的理论（源代码见TermVectorShow.java）：

package com.niyanchun;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.FieldType;
import org.apache.lucene.index.*;
import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;

import java.nio.file.Paths;

/**
 * Show Term Vector.
 *
 * @author NiYanchun
 **/
public class TermVectorShow {

    public static void main(String[] args) throws Exception {
        // 构建索引
        final String indexPath = "indices/tv-show";
        Directory indexDir = FSDirectory.open(Paths.get(indexPath));

        Analyzer analyzer = new StandardAnalyzer();
        IndexWriterConfig iwc = new IndexWriterConfig(analyzer);
        iwc.setOpenMode(IndexWriterConfig.OpenMode.CREATE);
        IndexWriter writer = new IndexWriter(indexDir, iwc);

        String sentence = "a good student, a gifted student";
        // 默认不会保存词向量，这里我们通过一些设置来保存词向量的相关信息
        FieldType fieldType = new FieldType();
        fieldType.setStored(true);
        fieldType.setStoreTermVectors(true);
        fieldType.setStoreTermVectorOffsets(true);
        fieldType.setStoreTermVectorPositions(true);
        fieldType.setIndexOptions(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS);
        Field field = new Field("content", sentence, fieldType);
        Document document = new Document();
        document.add(field);
        writer.addDocument(document);
        writer.close();

        // 从索引读取Term Vector信息
        IndexReader indexReader = DirectoryReader.open(indexDir);
        Terms termVector = indexReader.getTermVector(0, "content");
        TermsEnum termIter = termVector.iterator();
        while (termIter.next() != null) {
            PostingsEnum postingsEnum = termIter.postings(null, PostingsEnum.ALL);
            while (postingsEnum.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
                int freq = postingsEnum.freq();
                System.out.printf("term: %s, freq: %d,", termIter.term().utf8ToString(), freq);
                while (freq > 0) {
                    System.out.printf(" nextPosition: %d,", postingsEnum.nextPosition());
                    System.out.printf(" startOffset: %d, endOffset: %d",
                            postingsEnum.startOffset(), postingsEnum.endOffset());
                    freq--;
                }
                System.out.println();
            }
        }
    }
}

这段代码实现的功能是先indexing 1条document，形成index，然后我们读取index，从中获取那条document content字段的词向量。需要注意，indexing时默认是不存储词向量相关信息的，我们需要通过FieldType做显式的设置，否则你读取出来的Term Vector会是null。

我们看一下程序的输出结果：

term: a, freq: 2, nextPosition: 0, startOffset: 0, endOffset: 1 nextPosition: 3, startOffset: 16, endOffset: 17
term: gifted, freq: 1, nextPosition: 4, startOffset: 18, endOffset: 24
term: good, freq: 1, nextPosition: 1, startOffset: 2, endOffset: 6
term: student, freq: 2, nextPosition: 2, startOffset: 7, endOffset: 14 nextPosition: 5, startOffset: 25, endOffset: 32

这里我们indexing的数据和上一节token部分的数据是一样的，而且都使用的是StandardAnalyzer，所以我们可以对比着看上一节输出的token和这里输出的term vector数据。可以看到，之前重复的token（a和student）到这里已经被合并了，并且词频也相应的变成了2。然后我们看一下position信息和offset信息也是OK的。而像token中的positionLength、type等信息都丢弃了。

词向量的信息量比较大，所以默认并不记录，我们想要保存时需要针对每个字段做显式的设置，Lucene 8.2.0中包含如下一些选项（见org.apache.lucene.index.IndexOptions枚举类）：

• NONE：不索引
• DOCS：只索引字段，不保存词频等位置信息
• DOCS_AND_FREQS：索引字段并保存词频信息，但不保存位置信息
• DOCS_AND_FREQS_AND_POSITIONS：索引字段并保存词频及位置信息
• DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS：索引字段并保存词频、位置、偏移量等信息

phrase search和span search需要position信息支持，所以一般全文搜索引擎默认会采用DOCS_AND_FREQS_AND_POSITIONS策略，这样基本就能覆盖常用的搜索需求了。而需要高亮等功能的时候，才需要记录offset信息。

最后还有个问题就是为什么词向量里面会带向量这个词呢？词向量一词并非Lucene中发明的概念，而是IR领域的一个概念，再细点就是Vector space model 文本相似度模型中的概念，做文本相关算法的朋友应该对这个比较熟悉。将term转化成向量空间之后，我们就可以使用余弦相似度（cosine similarity）来计算我们搜索语句与index中document之间的相似度了（推荐领域使用这种算法的也比较多）。这块内容比较多，后面有空专门写文章介绍吧。