edu.cmu.sphinx.result
Class Lattice

java.lang.Object
  extended byedu.cmu.sphinx.result.Lattice

public class Lattice
extends java.lang.Object

Provides recognition lattice results. Lattices are created from Results which can be partial or final.

Lattices describe all theories considered by the Recognizer that have not been pruned out. Lattices are a directed graph containing Nodes and Edges. A Node that correponds to a theory that a word was spoken over a particular period of time. An Edge that corresponds to the score of one word following another. The usual result transcript is the sequence of Nodes though the Lattice with the best scoring path. Lattices are a useful tool for analyzing "alternate results".

A Lattice can be created from a Result that has a full token tree (with its corresponding AlternativeHypothesisManager). Currently, only the WordPruningBreadthFirstSearchManager has an AlternativeHypothesisManager. Furthermore, the lattice construction code currently only works for linguists where the WordSearchState returns false on the isWordStart method, i.e., where the word states appear at the end of the word in the linguist. Therefore, lattices should only be created from Result from the LexTreeLinguist and the WordPruningBreadthFirstSearchManager.

Lattices can also be created from a collapsed Token tree and its AlternativeHypothesisManager. This is what 'collapsed' means. Normally, between two word tokens is a series of tokens for other types of states, such as unit or HMM states. Using 'W' for word tokens, 'U' for unit tokens, 'H' for HMM tokens, a token chain can look like:

 W - U - H - H - H - H - U - H - H - H - H - W
 

Usually, HMM tokens contains acoustic scores, and word tokens contains language scores. If we want to know the total acoustic and language scores between any two words, it is unnecessary to keep around the unit and HMM tokens. Therefore, all their acoustic and language scores are 'collapsed' into one token, so that it will look like:

 W - P - W
 

where 'P' is a token that represents the path between the two words, and P contains the acoustic and language scores between the two words. It is this type of collapsed token tree that the Lattice class is expecting. Normally, the task of collapsing the token tree is done by the WordPruningBreadthFirstSearchManager. A collapsed token tree can look like:

                             "cat" - P - </s>
                            / 
                           P
                          /
 <s> - P - "a" - P - "big"
                          \
                           P
                            \
                             "dog" - P - </s>
 

When a Lattice is constructed from a Result, the above collapsed token tree together with the alternate hypothesis of "all" instead of "a", will be converted into a Lattice that looks like the following:

       "a"           "cat"
     /     \        /     \
 <s>          "big"         - </s>
     \     /        \     /
      "all"          "dog"
 

Initially, a lattice can have redundant nodes, i.e., nodes referring to the same word and that originate from the same parent node. These nodes can be collapsed using the LatticeOptimizer.


Constructor Summary
Lattice(Result result)
          Create a Lattice from a Result.
Lattice(java.lang.String fileName)
          Create a Lattice from a LAT file.
 
Method Summary
 Edge addEdge(Node fromNode, Node toNode, double acousticScore, double lmScore)
          Add an edge from fromNode to toNode.
 Node addNode(java.lang.String word, int beginTime, int endTime)
          Add a Node that represents the theory that a given word was spoken over a given period of time.
 Node addNode(Word word, int beginTime, int endTime)
          Add a Node that represents the theory that a given word was spoken over a given period of time.
 java.util.List allPaths()
          Generate a List of all paths through this Lattice.
 void computeNodePosteriors(float languageModelWeight)
          Compute the utterance-level posterior for every node in the lattice, i.e. the probability that this node occurs on any path through the lattice.
 void computeNodePosteriors(float languageModelWeight, boolean useAcousticScoresOnly)
          Compute the utterance-level posterior for every node in the lattice, i.e. the probability that this node occurs on any path through the lattice.
 void dump(java.lang.String file)
          Dump the Lattice as a .LAT file.
 void dumpAISee(java.lang.String fileName, java.lang.String title)
          Dump the Lattice in the form understood by AiSee (a graph visualization tool).
 void dumpAllPaths()
          Dump all paths through this Lattice.
 java.util.Collection getEdges()
          Get the set of all Edges.
 Node getInitialNode()
          Get the initialNode for this Lattice.
 double getLogBase()
          Edge scores are usually log-likelyhood.
 LogMath getLogMath()
           
 java.util.Collection getNodes()
          Get the Collection of all Nodes.
 Node getTerminalNode()
          Get the terminalNode for this Lattice.
 boolean isEquivalent(Lattice other)
          Returns true if the given Lattice is equivalent to this Lattice.
static void main(java.lang.String[] args)
          Self test for Lattices.
 void setInitialNode(Node p_initialNode)
          Set the initialNode for this Lattice.
 void setLogMath(LogMath logMath)
          Sets the LogMath to use.
 void setTerminalNode(Node p_terminalNode)
          Set the terminalNode for this Lattice.
 java.util.List sortNodes()
          Topologically sort the nodes in this lattice.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Lattice

