lattice.cc

这是一款很好用的工具包

/*
 * Lattice.cc --
 *	Word lattices
 *
 */

#ifndef lint
static char Copyright[] = "Copyright (c) 1997-2006 SRI International.  All Rights Reserved.";
static char RcsId[] = "@(#)$Header: /home/srilm/devel/lattice/src/RCS/Lattice.cc,v 1.118 2006/01/16 19:34:15 stolcke Exp $";
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <errno.h>

#include "Lattice.h"

#include "SArray.cc"
#include "LHash.cc"
#include "Array.cc"
#include "WordAlign.h"                  /* for *_COST constants */
#include "NBest.h"			/* for phoneSeparator defn */

const char *LATTICE_OR		= "or";
const char *LATTICE_CONCATE	= "concatenate";
const char *LATTICE_NONAME	= "***NONAME***";

const char *NullNodeName	= "NULL";

#define DebugPrintFatalMessages         0 

#define DebugPrintFunctionality         1 
// for large functionality listed in options of the program
#define DebugPrintOutLoop               2
// for out loop of the large functions or small functions
#define DebugPrintInnerLoop             3
// for inner loop of the large functions or outloop of small functions

#ifdef INSTANTIATE_TEMPLATES
#ifdef USE_SARRAY
INSTANTIATE_SARRAY(NodeIndex,LatticeTransition);
#else
INSTANTIATE_LHASH(NodeIndex,LatticeTransition);
#endif
INSTANTIATE_LHASH(NodeIndex,LatticeNode);
INSTANTIATE_ARRAY(HTKWordInfo *);
#endif

/* **************************************************
   the queue related methods
   ************************************************** */

NodeQueue::~NodeQueue()
{
    while (is_empty() != true) {
	(void) popNodeQueue();
    }
}

NodeIndex NodeQueue::popNodeQueue()
{
    if (is_empty() == true) {
        dout() << "popNodeQueue() on an empty queue\n";
        exit(-1); 
    }

    QueueItem *pt = queueHead; 
    queueHead = queueHead->next;
    if (queueHead == 0) { 
	queueTail = 0;
    }
    NodeIndex retval = pt->item;
    delete pt;
    return retval;
} 

QueueItem * NodeQueue::popQueueItem()
{
    if (is_empty() == true) {
        dout() << "popQueueItem() on an empty queue\n";
        exit(-1); 
    }

    QueueItem *pt = queueHead; 
    queueHead = queueHead->next;

    return pt;
} 
    
Boolean NodeQueue::addToNodeQueue(NodeIndex nodeIndex, 
				  unsigned level, LogP weight)
{
    QueueItem *pt = new QueueItem(nodeIndex, level, weight);
    assert(pt != 0); 

    if (is_empty() == true) {
        queueHead = queueTail = pt;
    } else {
        queueTail->next = pt;
	queueTail = pt;
    }

    return true;
}

// add to NodeQueue if the previous element is not the same
// as the element to be added.
Boolean 
NodeQueue::addToNodeQueueNoSamePrev(NodeIndex nodeIndex, 
				    unsigned level, LogP weight)
{
    if (is_empty() == false && nodeIndex == queueTail->item) {
        if (debug(DebugPrintOutLoop)) {
	  dout() << "In addToNodeQueueNoSamePrev: skip the current nodeIndex ("
		 << nodeIndex << ")" << endl;
	}
        return true;
    }

    if (debug(DebugPrintOutLoop)) {
      dout() << "In addToNodeQueueNoSamePrev: add the current nodeIndex ("
	     << nodeIndex << ")" << endl;
    }
    QueueItem *pt = new QueueItem(nodeIndex, level, weight);
    assert(pt != 0); 

    if (is_empty() == true) {
        queueHead = queueTail = pt;
    } else {
        queueTail->next = pt;
	queueTail = pt;
    }

    return true;
}

Boolean NodeQueue::inNodeQueue(NodeIndex nodeIndex)
{
  
    QueueItem *pt = queueHead;

    while (pt != 0) {
	if (pt->item == nodeIndex) {
	    return true; 
	}
	pt = pt->next;
    }

    return false;
}

QueueItem::QueueItem(NodeIndex nodeIndex, unsigned clevel, LogP cweight)
{
    item = nodeIndex;
    level = clevel;
    weight = cweight; 
    next = 0; 
}


