latticereduce.cc

这是一款很好用的工具包

    LatticeNode * nodeI = findNode(nodeIndexI); 
    LatticeNode * nodeJ = findNode(nodeIndexJ); 

    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxMatchInTrans: "
	     << "      i.e., (" << getWord(nodeI->word)
	     << ", " << getWord(nodeJ->word) << ")\n";
    }

    unsigned numInTransI = nodeI->inTransitions.numEntries();
    unsigned numInTransJ = nodeJ->inTransitions.numEntries();
    unsigned minIJ = ( numInTransI > numInTransJ ) ? 
      numInTransJ : numInTransI;

    if (overlap > (int)minIJ) return false;

    int nonOverlap = minIJ-overlap; 

    NodeIndex toNodeIndex, fromNodeIndex;

    if (debug(DebugPrintInnerLoop)) {
      dout() << "Lattice::approxMatchInTrans: "
	     << "number of transitions (" 
	     << numInTransI << ", " << numInTransJ << ")\n";
    }

    // **********************************************************************
    // preventing self loop generation
    // **********************************************************************

    if (nodeI->inTransitions.find(nodeIndexJ)) {
      if (debug(DebugPrintInnerLoop)) {
	dout() << "Lattice::approxMatchInTrans: "
	       << " preventing potential selfloop (" << nodeIndexJ
	       << ", " << nodeIndexI << ")\n";
      }
      return false;
    }

    if (nodeI->outTransitions.find(nodeIndexJ)) {
      if (debug(DebugPrintInnerLoop)) {
	dout() << "Lattice::approxMatchInTrans: "
	       << " preventing potential selfloop (" << nodeIndexI
	       << ", " << nodeIndexJ << ")\n";
      }
      return false;
    }


    // **********************************************************************
    // compare the sink nodes of the incoming edges of the two given
    // nodes.
    // **********************************************************************

    // loop over J
    TRANSITER_T<NodeIndex,LatticeTransition> 
      inTransIterJ(nodeJ->inTransitions);
    while (inTransIterJ.next(fromNodeIndex)) {
      
      if (debug(DebugPrintInnerLoop)) {
	dout() << "Lattice::approxMatchInTrans: "
	       << "loop (" << fromNodeIndex << ")\n";
      }

      LatticeTransition * transI = nodeI->inTransitions.find(fromNodeIndex);
      if (!transI) {
	// one mismatch occurs;
	if (--nonOverlap < 0) { 
	  return false; }
      } else {
	if (--overlap == 0) { 
	  // already exceed minimum overlap required.
	  break;
	}
      }
    }

    // **********************************************************************
    // I and J are qualified for merging.
    // **********************************************************************

    // merging incoming node sets.
    inTransIterJ.init(); 
    while (LatticeTransition *trans = inTransIterJ.next(fromNodeIndex)) {
      insertTrans(fromNodeIndex, nodeIndexI, *trans);
    }

    // merging outgoing nodes
    TRANSITER_T<NodeIndex,LatticeTransition> 
      outTransIterJ(nodeJ->outTransitions);
    while (LatticeTransition *trans = outTransIterJ.next(toNodeIndex)) {
      insertTrans(nodeIndexI, toNodeIndex, *trans);
    }
    
    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxMatchInTrans: "
	     << "(" << nodeIndexJ << ") has been merged with "
	     << "(" << nodeIndexI << ") and has been removed\n";
    }

    // delete this redudant node.
    removeNode(nodeIndexJ); 
    
    return true;
}

/* ********************************************************
   this procedure is to pack two nodes if their OutNode sets 
   overlap beyong certain threshold
   
   input: 
   1) nodeIndex: the node to be processed;
   2) nodeQueue: the current queue.
   3) base: overlap base
   4) ratio: overlap ratio

   function:
       going through all the in-nodes of nodeIndex, and tries to merge
       as many as possible.
   ******************************************************** */
