FST源代码解读4——结束添加
程序员文章站
2022-03-23 14:33:59
...
lucene fst 源代码 解读
前面讲到调用FST.finish方法了,进入到这个阶段的前提是所有的term都已经被编译进fst了,也就是写入到bytes中了。看下代码如下:
/** 当编译root节点之后调用,传入的是root节点的编号(或者是在bytes中的开始位置) */ void finish(long newStartNode) throws IOException { assert newStartNode <= bytes.getPosition(); if (startNode != -1) { throw new IllegalStateException("already finished"); } if (newStartNode == FINAL_END_NODE && emptyOutput != null) { newStartNode = 0; } startNode = newStartNode;//start节点在bytes中的开始 bytes.finish(); cacheRootArcs();//缓存从root发出的部分arc }
里面有一个cacheRootArcs方法,因为FST在查找的时候,每次必须从root出发,也就是从root出发的arc每次都要被查找,所以可以将其缓存起来,提高效率。
/** Optionally caches first 128 labels <br/> 缓存从root节点发出的lebal值小于128的多个arc,这样就根据lebal查找arc,因为从root出发的是每次查找都必须用得到的,缓存的方式是将值作为下标。 */ @SuppressWarnings({ "unchecked" }) private void cacheRootArcs() throws IOException { // We should only be called once per FST: assert cachedArcsBytesUsed == 0; final Arc<T> arc = new Arc<>();// 模拟一个指向root的一个arc getFirstArc(arc);// 获得一个虚拟的指向root的arc if (targetHasArcs(arc)) {// 如果这个root有输出,如果root都没有输出,则没有任何东西了。所以一定是true final BytesReader in = getBytesReader();// 获得用来读取bytes的对象 Arc<T>[] arcs = (Arc<T>[]) new Arc[0x80];// 用来封装查询到的arc(不是全部查完,下面有说明)。这个arc类和builder时的arc类不一样,不是一个类 readFirstRealTargetArc(arc.target, arc, in);// 读取第一个arc int count = 0;// 一共缓存了多少个 while (true) { assert arc.label != END_LABEL; if (arc.label < arcs.length) {// 如果这个的lebal是小于128的,则缓存这个,写入到arcs中 arcs[arc.label] = new Arc<T>().copyFrom(arc); } else { break; } if (arc.isLast()) {// 是不是所在的节点的最后一个arc break; } readNextRealArc(arc, in); count++; } int cacheRAM = (int) ramBytesUsed(arcs); // Don't cache if there are only a few arcs or if the cache would // use > 20% RAM of the FST itself: if (count >= FIXED_ARRAY_NUM_ARCS_SHALLOW && cacheRAM < ramBytesUsed() / 5) { cachedRootArcs = arcs; cachedArcsBytesUsed = cacheRAM; } } } /** * 读取一个节点的第一个arc的信息 * @param node 节点(或者是位置或者是节点的编号) * @param arc 指向节点的arc * @param in 读取fst的对象 */ public Arc<T> readFirstRealTargetArc(long node, Arc<T> arc, final BytesReader in) throws IOException { final long address = getNodeAddress(node);// 节点的开始位置(如果是倒序的,就从后面开始的) in.setPosition(address);// 定位到要读取的节点的第一个byte arc.node = node; if (in.readByte() == ARCS_AS_FIXED_ARRAY) {// 这个节点的存储格式是fixedArray,先读取一些header,也就是addNode中写的那一部分header // this is first arc in a fixed-array arc.numArcs = in.readVInt();// 这个节点发出的arc的数量 if (packed || version >= VERSION_VINT_TARGET) { arc.bytesPerArc = in.readVInt(); } else { arc.bytesPerArc = in.readInt(); } arc.arcIdx = -1; arc.nextArc = arc.posArcsStart = in.getPosition(); } else {// 如果不是fixedArray的话,没有header,位置就是第一个arc(也就是nextArc)的开始位置 // arc.flags = b; arc.nextArc = address; arc.bytesPerArc = 0; } // 上面是定位第一个arc的开始,下面开始读了 return readNextRealArc(arc, in); } /** 读取一个arc <br/> Never returns null, but you should never call this if arc.isLast() is true. */ public Arc<T> readNextRealArc(Arc<T> arc, final BytesReader in) throws IOException { // TODO: can't assert this because we call from readFirstArc // assert !flag(arc.flags, BIT_LAST_ARC); // this is a continuing arc in a fixed array if (arc.bytesPerArc != 0) {// fixedArray的格式 // arcs are at fixed entries arc.arcIdx++;// 这个在设置第一个arc的时候是-1,所以第一个arc的话这里是0 assert arc.arcIdx < arc.numArcs; in.setPosition(arc.posArcsStart);// 采用的策略是先定位到这个节点的第一个arc的开始,然后下面再根据arc的下标定位到某一个arc的开始。 in.skipBytes(arc.arcIdx * arc.bytesPerArc);// 倒退指定的bytes,开始读取这个 } else {// 如果 // arcs are packed in.setPosition(arc.nextArc);// 定位到开始 } // flag和label是一定有的,其他的属性是否有要根据flag来判断。 arc.flags = in.readByte(); arc.label = readLabel(in); if (arc.flag(BIT_ARC_HAS_OUTPUT)) {// 是否有输出 arc.output = outputs.read(in); } else { arc.output = outputs.getNoOutput(); } if (arc.flag(BIT_ARC_HAS_FINAL_OUTPUT)) {// 有final输出 arc.nextFinalOutput = outputs.readFinalOutput(in); } else { arc.nextFinalOutput = outputs.getNoOutput(); } // 上面已经读取完了这个arc的属性,下面是读取这个arc的target node if (arc.flag(BIT_STOP_NODE)) {// 是指向最后一个节点,也就是这个arc是一个线路中的最后一个,也就是他已经构成一个线路了,不需要再读取下一个节点 if (arc.flag(BIT_FINAL_ARC)) {// 是final的 arc.target = FINAL_END_NODE; } else {// TODO 这个一直不懂,是什么鬼,已经指向最后一个node了为啥不是final的? arc.target = NON_FINAL_END_NODE; } arc.nextArc = in.getPosition(); } else if (arc.flag(BIT_TARGET_NEXT)) {// 该arc的目标节点就是fst中的下一个节点,此时不用存储target,两个的node是有联系的,可以计算出来 arc.nextArc = in.getPosition(); // TODO: would be nice to make this lazy -- maybe // caller doesn't need the target and is scanning arcs... if (nodeAddress == null) {// 不是null,不看 if (!arc.flag(BIT_LAST_ARC)) { if (arc.bytesPerArc == 0) { // must scan seekToNextNode(in); } else { in.setPosition(arc.posArcsStart); in.skipBytes(arc.bytesPerArc * arc.numArcs); } } arc.target = in.getPosition(); } else { arc.target = arc.node - 1;// nodeAddress不是null,说明arc.node是编号,又因为是BIT_TARGET_NEXT,说明是连续存储的,arc.node-1就是下一个节点的编号 assert arc.target > 0; } } else {// 需要单独的查找下一个节点 if (packed) {// 是压缩的fst final long pos = in.getPosition(); final long code = in.readVLong(); if (arc.flag(BIT_TARGET_DELTA)) {//记录的是差值的,用当前的位置+差值(到目前为止还没有出现过,但是后面会有,经过对FST的压缩之后就会有这个) // Address is delta-coded from current address: arc.target = pos + code; } else if (code < nodeRefToAddress.size()) {//记录的是编号,从另一个对象中获得这个编号的节点的开始位置。之前在写入的时候加上nodeRefToAddress.size()的目的就是这个。 // Deref arc.target = nodeRefToAddress.get((int) code); } else { // Absolute 记录的是绝对值 arc.target = code; } } else { // 读取下一个节点的编号 arc.target = readUnpackedNodeTarget(in); } arc.nextArc = in.getPosition(); } return arc; }
这样就缓存完了前128个arc。
这里又有一个新的Arc,这个和构建FST的时候 不是一个类,是另一个类的arc,代码如下:
/** 用于读FST时的arc <br/> Represents a single arc. */ public static final class Arc<T> { /** 这个arc的标记,也就是路径上的值 */ public int label; public T output; // From node (ord or address); currently only used when building an FST w/ willPackFST=true: /** 或者是fst中节点的编号,或者是fst中节点的开始位置,通过编号也可以获得位置 */ long node; /** 指向的node<br/> To node (ord or address) */ public long target; /** 这个arc的flag,标识他都是有哪些属性 */ byte flags; public T nextFinalOutput; // address (into the byte[]), or ord/address if label == END_LABEL /** 同一个节点的下一个arc的开始 */ long nextArc; /** * 在使用fixedArray的时候,第一个arc的开始 <br/> * Where the first arc in the array starts; only valid if bytesPerArc != * 0 */ public long posArcsStart; /** * 如果不是0 表示使用fixedBytes的格式,一个arc使用的byte的数量;是0表示不是fixedBytes的格式 <br/> * Non-zero if this arc is part of an array, which means all arcs for * the node are encoded with a fixed number of bytes so that we can * random access by index. We do when there are enough arcs leaving one * node. It wastes some bytes but gives faster lookups. */ public int bytesPerArc; /** * 当使用fixedArray的格式的时候使用 <br/> * Where we are in the array; only valid if bytesPerArc != 0. */ public int arcIdx; /** 发出这个arc的节点一共有多少个arc <br/> How many arcs in the array; only valid if bytesPerArc != 0. */ public int numArcs; /** Returns this 复制一个 */ public Arc<T> copyFrom(Arc<T> other) { node = other.node; label = other.label; target = other.target; flags = other.flags; output = other.output; nextFinalOutput = other.nextFinalOutput; nextArc = other.nextArc; bytesPerArc = other.bytesPerArc; if (bytesPerArc != 0) { posArcsStart = other.posArcsStart; arcIdx = other.arcIdx; numArcs = other.numArcs; } return this; } /** 这个arc的flag是否有指定的属性 */ boolean flag(int flag) { return FST.flag(flags, flag); } };
经过这样就完成了所有的term的添加,形成了一个fst,最终存储在一个叫做BytesStore的对象中,不过在存储的时候是倒叙的,如果要读,必须要从后向前读,代码如下
/** 获得一个读取byteStore的对象 <br/> Returns a {@link BytesReader} for this FST, positioned at position 0. */ public BytesReader getBytesReader() { if (packed) {// 如果是经过压缩的,则是正向的,否则是反向的 if (bytesArray != null) { return new ForwardBytesReader(bytesArray); } else { return bytes.getForwardReader(); } } else { if (bytesArray != null) {// 建立的时候不用,读的时候,如果fst不是很大才会用 return new ReverseBytesReader(bytesArray); } else { return bytes.getReverseReader(); } } }
现在还没有说过压缩fst,所以都是进入的return new ReverseBytesReader(bytesArray);也就是生成一个倒叙读的reader。下一篇博客将介绍如何对FST做压缩。
如果读者发现我写的有问题,请联系我的QQ:1308567317
下一篇: 笑喷,二货搞的笑就是这么强大!