edu.stanford.nlp.fsm

Class FastExactAutomatonMinimizer

java.lang.Object

edu.stanford.nlp.fsm.FastExactAutomatonMinimizer

All Implemented Interfaces:

AutomatonMinimizer

public class FastExactAutomatonMinimizer
extends java.lang.Object
implements AutomatonMinimizer

Minimization in n log n a la Hopcroft.

Author:

Dan Klein (klein@cs.stanford.edu)

Constructor Summary

Constructors

Constructor and Description
FastExactAutomatonMinimizer()

Method Summary

Modifier and Type	Method and Description
protected void	addSplit(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)
protected void	addSplits(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block block)
protected TransducerGraph	buildMinimizedFA()
protected java.util.Collection	difference(java.util.Collection block, java.util.Collection members)
protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block	getBlock(java.lang.Object o)
protected java.util.Collection<TransducerGraph.Arc>	getInverseArcs(java.lang.Object member)
protected java.util.Collection<TransducerGraph.Arc>	getInverseArcs(java.lang.Object member, java.lang.Object symbol)
protected java.util.Collection	getInverseImages(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)
protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split	getSplit()
protected java.util.Collection	getSymbols()
protected TransducerGraph	getUnminimizedFA()
protected boolean	hasSplit()
static void	main(java.lang.String[] args)
protected void	makeBlock(java.util.Collection members)
protected void	makeInitialBlocks()
protected void	minimize()
TransducerGraph	minimizeFA(TransducerGraph unminimizedFA)
protected java.lang.Object	projectNode(java.lang.Object node)
protected void	removeAll(java.util.Collection block, java.util.Collection members)
protected java.util.Map	sortIntoBlocks(java.util.Collection nodes)

Methods inherited from class java.lang.Object

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

Constructor Detail

FastExactAutomatonMinimizer

public FastExactAutomatonMinimizer()

Method Detail

getUnminimizedFA

protected TransducerGraph getUnminimizedFA()

getSymbols

protected java.util.Collection getSymbols()

minimizeFA

public TransducerGraph minimizeFA(TransducerGraph unminimizedFA)

Specified by:

minimizeFA in interface AutomatonMinimizer

buildMinimizedFA

protected TransducerGraph buildMinimizedFA()

projectNode

protected java.lang.Object projectNode(java.lang.Object node)

hasSplit

protected boolean hasSplit()

getSplit

protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split getSplit()

addSplit

protected void addSplit(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)

sortIntoBlocks

protected java.util.Map sortIntoBlocks(java.util.Collection nodes)

makeBlock

protected void makeBlock(java.util.Collection members)

addSplits

protected void addSplits(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block block)

removeAll

protected void removeAll(java.util.Collection block,
                         java.util.Collection members)

difference

protected java.util.Collection difference(java.util.Collection block,
                                          java.util.Collection members)

getBlock

protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block getBlock(java.lang.Object o)

getInverseImages

protected java.util.Collection getInverseImages(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)

getInverseArcs

protected java.util.Collection<TransducerGraph.Arc> getInverseArcs(java.lang.Object member,
                                                                   java.lang.Object symbol)

getInverseArcs

protected java.util.Collection<TransducerGraph.Arc> getInverseArcs(java.lang.Object member)

makeInitialBlocks

protected void makeInitialBlocks()

minimize

protected void minimize()

main

public static void main(java.lang.String[] args)