edu.cmu.sphinx.result

Class Lattice

java.lang.Object

edu.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 corresponds 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.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Set<Edge>	edges
protected Node	initialNode
protected double	logBase
protected LogMath	logMath
protected java.util.Map<java.lang.String,Node>	nodes
protected Node	terminalNode

Constructor Summary

Constructors

Constructor and Description
Lattice() Create an empty Lattice.
Lattice(Result result) Create a Lattice from a Result.
Lattice(java.lang.String fileName) Create a Lattice from a LAT file.

Method Summary

Modifier and Type	Method and Description
Edge	addEdge(Node fromNode, Node toNode, double acousticScore, double lmScore) Add an edge from fromNode to toNode.
protected void	addNode(Node n) Add a Node to the set of all Nodes
Node	addNode(java.lang.String id, java.lang.String word, long beginTime, long endTime) Add a Node with a given ID that represents the theory that a given word was spoken over a given period of time.
protected Node	addNode(java.lang.String id, Word word, long beginTime, long endTime) Add a Node with a given ID that represents the theory that a given word was spoken over a given period of time.
java.util.List<java.lang.String>	allPaths() Generate a List of all paths through this Lattice.
protected java.util.List<java.lang.String>	allPathsFrom(java.lang.String path, Node n) Internal routine used to generate all paths starting at a given node.
void	computeNodePosteriors(float languageModelWeightAdjustment) Compute the utterance-level posterior for every node in the lattice, i.e.
void	computeNodePosteriors(float languageModelWeightAdjustment, boolean useAcousticScoresOnly) Compute the utterance-level posterior for every node in the lattice, i.e.
protected void	dump(java.io.PrintWriter out) Dump the Lattice as a .LAT file
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.
void	dumpDot(java.lang.String fileName, java.lang.String title) Dump the Lattice in the form understood by Graphviz.
void	dumpSlf(java.io.Writer w)
protected java.util.Collection<Node>	getCopyOfNodes() Get a copy of the Collection of all Nodes.
java.util.Collection<Edge>	getEdges() Get the set of all Edges.
Node	getInitialNode() Get the initialNode for this Lattice.
protected Node	getNode(java.lang.String id) Get the Node associated with an ID
java.util.Collection<Node>	getNodes() Get the Collection of all Nodes.
Node	getTerminalNode() Get the terminalNode for this Lattice.
java.util.List<Node>	getViterbiPath() Retrieves the MAP path from this lattice.
java.util.List<WordResult>	getWordResultPath() Retrieves the list of WordResult from this lattice.
protected boolean	hasNode(java.lang.String ID) Test to see if the Lattice already contains a Node corresponding to a given Token.
boolean	isEquivalent(Lattice other) Returns true if the given Lattice is equivalent to this Lattice.
static Lattice	readSlf(java.io.InputStream stream)
static Lattice	readSlf(java.lang.String fileName)
protected void	removeEdge(Edge e) Remove an Edge from the set of all Edges.
protected void	removeNode(Node n) Remove a Node from the set of all Nodes
protected void	removeNodeAndCrossConnectEdges(Node n) Remove a Node and cross connect all Nodes with Edges to it.
protected void	removeNodeAndEdges(Node n) Remove a Node and all Edges connected to it.
void	setInitialNode(Node initialNode) Set the initialNode for this Lattice.
void	setTerminalNode(Node terminalNode) Set the terminalNode for this Lattice.
protected void	sortHelper(Node n, java.util.List<Node> sorted, java.util.Set<Node> visited)
java.util.List<Node>	sortNodes() Topologically sort the nodes in this lattice.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

initialNode

protected Node initialNode

terminalNode

protected Node terminalNode

edges

protected java.util.Set<Edge> edges

nodes

protected java.util.Map<java.lang.String,Node> nodes

logBase

protected double logBase

logMath

protected LogMath logMath

Constructor Detail

Lattice

public Lattice()

Create an empty Lattice.

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 - filename to load from

Method Detail

readSlf

public static Lattice readSlf(java.io.InputStream stream)
                       throws java.lang.NumberFormatException,
                              java.io.IOException

Throws:

java.lang.NumberFormatException

java.io.IOException

readSlf

public static Lattice readSlf(java.lang.String fileName)
                       throws java.io.IOException

Throws:

java.io.IOException

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 - from node

toNode - to node

acousticScore - acoustic score

lmScore - langauge model score

Returns:

the new Edge

addNode

protected Node addNode(java.lang.String id,
                       Word word,
                       long beginTime,
                       long endTime)

Add a Node with a given ID that represents the theory that a given word was spoken over a given period of time. This method is used when loading Lattices from .LAT files.

Parameters:

id - id of the node

word - word word

beginTime - begin time

endTime - end time

Returns:

the new Node

addNode

public Node addNode(java.lang.String id,
                    java.lang.String word,
                    long beginTime,
                    long endTime)

