lattice.h

这是一款很好用的工具包

    LatticeNode *findNode(NodeIndex nodeIndex) {
        return nodes.find(nodeIndex); };
    void removeAll();		// remove all nodes
    unsigned removeUselessNodes();		

    Boolean insertTrans(NodeIndex fromNodeIndex, NodeIndex toNodeIndex, 
			const LatticeTransition &trans, Boolean maxAdd = false);
    LatticeTransition *findTrans(NodeIndex fromNodeIndex,
						    NodeIndex toNodeIndex);
    Boolean setWeightTrans(NodeIndex fromNodeIndex, 
			   NodeIndex toNodeIndex, LogP weight); 
    void markTrans(NodeIndex fromNodeIndex, NodeIndex toNodeIndex, 
		   unsigned flag);
    Boolean removeTrans(NodeIndex fromNodeIndex, NodeIndex toNodeIndex);

    void dumpFlags();
    void clearMarkOnAllNodes(unsigned flag = ~0); 
    void clearMarkOnAllTrans(unsigned flag = ~0);

    // topological sorting
    unsigned sortNodes(NodeIndex *sortedNodes, Boolean reversed = false); 
    
    // detect words ignored by lattice LM
    inline Boolean ignoreWord(VocabIndex word)
	{ return word == Vocab_None || ignoreVocab.getWord(word) != 0; };

    /* ********************************************************* 
       get protected class values
       ********************************************************* */
    NodeIndex getInitial() { return initial; }
    NodeIndex getFinal() { return final; }
    const char *getName() { return name; }
    NodeIndex getMaxIndex() { return maxIndex; }
    VocabString getWord(VocabIndex word);
    unsigned getNumNodes() { return nodes.numEntries(); }
    unsigned getNumTransitions();

    NodeIndex setInitial(NodeIndex index) { return (initial=index); }
    NodeIndex setFinal(NodeIndex index) { return (final=index); }

    /* ********************************************************* 
       diagnostic tools
       ********************************************************* */
    Boolean printNodeIndexNamePair(File &file); 
    Boolean areConnected(NodeIndex fromNodeIndex, NodeIndex toNodeIndex,
			 unsigned direction = 0); 
    unsigned latticeWER(const VocabIndex *words,
			unsigned &sub, unsigned &ins, unsigned &del)
        { return latticeWER(words, sub, ins, del, ignoreVocab); };
    unsigned latticeWER(const VocabIndex *words,
			unsigned &sub, unsigned &ins, unsigned &del,
			SubVocab &ignoreWords); 

    LogP2 computePosteriors(double posteriorScale = 1.0,
						Boolean normalize = false);
    Boolean writePosteriors(File &file, double posteriorScale = 1.0);
    Boolean prunePosteriors(Prob threshold, double posteriorScale = 1.0,
				double maxDensity = 0.0, unsigned maxNodes = 0,
				Boolean fast = false);

    LogP bestWords(VocabIndex *words, unsigned maxLength)
	{ return bestWords(words, maxLength, ignoreVocab); }
    LogP bestWords(VocabIndex *words, unsigned maxLength,
						    SubVocab &ignoreWords);
    LogP bestWords(NBestWordInfo *words, unsigned maxLength,
						    SubVocab &ignoreWords);
    Boolean computeNBest(unsigned N, NBestOptions &nbestOut,
					SubVocab &ignoreWords,
					const char *multiwordSeparator = 0,
					unsigned maxHyps = 0,
					unsigned nbestDuplicates = 0);
    Boolean computeNBestViterbi(unsigned N, NBestOptions &nbestOut,
					SubVocab &ignoreWords,
					const char *multiwordSeparator = 0);
    FloatCount countNgrams(unsigned order, NgramCounts<FloatCount> &counts,
						double posteriorScale = 1.0);

    double getDuration();
    double computeDensity(double duration = 0.0)
	{ unsigned numNodes; return computeDensity(numNodes, duration); }
    double computeDensity(unsigned &numNodes, double duration = 0.0);

    /* ********************************************************* 
       self-loop processing
       ********************************************************* */
    static void initASelfLoopDB(SelfLoopDB &selfLoopDB, LM &lm,
				NodeIndex nodeIndex, LatticeNode *node,
				LatticeTransition *trans);
    static void initBSelfLoopDB(SelfLoopDB &selfLoopDB, LM &lm, 
				NodeIndex fromNodeIndex, LatticeNode *fromNode,
				LatticeTransition *fromTrans);
    static void initCSelfLoopDB(SelfLoopDB &selfLoopDB, NodeIndex toNodeIndex,
				LatticeTransition *toTrans);

    Boolean expandSelfLoop(LM &lm, SelfLoopDB &selfLoopDB, 
				PackedNodeList &packedSelfLoopNodeList);

    /* ********************************************************* 
       internal data structure
       ********************************************************* */
    Vocab &vocab;		// vocabulary used for words
    LHash<NodeIndex,LatticeNode> nodes;	// node list; 

    SubVocab ignoreVocab;	// words to ignore in lattice operations

