transducer.java

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

						// we could save a list of the non-null ones
						continue;
					nodes[ip][i].sortPredecessor();
				}


			//sort finalNodePredecessor
			int[] predecessorIndex = new int[numStates];
			predecessorIndex[0] = 0;
			for(int i=1; i<numStates; i++){
				boolean atEnd = true;
				for(int j=0; j<i; j++){
					if(nodes[latticeLength-1][i].delta < nodes[latticeLength-1][predecessorIndex[j]].delta){
						for(int k=i-1; k>=j; k--){
							predecessorIndex[k+1] = predecessorIndex[k];
						}
						predecessorIndex[j] = i;
						atEnd = false;
						break;
					}
				}

				if(atEnd) predecessorIndex[i] = i;
			}
			for(int i=0; i<numStates; i++){
				if(nodes[latticeLength-1][predecessorIndex[i]] != null)
					finalNodePredecessor[i] = nodes[latticeLength-1][predecessorIndex[i]];
				else
					throw new IllegalArgumentException("null node");
			}


			// Find the final state with minimum cost, and get the total
			// cost of the Viterbi path.
			ViterbiNode_NBest 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_NBest[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
//						 + " state: " + minCostNode.state.getName()
//						 + " delta: " + minCostNode.delta);

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

		}

		protected Sequence[] NBestBackwardASearch(int N)
		{

			NBestStack stack = new NBestStack();

			ASearchNode_NBest startNode = new ASearchNode_NBest(latticeLength, null);// null terminal node
			startNode.predecessorNodes = finalNodePredecessor;
			for(int i=0; i<numStates; i++){// i here is the rank
				if(finalNodePredecessor[i] == null){
					throw new IllegalArgumentException(i + ": null node");
				}

				startNode.totalCost[i] = finalNodePredecessor[i].delta + 0;//the cost for the last state to terminal node is zero
			}

			startNode.backwardCost = 0;
			startNode.nextBestStateIndex = 0;
			startNode.succeedNode = null;
			startNode.output = null;

			stack.push(startNode);// initialize the stack

			int nFound = 0;
			ArrayList hypothesisList = new ArrayList();
			ArrayList costList = new ArrayList();

//			System.out.println(startNode.totalCost[0]);
			// search iteratively for the N best hypothesis
			while(!stack.empty()){
				ASearchNode_NBest node_current = (ASearchNode_NBest) stack.pop();

//				if(node_current.inputPosition < latticeLength )
//				System.out.println("current_node: " + node_current.inputPosition
//					+ " : " + latticeLength + " "
//					+ node_current.totalCost[node_current.nextBestStateIndex]
//					+ " nextState= " + node_current.nextBestStateIndex
//					+ " state= " + node_current.state.getName()
//					+ " delta= " + nodes[node_current.inputPosition][node_current.state.getIndex()].delta
//					+ " nFound= " + nFound
//					);


				//update current node and push it back to the stack
				int nextStateIndex =  node_current.nextBestStateIndex;
				node_current.nextBestStateIndex ++;
				if ( node_current.nextBestStateIndex  < numStates ){
					stack.push(node_current);
				}

				//create a new node
				State s = node_current.predecessorNodes[nextStateIndex].state;
				ASearchNode_NBest node_next = new ASearchNode_NBest(node_current.inputPosition-1, s);
				node_next.output = nodes[node_next.inputPosition][s.getIndex()].output;
//				System.out.println( nextStateIndex + ":" + node_next.inputPosition +  ": " + s.getName() + ": " + node_next.output);

				// if s is a goal state, i.e., reaching the beginining of the sequence
				if(node_next.inputPosition == 1){
					//obtain the hypothesis by backtracking through the stored pointers

					Object[] outputArray = new Object[input.size()];
					outputArray[0] = node_next.output;
					ASearchNode_NBest v = node_current;
					int i=1;
					while(v.succeedNode != null){
						assert(i < input.size());
						outputArray[i++] = v.output;
//						System.out.println(v.state.getName());
						v = v.succeedNode;
					}

					Sequence hypo_current = new ArraySequence (outputArray, false);

					//store the new hypothesis
					hypothesisList.add(hypo_current);
					costList.add(new Double(node_current.totalCost[nextStateIndex] ));

					nFound ++;

					if(nFound >= N) break;
				}
				else{// expand new successor node
					node_next.predecessorNodes = nodes[node_next.inputPosition][s.getIndex()].minCostPredecessor;

					if(node_next.inputPosition < latticeLength-1 ){//the last symbol of the sequence
						int current_state_index = node_current.state.getIndex();
						int next_state_index    = node_next.state.getIndex();
						node_next.backwardCost = node_current.backwardCost +
							nodes[node_current.inputPosition][current_state_index].iterCost[next_state_index];
					}
					else{
						// the final node has a default cost
						node_next.backwardCost = node_next.state.getFinalCost();
					}

					ViterbiNode_NBest tempNode = nodes[node_next.inputPosition][s.getIndex()];
					for(int k=0; k<numStates; k++){
						node_next.totalCost[k] = tempNode.rankedPhi(k);
						// since rankedPhi[latticeLength-1] already contains a default final cost
						// as added in forward viterbi, there is no need to add the final cost again here.
						if(node_next.inputPosition < latticeLength-1){
							node_next.totalCost[k] +=  node_next.backwardCost;
						}
					}

					node_next.nextBestStateIndex = 0;
					node_next.succeedNode = node_current;

//					System.out.println(s.getName() + ": " + tempNode.rankedPhi(0) + " + "
//							+ " " + node_next.backwardCost
//							+ " = " + node_next.totalCost[0]);

//					if(Math.abs(node_next.totalCost[node_next.nextBestStateIndex]-this.cost) < 1)//constraint n-best
					stack.push(node_next);
				}

			}

			// store the n-best list and the costS
                        Sequence[] sequenceList = new Sequence[hypothesisList.size()];
                        costNBest = new double[hypothesisList.size()];
			for(int i=0; i<hypothesisList.size(); i++){
				sequenceList[i] = (Sequence) hypothesisList.get(i);
				costNBest[i] = ((Double)costList.get(i)).doubleValue();

//				System.out.println(i + ": " + sequenceList[i].size() + "/" + input.size() + " : " + costNBest[i]);
//				for(int j=0; j<sequenceList[i].size(); j++){
//					System.out.print(sequenceList[i].get(j) + " ");
//				}
//				System.out.println();

			}

			return sequenceList;
		}

		private class NBestStack
		{
			ArrayList list = new ArrayList();
			NBestStack()
			{
			}

			int size()
			{
				return list.size();
			}

			boolean empty()
			{
				return list.isEmpty();
			}

			Object pop()
			{
				return list.remove(0);
			}
			ArrayList push(ASearchNode_NBest o)
			{
				double f = o.totalCost[o.nextBestStateIndex];
				boolean atEnd = true;
				for(int i=0; i<list.size(); i++){
					ASearchNode_NBest tempNode = (ASearchNode_NBest)list.get(i);
					double f1 = tempNode.totalCost[tempNode.nextBestStateIndex];
					if(f < f1) {
						list.add(i, o);
						atEnd = false;
						break;
					}
				}

				if(atEnd) list.add(o);

				return list;
			}
		}

		// combine results and produce one final result
		protected void combineNBest()
		{

			Alphabet targets = inputPipe.getTargetAlphabet();
        	        assert(targets != null);

			if(numStates == 0) numStates = numStates();

			double[][] node_weight = new double[input.size()][numStates];

			double totalWeight = 0;
			for(int i=0; i<outputNBest.length; i++){
				double weight = Math.exp(-(costNBest[i]-costNBest[0])); //soft weighting
//				double weight = 1; // hard weighting

				for(int j=0; j<input.size(); j++){
					Object obj = outputNBest[i].get(j);
					int index = targets.lookupIndex(obj);

					node_weight[j][index] += weight;
				}
			}

			Object[] outputArray = new Object[input.size()];

			for(int j=0; j<input.size(); j++){
				int index = 0;
				for(int k=1; k<numStates; k++){
					if(node_weight[j][k] > node_weight[j][index]){
						index = k;
					}
				}
				outputArray[j] = targets.lookupObject(index);
			}

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

		}

		private class ViterbiNode_NBest
		{
			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; // the highest likelihood of the partial path reaching this node
			double[] phi; // the cost of all partial path reaching this node
			double[] rankedPhi;
			ViterbiNode_NBest[] minCostPredecessor;//predecessor list ordered according to phi
			double[] iterCost; //store the transition cost from all source nodes
			ViterbiNode_NBest (int inputPosition, State state)
			{
				this.inputPosition = inputPosition;
				this.state = state;

				phi = new double[numStates];
				rankedPhi = new double[numStates];
				minCostPredecessor = new ViterbiNode_NBest[numStates];
				iterCost = new double[numStates];
				for(int i=0; i<numStates; i++){
					phi[i] = INFINITE_COST;
					minCostPredecessor[i] = null;
					iterCost[i] = INFINITE_COST;
				}
			}

			// return the cost ranking at k
			double rankedPhi(int k)
			{
//				int index = minCostPredecessor[k].state.getIndex();
//				return phi[index];
				return rankedPhi[k];
			}

			//sort acendingly according to phi
			void sortPredecessor()
			{
				if(inputPosition == 0){
					return;
				}

				int[] predecessorIndex = new int[numStates];
				predecessorIndex[0] = 0;
				for(int i=1; i<numStates; i++){

					boolean atEnd = true;
					for(int j=0; j<i; j++){
						if( phi[i]< phi[predecessorIndex[j]]){
							for(int k=i-1; k>=j; k--){
								predecessorIndex[k+1] = predecessorIndex[k];
							}
							predecessorIndex[j] = i;
							atEnd = false;
							break;
						}
					}

					if(atEnd) predecessorIndex[i] = i;
				}


				assert(inputPos