public Lattice(Result result)
Create a Lattice from a Result. The Lattice is created from the Token tree referenced by the Result. The Lattice is then optimized to all collapse equivalent paths.

Parameters:
result - the result to convert into a lattice

Lattice

public Lattice(java.lang.String fileName)
Create a Lattice from a LAT file. LAT files are created by the method Lattice.dump()

Parameters:
fileName -
Method Detail

addEdge

public Edge addEdge(Node fromNode,
                    Node toNode,
                    double acousticScore,
                    double lmScore)
Add an edge from fromNode to toNode. This method creates the Edge object and does all the connecting

Parameters:
fromNode -
toNode -
acousticScore -
lmScore -
Returns:
the new Edge

addNode

public Node addNode(Word word,
                    int beginTime,
                    int endTime)
Add a Node that represents the theory that a given word was spoken over a given period of time.

Parameters:
word -
beginTime -
endTime -
Returns:
the new Node

addNode

public Node addNode(java.lang.String word,
                    int beginTime,
                    int endTime)
Add a Node that represents the theory that a given word was spoken over a given period of time.

Parameters:
word -
beginTime -
endTime -
Returns:
the new Node

getNodes

public java.util.Collection getNodes()
Get the Collection of all Nodes.

Returns:
the colllection of all Nodes

getEdges

public java.util.Collection getEdges()
Get the set of all Edges.

Returns:
the set of all edges

dumpAISee

public void dumpAISee(java.lang.String fileName,
                      java.lang.String title)
Dump the Lattice in the form understood by AiSee (a graph visualization tool). See http://www.AbsInt.com

Parameters:
fileName -
title -

dump

public void dump(java.lang.String file)
Dump the Lattice as a .LAT file. Used to save Lattices as ASCII files for testing and experimentation.

Parameters:
file -

getInitialNode

public Node getInitialNode()
Get the initialNode for this Lattice. This corresponds usually to the symbol

Returns:
the initial Node

setInitialNode

public void setInitialNode(Node p_initialNode)
Set the initialNode for this Lattice. This corresponds usually to the symbol

Parameters:
p_initialNode -

getTerminalNode

public Node getTerminalNode()
Get the terminalNode for this Lattice. This corresponds usually to the symbol

Returns:
the initial Node

setTerminalNode

public void setTerminalNode(Node p_terminalNode)
Set the terminalNode for this Lattice. This corresponds usually to the symbol

Parameters:
p_terminalNode -

getLogBase

public double getLogBase()
Edge scores are usually log-likelyhood. Get the log base.

Returns:
the log base

getLogMath

public LogMath getLogMath()
Returns:
Returns the logMath object used in this lattice.

setLogMath

public void setLogMath(LogMath logMath)
Sets the LogMath to use.

Parameters:
logMath - the LogMath to use

dumpAllPaths

public void dumpAllPaths()
Dump all paths through this Lattice. Used for debugging.


allPaths

public java.util.List allPaths()
Generate a List of all paths through this Lattice.

Returns:
a lists of lists of Nodes

sortNodes

public java.util.List sortNodes()
Topologically sort the nodes in this lattice.

Returns:
Topologically sorted list of nodes in this lattice.

computeNodePosteriors

public void computeNodePosteriors(float languageModelWeight)
Compute the utterance-level posterior for every node in the lattice, i.e. the probability that this node occurs on any path through the lattice. Uses a forward-backward algorithm specific to the nature of non-looping left-to-right lattice structures. Node posteriors can be retrieved by calling getPosterior() on Node objects.

Parameters:
languageModelWeight - the language model weight that was used in generating the scores in the lattice

computeNodePosteriors

public void computeNodePosteriors(float languageModelWeight,
                                  boolean useAcousticScoresOnly)
Compute the utterance-level posterior for every node in the lattice, i.e. the probability that this node occurs on any path through the lattice. Uses a forward-backward algorithm specific to the nature of non-looping left-to-right lattice structures. Node posteriors can be retrieved by calling getPosterior() on Node objects.

Parameters:
languageModelWeight - the language model weight that was used in generating the scores in the lattice
useAcousticScoresOnly - use only the acoustic scores to compute the posteriors, ignore the language weight and scores

isEquivalent

public boolean isEquivalent(Lattice other)
Returns true if the given Lattice is equivalent to this Lattice. Two lattices are equivalent if all their nodes and edges are equivalent.

Parameters:
other - the Lattice to compare this Lattice against
Returns:
true if the Lattices are equivalent; false otherwise

main

public static void main(java.lang.String[] args)
Self test for Lattices. Test loading, saving, dynamically creating and optimizing Lattices

Parameters:
args -