get方式表单提交 传递参数乱码问题完美解决方案

表单提交 使用get方法,jsp完美解决乱码问题:

有一次项目需要使用get方法提交表单,中文乱码苦恼了我很久,我查了很多资料,大部分人都是建议修改tomcat中的URIEncoding,但是这样会导致所有项目都改变编码,不同项目使用不同编码,这样又会引来更多问题。

下面有一种超级简单的解决方法:

JSP页面中文参数传递实现之代码MyJsp1.jsp:

 

﹤%@ page language="java" import="java.util.*" pageEncoding="gb2312"%﹥
﹤form action="MyJsp2.jsp" method="get"﹥
    ﹤input type=hidden name=act value=动作 /﹥
    ﹤input type=submit value=ok﹥
﹤/form﹥

JSP页面中文参数传递实现之代码MyJsp2.jsp:
 

﹤%@ page language="java" import="java.util.*" pageEncoding="gb2312"%﹥  
﹤%
    String tempVal = request.getParameter("act");
    out.println(new String(tempVal.getBytes("ISO-8859-1"), "gb2312"));
%﹥ 

使用ISO-8859-1的原因是Tomcat默认URIEncoding是这种编码,这样就很简单的解决了乱码问题了。

Lucene学习总结之三:Lucene的索引文件格式(2)

四、具体格式

上面曾经交代过,lucene保存了从Index到Segment到Document到Field一直到Term的正向信息,也包括了从Term到Document映射的反向信息,还有其他一些Lucene特有的信息。下面对这三种信息一一介绍。

4.1. 正向信息

Index –> Segments (segments.gen, segments_N) –> Field(fnm, fdx, fdt) –> Term (tvx, tvd, tvf)

上面的层次结构不是十分的准确,因为segments.gen和segments_N保存的是段(segment)的元数据信息(metadata),其实是每个Index一个的,而段的真正的数据信息,是保存在域(Field)和词(Term)中的。

4.1.1. 段的元数据信息(segments_N)

一个索引(Index)可以同时存在多个segments_N(至于如何存在多个segments_N,在描述完详细信息之后会举例说明),然而当我们要打开一个索引的时候,我们必须要选择一个来打开,那如何选择哪个segments_N呢?

Lucene采取以下过程:

  • 其一,在所有的segments_N中选择N最大的一个。基本逻辑参照SegmentInfos.getCurrentSegmentGeneration(File[] files),其基本思路就是在所有以segments开头,并且不是segments.gen的文件中,选择N最大的一个作为genA。
  • 其二,打开segments.gen,其中保存了当前的N值。其格式如下,读出版本号(Version),然后再读出两个N,如果两者相等,则作为genB。
  • segments.gen
    IndexInput genInput = directory.openInput(IndexFileNames.SEGMENTS_GEN);//”segments.gen”
    int version = genInput.readInt();//读出版本号
    if (version == FORMAT_LOCKLESS) {//如果版本号正确
    long gen0 = genInput.readLong();//读出第一个N
    long gen1 = genInput.readLong();//读出第二个N
    if (gen0 == gen1) {//如果两者相等则为genB
    genB = gen0;
    }
    }
  • 其三,在上述得到的genA和genB中选择最大的那个作为当前的N,方才打开segments_N文件。其基本逻辑如下:
    if (genA > genB)
    gen = genA;
    else
    gen = genB;

 

如下图是segments_N的具体格式:

segments_N

  • Format:
    • 索引文件格式的版本号。
    • 由于Lucene是在不断开发过程中的,因而不同版本的Lucene,其索引文件格式也不尽相同,于是规定一个版本号。
    • Lucene 2.1此值-3,Lucene 2.9时,此值为-9。
    • 当用某个版本号的IndexReader读取另一个版本号生成的索引的时候,会因为此值不同而报错。
  • Version:
    • 索引的版本号,记录了IndexWriter将修改提交到索引文件中的次数。
    • 其初始值大多数情况下从索引文件里面读出,仅仅在索引开始创建的时候,被赋予当前的时间,已取得一个唯一值。
    • 其值改变在IndexWriter.commit->IndexWriter.startCommit->SegmentInfos.prepareCommit->SegmentInfos.write->writeLong(++version)
    • 其初始值之所最初取一个时间,是因为我们并不关心IndexWriter将修改提交到索引的具体次数,而更关心到底哪个是最新的。IndexReader中常比较自己的version和索引文件中的version是否相同来判断此IndexReader被打开后,还有没有被IndexWriter更新。
//在DirectoryReader中有一下函数。

public boolean isCurrent() throws CorruptIndexException, IOException {
return SegmentInfos.readCurrentVersion(directory) == segmentInfos.getVersion();
}

  • NameCount
    • 是下一个新段(Segment)的段名。
    • 所有属于同一个段的索引文件都以段名作为文件名,一般为_0.xxx, _0.yyy, _1.xxx, _1.yyy ……
    • 新生成的段的段名一般为原有最大段名加一。
    • 如同的索引,NameCount读出来是2,说明新的段为_2.xxx, _2.yyy

image

  • SegCount
    • 段(Segment)的个数。
    • 如上图,此值为2。
  • SegCount个段的元数据信息:
    • SegName
      • 段名,所有属于同一个段的文件都有以段名作为文件名。
      • 如上图,第一个段的段名为”_0″,第二个段的段名为”_1″
    • SegSize
      • 此段中包含的文档数
      • 然而此文档数是包括已经删除,又没有optimize的文档的,因为在optimize之前,Lucene的段中包含了所有被索引过的文档,而被删除的文档是保存在.del文件中的,在搜索的过程中,是先从段中读到了被删除的文档,然后再用.del中的标志,将这篇文档过滤掉。
      • 如下的代码形成了上图的索引,可以看出索引了两篇文档形成了_0段,然后又删除了其中一篇,形成了_0_1.del,又索引了两篇文档形成_1段,然后又删除了其中一篇,形成_1_1.del。因而在两个段中,此值都是2。
IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR), new StandardAnalyzer(Version.LUCENE_CURRENT), true, IndexWriter.MaxFieldLength.LIMITED);
writer.setUseCompoundFile(false);
indexDocs(writer, docDir);//docDir中只有两篇文档

//文档一为:Students should be allowed to go out with their friends, but not allowed to drink beer.

//文档二为:My friend Jerry went to school to see his students but found them drunk which is not allowed.

writer.commit();//提交两篇文档,形成_0段。

writer.deleteDocuments(new Term(“contents”, “school”));//删除文档二
writer.commit();//提交删除,形成_0_1.del
indexDocs(writer, docDir);//再次索引两篇文档,Lucene不能判别文档与文档的不同,因而算两篇新的文档。
writer.commit();//提交两篇文档,形成_1段
writer.deleteDocuments(new Term(“contents”, “school”));//删除第二次添加的文档二
writer.close();//提交删除,形成_1_1.del

    • DelGen
      • .del文件的版本号
      • Lucene中,在optimize之前,删除的文档是保存在.del文件中的。
      • 在Lucene 2.9中,文档删除有以下几种方式:
        • IndexReader.deleteDocument(int docID)是用IndexReader按文档号删除。
        • IndexReader.deleteDocuments(Term term)是用IndexReader删除包含此词(Term)的文档。
        • IndexWriter.deleteDocuments(Term term)是用IndexWriter删除包含此词(Term)的文档。
        • IndexWriter.deleteDocuments(Term[] terms)是用IndexWriter删除包含这些词(Term)的文档。
        • IndexWriter.deleteDocuments(Query query)是用IndexWriter删除能满足此查询(Query)的文档。
        • IndexWriter.deleteDocuments(Query[] queries)是用IndexWriter删除能满足这些查询(Query)的文档。
        • 原来的版本中Lucene的删除一直是由IndexReader来完成的,在Lucene 2.9中虽可以用IndexWriter来删除,但是其实真正的实现是在IndexWriter中,保存了readerpool,当IndexWriter向索引文件提交删除的时候,仍然是从readerpool中得到相应的IndexReader,并用IndexReader来进行删除的。下面的代码可以说明:
IndexWriter.applyDeletes()

-> DocumentsWriter.applyDeletes(SegmentInfos)

-> reader.deleteDocument(doc);

        • DelGen是每当IndexWriter向索引文件中提交删除操作的时候,加1,并生成新的.del文件。
IndexWriter.commit()

-> IndexWriter.applyDeletes()

-> IndexWriter$ReaderPool.release(SegmentReader)

-> SegmentReader(IndexReader).commit()

-> SegmentReader.doCommit(Map)

