Parsing Engine

danbikel.parser
Class CKYChart

java.lang.Object
  extended by danbikel.parser.Chart
      extended by danbikel.parser.CKYChart
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
EMChart

public class CKYChart
extends Chart

Implementation of a chart for probabilistic Cocke-Kasami-Younger (CKY) parsing.

See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class danbikel.parser.Chart
Chart.Entry
 
Field Summary
 
Fields inherited from class danbikel.parser.Chart
cellLimit, chart, debugNumItemsGenerated, debugNumPrunedItems, itemPool, numPrePruned, numPruned, pruneFact, pruning, relax, size, totalItems, totalItemsGenerated
 
Constructor Summary
CKYChart()
          Constructs a new chart with the default chart size.
CKYChart(int size)
          Constructs a new chart with the specified chart size.
CKYChart(int cellLimit, double pruneFact)
          Constructs a new chart with a default initial chart size, and with the specified cell limit and prune factor.
CKYChart(int size, int cellLimit, double pruneFact)
          Constructs a new chart with the specified initial chart size, cell limit and prune factor.
 
Method Summary
protected  boolean cellLimitShouldApplyTo(Item item)
          Returns true if the specified item has received its stop probabilities (that is, if item.stop() == true).
 void clearNonPreterminals()
          Used by the decoder when it abandons a parse forest for a given sentence and is about to try again with a larger beam (beam-widening).
 CKYItem getNewItem()
          Returns a new chart item from the internal pool of reusable items.
protected  boolean outsideBeam(Item item, double topProb)
          Returns whether the specified chart item is outside the beam given the specified top log prob.
protected  void reclaimItemCollection(Collection c)
          A hook called by Chart.reclaimItemsInChart() to allow subclasses to reclaim each span's collection of chart items.
protected  void setUpItemPool()
          Sets up the item object pools.
 
Methods inherited from class danbikel.parser.Chart
add, clear, dontDoPruning, dontRelax, doPruning, get, getTopItem, getTopLogProb, numItems, postParseCleanup, prune, reclaimItem, reclaimItemsInChart, relax, resetTopLogProb, setPruneFactor, setSize, setSizeAndClear, toPrune
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

CKYChart

public CKYChart()
Constructs a new chart with the default chart size.


CKYChart

public CKYChart(int size)
Constructs a new chart with the specified chart size.

Parameters:
size - the initial size of this chart

CKYChart

public CKYChart(int cellLimit,
                double pruneFact)
Constructs a new chart with a default initial chart size, and with the specified cell limit and prune factor.

Parameters:
cellLimit - the limit to the number of items per cell
pruneFact - that log of the prune factor
See Also:
Chart.cellLimit, Chart.pruneFact

CKYChart

public CKYChart(int size,
                int cellLimit,
                double pruneFact)
Constructs a new chart with the specified initial chart size, cell limit and prune factor.

Parameters:
size - the initial size of this chart
cellLimit - the limit to the number of items per cell
pruneFact - that log of the prune factor
See Also:
Chart.cellLimit, Chart.pruneFact
Method Detail

clearNonPreterminals

public void clearNonPreterminals()
Used by the decoder when it abandons a parse forest for a given sentence and is about to try again with a larger beam (beam-widening).

See Also:
Settings.decoderMaxPruneFactor, Settings.decoderPruneFactorIncrement

outsideBeam

protected boolean outsideBeam(Item item,
                              double topProb)
Description copied from class: Chart
Returns whether the specified chart item is outside the beam given the specified top log prob.

Overrides:
outsideBeam in class Chart
Parameters:
item - the item to be tested for inclusion within the beam
topProb - the log prob of the top-ranked item for the specified item's span
Returns:
true if the specified item is outisde the beam given the specified top log prob, false otherwise

setUpItemPool

protected void setUpItemPool()
Description copied from class: Chart
Sets up the item object pools. This allows subclasses to specify the type of item to be held in the object pool.

Specified by:
setUpItemPool in class Chart

getNewItem

public CKYItem getNewItem()
Returns a new chart item from the internal pool of reusable items.

Returns:
a new chart item from the internal pool of reusable items.

reclaimItemCollection

protected void reclaimItemCollection(Collection c)
Description copied from class: Chart
A hook called by Chart.reclaimItemsInChart() to allow subclasses to reclaim each span's collection of chart items.

Specified by:
reclaimItemCollection in class Chart
Parameters:
c - the collection of chart items to be reclaimed

cellLimitShouldApplyTo

protected boolean cellLimitShouldApplyTo(Item item)
Returns true if the specified item has received its stop probabilities (that is, if item.stop() == true).

Specified by:
cellLimitShouldApplyTo in class Chart
Parameters:
item - the item to be tested
Returns:
whether cell limiting should apply to the specified item

Parsing Engine

Author: Dan Bikel.