de.up.ling.irtg.automata

Class BestFirstIntersectionAutomaton<LeftState,RightState>

java.lang.Object

de.up.ling.irtg.automata.TreeAutomaton<Pair<LeftState,RightState>>

de.up.ling.irtg.automata.IntersectionAutomaton<LeftState,RightState>

de.up.ling.irtg.automata.BestFirstIntersectionAutomaton<LeftState,RightState>

Type Parameters:

LeftState -

RightState -

All Implemented Interfaces:

Intersectable<Pair<LeftState,RightState>>, Serializable

public class BestFirstIntersectionAutomaton<LeftState,RightState>
extends IntersectionAutomaton<LeftState,RightState>

An intersection automaton for viterbi search that constructs transitions bottom up when makeAllRulesExplicit is called, according to a queue and stops construction once a complete tree can be derived. This is used when only the best parse is of interest and a complete automaton is not necessary. Note that the automaton requires an EdgeEvaluator to provide outside scores.

Author:

koller

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class de.up.ling.irtg.automata.IntersectionAutomaton

IntersectionAutomaton.StateDiscoveryListener

Nested classes/interfaces inherited from class de.up.ling.irtg.automata.TreeAutomaton

TreeAutomaton.BottomUpStateVisitor

Field Summary

Fields inherited from class de.up.ling.irtg.automata.TreeAutomaton

D, DEBUG_STORE

Constructor Summary

Constructors

Constructor and Description
BestFirstIntersectionAutomaton(TreeAutomaton<LeftState> left, TreeAutomaton<RightState> right, EdgeEvaluator evaluator) Creates a new instance with the given evaluator.

Method Summary

Modifier and Type	Method and Description
void	makeAllRulesExplicit() Intersects the two automata bottom-up.

Methods inherited from class de.up.ling.irtg.automata.IntersectionAutomaton

getFinalStates, getLeftState, getRightState, getRulesBottomUp, getRulesTopDown, intersectBottomUpNaive, intersectTopDownBottomUpCKY, isBottomUpDeterministic, makeAllRulesExplicitCKY, makeAllRulesExplicitCKYOld, makeAllRulesExplicitEarley, setStateDiscoveryListener

Methods inherited from class de.up.ling.irtg.automata.TreeAutomaton

accepts, acceptsRaw, analyze, asConcreteTreeAutomaton, asConcreteTreeAutomatonBottomUp, asConcreteTreeAutomatonWithStringStates, countTrees, createRule, createRule, createRule, createRule, createRule, createRule, determinize, determinize, dumpToFile, equals, evaluateInSemiring, evaluateInSemiring, evaluateInSemiringTopDown, foreachRuleBottomUpForSets, foreachRuleTopDown, foreachStateInBottomUpOrder, getAllLabels, getAllRulesTopDown, getAllStates, getIdForState, getLabelsTopDown, getNumberOfRules, getNumberOfSeenStates, getRandomRuleTree, getRandomRuleTreeFromInside, getRandomTree, getRandomTreeFromInside, getReachableStates, getRulesBottomUp, getRulesBottomUp, getRuleSet, getRulesForRhsState, getRulesTopDown, getRuleTree, getSignature, getStateForId, getStateInterner, getStatesInBottomUpOrder, getStoredConstantsForID, getWeight, getWeightRaw, hasRuleWithPrefix, hasStoredConstants, homomorphism, inside, intersect, intersect, intersectBottomUp, intersectCondensed, intersectCondensed, intersectCondensed, intersectCondensedBottomUp, intersectCondensedBottomUp, intersectEarley, intersectViterbi, intersectViterbi, inverseCondensedHomomorphism, inverseHomomorphism, isCyclic, isEmpty, isStoring, language, languageIterable, languageIterator, languageIteratorRaw, languageRaw, newSiblingFinder, normalizeRuleWeights, outside, processAllRulesBottomUp, processAllRulesTopDown, reduceTopDown, run, run, runRaw, setRulePrintingFilter, setSkipFail, setStoring, sortedLanguageIterator, supportsBottomUpQueries, supportsTopDownQueries, toString, toStringBottomUp, useSiblingFinder, viterbi, viterbiRaw, write

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BestFirstIntersectionAutomaton

public BestFirstIntersectionAutomaton(TreeAutomaton<LeftState> left,
                                      TreeAutomaton<RightState> right,
                                      EdgeEvaluator evaluator)

Creates a new instance with the given evaluator. If the score provided by the evaluator is an upper bound, then makeAllRulesExplicit will implement A*-search.

Parameters:

left -

right -

evaluator -

Method Detail

makeAllRulesExplicit

public void makeAllRulesExplicit()

Intersects the two automata bottom-up. The intersection algorithm uses a priority queue for its agenda, on which edges (i.e., states of the output automaton) are ordered in descending order with respect to the edge evaluator that was passed to the constructor. The intersection algorithm terminates once it discovers the first final state of the output automaton. At this point, it will typically NOT have computed the entire output automaton; the only guarantee is that it has discovered enough of the automaton to generate at least one tree from the first final state. If the edge evaluator is an admissible heuristic in the sense of A* search, this tree is also guaranteed to be optimal.

Overrides:

makeAllRulesExplicit in class IntersectionAutomaton<LeftState,RightState>