Add a Node with a given ID that represents the theory that a given word was spoken over a given period of time. This method is used when loading Lattices from .LAT files.

Parameters:

id - id

word - word

beginTime - begin time

endTime - end time

Returns:

the new Node

hasNode

protected boolean hasNode(java.lang.String ID)

Test to see if the Lattice already contains a Node corresponding to a given Token.

Parameters:

ID - the ID of the Node to find

Returns:

true if yes

addNode

protected void addNode(Node n)

Add a Node to the set of all Nodes

Parameters:

n - node to remove

removeNode

protected void removeNode(Node n)

Remove a Node from the set of all Nodes

Parameters:

n - node to remove

getNode

protected Node getNode(java.lang.String id)

Get the Node associated with an ID

Parameters:

id - id to look for

Returns:

the Node

getCopyOfNodes

protected java.util.Collection<Node> getCopyOfNodes()

Get a copy of the Collection of all Nodes. Used by LatticeOptimizer to avoid Concurrent modification of the nodes list.

Returns:

a copy of the collection of Nodes

getNodes

public java.util.Collection<Node> getNodes()

Get the Collection of all Nodes.

Returns:

the collection of all Nodes

removeEdge

protected void removeEdge(Edge e)

Remove an Edge from the set of all Edges.

Parameters:

e - edge to remove

getEdges

public java.util.Collection<Edge> 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 - file to store to

title - title in the file

dumpDot

public void dumpDot(java.lang.String fileName,
                    java.lang.String title)

Dump the Lattice in the form understood by Graphviz. See http://graphviz.org

Parameters:

fileName - filename to store

title - title in graph

dumpSlf

public void dumpSlf(java.io.Writer w)
             throws java.io.IOException

Throws:

java.io.IOException

dump

protected void dump(java.io.PrintWriter out)
             throws java.io.IOException

Dump the Lattice as a .LAT file

Parameters:

out - writer for the lattice

Throws:

java.io.IOException - if error occurred

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 - file to store

removeNodeAndEdges

protected void removeNodeAndEdges(Node n)

Remove a Node and all Edges connected to it. Also remove those Edges from all connected Nodes.

Parameters:

n - node to remove

removeNodeAndCrossConnectEdges

protected void removeNodeAndCrossConnectEdges(Node n)

Remove a Node and cross connect all Nodes with Edges to it.

For example given

Nodes A, B, X, M, N Edges A-->X, B-->X, X-->M, X-->N

Removing and cross connecting X would result in

Nodes A, B, M, N Edges A-->M, A-->N, B-->M, B-->N

Parameters:

n - node to remove

getInitialNode

public Node getInitialNode()

Get the initialNode for this Lattice. This corresponds usually to the <s> symbol

Returns:

the initial Node

setInitialNode

public void setInitialNode(Node initialNode)

Set the initialNode for this Lattice. This corresponds usually to the <s> symbol

Parameters:

initialNode - node to set as initial

getTerminalNode

public Node getTerminalNode()

Get the terminalNode for this Lattice. This corresponds usually to the </s> symbol

Returns:

the terminal node

setTerminalNode

public void setTerminalNode(Node terminalNode)

Set the terminalNode for this Lattice. This corresponds usually to the </s> symbol

Parameters:

terminalNode - not to set as terminal

dumpAllPaths

public void dumpAllPaths()

Dump all paths through this Lattice. Used for debugging.

allPaths

public java.util.List<java.lang.String> allPaths()

Generate a List of all paths through this Lattice.

Returns:

a lists of lists of Nodes

allPathsFrom

protected java.util.List<java.lang.String> allPathsFrom(java.lang.String path,
                                                        Node n)

Internal routine used to generate all paths starting at a given node.

Parameters:

path - word path

n - node to start

Returns:

a list of lists of Nodes

sortHelper

protected void sortHelper(Node n,
                          java.util.List<Node> sorted,
                          java.util.Set<Node> visited)

sortNodes

public java.util.List<Node> sortNodes()

Topologically sort the nodes in this lattice.

Returns:

Topologically sorted list of nodes in this lattice.

computeNodePosteriors

public void computeNodePosteriors(float languageModelWeightAdjustment)

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:

languageModelWeightAdjustment - the weight multiplier that will be applied to language score already scaled by language weight

computeNodePosteriors

public void computeNodePosteriors(float languageModelWeightAdjustment,
                                  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:

languageModelWeightAdjustment - the weight multiplier that will be applied to language score already scaled by language weight

useAcousticScoresOnly - use only the acoustic scores to compute the posteriors, ignore the language weight and scores

getViterbiPath

public java.util.List<Node> getViterbiPath()

Retrieves the MAP path from this lattice. Only works once computeNodePosteriors has been called.

Returns:

a list of nodes representing the MAP path.

getWordResultPath

public java.util.List<WordResult> getWordResultPath()

Retrieves the list of WordResult from this lattice. Only works once computeNodePosteriors has been called.

Returns:

list of WordResult

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