Parsing Engine

danbikel.parser.constraints
Class UnlexTreeConstraint

java.lang.Object
  extended by danbikel.parser.constraints.UnlexTreeConstraint
All Implemented Interfaces:
SexpConvertible, Constraint, Serializable
Direct Known Subclasses:
LexTreeConstraint, PartialLexTreeConstraint

public class UnlexTreeConstraint
extends Object
implements Constraint, SexpConvertible

An implementation of a constraint to sit in a tree structure of constraints that represents a particular, unlexicalized tree, constraining a decoder to only pursue derivations consistent with that unlexicalized tree.

See Also:
Serialized Form

Field Summary
protected  List children
          The children of this constraint.
protected  int end
          The end index of the span associated with this constraint.
protected  Symbol label
          The nonterminal label associated with this constraint.
protected  UnlexTreeConstraint parent
          The parent of this constraint.
protected  boolean satisfied
          Contains whether this constraint has been satisfied at least once during the bottom-up decoding process.
protected  int start
          The start index of the span associated with this constraint.
 
Constructor Summary
protected UnlexTreeConstraint()
          Constructs an empty constraint.
  UnlexTreeConstraint(Sexp tree)
          Constructs the root constraint of a tree of constraints isomorphic to the specified unlexicalized tree.
protected UnlexTreeConstraint(UnlexTreeConstraint parent, Sexp tree, IntCounter currWordIdx)
          Constructs a tree of constraints isomorphic to the specified unlexicalized syntactic tree.
 
Method Summary
 int end()
          Returns the end index of the span covered by this constraint.
protected  List getChildren()
          Returns the children of this constraint.
 Constraint getParent()
          Returns the parent of this constraint.
 boolean hasBeenSatisfied()
          Returns whether this constraint has been satisfied by at least one chart item.
 boolean isLeaf()
          Returns whether this constraint corresponds to a leaf (a preterminal).
 boolean isLocallySatisfiedBy(Item item)
          Returns whether the specified chart item satisfies the local information contained in this constraint (span and nonterminal label).
 boolean isSatisfiedBy(Item item)
          Returns true if this constraint is satisfied by its local information and either the specified item represents a preterminal or the constraints of the specified item's children are identical to the children of this constraint, and are in the same order More formally, let us define the term nuclear family of a node in a tree to refer to the node itself and its (immediately dominated) sequence of children.
protected  boolean isSatisfiedByPreterminal(CKYItem item)
          Simply returns true and sets this constraint's satisfaction bit to be true.
 boolean isViolatedBy(Item item)
          Throws an UnsupportedOperationException.
 boolean isViolatedByChild(Item childItem)
          Returns whether this constraint is violated by the specified child chart item.
 Symbol label()
          Returns the nonterminal label associated with this constraint.
protected  boolean spanMatches(Item item)
          Returns whether the specified item's span matches that of this constraint.
 int start()
          Returns the start index of the span covered by this constraint.
 Sexp toSexp()
          Returns a symbolic expression version of the constraint tree rooted at this constraint.
 String toString()
          Returns a human-readable string representation of the local information of this constraint (for debugging purposes).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

parent

protected UnlexTreeConstraint parent
The parent of this constraint.


children

protected List children
The children of this constraint.


label

protected Symbol label
The nonterminal label associated with this constraint.


start

protected int start
The start index of the span associated with this constraint.


end

protected int end
The end index of the span associated with this constraint.


satisfied

protected boolean satisfied
Contains whether this constraint has been satisfied at least once during the bottom-up decoding process.

Constructor Detail

UnlexTreeConstraint

public UnlexTreeConstraint(Sexp tree)
Constructs the root constraint of a tree of constraints isomorphic to the specified unlexicalized tree.

Parameters:
tree - the unlexicalized syntactic tree with which to construct this constraint and all its constraint subtrees

UnlexTreeConstraint

protected UnlexTreeConstraint()
Constructs an empty constraint.


UnlexTreeConstraint

protected UnlexTreeConstraint(UnlexTreeConstraint parent,
                              Sexp tree,
                              IntCounter currWordIdx)
Constructs a tree of constraints isomorphic to the specified unlexicalized syntactic tree.

