欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

相关标签: FST lucene