FST源代码解读4——结束添加

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