de.up.ling.irtg.automata.condensed

Class NonCondensedIntersectionAutomaton<LeftState,RightState>

java.lang.Object

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

de.up.ling.irtg.automata.condensed.NonCondensedIntersectionAutomaton<LeftState,RightState>

All Implemented Interfaces:

Intersectable<Pair<LeftState,RightState>>, Serializable

public class NonCondensedIntersectionAutomaton<LeftState,RightState>
extends TreeAutomaton<Pair<LeftState,RightState>>

A variant of GenericCondensedIntersectionAutomaton that expands each condensed rule into the individual ordinary rules it represents. This makes the intersection algorithm extremely inefficient. This class should not be used in practical parsers; it is only intended as a baseline to quantify the performance benefits of condensed automata.

Author:

koller

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	NonCondensedIntersectionAutomaton.IntersectionCall

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

TreeAutomaton.BottomUpStateVisitor

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	DEBUG

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

D, DEBUG_STORE

Constructor Summary

Constructors

Constructor and Description
NonCondensedIntersectionAutomaton(TreeAutomaton<LeftState> left, CondensedTreeAutomaton<RightState> right) Assumes the signatures are identical.
NonCondensedIntersectionAutomaton(TreeAutomaton<LeftState> left, CondensedTreeAutomaton<RightState> right, SignatureMapper sigMapper)
NonCondensedIntersectionAutomaton(TreeAutomaton<LeftState> left, CondensedTreeAutomaton<RightState> right, SignatureMapper sigMapper, boolean debug)

Method Summary

Modifier and Type	Method and Description
IntSet	getFinalStates() Returns the IDs of the final states of the automaton.
int	getNumberOfSeenRhsStates()
Iterable<Rule>	getRulesBottomUp(int label, int[] childStates) Finds automaton rules bottom-up for a given list of child states and a given parent label.
Iterable<Rule>	getRulesTopDown(int label, int parentState) Finds automaton rules top-down for a given parent state and label.
static NonCondensedIntersectionAutomaton	intersectTopDownBottomUpNonCondensed(TreeAutomaton lhs, CondensedTreeAutomaton rhs)
boolean	isBottomUpDeterministic() Determines whether the automaton is deterministic if read as a bottom-up automaton.
static void	main(String[] args, boolean showViterbiTrees, NonCondensedIntersectionAutomaton.IntersectionCall icall) Function to test the efficiency of this intersection algorithm by parsing each sentence in a text file with a given IRTG.
void	makeAllRulesExplicit() Computes all rules in this automaton and stores them in the cache.

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

Field Detail

DEBUG

public static boolean DEBUG

Constructor Detail

NonCondensedIntersectionAutomaton

public NonCondensedIntersectionAutomaton(TreeAutomaton<LeftState> left,
                                         CondensedTreeAutomaton<RightState> right)

Assumes the signatures are identical.

Parameters:

left -

right -

NonCondensedIntersectionAutomaton

public NonCondensedIntersectionAutomaton(TreeAutomaton<LeftState> left,
                                         CondensedTreeAutomaton<RightState> right,
                                         SignatureMapper sigMapper,
                                         boolean debug)

NonCondensedIntersectionAutomaton

public NonCondensedIntersectionAutomaton(TreeAutomaton<LeftState> left,
                                         CondensedTreeAutomaton<RightState> right,
                                         SignatureMapper sigMapper)

Method Detail

getNumberOfSeenRhsStates

public int getNumberOfSeenRhsStates()

makeAllRulesExplicit

public void makeAllRulesExplicit()

Description copied from class: TreeAutomaton

Computes all rules in this automaton and stores them in the cache. This only makes a difference for lazy automata, in which rules are only computed by need. After calling this function, it is guaranteed that all rules are in the cache.

Overrides:

makeAllRulesExplicit in class TreeAutomaton<Pair<LeftState,RightState>>

isBottomUpDeterministic

public boolean isBottomUpDeterministic()

Description copied from class: TreeAutomaton

Determines whether the automaton is deterministic if read as a bottom-up automaton.

Specified by:

isBottomUpDeterministic in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

getFinalStates

public IntSet getFinalStates()

Description copied from class: TreeAutomaton

Returns the IDs of the final states of the automaton.

Overrides:

getFinalStates in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

getRulesBottomUp

public Iterable<Rule> getRulesBottomUp(int label,
                                       int[] childStates)

Description copied from class: TreeAutomaton

Finds automaton rules bottom-up for a given list of child states and a given parent label. The method returns a collection of rules that can be used to assign a state to the parent node. The parent label is a numeric symbol ID, which represents a terminal symbol according to the automaton's signature.

Specified by:

getRulesBottomUp in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

getRulesTopDown

public Iterable<Rule> getRulesTopDown(int label,
                                      int parentState)

Description copied from class: TreeAutomaton

Finds automaton rules top-down for a given parent state and label. The method returns a collection of rules that can be used to assign states to the children. The parent label is a numeric symbol ID, which represents a terminal symbol according to the automaton's signature.

Note that not every method of TreeAutomaton is safely available in your implementation of getRulesTopDown. Most notably, you can't use the default implementation of TreeAutomaton.getAllStates(), because that method makes all rules of the automaton explicit and calls TreeAutomaton.getRulesTopDown(int, int) in the process, leading to an infinite recursion.

Specified by:

getRulesTopDown in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

intersectTopDownBottomUpNonCondensed

public static NonCondensedIntersectionAutomaton intersectTopDownBottomUpNonCondensed(TreeAutomaton lhs,
                                                                                     CondensedTreeAutomaton rhs)

main

public static void main(String[] args,
                        boolean showViterbiTrees,
                        NonCondensedIntersectionAutomaton.IntersectionCall icall)
                 throws FileNotFoundException,
                        ParseException,
                        IOException,
                        ParserException,
                        CodecParseException

Function to test the efficiency of this intersection algorithm by parsing each sentence in a text file with a given IRTG. Args: /path/to/grammar.irtg, /path/to/sentences, interpretation, /path/to/result_file, "Additional comment"

Parameters:

args - CMD arguments

showViterbiTrees -

icall - what intersection should be used?

Throws:

FileNotFoundException

ParseException

IOException

ParserException

AntlrIrtgBuilder.ParseException

ParseException

CodecParseException