-> SegmentInfo.advanceDelGen()

-> if (delGen == NO) {
delGen = YES;
} else {
delGen++;
}

IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR), new StandardAnalyzer(Version.LUCENE_CURRENT), true, IndexWriter.MaxFieldLength.LIMITED);
writer.setUseCompoundFile(false);

indexDocs(writer, docDir);//索引两篇文档,一篇包含”school”,另一篇包含”beer”
writer.commit();//提交两篇文档到索引文件,形成段(Segment) “_0”
writer.deleteDocuments(new Term(“contents”, “school”));//删除包含”school”的文档,其实是删除了两篇文档中的一篇。
writer.commit();//提交删除到索引文件,形成”_0_1.del”
writer.deleteDocuments(new Term(“contents”, “beer”));//删除包含”beer”的文档,其实是删除了两篇文档中的另一篇。
writer.commit();//提交删除到索引文件,形成”_0_2.del”
indexDocs(writer, docDir);//索引两篇文档,和上次的文档相同,但是Lucene无法区分,认为是另外两篇文档。
writer.commit();//提交两篇文档到索引文件,形成段”_1″
writer.deleteDocuments(new Term(“contents”, “beer”));//删除包含”beer”的文档,其中段”_0″已经无可删除,段”_1″被删除一篇。
writer.close();//提交删除到索引文件,形成”_1_1.del”

形成的索引文件如下:

image

 

    • DocStoreOffset
    • DocStoreSegment
    • DocStoreIsCompoundFile
      • 对于域(Stored Field)和词向量(Term Vector)的存储可以有不同的方式,即可以每个段(Segment)单独存储自己的域和词向量信息,也可以多个段共享域和词向量,把它们存储到一个段中去。
      • 如果DocStoreOffset为-1,则此段单独存储自己的域和词向量,从存储文件上来看,如果此段段名为XXX,则此段有自己的XXX.fdt,XXX.fdx,XXX.tvf,XXX.tvd,XXX.tvx文件。DocStoreSegment和DocStoreIsCompoundFile在此处不被保存。
      • 如果DocStoreOffset不为-1,则DocStoreSegment保存了共享的段的名字,比如为YYY,DocStoreOffset则为此段的域及词向量信息在共享段中的偏移量。则此段没有自己的XXX.fdt,XXX.fdx,XXX.tvf,XXX.tvd,XXX.tvx文件,而是将信息存放在共享段的YYY.fdt,YYY.fdx,YYY.tvf,YYY.tvd,YYY.tvx文件中。
      • DocumentsWriter中有两个成员变量:String segment是当前索引信息存放的段,String docStoreSegment是域和词向量信息存储的段。两者可以相同也可以不同,决定了域和词向量信息是存储在本段中,还是和其他的段共享。
      • IndexWriter.flush(boolean triggerMerge, boolean flushDocStores, boolean flushDeletes)中第二个参数flushDocStores会影响到是否单独或是共享存储。其实最终影响的是DocumentsWriter.closeDocStore()。每当flushDocStores为false时,closeDocStore不被调用,说明下次添加到索引文件中的域和词向量信息是同此次共享一个段的。直到flushDocStores为true的时候,closeDocStore被调用,从而下次添加到索引文件中的域和词向量信息将被保存在一个新的段中,不同此次共享一个段(在这里需要指出的是Lucene的一个很奇怪的实现,虽然下次域和词向量信息是被保存到新的段中,然而段名却是这次被确定了的,在initSegmentName中当docStoreSegment == null时,被置为当前的segment,而非下一个新的segment,docStoreSegment = segment,于是会出现如下面的例子的现象)。
      • 好在共享域和词向量存储并不是经常被使用到,实现也或有缺陷,暂且解释到此。
IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR), new StandardAnalyzer(Version.LUCENE_CURRENT), true, IndexWriter.MaxFieldLength.LIMITED);
writer.setUseCompoundFile(false);
indexDocs(writer, docDir);
writer.flush();

//flush生成segment “_0″,并且flush函数中,flushDocStores设为false,也即下个段将同本段共享域和词向量信息,这时DocumentsWriter中的docStoreSegment= “_0″。

indexDocs(writer, docDir);
writer.commit();

//commit生成segment “_1″,由于上次flushDocStores设为false,于是段”_1″的域以及词向量信息是保存在”_0″中的,在这个时刻,段”_1″并不生成自己的”_1.fdx”和”_1.fdt”。然而在commit函数中,flushDocStores设为true,也即下个段将单独使用新的段来存储域和词向量信息。然而这时,DocumentsWriter中的docStoreSegment= “_1″,也即当段”_2″存储其域和词向量信息的时候,是存在”_1.fdx”和”_1.fdt”中的,而段”_1″的域和词向量信息却是存在”_0.fdt”和”_0.fdx”中的,这一点非常令人困惑。 如图writer.commit的时候,_1.fdt和_1.fdx并没有形成。

image

indexDocs(writer, docDir);
writer.flush();

//段”_2″形成,由于上次flushDocStores设为true,其域和词向量信息是新创建一个段保存的,却是保存在_1.fdt和_1.fdx中的,这时候才产生了此二文件。

image

indexDocs(writer, docDir);
writer.flush();

//段”_3″形成,由于上次flushDocStores设为false,其域和词向量信息是共享一个段保存的,也是是保存在_1.fdt和_1.fdx中的

indexDocs(writer, docDir);
writer.commit();

//段”_4″形成,由于上次flushDocStores设为false,其域和词向量信息是共享一个段保存的,也是是保存在_1.fdt和_1.fdx中的。然而函数commit中flushDocStores设为true,也意味着下一个段将新创建一个段保存域和词向量信息,此时DocumentsWriter中docStoreSegment= “_4″,也表明了虽然段”_4″的域和词向量信息保存在了段”_1″中,将来的域和词向量信息却要保存在段”_4″中。此时”_4.fdx”和”_4.fdt”尚未产生。

image

indexDocs(writer, docDir);
writer.flush();

//段”_5″形成,由于上次flushDocStores设为true,其域和词向量信息是新创建一个段保存的,却是保存在_4.fdt和_4.fdx中的,这时候才产生了此二文件。

image

indexDocs(writer, docDir);
writer.commit();
writer.close();

//段”_6″形成,由于上次flushDocStores设为false,其域和词向量信息是共享一个段保存的,也是是保存在_4.fdt和_4.fdx中的

image

    • HasSingleNormFile
      • 在搜索的过程中,标准化因子(Normalization Factor)会影响文档最后的评分。
      • 不同的文档重要性不同,不同的域重要性也不同。因而每个文档的每个域都可以有自己的标准化因子。
      • 如果HasSingleNormFile为1,则所有的标准化因子都是存在.nrm文件中的。
      • 如果HasSingleNormFile不是1,则每个域都有自己的标准化因子文件.fN
    • NumField
      • 域的数量
    • NormGen
      • 如果每个域有自己的标准化因子文件,则此数组描述了每个标准化因子文件的版本号,也即.fN的N。
    • IsCompoundFile
      • 是否保存为复合文件,也即把同一个段中的文件按照一定格式,保存在一个文件当中,这样可以减少每次打开文件的个数。
      • 是否为复合文件,由接口IndexWriter.setUseCompoundFile(boolean)设定。
      • 非符合文件同符合文件的对比如下图:
非复合文件:
image
复合文件:
image

 

    • DeletionCount
      • 记录了此段中删除的文档的数目。
    • HasProx
      • 如果至少有一个段omitTf为false,也即词频(term freqency)需要被保存,则HasProx为1,否则为0。
    • Diagnostics
      • 调试信息。
  • User map data
    • 保存了用户从字符串到字符串的映射Map
  • CheckSum
    • 此文件segment_N的校验和。
