Lucene系列(5)——倒排索引、Token与词向量

2021-11-26 From NYC's Blog By 倪彦春
注:本文基于Lucene 8.2.0 版本。
<p> 上文我们对Analyzer原理代码进行分析,主要偏重流程,这篇文章分析Analyzer的输出细节——Token。对原始数据进行Analyze的终极目的是为了更好的搜索,所以还会讨论和搜索相关的倒排索引词向量(Term Vector)p>

倒排索引(Inverted Index)和正向索引(Forward Index)

<p> 我们用一个例子来看什么是倒排索引,什么是正向索引。假设有两个文档(前面的数字为文档ID): p>
  1. a good student.
  2. a gifted student.
<p> 这两个文档经过Analyzer之后(这里我们不去停顿词),分别得到以下两个索引表: p> <p> Inverted Index p> <p> Forward Index p> <p> 这两个表都是key-value形式的Map结构,该数据结构的最大特点就是可以根据key快速访问value。我们分别分析以下这两个表。 p> <p> 表1中,Map的key是一个个词,也就是上文中Analyzer的输出。value是包含该词的文档的ID。这种映射的好处就是如果我们知道了词,就可以很快的查出有哪些文档包含该词。大家想一下我们平时的检索是不是就是这种场景:我们知道一些关键字,然后想查有哪些网页包含该关键词。表1这种词到文档的映射结构就称之为倒排索引p> <p> 表2中,Map的key文档id,而value是该文档中包含的所有词。这种结构的映射的好处是只要我们知道了文档(ID),就能知道这个文档里面包含了哪些词。这种文档到词的映射结构称之为正向索引p> <p> 倒排索引文档检索系统最常用的数据结构,Lucene用的就是这种数据结构。那对于检索有了倒排索引是不是就够用了呢?我们来看一个搜索结果: p> <p> SHE p> <p> 这里我搜索了我年少时的偶像S.H.E,一个台湾女团,Google返回了一些包含该关键字的网页,同时它将网页中该关键字用红色字体标了出来。几乎所有的搜索引擎都有该功能。大家想一下,使用上述的倒排索引结构能否做到这一点? p> <p> 答案是做不到的。倒排索引的结构只能让我们快速判断一个文档(上述例子中一个网页就是一个文档是否包含该关键字,但无法知道关键字现在文档中的哪个位置。那搜索引擎是如何知道的呢?其实使用的是另外一个结构——词向量,词向量和倒排索引的信息都是在Analyze阶段计算出来的。在介绍词向量之前,我们先来看一下Analyze的输出结果——Token。 p>

Token

<p> 在《Lucene系列(3)——术语总结》一文中我们说了token除了包含词以外,还存在一些其它属性,下面就让我们来看看完整的token长什么样?看下面代码(源文件AnalysisDebug.java): p>
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();
        }
    }
}
<p> 上述代码很简单,如果你看过上篇文章Lucene系列(4)——探秘Analyzer》的话,应该不难理解。我们借助TokenStream对象输出经过StandardAnalyzer处理数据程序运行结果如下: p>
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
<p> 这个输出结果是非常值得探究的。可以看到sentence字段的文本数据"a good student, a gifted student"经过StandardAnalyzer分析之后输出了6个token,每个token由一些属性组成,这些属性对应的定义类在org.apache.lucene.analysis.tokenattributes包下面,有兴趣的可以查阅。这里我们简单介绍一下这些属性: p> <p> 除了以上属性外,还有一个可能存在的属性就是payload,我们可以在这个字段里面存储一些信息。以上就是一个完整的Token。接下来让我们看什么是词向量。 p>

词向量(Term Vector)

<p> Analyzer分析出来的Token并不会直接写入Index,还需要做一些转化: p>
  • token中的词,以及包含该词的字段信息、文档信息(doc id),形成词到字段信息、文档信息的映射,也就是我们前面介绍的倒排索引
  • token中的词,以及包含该词的positionIncrement、startOffset、endOffset、termFrequency信息,组成从token到后面四个信息的映射,这就是词向量
<p> 所以,倒排索引和词向量都是从term到某个value的映射,只是value的值不一样。这里需要注意,倒排索引是所有文档范围内的,而词向量是某个文档范围的。简言之就是一个index对应一个倒排索引,而一个document就有一个词向量。有了倒排索引,我们就知道搜索关键字包含在index的哪些document的字段中。有了词向量,我们就知道关键字匹配到的document的具体位置。 p> <p> 下面让我们从代码角度来验证一下上面的理论(源代码TermVectorShow.java): p>
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();
            }
        }
    }
}
<p> 这段代码实现的功能是先indexing 1条document,形成index,然后我们读取index,从中获取那条document content字段的词向量。需要注意,indexing时默认是不存储词向量相关信息的,我们需要通过FieldType做显式的设置,否则你读取出来的Term Vector会是nullp> <p> 我们看一下程序的输出结果: p>
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
<p> 这里我们indexing的数据和上一节token部分的数据是一样的,而且都使用的是StandardAnalyzer,所以我们可以对比着看上一节输出的token和这里输出的term vector数据。可以看到,之前重复token(a和student)到这里已经被合并了,并且词频也相应的变成了2。然后我们看一下position信息和offset信息也是OK的。而像token中的positionLength、type等信息都丢弃了。 p> <p> 词向量的信息量比较大,所以默认并不记录,我们想要保存时需要针对每个字段做显式的设置Lucene 8.2.0中包含如下一些选项(见org.apache.lucene.index.IndexOptions枚举类): p>
  • NONE:不索引
  • DOCS:只索引字段,不保存词频等位置信息
  • DOCS_AND_FREQS:索引字段并保存词频信息,但不保存位置信息
  • DOCS_AND_FREQS_AND_POSITIONS:索引字段并保存词频及位置信息
  • DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS:索引字段并保存词频、位置、偏移量等信息
<p> phrase search和span search需要position信息支持,所以一般全文搜索引擎默认会采用DOCS_AND_FREQS_AND_POSITIONS策略,这样基本就能覆盖常用的搜索需求了。而需要高亮等功能的时候,才需要记录offset信息。 p> <p> 最后还有个问题就是为什么词向量里面会带向量这个词呢?词向量一词并非Lucene中发明的概念,而是IR领域的一个概念,再细点就是Vector space model 文本相似度模型中的概念,做文本相关算法的朋友应该对这个比较熟悉。将term转化成向量空间之后,我们就可以使用余弦相似度(cosine similarity)来计算我们搜索语句index中document之间的相似度了(推荐领域使用这种算法的也比较多)。这块内容比较多,后面有空专门写文章介绍吧。 p>

本文来源:NYC's Blog,转载请注明出处!

来源地址:https://niyanchun.com/lucene-learning-5.html

发表感想

© 2016 - 2022 chengxuzhixin.com All Rights Reserved.

浙ICP备2021034854号-1    浙公网安备 33011002016107号