/* ************************************************************
   function definitions for class LatticeFollowIter
   ************************************************************ */

LatticeFollowIter::LatticeFollowIter(Lattice &lat, LatticeNode &node,
				     LHash<NodeIndex, LogP> *useVisitedNodes,
				     LogP startWeight)
    : lat(lat), transIter(node.outTransitions), subFollowIter(0),
      visitedNodes(useVisitedNodes), startWeight(startWeight)
{
    /*
     * Use shared visitedNodes table if passed from our recursive invoker,
     * otherwise create our own.
     */
    if (useVisitedNodes == 0) {
	visitedNodes = new LHash<NodeIndex, LogP>;
	assert(visitedNodes != 0);

	freeVisitedNodes = true;
    } else {
	freeVisitedNodes = false;
    }
}

LatticeFollowIter::~LatticeFollowIter()
{
    delete subFollowIter;

    if (freeVisitedNodes) {
	delete visitedNodes;
    }
}

void
LatticeFollowIter::init()
{
    /* 
     * terminate recursive iteration, if any
     */
    delete subFollowIter;
    subFollowIter = 0;

    /*
     * restart top-level iteration
     */
    transIter.init();

    /*
     * forget visited nodes 
     */
    if (freeVisitedNodes) {
	delete visitedNodes;
	visitedNodes = new LHash<NodeIndex, LogP>;
	assert(visitedNodes != 0);
    }
}

LatticeNode *
LatticeFollowIter::next(NodeIndex &followIndex, LogP &weight)
{
    LatticeNode *followNode;

    /*
     * if a recursive iteration is pending, continue it
     */
    if (subFollowIter != 0) {
	followNode = subFollowIter->next(followIndex, weight);

	if (followNode) {
	    return followNode;
	} else {
	    delete subFollowIter;
	    subFollowIter = 0;
	}
    }
	    
    /*
     * otherwise proceed with the next transition at this node
     */
    LatticeTransition *trans;
    Boolean visitedBefore;

    do {
	/*
	 * find next follow node that hasn't already been visited
	 */
	do {
	    trans = transIter.next(followIndex);

	    if (trans == 0) break;

	    /* record that node has been visited */
	    LogP *oldWeight = visitedNodes->insert(followIndex, visitedBefore);

	    /* if previous visit had lower weight, visit again */
	    if (visitedBefore && *oldWeight < startWeight + trans->weight) {
		visitedBefore = false;
	    }
		    
	    if (!visitedBefore) {
		/* record weight for this visit for future reference */
		*oldWeight = startWeight + trans->weight;
	    }
	} while (visitedBefore);

	if (trans == 0) {
	    /* no more transitions to follow, so stop */
	    break;
	} else {
	    LatticeNode *followNode = lat.findNode(followIndex);
	    assert(followNode != 0);

	    if (!lat.ignoreWord(followNode->word)) {
		weight = startWeight + trans->weight;
		return followNode;
	    } else {
		/*
		 * recursively iterate over following nodes, sharing
		 * visitedNodes table to avoid double visits and infinite loops.
		 */
		subFollowIter =
		    new LatticeFollowIter(lat, *followNode, visitedNodes,
					  startWeight + trans->weight);
		assert(subFollowIter != 0);

		LatticeNode *result = subFollowIter->next(followIndex, weight);
		if (result) {
		    return result;
		}
	    }
	}
    } while (1);

    /* end of iteration reached */
    return 0;
}


/* ************************************************************
   function definitions for class LatticeNode
   ************************************************************ */
LatticeNode::LatticeNode()
    : flags(0), word(Vocab_None), posterior(LogP_Zero), htkinfo(0)
{
}

/* ************************************************************
   function definitions for class LatticeTransition
   ************************************************************ */

/* ************************************************************
   function definitions for class Lattice
   ************************************************************ */

Lattice::Lattice(Vocab &vocab, const char *name)
    : name(strdup(name != 0 ? name : LATTICE_NONAME)),
      initial(NoNode), final(NoNode), maxIndex(0),
      duration(0.0), vocab(vocab), ignoreVocab(vocab),
      useUnk(false), limitIntlogs(false), noBackoffWeights(false), top(true)
{
    /*
     * Default is to ignore pause nodes (only)
     */
    if (vocab.pauseIndex() != Vocab_None) {
	ignoreVocab.addWord(vocab.pauseIndex());
    }
}