Boolean 
Lattice::approxRedNodeF(NodeIndex nodeIndex, NodeQueue &nodeQueue, 
			int base, double ratio)
{

    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxRedNodeF: "
	     << "processing (" << nodeIndex << ") ***********\n"; 
    }

    NodeIndex fromNodeIndex, toNodeIndex; 
    LatticeNode * node = findNode(nodeIndex); 
    if (!node) { // skip through this node, being merged.
      return true; 
    }

    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxRedNodeF: "
	     << "      i.e., (" << getWord(node->word) << ")\n";
    }

    // going in a forward direction
    TRANSITER_T<NodeIndex,LatticeTransition> 
      outTransIter(node->outTransitions);
    unsigned numTransitions = node->outTransitions.numEntries();
    makeArray(NodeIndex, list, numTransitions+1); 
    unsigned position = 0; 
    
    // collect all the out-nodes of nodeIndex
    while (outTransIter.next(toNodeIndex)) {
      list[position++] = toNodeIndex; 
    }

    // do a pair-wise comparison for all the out-nodes.
    unsigned i, j; 
    for (i = 0; i< position; i++) {
        j = i+1; 

	if (j >= position) { 
	  break; }

	LatticeNode * nodeI = findNode(list[i]);

	// ***********************************
	// compare nodeI with nodeJ:
	//    Notice that numInTransI changes because
	//    merger occurs in the loop. this is different
	//    from exact match case.   
	// ***********************************
	unsigned merged = 0; 
	while (j < position) {
	  if (debug(DebugPrintInnerLoop)) {
	    dout() << "Lattice::approxRedNodeF: "
		   << "comparing (" << list[i] << ", "
		   << list[j] << ")\n"; 
	  }

          LatticeNode * nodeI = findNode(list[i]);
	  unsigned numInTransI = nodeI->inTransitions.numEntries();

	  LatticeNode * nodeJ = findNode(list[j]);
	  unsigned numInTransJ = nodeJ->inTransitions.numEntries();
	  
	  if (nodeI->word == nodeJ->word) {
	    unsigned overlap; 
	    if ((!base && (numInTransI < numInTransJ)) ||
		(base && (numInTransI > numInTransJ))) {
	      overlap = (unsigned ) floor(numInTransI*ratio + 0.5);
	    } else {
	      overlap = (unsigned ) floor(numInTransJ*ratio + 0.5);
	    }

	    overlap = (overlap > 0) ? overlap : 1;
	    if (approxMatchInTrans(list[i], list[j], overlap)) {
	      merged = 1; 
	      list[j] = list[--position];
	      continue;
	    } 
	  } 
	  j++; 
	}

	// clear marks on the inNodes, if nodeI matches some other nodes.
	if (merged) {
	  nodeI = findNode(list[i]);
	  TRANSITER_T<NodeIndex,LatticeTransition> 
	    inTransIter(nodeI->inTransitions);
	  while (inTransIter.next(fromNodeIndex)) {
	    LatticeNode * fromNode = findNode(fromNodeIndex); 
	    fromNode->unmarkNode(markedFlag); 
	  }
	}
    }

    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxRedNodeF: "
	     << "adding nodes ("; 
    }

    // **************************************************
    // preparing next level nodes for merging processing.
    // **************************************************
    node = findNode(nodeIndex); 
    TRANSITER_T<NodeIndex,LatticeTransition> 
      transIter(node->outTransitions);
    while (transIter.next(toNodeIndex)) {
      if (debug(DebugPrintInnerLoop)) {
	dout() << "Lattice::approxRedNodeF: "
	       << " " << toNodeIndex; 
      }
	  
      nodeQueue.addToNodeQueueNoSamePrev(toNodeIndex); 
      // nodeQueue.addToNodeQueue(toNodeIndex); 
    }

    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxRedNodeF: "
	     << ") to the queue\n"; 
    }

    // mark that the current node has been processed.
    node->markNode(markedFlag);
    
    return true;
}


/* ********************************************************
   this procedure tries to compare two nodes to see whether their
   outgoing node sets overlap more than x.
   ******************************************************** */

Boolean 
Lattice::approxMatchOutTrans(NodeIndex nodeIndexI, NodeIndex nodeIndexJ,
			     int overlap)
{
    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxMatchOutTrans: "
	     << "try to match (" << nodeIndexI
	     << ", " << nodeIndexJ << ") with overlap "
	     << overlap << "\n"; 
    }

    LatticeNode * nodeI = findNode(nodeIndexI); 
    LatticeNode * nodeJ = findNode(nodeIndexJ); 

    if (debug(DebugPrintOutLoop)) {
      dout() << "Lattice::approxMatchOutTrans: "
	     << "      i.e., (" << getWord(nodeI->word)
	     << ", " << getWord(nodeJ->word) << ")\n";
    }

    unsigned numOutTransI = nodeI->outTransitions.numEntries();
    unsigned numOutTransJ = nodeJ->outTransitions.numEntries();
    unsigned minIJ = ( numOutTransI > numOutTransJ ) ? 
      numOutTransJ : numOutTransI;

    if (overlap > (int)minIJ) return false;

    int nonOverlap = minIJ-overlap; 

    NodeIndex toNodeIndex, fromNodeIndex;

    if (debug(DebugPrintInnerLoop)) {
      dout() << "Lattice::approxMatchOutTrans: "
	     << "number of transitions (" 
	     << numOutTransI << ", " << numOutTransJ << ")\n";
    }

    // **********************************************************************
    // preventing self loop generation
    // **********************************************************************

    if (nodeI->inTransitions.find(nodeIndexJ)) {
      if (debug(DebugPrintInnerLoop)) {
        dout() << "Lattice::approxMatchInTrans: "
               << " preventing potential selfloop (" << nodeIndexJ
               << ", " << nodeIndexI << ")\n";
      }
      return false;
    }

    if (nodeI->outTransitions.find(nodeIndexJ)) {
      if (debug(DebugPrintInnerLoop)) {
        dout() << "Lattice::approxMatchInTrans: "
               << " preventing potential selfloop (" << nodeIndexI
               << ", " << nodeIndexJ << ")\n";
      }
      return false;
    }

    // **********************************************************************
    // compare the sink nodes of the outgoing edges of the two given
    // nodes.
    // **********************************************************************

    // loop over J
    TRANSITER_T<NodeIndex,LatticeTransition> 
      outTransIterJ(nodeJ->outTransitions);
    while (outTransIterJ.next(toNodeIndex)) {
      
      if (debug(DebugPrintInnerLoop)) {
	dout() << "Lattice::approxMatchOutTrans: "
	       << "loop (" << toNodeIndex << ")\n";
      }

      LatticeTransition * transI = nodeI->outTransitions.find(toNodeIndex);
      if (!transI) {
	// one mismatch occurs;
	if (--nonOverlap < 0) { 
	  return false; }
      } else {
	if (--overlap == 0) { 
	  // already exceed minimum overlap required.
	  break;
	}
      }
    }

    // **********************************************************************
    // I and J are qualified for merging.
    // **********************************************************************

    // merging outgoing node sets.
    outTransIterJ.init(); 
    while (LatticeTransition *trans = outTransIterJ.next(toNodeIndex)) {
      insertTrans(nodeIndexI, toNodeIndex, *trans);
    }