Parameters:
parent - the parent of the constraint subtree to be constructed
tree - the unlexicalized syntactic tree for which an isomorphic constraint tree is to be constructed
currWordIdx - the index of the leftmost word, threaded throughout the recursive calls to this constructor
Method Detail

isLeaf

public boolean isLeaf()
Returns whether this constraint corresponds to a leaf (a preterminal).

Specified by:
isLeaf in interface Constraint
Returns:
whether this constraint corresponds to a leaf (a preterminal)
See Also:
ConstraintSet.hasTreeStructure()

isViolatedByChild

public boolean isViolatedByChild(Item childItem)
Returns whether this constraint is violated by the specified child chart item. Violation occurs when the specified child item's parent's constraint is not this constraint or if the specified child item's constraint is not equal to any of this constraint's child constraints.

Specified by:
isViolatedByChild in interface Constraint
Parameters:
childItem - the child chart item item to be tested against this constraint
Returns:
whether this constraint is violated by the specified child chart item
See Also:
ConstraintSet.hasTreeStructure()

getParent

public Constraint getParent()
Returns the parent of this constraint.

Specified by:
getParent in interface Constraint
Returns:
the parent of this constraint
See Also:
ConstraintSet.hasTreeStructure()

getChildren

protected List getChildren()
Returns the children of this constraint.

Returns:
the children of this constraint

label

public Symbol label()
Returns the nonterminal label associated with this constraint.

Returns:
the nonterminal label associated with this constraint

start

public int start()
Returns the start index of the span covered by this constraint.

Returns:
the start index of the span covered by this constraint

end

public int end()
Returns the end index of the span covered by this constraint.

Returns:
the end index of the span covered by this constraint

isViolatedBy

public boolean isViolatedBy(Item item)
Throws an UnsupportedOperationException.

Specified by:
isViolatedBy in interface Constraint
Parameters:
item - the item to test
Returns:
whether the specified item violates this constraint.

isSatisfiedByPreterminal

protected boolean isSatisfiedByPreterminal(CKYItem item)
Simply returns true and sets this constraint's satisfaction bit to be true.

Parameters:
item - the preterminal item to be tested against this constraint
Returns:
true and sets this constraint's satisfaction bit to be true

isSatisfiedBy

public boolean isSatisfiedBy(Item item)
Returns true if this constraint is satisfied by its local information and either More formally, let us define the term nuclear family of a node in a tree to refer to the node itself and its (immediately dominated) sequence of children. Given that chart items that have received their stop probabilities form a tree structure, let us also define an item-induced constraint tree as the tree of constraints induced by mapping the nodes of a tree of stopped chart items to their assigned constraints. Let c be the nuclear family of this constraint and let t be the nuclear family of the item-induced constraint tree of the specified item. This method returns true if this constraint is satisfied by its local information and if c is identical to t.

Specified by:
isSatisfiedBy in interface Constraint
Parameters:
item - the item to test for satisfaction by this constraint
Returns:
whether this constraint is satisfied the specified item
See Also:
isLocallySatisfiedBy(Item)

hasBeenSatisfied

public boolean hasBeenSatisfied()
Returns whether this constraint has been satisfied by at least one chart item.

Specified by:
hasBeenSatisfied in interface Constraint
Returns:
whether this constraint has been satisfied by at least one chart item

isLocallySatisfiedBy

public boolean isLocallySatisfiedBy(Item item)
Returns whether the specified chart item satisfies the local information contained in this constraint (span and nonterminal label).

Specified by:
isLocallySatisfiedBy in interface Constraint
Parameters:
item - the chart item to be tested against this constraint
Returns:
whether the specified chart item satisfies the local information contained in this constraint (span and nonterminal label)

spanMatches

protected boolean spanMatches(Item item)
Returns whether the specified item's span matches that of this constraint.

Parameters:
item - the chart item whose span is to be compared to that of this constraint
Returns:
whether the specified item's span matches that of this constraint

toSexp

public Sexp toSexp()
Returns a symbolic expression version of the constraint tree rooted at this constraint.

Specified by:
toSexp in interface SexpConvertible
Returns:
a symbolic expression version of the constraint tree rooted at this constraint

toString

public String toString()
Returns a human-readable string representation of the local information of this constraint (for debugging purposes).

Overrides:
toString in class Object
Returns:
a human-readable string representation of the local information of this constraint

Parsing Engine

Author: Dan Bikel.