protected: 
    HTKHeader htkheader;	// HTK header information
    Array<HTKWordInfo *> htkinfos;
				// HTK link information (to avoid duplication
				// inside node structures)
    LHash<VocabIndex, Lattice *> subPFSGs;  // for processing subPFSGs

    NodeIndex maxIndex;		// the current largest node index plus one
				// (i.e., the next index we can allocate)
    const char *name;		// name string for lattice
    double duration;		// waveform duration

    NodeIndex initial;		// start node index
    NodeIndex final;		// final node index;

    Boolean top;                // an indicator for whether two null nodes 
				// (initial and final) have been converted
				// to <s> and </s>.

    Lattice *getNonRecPFSG(VocabIndex nodeVocab);
    Boolean recoverPause(NodeIndex nodeIndex, Boolean loop = true,
							Boolean all = false);
    Boolean recoverCompactPause(NodeIndex nodeIndex, Boolean loop = true,
							Boolean all = false); 

    void sortNodesRecursive(NodeIndex nodeIndex, unsigned &numVisited,
			    NodeIndex *sortedNodes, Boolean *visitedNodes);

    LogP2 computeForwardBackward(LogP2 forwardProbs[], LogP2 backwardProbs[],
							double posteriorScale);
    LogP computeForwardBackwardViterbi(LogP forwardProbs[],
							LogP backwardProbs[]);

    LogP computeViterbi(NodeIndex forwardPreds[], NodeIndex *backwardPreds = 0);

    FloatCount countNgramsAtNode(VocabIndex oldIndex, unsigned order,
		 NgramCounts<FloatCount> &counts,
		 LogP2 backwardProbs[], double posteriorScale,
		 Map2<NodeIndex, VocabContext, LogP2> &forwardProbMap);
    Boolean
      expandNodeToTrigram(NodeIndex nodeIndex, LM &lm, unsigned maxNodes = 0);

    Boolean
      expandNodeToCompactTrigram(NodeIndex nodeIndex, Ngram &ngram,
							unsigned maxNodes = 0);

    Boolean
      expandAddTransition(VocabIndex *usedContext, unsigned usedLength,
		  VocabIndex word, LogP wordProb, LM &lm,
		  NodeIndex oldIndex2, VocabIndex newIndex,
		  LatticeTransition *oldtrans, unsigned maxNodes,
		  Map2<NodeIndex, VocabContext, NodeIndex> &expandMap);

    Boolean
      expandNodeToLM(VocabIndex node, LM &ngram, unsigned maxNodes, 
			Map2<NodeIndex, VocabContext, NodeIndex> &expandMap);

    Boolean
      expandNodeToCompactLM(VocabIndex node, LM &ngram, unsigned maxNodes,
			Map2<NodeIndex, VocabContext, NodeIndex> &expandMap);

    void
      mergeNodes(NodeIndex nodeIndex1, NodeIndex nodeIndex2,
			LatticeNode *node1 = 0, LatticeNode *node2 = 0,
			Boolean maxAdd = false);

    Boolean 
      approxMatchInTrans(NodeIndex nodeIndexI, NodeIndex nodeIndexJ,
			 int overlap); 

    Boolean 
      approxMatchOutTrans(NodeIndex nodeIndexI, NodeIndex nodeIndexJ,
			  int overlap); 

    void
      packNodeF(NodeIndex nodeIndex, Boolean maxAdd = false);

    void
      packNodeB(NodeIndex nodeIndex, Boolean maxAdd = false);

    Boolean 
      approxRedNodeF(NodeIndex nodeIndex, NodeQueue &nodeQueue, 
		     int base, double ratio);

    Boolean 
      approxRedNodeB(NodeIndex nodeIndex, NodeQueue &nodeQueue, 
		     int base, double ratio);

    // helpers to alignLattice()
    NodeIndex findMaxPosteriorNode(LHash<NodeIndex,LogP2> &nodeSet, LogP2 &max);
    unsigned findFirstAligned(NodeIndex from, NodeIndex predecessors[],
				LHash<NodeIndex, unsigned> &nodeSet,
				NodeIndex pathNodes[]);
};

