import cc.mallet.fst.Transducer.TransitionIterator; //导入依赖的package包/类
private WeightCache getCache(int position) {
		WeightCache cache = caches[position];
		if (cache == null) {            // No cache for this position
//			System.out.println("cache " + numCaches + "/" + maxCaches);
			if (numCaches < maxCaches)  { // Create another cache
				cache = new WeightCache(position);
				if (numCaches++ == 0)
					first = last = cache;
			}
			else {                        // Steal least used cache
				cache = last;
				caches[cache.position] = null;
				cache.init(position);
			}
			for (int i = 0; i < t.numStates(); i++) {
				if (lattice[position][i] == null || lattice[position][i].delta == Transducer.IMPOSSIBLE_WEIGHT)
					continue;
				State s = t.getState(i);
				TransitionIterator iter =
					s.transitionIterator (input, position, providedOutput, position);
				while (iter.hasNext()) {
					State d = iter.next();
					cache.weight[i][d.getIndex()] = iter.getWeight();
				}
			}        
			caches[position] = cache;
		}
		if (cache != first) {           // Move to front
			if (cache == last)
				last = cache.prev;
			if (cache.prev != null)
				cache.prev.next = cache.next;
			cache.next = first;
			cache.prev = null;
			first.prev = cache;
			first = cache;
		}
		return cache;
	}
 

import cc.mallet.fst.Transducer.TransitionIterator; //导入依赖的package包/类
/** Increment states and transitions with a count of 1.0 along the best state sequence.
 *  This provides for a so-called "Viterbi training" approximation. */
public void incrementTransducer (Transducer.Incrementor incrementor)
{
	// We are only going to increment along the single best path ".get(0)" below.
	// We could consider having a version of this method:
	// incrementTransducer(Transducer.Incrementor incrementor, double[] counts)
	// where the number of n-best paths to increment would be determined by counts.length
	SequencePairAlignment<Object,ViterbiNode> viterbiNodeAlignment = this.bestViterbiNodeSequences(1).get(0);
	int sequenceLength = viterbiNodeAlignment.output().size();
	assert (sequenceLength == viterbiNodeAlignment.input().size()); // Not sure this works for unequal input/output lengths
	// Increment the initial state
	incrementor.incrementInitialState(viterbiNodeAlignment.output().get(0).state, 1.0);
	// Increment the final state
	incrementor.incrementFinalState(viterbiNodeAlignment.output().get(sequenceLength-1).state, 1.0);
	for (int ip = 0; ip < viterbiNodeAlignment.input().size()-1; ip++) {
		TransitionIterator iter =
			viterbiNodeAlignment.output().get(ip).state.transitionIterator (input, ip, providedOutput, ip);
		// xxx This assumes that a transition is completely
		// identified, and made unique by its destination state and
		// output.  This may not be true!
		int numIncrements = 0;
		while (iter.hasNext()) {
			if (iter.next().equals (viterbiNodeAlignment.output().get(ip+1).state)
					&& iter.getOutput().equals (viterbiNodeAlignment.output().get(ip).output)) {
				incrementor.incrementTransition(iter, 1.0);
				numIncrements++;
			}
		}
		if (numIncrements > 1)
			throw new IllegalStateException ("More than one satisfying transition found.");
		if (numIncrements == 0)
			throw new IllegalStateException ("No satisfying transition found.");
	}
}
 

import cc.mallet.fst.Transducer.TransitionIterator; //导入依赖的package包/类
/** Initiate Viterbi decoding of the inputSequence, contrained to match non-null parts of the outputSequence.
 * maxCaches indicates how much state information to memoize in n-best decoding. */
public MaxLatticeDefault (Transducer t, Sequence inputSequence, Sequence outputSequence, int maxCaches) 
{
	// This method initializes the forward path, but does not yet do the backward pass.
	this.t = t;
	if (maxCaches < 1)
		maxCaches = 1;
	this.maxCaches = maxCaches;
	assert (inputSequence != null);
	if (logger.isLoggable (Level.FINE)) {
		logger.fine ("Starting ViterbiLattice");
		logger.fine ("Input: ");
		for (int ip = 0; ip < inputSequence.size(); ip++)
			logger.fine (" " + inputSequence.get(ip));
		logger.fine ("\nOutput: ");
		if (outputSequence == null)
			logger.fine ("null");
		else
			for (int op = 0; op < outputSequence.size(); op++)
				logger.fine (" " + outputSequence.get(op));
		logger.fine ("\n");
	}

	this.input = inputSequence;
	this.providedOutput = outputSequence;
	latticeLength = input.size()+1;
	int numStates = t.numStates();
	lattice = new ViterbiNode[latticeLength][numStates];
	caches = new WeightCache[latticeLength-1];

	// Viterbi Forward
	logger.fine ("Starting Viterbi");
	boolean anyInitialState = false;
	for (int i = 0; i < numStates; i++) {
		double initialWeight = t.getState(i).getInitialWeight();
		if (initialWeight > Transducer.IMPOSSIBLE_WEIGHT) {
			ViterbiNode n = getViterbiNode (0, i);
			n.delta = initialWeight;
			anyInitialState = true;
		}
	}

	if (!anyInitialState) {
		logger.warning ("Viterbi: No initial states!");
	}

	for (int ip = 0; ip < latticeLength-1; ip++)
		for (int i = 0; i < numStates; i++) {
			if (lattice[ip][i] == null || lattice[ip][i].delta == Transducer.IMPOSSIBLE_WEIGHT)
				continue;
			State s = t.getState(i);
			TransitionIterator iter = s.transitionIterator (input, ip, providedOutput, ip);
			if (logger.isLoggable (Level.FINE))
				logger.fine (" Starting Viterbi transition iteration from state "
						+ s.getName() + " on input " + input.get(ip));
			while (iter.hasNext()) {
				State destination = iter.next();
				if (logger.isLoggable (Level.FINE))
					logger.fine ("Viterbi[inputPos="+ip
							+"][source="+s.getName()
							+"][dest="+destination.getName()+"]");
				ViterbiNode destinationNode = getViterbiNode (ip+1, destination.getIndex());
				destinationNode.output = iter.getOutput();
				double weight = lattice[ip][i].delta + iter.getWeight();
				if (ip == latticeLength-2) {
					weight += destination.getFinalWeight();
				}
				if (weight > destinationNode.delta) {
					if (logger.isLoggable (Level.FINE))
						logger.fine ("Viterbi[inputPos="+ip
								+"][source][dest="+destination.getName()
								+"] weight increased to "+weight+" by source="+
								s.getName());
					destinationNode.delta = weight;
					destinationNode.maxWeightPredecessor = lattice[ip][i];
				}
			}
		}
}