transducer.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

				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;
			// this.output is set at the end when we know the exact outputs
			// of the Viterbi path.  Note that in some cases the "output"
			// may be provided non-null as an argument to this method, but the
			// "output" objects may not be fully-specified even though they do
			// provide some restrictions.  This is why we set our this.output
			// from the outputs provided by the transition iterator along the
			// Viterbi path.

			// xxx Not very efficient when the lattice is actually sparse,
			// especially when the number of states is large and the
			// sequence is long.
			latticeLength = input.size()+1;
			int numStates = numStates();
			ViterbiNode[][] nodes = new ViterbiNode[latticeLength][numStates];

			// Viterbi Forward
			logger.fine ("Starting Viterbi");
			for (int i = 0; i < numStates; i++) {
				double initialCost = getState(i).initialCost;
				if (initialCost < INFINITE_COST) {
					ViterbiNode n = getViterbiNode (nodes, 0, i);
					n.delta = initialCost;
				}
			}
			for (int ip = 0; ip < latticeLength-1; ip++)
				for (int i = 0; i < numStates; i++) {
					if (nodes[ip][i] == null || nodes[ip][i].delta == INFINITE_COST)
						// xxx if we end up doing this a lot,
						// we could save a list of the non-null ones
						continue;
					State s = 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.nextState();
						if (logger.isLoggable (Level.FINE))
							logger.fine ("Viterbi[inputPos="+ip
													 +"][source="+s.getName()
													 +"][dest="+destination.getName()+"]");
						ViterbiNode destinationNode = getViterbiNode (nodes, ip+1,
																													destination.getIndex());
						destinationNode.output = iter.getOutput();
						cost = nodes[ip][i].delta + iter.getCost();

//						System.out.println("cost = " + iter.getCost() + " (" + ip + " " + i +")");

						if (ip == latticeLength-2){// why there is multiple next states at the end of sequence????
							cost += destination.getFinalCost();

//							System.out.println("number of next states: " + iter.numberNext());
						}

						if (cost < destinationNode.delta) {
							if (logger.isLoggable (Level.FINE))
								logger.fine ("Viterbi[inputPos="+ip
														 +"][source][dest="+destination.getName()
														 +"] cost reduced to "+cost+" by source="+
														 s.getName());
							destinationNode.delta = cost;
							destinationNode.minCostPredecessor = nodes[ip][i];
						}
					}
				}

			// Find the final state with minimum cost, and get the total
			// cost of the Viterbi path.
			ViterbiNode minCostNode;
			int ip = latticeLength-1;
			this.cost = INFINITE_COST;
			minCostNode = null;
			for (int i = 0; i < numStates; i++) {
				if (nodes[ip][i] == null)
					continue;
				if (nodes[ip][i].delta < this.cost) {
					minCostNode = nodes[ip][i];
					this.cost = minCostNode.delta;

//					System.out.println("this.cost = " + this.cost);
				}
			}

			// Build the path and the output sequence.
			this.nodePath = new ViterbiNode[latticeLength];
			Object[] outputArray = new Object[input.size()];
			for (ip = latticeLength-1; ip >= 0; ip--) {
				this.nodePath[ip] = minCostNode;
				if (ip > 0){
					outputArray[ip-1] = minCostNode.output;
//					System.out.println(ip + ":" + outputArray[ip-1]);
				}


//				System.out.println(ip + ": " + latticeLength);
//				System.out.println("posit: " + minCostNode.inputPosition);
//				System.out.println("state: " + minCostNode.state.getName());
//				System.out.println("delta: " + minCostNode.delta);

				minCostNode = minCostNode.minCostPredecessor;
			}
			this.output = new ArraySequence (outputArray, false);
		}

		// xxx Delete this method and move it into the Viterbi constructor, just like Lattice.
		// Increment states and transitions in the tranducer with the
		// expectations from this path.  This provides for the so-called
		// "Viterbi training" approximation.
		public void incrementTransducerCounts ()
		{
			nodePath[0].state.incrementInitialCount (1.0);
			nodePath[nodePath.length-1].state.incrementFinalCount (1.0);
			for (int ip = 0; ip < nodePath.length-1; ip++) {
				TransitionIterator iter =
					nodePath[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.nextState().equals (nodePath[ip+1].state)
							&& iter.getOutput().equals (nodePath[ip].output)) {
						iter.incrementCount (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.");
			}
		}

		public SequencePairAlignment trimStateInfo ()
		{
			return new SequencePairAlignment (input, output, cost);
		}

		public double tokenAccuracy (Sequence referenceOutput)
		{
			int accuracy = 0;
			assert (referenceOutput.size() == output.size());
			for (int i = 0; i < output.size(); i++) {
				//logger.fine("tokenAccuracy: ref: "+referenceOutput.get(i)+" viterbi: "+output.get(i));
				if (referenceOutput.get(i).toString().equals (output.get(i).toString())) {
					accuracy++;
				}
			}
			logger.info ("Number correct: " + accuracy + " out of " + output.size());
			return ((double)accuracy)/output.size();
		}

		public double tokenAccuracy (Sequence referenceOutput, PrintWriter out)
		{
			int accuracy = 0;
			String testString;
			assert (referenceOutput.size() == output.size());
			for (int i = 0; i < output.size(); i++) {
				//logger.fine("tokenAccuracy: ref: "+referenceOutput.get(i)+" viterbi: "+output.get(i));
				testString = output.get(i).toString();
				if (out != null) {
					out.println(testString);
				}
				if (referenceOutput.get(i).toString().equals (testString)) {
					accuracy++;
				}
			}
			logger.info ("Number correct: " + accuracy + " out of " + output.size());
			return ((double)accuracy)/output.size();
		}


		private class ViterbiNode
		{
			int inputPosition;								// Position of input used to enter this node
			State state;											// Transducer state from which this node entered
			Object output;										// Transducer output produced on entering this node
			double delta = INFINITE_COST;
			ViterbiNode minCostPredecessor = null;
			ViterbiNode (int inputPosition, State state)
			{
				this.inputPosition = inputPosition;
				this.state = state;
			}
		}

	} // end of ViterbiPath


	//
	// Fuchun Peng [e-mail]
	//
	//
	// return top N best list,
	// N best list generation involves a forward Viterbi decoding
	// and N passes of A* backward search
	//
	// sample research using N-best algorithms include speech regonition, disambiguation, and handwriting recognition.
	// 1: N-Best Search Methods Applied to Speech Recognition,  Diploma Thesis,
	//  Department of Telecommunications, Norwegian Institut of Technology, 1994
	// 2: N-Best Hidden Markov Model Supertagging for Tying with Ambiguous Keywords, Sasa Hansan, 2003
	// 3: SCHWARTZ,RICHARD,&YEN-LU CHOW. 1990.
	// The N-best algorithm: An efficient and exact procedure for finding the n most likely sentence hypotheses. ICASSP 1990
	// 4: Online handwriting reognition with Constraint N-best  decoding Jianying Hu, Michael Brown
	public class ViterbiPath_NBest extends SequencePairAlignment
	{
		// double cost inherited from SequencePairAlignment
		// Sequence input, output inherited from SequencePairAlignment
		// this.output stores the actual output of Viterbi transitions
		Sequence providedOutput;
		ViterbiNode_NBest[] nodePath;
		int latticeLength;
		int numStates;

		ViterbiNode_NBest[][] nodes;
		ViterbiNode_NBest[] finalNodePredecessor;


		protected ViterbiNode_NBest getViterbiNode (ViterbiNode_NBest[][] nodes, int ip, int stateIndex)
		{
			if (nodes[ip][stateIndex] == null)
				nodes[ip][stateIndex] = new ViterbiNode_NBest (ip, getState (stateIndex));

			if(nodes[ip][stateIndex] == null){
				throw new IllegalArgumentException("WARNING: nodes["+ip+"]["+stateIndex+"] is not successfully generated." );
			}

			return nodes[ip][stateIndex];
		}

		protected ViterbiPath_NBest (Sequence inputSequence, Sequence outputSequence, int N)
		{

			this.input = inputSequence;
			this.providedOutput = outputSequence;
			this.latticeLength = input.size()+1;
			this.numStates = numStates();

			//forward Viterbi
			nodes = new ViterbiNode_NBest[latticeLength][numStates];
			finalNodePredecessor = new ViterbiNode_NBest[numStates];// list of predecessors ranked according to final cost
			NBestForwardViterbi(nodes, finalNodePredecessor, N);

			//backward A* search
			outputNBest = NBestBackwardASearch(N);

			//combine the N best results, and produce a final output
			combineNBest();
		}


		protected void NBestForwardViterbi(ViterbiNode_NBest[][] nodes,
			ViterbiNode_NBest[] finalNodePredecessor,
			int N)
		{
			assert (input != null);
			if (logger.isLoggable (Level.FINE)) {
				logger.fine ("Starting ViterbiPath");
				logger.fine ("Input: ");
				for (int ip = 0; ip < input.size(); ip++)
					logger.fine (" " + input.get(ip));
				logger.fine ("\nOutput: ");
				if (providedOutput == null)
					logger.fine ("null");
				else
					for (int op = 0; op < providedOutput.size(); op++)
						logger.fine (" " + providedOutput.get(op));
				logger.fine ("\n");
			}

			// this.output is set at the end when we know the exact outputs
			// of the Viterbi path.  Note that in some cases the "output"
			// may be provided non-null as an argument to this method, but the
			// "output" objects may not be fully-specified even though they do
			// provide some restrictions.  This is why we set our this.output
			// from the outputs provided by the transition iterator along the
			// Viterbi path.

			// Viterbi Forward
			logger.fine ("Starting Viterbi");
			for (int i = 0; i < numStates; i++) {// position 0 is a null starting node
				double initialCost = getState(i).initialCost;
				if (initialCost < INFINITE_COST) {
					ViterbiNode_NBest n = getViterbiNode (nodes, 0, i);
					n.delta = initialCost;
				}
			}


			for (int ip = 0; ip < latticeLength-1; ip++)
				for (int i = 0; i < numStates; i++) {
					if (nodes[ip][i] == null || nodes[ip][i].delta == INFINITE_COST)
						// xxx if we end up doing this a lot,
						// we could save a list of the non-null ones
						continue;
					State s = 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.nextState();
						if (logger.isLoggable (Level.FINE))
							logger.fine ("Viterbi[inputPos="+ip
													 +"][source="+s.getName()
													 +"][dest="+destination.getName()+"]");
						ViterbiNode_NBest destinationNode = getViterbiNode (nodes, ip+1,
																													destination.getIndex());
						destinationNode.output = iter.getOutput();
//						System.out.println(ip + ":" + destinationNode.state.getIndex() + " : " + iter.getOutput());
						cost = nodes[ip][i].delta + iter.getCost();
						destinationNode.iterCost[i] = iter.getCost();

//						System.out.println("cost = " + iter.getCost() + " (" + ip + " " + i +")");

						if (ip == latticeLength-2){// why there is multiple next states at the end of sequence????
							cost += destination.getFinalCost();
						}


						if (cost < destinationNode.delta) {
							if (logger.isLoggable (Level.FINE))
								logger.fine ("Viterbi[inputPos="+ip
														 +"][source][dest="+destination.getName()
														 +"] cost reduced to "+cost+" by source="+
														 s.getName());
							destinationNode.delta = cost;
						}

						destinationNode.phi[i] = cost;
					}
				}

			// sorting predecessors according to phi
			for (int ip = latticeLength - 1; ip > 0; ip--)
				for (int i = 0; i < numStates; i++) {
					if (nodes[ip][i] == null || nodes[ip][i].delta == INFINITE_COST)
						// xxx if we end up doing this a lot,