Lattice::Lattice(Vocab &vocab, const char *name, SubVocab &ignore)
    : name(strdup(name != 0 ? name : LATTICE_NONAME)),
      initial(NoNode), final(NoNode), maxIndex(0),
      duration(0.0), vocab(vocab), ignoreVocab(vocab),
      useUnk(false), limitIntlogs(false), noBackoffWeights(false), top(true)
{
    /*
     * Copy words-to-be-ignored locally
     */
    VocabIter ignoreIter(ignore);
    VocabIndex ignoreWord;
    while (ignoreIter.next(ignoreWord)) {
	ignoreVocab.addWord(ignoreWord);
    }
}

Lattice::~Lattice()
{
    free((void *)name);
    name = 0;

    LHashIter<NodeIndex, LatticeNode> nodeIter(nodes);
    NodeIndex nodeIndex;

    while (LatticeNode *node = nodeIter.next(nodeIndex)) {
	node->~LatticeNode();
    }

    for (unsigned i = 0; i < htkinfos.size(); i ++) {
	delete htkinfos[i];
    }
}

VocabString
Lattice::getWord(VocabIndex word)
{
    if (word == Vocab_None) {
	return NullNodeName;
    } else {
	return vocab.getWord(word);
    }
}

/* To insert a node with name *word in the NodeLattice */
Boolean 
Lattice::insertNode(const char *word, NodeIndex nodeIndex)
{
    VocabIndex windex;

    if (strcmp(word, NullNodeName) == 0) {
	windex = Vocab_None;
    } else if (useUnk) {
	windex = vocab.getIndex(word, vocab.unkIndex());
    } else {
	windex = vocab.addWord(word);
    }

    LatticeNode *node = nodes.insert(nodeIndex);

    node->word = windex;

    if (maxIndex <= nodeIndex) {
	maxIndex = nodeIndex + 1;
    }

    return true; 
}

/* duplicate a node with a same word name without making 
   any commitment on edges
   */
NodeIndex
Lattice::dupNode(VocabIndex windex, unsigned markedFlag, HTKWordInfo *htkinfo) 
{
    LatticeNode *node = nodes.insert(maxIndex);

    node->word = windex;
    node->flags = markedFlag; 
    node->htkinfo = htkinfo;

    return maxIndex++; 
}

/* remove the node and all of its edges (incoming and outgoing)
   and check to see whether it makes the graph disconnected
*/
Boolean 
Lattice::removeNode(NodeIndex nodeIndex) 
{
    LatticeNode *node = findNode(nodeIndex);
    if (!node) {
      if (debug(DebugPrintOutLoop)) {
	dout() << " In Lattice::removeNode: undefined node in graph " 
	       << nodeIndex << endl;
      }
      return false; 
    }

    // delete incoming transitions -- need do only the fromNode->outTransitions
    // node->inTransition will be freed shortly
    TRANSITER_T<NodeIndex,LatticeTransition> 
      inTransIter(node->inTransitions);
    NodeIndex fromNodeIndex;
    while (inTransIter.next(fromNodeIndex)) {
	LatticeNode *fromNode = findNode(fromNodeIndex);
	assert(fromNode != 0);
	fromNode->outTransitions.remove(nodeIndex);
    } 

    // delete outgoing transitions -- need do only the toNode->inTransitions
    // node->outTransition will be freed shortly
    TRANSITER_T<NodeIndex,LatticeTransition> 
      outTransIter(node->outTransitions);
    NodeIndex toNodeIndex;
    while (outTransIter.next(toNodeIndex)) {
	LatticeNode *toNode = findNode(toNodeIndex);
	assert(toNode != 0);
	toNode->inTransitions.remove(nodeIndex);
    } 

    // remove this node
    LatticeNode *removedNode = nodes.remove(nodeIndex);
    if (debug(DebugPrintOutLoop)) {
      dout() << "In Lattice::removeNode: remove node " << nodeIndex << endl; 
    }

    removedNode->~LatticeNode();

    if (nodeIndex == initial) {
	initial = NoNode;
    } 
    if (nodeIndex == final) {
	final = NoNode;
    } 
    
    return true;
}

void
Lattice::removeAll()
{
    LHashIter<NodeIndex, LatticeNode> nodeIter(nodes);
    NodeIndex nodeIndex;