读取此文件格式参考SegmentInfos.read(Directory directory, String segmentFileName):

  • int format = input.readInt();
  • version = input.readLong(); // read version
  • counter = input.readInt(); // read counter
  • for (int i = input.readInt(); i > 0; i–) // read segmentInfos
    • add(new SegmentInfo(directory, format, input));
      • name = input.readString();
      • docCount = input.readInt();
      • delGen = input.readLong();
      • docStoreOffset = input.readInt();
      • docStoreSegment = input.readString();
      • docStoreIsCompoundFile = (1 == input.readByte());
      • hasSingleNormFile = (1 == input.readByte());
      • int numNormGen = input.readInt();
      • normGen = new long[numNormGen];
      • for(int j=0;j
      • normGen[j] = input.readLong();
    • isCompoundFile = input.readByte();
    • delCount = input.readInt();
    • hasProx = input.readByte() == 1;
    • diagnostics = input.readStringStringMap();
  • userData = input.readStringStringMap();
  • final long checksumNow = input.getChecksum();
  • final long checksumThen = input.readLong();

 

4.1.2. 域(Field)的元数据信息(.fnm)

一个段(Segment)包含多个域,每个域都有一些元数据信息,保存在.fnm文件中,.fnm文件的格式如下:

fnm

  • FNMVersion
    • 是fnm文件的版本号,对于Lucene 2.9为-2
  • FieldsCount
    • 域的数目
  • 一个数组的域(Fields)
    • FieldName:域名,如”title”,”modified”,”content”等。
    • FieldBits:一系列标志位,表明对此域的索引方式
      • 最低位:1表示此域被索引,0则不被索引。所谓被索引,也即放到倒排表中去。
        • 仅仅被索引的域才能够被搜到。
        • Field.Index.NO则表示不被索引。
        • Field.Index.ANALYZED则表示不但被索引,而且被分词,比如索引”hello world”后,无论是搜”hello”,还是搜”world”都能够被搜到。
        • Field.Index.NOT_ANALYZED表示虽然被索引,但是不分词,比如索引”hello world”后,仅当搜”hello world”时,能够搜到,搜”hello”和搜”world”都搜不到。
        • 一个域出了能够被索引,还能够被存储,仅仅被存储的域是搜索不到的,但是能通过文档号查到,多用于不想被搜索到,但是在通过其它域能够搜索到的情况下,能够随着文档号返回给用户的域。
        • Field.Store.Yes则表示存储此域,Field.Store.NO则表示不存储此域。
      • 倒数第二位:1表示保存词向量,0为不保存词向量。
        • Field.TermVector.YES表示保存词向量。
        • Field.TermVector.NO表示不保存词向量。
      • 倒数第三位:1表示在词向量中保存位置信息。
        • Field.TermVector.WITH_POSITIONS
      • 倒数第四位:1表示在词向量中保存偏移量信息。
        • Field.TermVector.WITH_OFFSETS
      • 倒数第五位:1表示不保存标准化因子
        • Field.Index.ANALYZED_NO_NORMS
        • Field.Index.NOT_ANALYZED_NO_NORMS
      • 倒数第六位:是否保存payload

要了解域的元数据信息,还要了解以下几点:

  • 位置(Position)和偏移量(Offset)的区别
    • 位置是基于词Term的,偏移量是基于字母或汉字的。

clip_image002

  • 索引域(Indexed)和存储域(Stored)的区别
    • 一个域为什么会被存储(store)而不被索引(Index)呢?在一个文档中的所有信息中,有这样一部分信息,可能不想被索引从而可以搜索到,但是当这个文档由于其他的信息被搜索到时,可以同其他信息一同返回。
    • 举个例子,读研究生时,您好不容易写了一篇论文交给您的导师,您的导师却要他所第一作者而您做第二作者,然而您导师不想别人在论文系统中搜索您的名字时找到这篇论文,于是在论文系统中,把第二作者这个Field的Indexed设为false,这样别人搜索您的名字,永远不知道您写过这篇论文,只有在别人搜索您导师的名字从而找到您的文章时,在一个角落表述着第二作者是您。
  • payload的使用
    • 我们知道,索引是以倒排表形式存储的,对于每一个词,都保存了包含这个词的一个链表,当然为了加快查询速度,此链表多用跳跃表进行存储。
    • Payload信息就是存储在倒排表中的,同文档号一起存放,多用于存储与每篇文档相关的一些信息。当然这部分信息也可以存储域里(stored Field),两者从功能上基本是一样的,然而当要存储的信息很多的时候,存放在倒排表里,利用跳跃表,有利于大大提高搜索速度。
    • Payload的存储方式如下图:

payload

    • Payload主要有以下几种用法:
      • 存储每个文档都有的信息:比如有的时候,我们想给每个文档赋一个我们自己的文档号,而不是用Lucene自己的文档号。于是我们可以声明一个特殊的域(Field)”_ID”和特殊的词(Term)”_ID”,使得每篇文档都包含词”_ID”,于是在词”_ID”的倒排表里面对于每篇文档又有一项,每一项都有一个payload,于是我们可以在payload里面保存我们自己的文档号。每当我们得到一个Lucene的文档号的时候,就能从跳跃表中查找到我们自己的文档号。
//声明一个特殊的域和特殊的词
public static final String ID_PAYLOAD_FIELD = “_ID”;

public static final String ID_PAYLOAD_TERM = “_ID”;

public static final Term ID_TERM = new Term(ID_PAYLOAD_TERM, ID_PAYLOAD_FIELD);

//声明一个特殊的TokenStream,它只生成一个词(Term),就是那个特殊的词,在特殊的域里面。

static class SinglePayloadTokenStream extends TokenStream {
private Token token;
private boolean returnToken = false;

SinglePayloadTokenStream(String idPayloadTerm) {
char[] term = idPayloadTerm.toCharArray();
token = new Token(term, 0, term.length, 0, term.length);
}

void setPayloadValue(byte[] value) {
token.setPayload(new Payload(value));
returnToken = true;
}

public Token next() throws IOException {
if (returnToken) {
returnToken = false;
return token;
} else {
return null;
}
}
}

//对于每一篇文档,都让它包含这个特殊的词,在特殊的域里面

SinglePayloadTokenStream singlePayloadTokenStream = new SinglePayloadTokenStream(ID_PAYLOAD_TERM);
singlePayloadTokenStream.setPayloadValue(long2bytes(id));
doc.add(new Field(ID_PAYLOAD_FIELD, singlePayloadTokenStream));

//每当得到一个Lucene的文档号时,通过以下的方式得到payload里面的文档号
long id = 0;
TermPositions tp = reader.termPositions(ID_PAYLOAD_TERM);
boolean ret = tp.skipTo(docID);
tp.nextPosition();
int payloadlength = tp.getPayloadLength();
byte[] payloadBuffer = new byte[payloadlength];
tp.getPayload(payloadBuffer, 0);
id = bytes2long(payloadBuffer);
tp.close();

 

      • 影响词的评分
        • 在Similarity抽象类中有函数public float scorePayload(byte [] payload, int offset, int length) 可以根据payload的值影响评分。
  • 读取域元数据信息的代码如下:
FieldInfos.read(IndexInput, String)

  • int firstInt = input.readVInt();
  • size = input.readVInt();
  • for (int i = 0; i < size; i++)
    • String name = input.readString();
    • byte bits = input.readByte();
    • boolean isIndexed = (bits & IS_INDEXED) != 0;
    • boolean storeTermVector = (bits & STORE_TERMVECTOR) != 0;
    • boolean storePositionsWithTermVector = (bits & STORE_POSITIONS_WITH_TERMVECTOR) != 0;
    • boolean storeOffsetWithTermVector = (bits & STORE_OFFSET_WITH_TERMVECTOR) != 0;
    • boolean omitNorms = (bits & OMIT_NORMS) != 0;
    • boolean storePayloads = (bits & STORE_PAYLOADS) != 0;
    • boolean omitTermFreqAndPositions = (bits & OMIT_TERM_FREQ_AND_POSITIONS) != 0;

 

4.1.3. 域(Field)的数据信息(.fdt,.fdx)

fdxfdt

  • 域数据文件(fdt):
    • 真正保存存储域(stored field)信息的是fdt文件
    • 在一个段(segment)中总共有segment size篇文档,所以fdt文件中共有segment size个项,每一项保存一篇文档的域的信息
    • 对于每一篇文档,一开始是一个fieldcount,也即此文档包含的域的数目,接下来是fieldcount个项,每一项保存一个域的信息。
    • 对于每一个域,fieldnum是域号,接着是一个8位的byte,最低一位表示此域是否分词(tokenized),倒数第二位表示此域是保存字符串数据还是二进制数据,倒数第三位表示此域是否被压缩,再接下来就是存储域的值,比如new Field(“title”, “lucene in action”, Field.Store.Yes, …),则此处存放的就是”lucene in action”这个字符串。
  • 域索引文件(fdx)
    • 由域数据文件格式我们知道,每篇文档包含的域的个数,每个存储域的值都是不一样的,因而域数据文件中segment size篇文档,每篇文档占用的大小也是不一样的,那么如何在fdt中辨别每一篇文档的起始地址和终止地址呢,如何能够更快的找到第n篇文档的存储域的信息呢?就是要借助域索引文件。
    • 域索引文件也总共有segment size个项,每篇文档都有一个项,每一项都是一个long,大小固定,每一项都是对应的文档在fdt文件中的起始地址的偏移量,这样如果我们想找到第n篇文档的存储域的信息,只要在fdx中找到第n项,然后按照取出的long作为偏移量,就可以在fdt文件中找到对应的存储域的信息。
  • 读取域数据信息的代码如下:
Document FieldsReader.doc(int n, FieldSelector fieldSelector)

  • long position = indexStream.readLong();//indexStream points to “.fdx”
  • fieldsStream.seek(position);//fieldsStream points to “fdt”
  • int numFields = fieldsStream.readVInt();
  • for (int i = 0; i < numFields; i++)
    • int fieldNumber = fieldsStream.readVInt();
    • byte bits = fieldsStream.readByte();
    • boolean compressed = (bits & FieldsWriter.FIELD_IS_COMPRESSED) != 0;
    • boolean tokenize = (bits & FieldsWriter.FIELD_IS_TOKENIZED) != 0;
    • boolean binary = (bits & FieldsWriter.FIELD_IS_BINARY) != 0;
    • if (binary)
      • int toRead = fieldsStream.readVInt();
      • final byte[] b = new byte[toRead];
      • fieldsStream.readBytes(b, 0, b.length);
      • if (compressed)
        • int toRead = fieldsStream.readVInt();
        • final byte[] b = new byte[toRead];
        • fieldsStream.readBytes(b, 0, b.length);
        • uncompress(b),
    • else
      • fieldsStream.readString()

4.1.3. 词向量(Term Vector)的数据信息(.tvx,.tvd,.tvf)

termvector

词向量信息是从索引(index)到文档(document)到域(field)到词(term)的正向信息,有了词向量信息,我们就可以得到一篇文档包含那些词的信息。

  • 词向量索引文件(tvx)
    • 一个段(segment)包含N篇文档,此文件就有N项,每一项代表一篇文档。
    • 每一项包含两部分信息:第一部分是词向量文档文件(tvd)中此文档的偏移量,第二部分是词向量域文件(tvf)中此文档的第一个域的偏移量。
  • 词向量文档文件(tvd)
    • 一个段(segment)包含N篇文档,此文件就有N项,每一项包含了此文档的所有的域的信息。
    • 每一项首先是此文档包含的域的个数NumFields,然后是一个NumFields大小的数组,数组的每一项是域号。然后是一个(NumFields – 1)大小的数组,由前面我们知道,每篇文档的第一个域在tvf中的偏移量在tvx文件中保存,而其他(NumFields – 1)个域在tvf中的偏移量就是第一个域的偏移量加上这(NumFields – 1)个数组的每一项的值。
  • 词向量域文件(tvf)
    • 此文件包含了此段中的所有的域,并不对文档做区分,到底第几个域到第几个域是属于那篇文档,是由tvx中的第一个域的偏移量以及tvd中的(NumFields – 1)个域的偏移量来决定的。
    • 对于每一个域,首先是此域包含的词的个数NumTerms,然后是一个8位的byte,最后一位是指定是否保存位置信息,倒数第二位是指定是否保存偏移量信息。然后是NumTerms个项的数组,每一项代表一个词(Term),对于每一个词,由词的文本TermText,词频TermFreq(也即此词在此文档中出现的次数),词的位置信息,词的偏移量信息。
  • 读取词向量数据信息的代码如下:
TermVectorsReader.get(int docNum, String field, TermVectorMapper)

  • int fieldNumber = fieldInfos.fieldNumber(field);//通过field名字得到field号
  • seekTvx(docNum);//在tvx文件中按docNum文档号找到相应文档的项
  • long tvdPosition = tvx.readLong();//找到tvd文件中相应文档的偏移量
  • tvd.seek(tvdPosition);//在tvd文件中按偏移量找到相应文档的项
  • int fieldCount = tvd.readVInt();//此文档包含的域的个数。
  • for (int i = 0; i < fieldCount; i++) //按域号查找域
    • number = tvd.readVInt();
    • if (number == fieldNumber)
      • found = i;
  • position = tvx.readLong();//在tvx中读出此文档的第一个域在tvf中的偏移量
  • for (int i = 1; i <= found; i++)
    • position += tvd.readVLong();//加上所要找的域在tvf中的偏移量
  • tvf.seek(position);
  • int numTerms = tvf.readVInt();
  • byte bits = tvf.readByte();
  • storePositions = (bits & STORE_POSITIONS_WITH_TERMVECTOR) != 0;
  • storeOffsets = (bits & STORE_OFFSET_WITH_TERMVECTOR) != 0;
  • for (int i = 0; i < numTerms; i++)
    • start = tvf.readVInt();
    • deltaLength = tvf.readVInt();
    • totalLength = start + deltaLength;
    • tvf.readBytes(byteBuffer, start, deltaLength);
    • term = new String(byteBuffer, 0, totalLength, “UTF-8”);
    • if (storePositions)
      • positions = new int[freq];
      • int prevPosition = 0;
      • for (int j = 0; j < freq; j++)
        • positions[j] = prevPosition + tvf.readVInt();
        • prevPosition = positions[j];
    • if (storeOffsets)
      • offsets = new TermVectorOffsetInfo[freq];
      • int prevOffset = 0;
      • for (int j = 0; j < freq; j++)
      • int startOffset = prevOffset + tvf.readVInt();
      • int endOffset = startOffset + tvf.readVInt();
      • offsets[j] = new TermVectorOffsetInfo(startOffset, endOffset);
      • prevOffset = endOffset;

 

本文转载http://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623599.html

仅为自己学习所用。

Lucene学习总结之三:Lucene的索引文件格式(1)

lucene的索引里面存了些什么,如何存放的,也即Lucene的索引文件格式,是读懂Lucene源代码的一把钥匙。

当我们真正进入到Lucene源代码之中的时候,我们会发现:

  • Lucene的索引过程,就是按照全文检索的基本过程,将倒排表写成此文件格式的过程。
  • Lucene的搜索过程,就是按照此文件格式将索引进去的信息读出来,然后计算每篇文档打分(score)的过程。

本文详细解读了Apache Lucene – Index File Formats(http://lucene.apache.org/java/2_9_0/fileformats.html) 这篇文章。

 

一、基本概念

下图就是Lucene生成的索引的一个实例:

image

Lucene的索引结构是有层次结构的,主要分以下几个层次:

  • 索引(Index):
    • 在Lucene中一个索引是放在一个文件夹中的。
    • 如上图,同一文件夹中的所有的文件构成一个Lucene索引。
  • 段(Segment):
    • 一个索引可以包含多个段,段与段之间是独立的,添加新文档可以生成新的段,不同的段可以合并。
    • 如上图,具有相同前缀文件的属同一个段,图中共两个段 “_0” 和 “_1″。
    • segments.gen和segments_5是段的元数据文件,也即它们保存了段的属性信息。
  • 文档(Document):
    • 文档是我们建索引的基本单位,不同的文档是保存在不同的段中的,一个段可以包含多篇文档。
    • 新添加的文档是单独保存在一个新生成的段中,随着段的合并,不同的文档合并到同一个段中。
  • 域(Field):
    • 一篇文档包含不同类型的信息,可以分开索引,比如标题,时间,正文,作者等,都可以保存在不同的域里。
    • 不同域的索引方式可以不同,在真正解析域的存储的时候,我们会详细解读。
  • 词(Term):
    • 词是索引的最小单位,是经过词法分析和语言处理后的字符串。

 

Lucene的索引结构中,即保存了正向信息,也保存了反向信息。

所谓正向信息:

  • 按层次保存了从索引,一直到词的包含关系:索引(Index) –> 段(segment) –> 文档(Document) –> 域(Field) –> 词(Term)
  • 也即此索引包含了那些段,每个段包含了那些文档,每个文档包含了那些域,每个域包含了那些词。
  • 既然是层次结构,则每个层次都保存了本层次的信息以及下一层次的元信息,也即属性信息,比如一本介绍中国地理的书,应该首先介绍中国地理的概况,以及中国包含多少个省,每个省介绍本省的基本概况及包含多少个市,每个市介绍本市的基本概况及包含多少个县,每个县具体介绍每个县的具体情况。
  • 如上图,包含正向信息的文件有:
    • segments_N保存了此索引包含多少个段,每个段包含多少篇文档。
    • XXX.fnm保存了此段包含了多少个域,每个域的名称及索引方式。
    • XXX.fdx,XXX.fdt保存了此段包含的所有文档,每篇文档包含了多少域,每个域保存了那些信息。
    • XXX.tvx,XXX.tvd,XXX.tvf保存了此段包含多少文档,每篇文档包含了多少域,每个域包含了多少词,每个词的字符串,位置等信息。

所谓反向信息:

  • 保存了词典到倒排表的映射:词(Term) –> 文档(Document)
  • 如上图,包含反向信息的文件有:
    • XXX.tis,XXX.tii保存了词典(Term Dictionary),也即此段包含的所有的词按字典顺序的排序。
    • XXX.frq保存了倒排表,也即包含每个词的文档ID列表。
    • XXX.prx保存了倒排表中每个词在包含此词的文档中的位置。

在了解Lucene索引的详细结构之前,先看看Lucene索引中的基本数据类型。

 

二、基本类型

Lucene索引文件中,用一下基本类型来保存信息:

  • Byte:是最基本的类型,长8位(bit)。
  • UInt32:由4个Byte组成。
  • UInt64:由8个Byte组成。
  • VInt:
    • 变长的整数类型,它可能包含多个Byte,对于每个Byte的8位,其中后7位表示数值,最高1位表示是否还有另一个Byte,0表示没有,1表示有。
    • 越前面的Byte表示数值的低位,越后面的Byte表示数值的高位。
    • 例如130化为二进制为 1000, 0010,总共需要8位,一个Byte表示不了,因而需要两个Byte来表示,第一个Byte表示后7位,并且在最高位置1来表示后面还有一个Byte,所以为(1) 0000010,第二个Byte表示第8位,并且最高位置0来表示后面没有其他的Byte了,所以为(0) 0000001。

clip_image002[1]

  • Chars:是UTF-8编码的一系列Byte。
  • String:一个字符串首先是一个VInt来表示此字符串包含的字符的个数,接着便是UTF-8编码的字符序列Chars。

 

三、基本规则

Lucene为了使的信息的存储占用的空间更小,访问速度更快,采取了一些特殊的技巧,然而在看Lucene文件格式的时候,这些技巧却容易使我们感到困惑,所以有必要把这些特殊的技巧规则提取出来介绍一下。

在下不才,胡乱给这些规则起了一些名字,是为了方便后面应用这些规则的时候能够简单,不妥之处请大家谅解。

1. 前缀后缀规则(Prefix+Suffix)

Lucene在反向索引中,要保存词典(Term Dictionary)的信息,所有的词(Term)在词典中是按照字典顺序进行排列的,然而词典中包含了文档中的几乎所有的词,并且有的词还是非常的长的,这样索引文件会非常的大,所谓前缀后缀规则,即当某个词和前一个词有共同的前缀的时候,后面的词仅仅保存前缀在词中的偏移(offset),以及除前缀以外的字符串(称为后缀)。

prefixsuffix

比如要存储如下词:term,termagancy,termagant,terminal,

如果按照正常方式来存储,需要的空间如下:

[VInt = 4] [t][e][r][m],[VInt = 10][t][e][r][m][a][g][a][n][c][y],[VInt = 9][t][e][r][m][a][g][a][n][t],[VInt = 8][t][e][r][m][i][n][a][l]

共需要35个Byte.

如果应用前缀后缀规则,需要的空间如下:

[VInt = 4] [t][e][r][m],[VInt = 4 (offset)][VInt = 6][a][g][a][n][c][y],[VInt = 8 (offset)][VInt = 1][t],[VInt = 4(offset)][VInt = 4][i][n][a][l]

共需要22个Byte。

大大缩小了存储空间,尤其是在按字典顺序排序的情况下,前缀的重合率大大提高。

2. 差值规则(Delta)

在Lucene的反向索引中,需要保存很多整型数字的信息,比如文档ID号,比如词(Term)在文档中的位置等等。

由上面介绍,我们知道,整型数字是以VInt的格式存储的。随着数值的增大,每个数字占用的Byte的个数也逐渐的增多。所谓差值规则(Delta)就是先后保存两个整数的时候,后面的整数仅仅保存和前面整数的差即可。

delta

比如要存储如下整数:16386,16387,16388,16389

如果按照正常方式来存储,需要的空间如下:

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001],[(1) 000, 0011][(1) 000, 0000][(0) 000, 0001],[(1) 000, 0100][(1) 000, 0000][(0) 000, 0001],[(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]

供需12个Byte。

如果应用差值规则来存储,需要的空间如下:

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001],[(0) 000, 0001],[(0) 000, 0001],[(0) 000, 0001]

共需6个Byte。

大大缩小了存储空间,而且无论是文档ID,还是词在文档中的位置,都是按从小到大的顺序,逐渐增大的。

3. 或然跟随规则(A, B?)

Lucene的索引结构中存在这样的情况,某个值A后面可能存在某个值B,也可能不存在,需要一个标志来表示后面是否跟随着B。

一般的情况下,在A后面放置一个Byte,为0则后面不存在B,为1则后面存在B,或者0则后面存在B,1则后面不存在B。

但这样要浪费一个Byte的空间,其实一个Bit就可以了。

在Lucene中,采取以下的方式:A的值左移一位,空出最后一位,作为标志位,来表示后面是否跟随B,所以在这种情况下,A/2是真正的A原来的值。

ab

如果去读Apache Lucene – Index File Formats这篇文章,会发现很多符合这种规则的:

  • .frq文件中的DocDelta[, Freq?],DocSkip,PayloadLength?
  • .prx文件中的PositionDelta,Payload? (但不完全是,如下表分析)

当然还有一些带?的但不属于此规则的:

  • .frq文件中的SkipChildLevelPointer?,是多层跳跃表中,指向下一层表的指针,当然如果是最后一层,此值就不存在,也不需要标志。
  • .tvf文件中的Positions?, Offsets?。
    • 在此类情况下,带?的值是否存在,并不取决于前面的值的最后一位。
    • 而是取决于Lucene的某项配置,当然这些配置也是保存在Lucene索引文件中的。
    • 如Position和Offset是否存储,取决于.fnm文件中对于每个域的配置(TermVector.WITH_POSITIONS和TermVector.WITH_OFFSETS)

为什么会存在以上两种情况,其实是可以理解的:

  • 对于符合或然跟随规则的,是因为对于每一个A,B是否存在都不相同,当这种情况大量存在的时候,从一个Byte到一个Bit如此8倍的空间节约还是很值得的。
  • 对于不符合或然跟随规则的,是因为某个值的是否存在的配置对于整个域(Field)甚至整个索引都是有效的,而非每次的情况都不相同,因而可以统一存放一个标志。
文章中对如下格式的描述令人困惑:Positions –> <PositionDelta,Payload?> Freq

Payload –> <PayloadLength?,PayloadData>

PositionDelta和Payload是否适用或然跟随规则呢?如何标识PayloadLength是否存在呢?

其实PositionDelta和Payload并不符合或然跟随规则,Payload是否存在,是由.fnm文件中对于每个域的配置中有关Payload的配置决定的(FieldOption.STORES_PAYLOADS) 。

当Payload不存在时,PayloadDelta本身不遵从或然跟随原则。

当Payload存在时,格式应该变成如下:Positions –> <PositionDelta,PayloadLength?,PayloadData> Freq

从而PositionDelta和PayloadLength一起适用或然跟随规则。

 

4. 跳跃表规则(Skip list)

为了提高查找的性能,Lucene在很多地方采取的跳跃表的数据结构。

跳跃表(Skip List)是如图的一种数据结构,有以下几个基本特征:

  • 元素是按顺序排列的,在Lucene中,或是按字典顺序排列,或是按从小到大顺序排列。
  • 跳跃是有间隔的(Interval),也即每次跳跃的元素数,间隔是事先配置好的,如图跳跃表的间隔为3。
  • 跳跃表是由层次的(level),每一层的每隔指定间隔的元素构成上一层,如图跳跃表共有2层。

skiplist

需要注意一点的是,在很多数据结构或算法书中都会有跳跃表的描述,原理都是大致相同的,但是定义稍有差别:

  • 对间隔(Interval)的定义: 如图中,有的认为间隔为2,即两个上层元素之间的元素数,不包括两个上层元素;有的认为是3,即两个上层元素之间的差,包括后面上层元素,不包括前面的上层元素;有的认为是4,即除两个上层元素之间的元素外,既包括前面,也包括后面的上层元素。Lucene是采取的第二种定义。
  • 对层次(Level)的定义:如图中,有的认为应该包括原链表层,并从1开始计数,则总层次为3,为1,2,3层;有的认为应该包括原链表层,并从0计数,为0,1,2层;有的认为不应该包括原链表层,且从1开始计数,则为1,2层;有的认为不应该包括链表层,且从0开始计数,则为0,1层。Lucene采取的是最后一种定义。

跳跃表比顺序查找,大大提高了查找速度,如查找元素72,原来要访问2,3,7,12,23,37,39,44,50,72总共10个元素,应用跳跃表后,只要首先访问第1层的50,发现72大于50,而第1层无下一个节点,然后访问第2层的94,发现94大于72,然后访问原链表的72,找到元素,共需要访问3个元素即可。

然而Lucene在具体实现上,与理论又有所不同,在具体的格式中,会详细说明。

<script type=”text/javascript”></script>

 

本文转载http://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623597.html

仅为自己学习所用

Lucene学习总结之二:Lucene的总体架构

lucene总的来说是:

  • 一个高效的,可扩展的,全文检索库。
  • 全部用java实现,无须配置。
  • 仅支持纯文本文件的索引(Indexing)和搜索(Search)。
  • 不负责由其他格式的文件抽取纯文本文件,或从网络中抓取文件的过程。

在Lucene in action中,Lucene 的构架和过程如下图,

说明Lucene是有索引和搜索的两个过程,包含索引创建,索引,搜索三个要点。

让我们更细一些看Lucene的各组件:

  • 被索引的文档用Document对象表示。
  • IndexWriter通过函数addDocument将文档添加到索引中,实现创建索引的过程。
  • Lucene的索引是应用反向索引。
  • 当用户有请求时,Query代表用户的查询语句。
  • IndexSearcher通过函数search搜索Lucene Index
  • IndexSearcher计算term weight和score并且将结果返回给用户。
  • 返回给用户的文档集合用TopDocsCollector表示。

 

那么如何应用这些组件呢?

让我们再详细到对Lucene API 的调用实现索引和搜索过程。

  • 索引过程如下:
    • 创建一个IndexWriter用来写索引文件,它有几个参数,INDEX_DIR就是索引文件所存放的位置,Analyzer便是用来对文档进行词法分析和语言处理的。
    • 创建一个Document代表我们要索引的文档。
    • 将不同的Field加入到文档中。我们知道,一篇文档有多种信息,如题目,作者,修改时间,内容等。不同类型的信息用不同的Field来表示,在本例子中,一共有两类信息进行了索引,一个是文件路径,一个是文件内容。其中FileReader的SRC_FILE就表示要索引的源文件。
    • IndexWriter调用函数addDocument将索引写到索引文件夹中。
  • 搜索过程如下:
    • IndexReader将磁盘上的索引信息读入到内存,INDEX_DIR就是索引文件存放的位置。
    • 创建IndexSearcher准备进行搜索。
    • 创建Analyer用来对查询语句进行词法分析和语言处理。
    • 创建QueryParser用来对查询语句进行语法分析。
    • QueryParser调用parser进行语法分析,形成查询语法树,放到Query中。
    • IndexSearcher调用search对查询语法树Query进行搜索,得到结果TopScoreDocCollector

以上便是Lucene API函数的简单调用。

然而当进入Lucene的源代码后,发现Lucene有很多包,关系错综复杂。

然而通过下图,我们不难发现,Lucene的各源码模块,都是对普通索引和搜索过程的一种实现。

此图是上一节介绍的全文检索的流程对应的Lucene实现的包结构。(参照http://www.lucene.com.cn/about.htm中文章《开放源代码的全文检索引擎Lucene》)

  • Lucene的analysis模块主要负责词法分析及语言处理而形成Term
  • Lucene的index模块主要负责索引的创建,里面有IndexWriter
  • Lucene的store模块主要负责索引的读写。
  • Lucene的QueryParser主要负责语法分析。
  • Lucene的search模块主要负责对索引的搜索。
  • Lucene的similarity模块主要负责对相关性打分的实现。

了解了Lucene的整个结构,我们便可以开始Lucene的源码之旅了。

 

本文转载http://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623596.html

仅为自己学习所用。

Lucene学习总结之一:全文检索的基本原理

一、总论

根据http://lucene.apache.org/java/docs/index.html定义:

lucene是一个高效的,基于java全文检索库。

所以在了解Lucene之前要费一番工夫了解一下全文检索。

那么什么叫做全文检索呢?这要从我们生活中的数据说起。

我们生活中的数据总体分为两种:结构化数据非结构化数据

  • 结构化数据:指具有固定格式或有限长度的数据,如数据库,元数据等。
  • 非结构化数据:指不定长或无固定格式的数据,如邮件,word文档等。

当然有的地方还会提到第三种,半结构化数据,如XML,HTML等,当根据需要可按结构化数据来处理,也可抽取出纯文本按非结构化数据来处理。

非结构化数据又一种叫法叫全文数据。

 

按照数据的分类,搜索也分为两种:

  • 对结构化数据的搜索:如对数据库的搜索,用SQL语句。再如对元数据的搜索,如利用windows搜索对文件名,类型,修改时间进行搜索等。
  • 对非结构化数据的搜索:如利用windows的搜索也可以搜索文件内容,linux下的grep命令,再如用Google和百度可以搜索大量内容数据。

对非结构化数据也即对全文数据的搜索主要有两种方法:

一种是顺序扫描法(Serial Scanning):所谓顺序扫描,比如要找内容包含某一个字符串的文件,就是一个文档一个文档的看,对于每一个文档,从头看到尾,如果此文档包含此字符串,则此文档为我们要找的文件,接着看下一个文件,直到扫描完所有的文件。如利用windows的搜索也可以搜索文件内容,只是相当的慢。如果你有一个80G硬盘,如果想在上面找到一个内容包含某字符串的文件,不花他几个小时,怕是做不到。Linux下的grep命令也是这一种方式。大家可能觉得这种方法比较原始,但对于小数据量的文件,这种方法还是最直接,最方便的。但是对于大量的文件,这种方法就很慢了。

有人可能会说,对非结构化数据顺序扫描很慢,对结构化数据的搜索却相对较快(由于结构化数据有一定的结构可以采取一定的搜索算法加快速度),那么把我们的非结构化数据想办法弄得有一定结构不就行了吗?

这种想法很天然,却构成了全文检索的基本思路,也即将非结构化数据中的一部分信息提取出来,重新组织,使其变得有一定结构,然后对此有一定结构的数据进行搜索,从而达到搜索相对较快的目的。

这部分从非结构化数据中提取出的然后重新组织的信息,我们称之索引

这种说法比较抽象,举几个例子就很容易明白,比如字典,字典的拼音表和部首检字表就相当于字典的索引,对每一个字的解释是非结构化的,如果字典没有音节表和部首检字表,在茫茫辞海中找一个字只能顺序扫描。然而字的某些信息可以提取出来进行结构化处理,比如读音,就比较结构化,分声母和韵母,分别只有几种可以一一列举,于是将读音拿出来按一定的顺序排列,每一项读音都指向此字的详细解释的页数。我们搜索时按结构化的拼音搜到读音,然后按其指向的页数,便可找到我们的非结构化数据——也即对字的解释。

 

这种先建立索引,再对索引进行搜索的过程就叫全文检索(Full-text Search)

 

下面这幅图来自《Lucene in action》,但却不仅仅描述了Lucene的检索过程,而是描述了全文检索的一般过程。

全文检索大体分两个过程,索引创建(Indexing)搜索索引(Search)

  • 索引创建:将现实世界中所有的结构化和非结构化数据提取信息,创建索引的过程。
  • 搜索索引:就是得到用户的查询请求,搜索创建的索引,然后返回结果的过程。

于是全文检索就存在三个重要问题:

1. 索引里面究竟存些什么?(Index)

2. 如何创建索引?(Indexing)

3. 如何对索引进行搜索?(Search)

下面我们顺序对每个个问题进行研究。

 

二、索引里面究竟存些什么

索引里面究竟需要存些什么呢?

首先我们来看为什么顺序扫描的速度慢:

其实是由于我们想要搜索的信息和非结构化数据中所存储的信息不一致造成的。

非结构化数据中所存储的信息是每个文件包含哪些字符串,也即已知文件,欲求字符串相对容易,也即是从文件到字符串的映射。而我们想搜索的信息是哪些文件包含此字符串,也即已知字符串,欲求文件,也即从字符串到文件的映射。两者恰恰相反。于是如果索引总能够保存从字符串到文件的映射,则会大大提高搜索速度。

由于从字符串到文件的映射是文件到字符串映射的反向过程,于是保存这种信息的索引称为反向索引

反向索引的所保存的信息一般如下:

假设我的文档集合里面有100篇文档,为了方便表示,我们为文档编号从1到100,得到下面的结构

左边保存的是一系列字符串,称为词典

每个字符串都指向包含此字符串的文档(Document)链表,此文档链表称为倒排表(Posting List)。

有了索引,便使保存的信息和要搜索的信息一致,可以大大加快搜索的速度。

比如说,我们要寻找既包含字符串“lucene”又包含字符串“solr”的文档,我们只需要以下几步:

1. 取出包含字符串“lucene”的文档链表。

2. 取出包含字符串“solr”的文档链表。

3. 通过合并链表,找出既包含“lucene”又包含“solr”的文件。

看到这个地方,有人可能会说,全文检索的确加快了搜索的速度,但是多了索引的过程,两者加起来不一定比顺序扫描快多少。的确,加上索引的过程,全文检索不一定比顺序扫描快,尤其是在数据量小的时候更是如此。而对一个很大量的数据创建索引也是一个很慢的过程。

然而两者还是有区别的,顺序扫描是每次都要扫描,而创建索引的过程仅仅需要一次,以后便是一劳永逸的了,每次搜索,创建索引的过程不必经过,仅仅搜索创建好的索引就可以了。

这也是全文搜索相对于顺序扫描的优势之一:一次索引,多次使用。

 

三、如何创建索引

全文检索的索引创建过程一般有以下几步:

第一步:一些要索引的原文档(Document)。

为了方便说明索引创建过程,这里特意用两个文件为例:

文件一:Students should be allowed to go out with their friends, but not allowed to drink beer.

文件二:My friend Jerry went to school to see his students but found them drunk which is not allowed.

 

第二步:将原文档传给分次组件(Tokenizer)。

分词组件(Tokenizer)会做以下几件事情(此过程称为Tokenize)

1. 将文档分成一个一个单独的单词。

2. 去除标点符号。

3. 去除停词(Stop word)

所谓停词(Stop word)就是一种语言中最普通的一些单词,由于没有特别的意义,因而大多数情况下不能成为搜索的关键词,因而创建索引时,这种词会被去掉而减少索引的大小。

英语中挺词(Stop word)如:“the”,“a”,“this”等。

对于每一种语言的分词组件(Tokenizer),都有一个停词(stop word)集合。

 

经过分词(Tokenizer)后得到的结果称为词元(Token)

在我们的例子中,便得到以下词元(Token):

“Students”,“allowed”,“go”,“their”,“friends”,“allowed”,“drink”,“beer”,“My”,“friend”,“Jerry”,“went”,“school”,“see”,“his”,“students”,“found”,“them”,“drunk”,“allowed”。

 

第三步:将得到的词元(Token)传给语言处理组件(Linguistic Processor)。

语言处理组件(linguistic processor)主要是对得到的词元(Token)做一些同语言相关的处理。

对于英语,语言处理组件(Linguistic Processor)一般做以下几点:

1. 变为小写(Lowercase)

2. 将单词缩减为词根形式,如“cars”到“car”等。这种操作称为:stemming

3. 将单词转变为词根形式,如“drove”到“drive”等。这种操作称为:lemmatization

 

Stemming 和 lemmatization的异同:

  • 相同之处:Stemming和lemmatization都要使词汇成为词根形式。
  • 两者的方式不同:
    • Stemming采用的是“缩减”的方式:“cars”到“car”,“driving”到“drive”。
    • Lemmatization采用的是“转变”的方式:“drove”到“drove”,“driving”到“drive”。
  • 两者的算法不同:
    • Stemming主要是采取某种固定的算法来做这种缩减,如去除“s”,去除“ing”加“e”,将“ational”变为“ate”,将“tional”变为“tion”。
    • Lemmatization主要是采用保存某种字典的方式做这种转变。比如字典中有“driving”到“drive”,“drove”到“drive”,“am, is, are”到“be”的映射,做转变时,只要查字典就可以了。
  • Stemming和lemmatization不是互斥关系,是有交集的,有的词利用这两种方式都能达到相同的转换。

 

语言处理组件(linguistic processor)的结果称为词(Term)

在我们的例子中,经过语言处理,得到的词(Term)如下:

“student”,“allow”,“go”,“their”,“friend”,“allow”,“drink”,“beer”,“my”,“friend”,“jerry”,“go”,“school”,“see”,“his”,“student”,“find”,“them”,“drink”,“allow”。

 

也正是因为有语言处理的步骤,才能使搜索drove,而drive也能被搜索出来。

 

第四步:将得到的词(Term)传给索引组件(Indexer)。

索引组件(Indexer)主要做以下几件事情:

1. 利用得到的词(Term)创建一个字典。

在我们的例子中字典如下:

 

Term Document ID
student 1
allow 1
go 1
their 1
friend 1
allow 1
drink 1
beer 1
my 2
friend 2
jerry 2
go 2
school 2
see 2
his 2
student 2
find 2
them 2
drink 2
allow 2

 

2. 对字典按字母顺序进行排序。

 

 

Term Document ID
allow 1
allow 1
allow 2
beer 1
drink 1
drink 2
find 2
friend 1
friend 2
go 1
go 2
his 2
jerry 2
my 2
school 2
see 2
student 1
student 2
their 1
them 2

 

3. 合并相同的词(Term)成为文档倒排(Posting List)链表。

在此表中,有几个定义:

  • Document Frequency 即文档频次,表示总共有多少文件包含此词(Term)。
  • Frequency 即词频率,表示此文件中包含了几个此词(Term)。

所以对词(Term) “allow”来讲,总共有两篇文档包含此词(Term),从而词(Term)后面的文档链表总共有两项,第一项表示包含“allow”的第一篇文档,即1号文档,此文档中,“allow”出现了2次,第二项表示包含“allow”的第二个文档,是2号文档,此文档中,“allow”出现了1次。

到此为止,索引已经创建好了,我们可以通过它很快的找到我们想要的文档。

而且在此过程中,我们惊喜地发现,搜索“drive”,“driving”,“drove”,“driven”也能够被搜到。因为在我们的索引中,“driving”,“drove”,“driven”都会经过语言处理而变成“drive”,在搜索时,如果您输入“driving”,输入的查询语句同样经过我们这里的一到三步,从而变为查询“drive”,从而可以搜索到想要的文档。

 

 

三、如何对索引进行搜索?

到这里似乎我们可以宣布“我们找到想要的文档了”。

然而事情并没有结束,找到了仅仅是全文检索的一个方面。不是吗?如果仅仅只有一个或十个文档包含我们查询的字符串,我们的确找到了。然而如果结果有一千个,甚至成千上万个呢?那个又是您最想要的文件呢?

打开Google吧,比如说您想在微软找份工作,于是您输入“Microsoft job”,您却发现总共有22600000个结果返回。好大的数字呀,突然发现找不到是一个问题,找到的太多也是一个问题。在如此多的结果中,如何将最相关的放在最前面呢?

当然Google做的很不错,您一下就找到了jobs at Microsoft。想象一下,如果前几个全部是“Microsoft does a good job at software industry…”将是多么可怕的事情呀。

如何像Google一样,在成千上万的搜索结果中,找到和查询语句最相关的呢?

如何判断搜索出的文档和查询语句的相关性呢?

这要回到我们第三个问题:如何对索引进行搜索?

搜索主要分为以下几步:

第一步:用户输入查询语句。

查询语句同我们普通的语言一样,也是有一定语法的。

不同的查询语句有不同的语法,如SQL语句就有一定的语法。

查询语句的语法根据全文检索系统的实现而不同。最基本的有比如:AND, OR, NOT等。

举个例子,用户输入语句:lucene AND learned NOT hadoop。

说明用户想找一个包含lucene和learned然而不包括hadoop的文档。

第二步:对查询语句进行词法分析,语法分析,及语言处理。

由于查询语句有语法,因而也要进行语法分析,语法分析及语言处理。

1. 词法分析主要用来识别单词和关键字。

如上述例子中,经过词法分析,得到单词有lucene,learned,hadoop, 关键字有AND, NOT。

如果在词法分析中发现不合法的关键字,则会出现错误。如lucene AMD learned,其中由于AND拼错,导致AMD作为一个普通的单词参与查询。

2. 语法分析主要是根据查询语句的语法规则来形成一棵语法树。

如果发现查询语句不满足语法规则,则会报错。如lucene NOT AND learned,则会出错。

如上述例子,lucene AND learned NOT hadoop形成的语法树如下:

3. 语言处理同索引过程中的语言处理几乎相同。

如learned变成learn等。

经过第二步,我们得到一棵经过语言处理的语法树。

第三步:搜索索引,得到符合语法树的文档。

此步骤有分几小步:

  1. 首先,在反向索引表中,分别找出包含lucene,learn,hadoop的文档链表。
  2. 其次,对包含lucene,learn的链表进行合并操作,得到既包含lucene又包含learn的文档链表。
  3. 然后,将此链表与hadoop的文档链表进行差操作,去除包含hadoop的文档,从而得到既包含lucene又包含learn而且不包含hadoop的文档链表。
  4. 此文档链表就是我们要找的文档。

 

 

 

第四步:根据得到的文档和查询语句的相关性,对结果进行排序。

虽然在上一步,我们得到了想要的文档,然而对于查询结果应该按照与查询语句的相关性进行排序,越相关者越靠前。

如何计算文档和查询语句的相关性呢?

不如我们把查询语句看作一片短小的文档,对文档与文档之间的相关性(relevance)进行打分(scoring),分数高的相关性好,就应该排在前面。

那么又怎么对文档之间的关系进行打分呢?

这可不是一件容易的事情,首先我们看一看判断人之间的关系吧。

首先看一个人,往往有很多要素,如性格,信仰,爱好,衣着,高矮,胖瘦等等。

其次对于人与人之间的关系,不同的要素重要性不同,性格,信仰,爱好可能重要些,衣着,高矮,胖瘦可能就不那么重要了,所以具有相同或相似性格,信仰,爱好的人比较容易成为好的朋友,然而衣着,高矮,胖瘦不同的人,也可以成为好的朋友。

因而判断人与人之间的关系,首先要找出哪些要素对人与人之间的关系最重要,比如性格,信仰,爱好。其次要判断两个人的这些要素之间的关系,比如一个人性格开朗,另一个人性格外向,一个人信仰佛教,另一个信仰上帝,一个人爱好打篮球,另一个爱好踢足球。我们发现,两个人在性格方面都很积极,信仰方面都很善良,爱好方面都爱运动,因而两个人关系应该会很好。

 

我们再来看看公司之间的关系吧。

首先看一个公司,有很多人组成,如总经理,经理,首席技术官,普通员工,保安,门卫等。

其次对于公司与公司之间的关系,不同的人重要性不同,总经理,经理,首席技术官可能更重要一些,普通员工,保安,门卫可能较不重要一点。所以如果两个公司总经理,经理,首席技术官之间关系比较好,两个公司容易有比较好的关系。然而一位普通员工就算与另一家公司的一位普通员工有血海深仇,怕也难影响两个公司之间的关系。

因而判断公司与公司之间的关系,首先要找出哪些人对公司与公司之间的关系最重要,比如总经理,经理,首席技术官。其次要判断这些人之间的关系,不如两家公司的总经理曾经是同学,经理是老乡,首席技术官曾是创业伙伴。我们发现,两家公司无论总经理,经理,首席技术官,关系都很好,因而两家公司关系应该会很好。

 

分析了两种关系,下面看一下如何判断文档之间的关系了。

首先,一个文档有很多词(Term)组成,如search, lucene, full-text, this, a, what等。

其次对于文档之间的关系,不同的Term重要性不同,比如对于本篇文档,search, Lucene, full-text就相对重要一些,this, a , what可能相对不重要一些。所以如果两篇文档都包含search, Lucene,fulltext,这两篇文档的相关性好一些,然而就算一篇文档包含this, a, what,另一篇文档不包含this, a, what,也不能影响两篇文档的相关性。

因而判断文档之间的关系,首先找出哪些词(Term)对文档之间的关系最重要,如search, Lucene, fulltext。然后判断这些词(Term)之间的关系。

 

找出词(Term)对文档的重要性的过程称为计算词的权重(Term weight)的过程。

计算词的权重(term weight)有两个参数,第一个是词(Term),第二个是文档(Document)。

词的权重(Term weight)表示此词(Term)在此文档中的重要程度,越重要的词(Term)有越大的权重(Term weight),因而在计算文档之间的相关性中将发挥更大的作用。

判断词(Term)之间的关系从而得到文档相关性的过程应用一种叫做向量空间模型的算法(Vector Space Model)

 

下面仔细分析一下这两个过程:

1. 计算权重(Term weight)的过程。

影响一个词(Term)在一篇文档中的重要性主要有两个因素:

  • Term Frequency (tf):即此Term在此文档中出现了多少次。tf 越大说明越重要。
  • Document Frequency (df):即有多少文档包含次Term。df 越大说明越不重要。

容易理解吗?词(Term)在文档中出现的次数越多,说明此词(Term)对该文档越重要,如“搜索”这个词,在本文档中出现的次数很多,说明本文档主要就是讲这方面的事的。然而在一篇英语文档中,this出现的次数更多,就说明越重要吗?不是的,这是由第二个因素进行调整,第二个因素说明,有越多的文档包含此词(Term), 说明此词(Term)太普通,不足以区分这些文档,因而重要性越低。

这也如我们程序员所学的技术,对于程序员本身来说,这项技术掌握越深越好(掌握越深说明花时间看的越多,tf越大),找工作时越有竞争力。然而对于所有程序员来说,这项技术懂得的人越少越好(懂得的人少df小),找工作越有竞争力。人的价值在于不可替代性就是这个道理。

道理明白了,我们来看看公式:

这仅仅只term weight计算公式的简单典型实现。实现全文检索系统的人会有自己的实现,Lucene就与此稍有不同。

 

2. 判断Term之间的关系从而得到文档相关性的过程,也即向量空间模型的算法(VSM)。

我们把文档看作一系列词(Term),每一个词(Term)都有一个权重(Term weight),不同的词(Term)根据自己在文档中的权重来影响文档相关性的打分计算。

于是我们把所有此文档中词(term)的权重(term weight) 看作一个向量。

Document = {term1, term2, …… ,term N}

Document Vector = {weight1, weight2, …… ,weight N}

同样我们把查询语句看作一个简单的文档,也用向量来表示。

Query = {term1, term 2, …… , term N}

Query Vector = {weight1, weight2, …… , weight N}

我们把所有搜索出的文档向量及查询向量放到一个N维空间中,每个词(term)是一维。

如图:

我们认为两个向量之间的夹角越小,相关性越大。

所以我们计算夹角的余弦值作为相关性的打分,夹角越小,余弦值越大,打分越高,相关性越大。

有人可能会问,查询语句一般是很短的,包含的词(Term)是很少的,因而查询向量的维数很小,而文档很长,包含词(Term)很多,文档向量维数很大。你的图中两者维数怎么都是N呢?

在这里,既然要放到相同的向量空间,自然维数是相同的,不同时,取二者的并集,如果不含某个词(Term)时,则权重(Term Weight)为0。

 

相关性打分公式如下:

举个例子,查询语句有11个Term,共有三篇文档搜索出来。其中各自的权重(Term weight),如下表格。

 

t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11
D1 0 0 .477 0 .477 .176 0 0 0 .176 0
D2 0 .176 0 .477 0 0 0 0 .954 0 .176
D3 0 .176 0 0 0 .176 0 0 0 .176 .176
Q 0 0 0 0 0 .176 0 0 .477 0 .176

于是计算,三篇文档同查询语句的相关性打分分别为:


于是文档二相关性最高,先返回,其次是文档一,最后是文档三。

到此为止,我们可以找到我们最想要的文档了。

说了这么多,其实还没有进入到Lucene,而仅仅是信息检索技术(Information retrieval)中的基本理论,然而当我们看过Lucene后我们会发现,Lucene是对这种基本理论的一种基本的的实践。所以在以后分析Lucene的文章中,会常常看到以上理论在Lucene中的应用。

在进入Lucene之前,对上述索引创建和搜索过程所一个总结,如图:

此图参照http://www.lucene.com.cn/about.htm中文章《开放源代码的全文检索引擎Lucene》

1. 索引过程:

1) 有一系列被索引文件

2) 被索引文件经过语法分析和语言处理形成一系列词(Term)

3) 经过索引创建形成词典和反向索引表。

4) 通过索引存储将索引写入硬盘。

2. 搜索过程:

a) 用户输入查询语句。

b) 对查询语句经过语法分析和语言分析得到一系列词(Term)

c) 通过语法分析得到一个查询树。

d) 通过索引存储将索引读入到内存。

e) 利用查询树搜索索引,从而得到每个词(Term)的文档链表,对文档链表进行交,差,并得到结果文档。

f) 将搜索到的结果文档对查询的相关性进行排序。

g) 返回查询结果给用户。

下面我们可以进入Lucene的世界了。

文章转载http://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623594.html

仅为自己学习所用。