/*
 * Iterators to enumerate non-null successor nodes
 */
class LatticeFollowIter
{
public:
    LatticeFollowIter(Lattice &lat, LatticeNode &node,
		      LHash<NodeIndex, LogP> *useVisitedNodes = 0,
		      LogP totalWeight = LogP_One);
    ~LatticeFollowIter();

    void init();
    LatticeNode *next(NodeIndex &followIndex, LogP &weight);

private:
    Lattice &lat;
    TRANSITER_T<NodeIndex,LatticeTransition> transIter;
    LatticeFollowIter *subFollowIter;
    LogP startWeight;		// accumulated weight from start node
    LHash<NodeIndex, LogP> *visitedNodes;
    Boolean freeVisitedNodes;
};

class QueueItem: public Debug
{
  // for template class, we need to add;
  // friend class Queue<Type>; 

friend class NodeQueue; 
  
public:
    QueueItem(NodeIndex nodeIndex, unsigned clevel = 0, 
	      LogP cweight = 0.0); 
    
    NodeIndex QueueGetItem() { return item; }
    unsigned QueueGetLevel() { return level; }
    LogP QueueGetWeight() { return weight; }

private:
    NodeIndex item;
    unsigned level; 
    LogP weight; 
    QueueItem *next; 
};

class NodeQueue: public Debug
{
public:
    NodeQueue() { queueHead = queueTail = 0; }

    ~NodeQueue(); 

    NodeIndex popNodeQueue(); 
    QueueItem *popQueueItem(); 

    Boolean is_empty() {
      return queueHead == 0 ? true : false; }

    // Boolean is_full();
      
    Boolean addToNodeQueue(NodeIndex nodeIndex, unsigned level = 0, 
			   LogP weight = 0.0); 

    Boolean addToNodeQueueNoSamePrev(NodeIndex nodeIndex, unsigned level = 0, 
			   LogP weight = 0.0); 

    // Boolean pushQueueItem(QueueItem queueItem); 

    Boolean inNodeQueue(NodeIndex nodeIndex);

private:

    QueueItem *queueHead;      // the head of the node queue;
    QueueItem *queueTail;      // the tail of the node queue;
    
};


typedef struct PackedNode {
  // currently, this information is not used.
  // In a later version, I will test this List first, and if the wordName
  //   is not found, then compute trigram prob. This way, I can gain
  //   some efficiency.
  // if there is a trigramProg, both bigramProg and backoffWeight are 0;
  // if there is a bigramProg,  trigramProg will be 0;

  // In the latest version, no distinction made for the order of ngram.
  // All the weights are treated as same, and they are based only their
  // positions.
  // LogP inWeight;
  LogP outWeight;
  unsigned toNodeId; 
  NodeIndex toNode; 
  NodeIndex midNodeIndex; 
} PackedNode; 

// this is an input structure for PackedNodeList::packingNodes
typedef struct PackInput {

  VocabIndex fromWordName;  // starting node name
  VocabIndex wordName;      // current node name
  VocabIndex toWordName;    // ending node name
  LM *lm;		    // LM to compute outWeight on demand

  unsigned toNodeId; 
  NodeIndex fromNodeIndex;  // starting node
  NodeIndex toNodeIndex;    // ending node, 
		  // a new node will be created in between these two nodes.  
  NodeIndex nodeIndex;      // for debugging purpose

  LogP inWeight;            // weight for an in-coming trans to the new node
  LogP outWeight;           // weight for an out-going trans from the new node
  unsigned inFlag; 
  unsigned outFlag; 

} PackInput; 

class PackedNodeList: public Debug 
{
public: 
  PackedNodeList() : lastPackedNode(0) {};
  Boolean packNodes(Lattice &lat, PackInput &packInput);

private:
  LHash<VocabIndex,PackedNode> packedNodesByFromNode;
  PackedNode *lastPackedNode;
}; 


#endif /* _Lattice_h_ */