edu.cmu.sphinx.result

Class LatticeOptimizer

java.lang.Object

edu.cmu.sphinx.result.LatticeOptimizer

public class LatticeOptimizer
extends java.lang.Object

Class used to collapse all equivalent paths in a Lattice. Results in a Lattices that is deterministic (no Node has Edges to two or more equivalent Nodes), and minimal (no Node has Edge from two or more equivalent Nodes).

Field Summary

Fields

Modifier and Type	Field and Description
protected Lattice	lattice

Constructor Summary

Constructors

Constructor and Description
LatticeOptimizer(Lattice lattice) Create a new Lattice optimizer

Method Summary

Modifier and Type	Method and Description
protected boolean	equivalentNodeLabels(Node n1, Node n2) Is the contents of these Node equivalent?
protected boolean	equivalentNodesBackward(Node n1, Node n2) nodes are equivalent backward if they have "to" edges to the same nodes, and have equivalent labels (Token, start/end times)
protected boolean	equivalentNodesForward(Node n1, Node n2) nodes are equivalent forward if they have "from" edges from the same nodes, and have equivalent labels (Token, start/end times)
protected void	mergeNodesAndEdgesBackward(Edge e1, Edge e2) given edges e1 and e2 to node n from nodes n1 and n2 merge e1 and e2, that is, merge the scores of e1 and e2 create n' that is a merge of n1 and n2 add n' add edge e' from n' to n remove n1 and n2 and all associated edges
protected void	mergeNodesAndEdgesForward(Edge e1, Edge e2) given edges e1 and e2 from node n to nodes n1 and n2 merge e1 and e2, that is, merge the scores of e1 and e2 create n' that is a merge of n1 and n2 add n' add edge e' from n to n' remove n1 and n2 and all associated edges
void	optimize() Code for optimizing Lattices.
protected void	optimizeBackward() Minimize the Lattice deterministic, so that no node has multiple incoming edges from equivalent nodes.
protected void	optimizeForward() Make the Lattice deterministic, so that no node has multiple outgoing edges to equivalent nodes.
protected boolean	optimizeNodeBackward(Node n) Look for 2 entering edges from equivalent nodes.
protected boolean	optimizeNodeForward(Node n) Look for 2 "to" edges to equivalent nodes.
protected void	removeHangingNodes() Remove all Nodes that have no Edges to them (but not <s>)

Methods inherited from class java.lang.Object

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

Field Detail

lattice

protected final Lattice lattice

Constructor Detail

LatticeOptimizer

public LatticeOptimizer(Lattice lattice)

Create a new Lattice optimizer

Parameters:

lattice - lattice to optimize

Method Detail

optimize

public void optimize()

Code for optimizing Lattices. An optimal lattice has all the same paths as the original, but with fewer nodes and edges

Note that these methods are all in Lattice so that it is easy to change the definition of "equivalent" nodes and edges. For example, an equivalent node might have the same word, but start or end at a different time.

To experiment with other definitions of equivalent, just create a superclass of Lattice.

optimizeForward

protected void optimizeForward()

Make the Lattice deterministic, so that no node has multiple outgoing edges to equivalent nodes.

Given two edges from the same node to two equivalent nodes, replace with one edge to one node with outgoing edges that are a union of the outgoing edges of the old two nodes.

A --> B --> C \--> B' --> Y

where B and B' are equivalent.

is replaced with

A --> B" --> C \--> Y

where B" is the merge of B and B'

Note that equivalent nodes must have the same incomming edges. For example

A --> B \ \ X --> B'

B and B' would not be equivalent because the incomming edges are different

optimizeNodeForward

protected boolean optimizeNodeForward(Node n)

Look for 2 "to" edges to equivalent nodes. Replace the edges with one edge to one node that is a merge of the equivalent nodes

nodes are equivalent if they have equivalent from edges, and the same label

merged nodes have a union of "from" and "to" edges

Parameters:

n - node

Returns:

true if Node n required an optimize forward

equivalentNodesForward

protected boolean equivalentNodesForward(Node n1,
                                         Node n2)

nodes are equivalent forward if they have "from" edges from the same nodes, and have equivalent labels (Token, start/end times)

Parameters:

n1 - first node

n2 - second node

Returns:

true if n1 and n2 are "equivalent forwards"

mergeNodesAndEdgesForward

protected void mergeNodesAndEdgesForward(Edge e1,
                                         Edge e2)

given edges e1 and e2 from node n to nodes n1 and n2

merge e1 and e2, that is, merge the scores of e1 and e2 create n' that is a merge of n1 and n2 add n' add edge e' from n to n'

remove n1 and n2 and all associated edges

Parameters:

e1 - first edge

e2 - second edge

optimizeBackward

protected void optimizeBackward()

Minimize the Lattice deterministic, so that no node has multiple incoming edges from equivalent nodes.

Given two edges from equivalent nodes to a single nodes, replace with one edge from one node with incoming edges that are a union of the incoming edges of the old two nodes.

A --> B --> C X --> B' --/

where B and B' are equivalent.

is replaced with

A --> B" --> C X --/

where B" is the merge of B and B'

Note that equivalent nodes must have the same outgoing edges. For example

A --> X \ \ \ A' --> B

A and A' would not be equivalent because the outgoing edges are different

optimizeNodeBackward

protected boolean optimizeNodeBackward(Node n)

Look for 2 entering edges from equivalent nodes. Replace the edges with one edge to one new node that is a merge of the equivalent nodes Nodes are equivalent if they have equivalent to edges, and the same label. Merged nodes have a union of entering and leaving edges

Parameters:

n - node

Returns:

true if Node n required optimizing backwards

equivalentNodesBackward

protected boolean equivalentNodesBackward(Node n1,
                                          Node n2)

nodes are equivalent backward if they have "to" edges to the same nodes, and have equivalent labels (Token, start/end times)

Parameters:

n1 - first node

n2 - second node

Returns:

true if n1 and n2 are "equivalent backwards"

equivalentNodeLabels

protected boolean equivalentNodeLabels(Node n1,
                                       Node n2)

Is the contents of these Node equivalent?

Parameters:

n1 - first node

n2 - second node

Returns:

true if n1 and n2 have "equivalent labels"

mergeNodesAndEdgesBackward

protected void mergeNodesAndEdgesBackward(Edge e1,
                                          Edge e2)

given edges e1 and e2 to node n from nodes n1 and n2

merge e1 and e2, that is, merge the scores of e1 and e2 create n' that is a merge of n1 and n2 add n' add edge e' from n' to n

remove n1 and n2 and all associated edges

Parameters:

e1 - first edge

e2 - second edge

removeHangingNodes

protected void removeHangingNodes()

Remove all Nodes that have no Edges to them (but not <s>)