|
Parsing Engine | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectdanbikel.parser.Chart
public abstract class Chart
Provides the skeletal infrastructure for a chart indexed by start and end words, as well as by arbitrary labels taken from the chart items.
Item
,
Serialized FormNested Class Summary | |
---|---|
protected static class |
Chart.Entry
Contains all information and items covering a particular span. |
Field Summary | |
---|---|
protected int |
cellLimit
The maximum number of items allowed in a cell (span) of this chart. |
protected Chart.Entry[][] |
chart
A chart is a two-dimensional array of maps, each of which maps Item objects to their logProbs. |
protected static boolean |
debugNumItemsGenerated
Indicats to keep track of the number of items generated by the decoder and print that information to System.err whenever reclaimItemsInChart() is invoked. |
protected static boolean |
debugNumPrunedItems
Indicats to keep track of the number of items pruned when parsing and print that information to System.err whenever reclaimItemsInChart() is invoked. |
protected ObjectPool |
itemPool
The pool of chart items, to be used by the decoder instead of constructing new chart items while decoding. |
protected int |
numPrePruned
The total number of items pre-pruned for a particular sentence, via calls to the toPrune(int,int,Item) method. |
protected int |
numPruned
The total number of items pruned during the parse of a particular sentence. |
protected double |
pruneFact
The natural log of the prune factor for this chart. |
protected boolean |
pruning
Indicates whether the chart is currently doing any pruning. |
protected boolean |
relax
Indicates whether to use a more relaxed form of pruning (wider beam in certain instances, to be determined by the concrete subclass). |
protected int |
size
The current size of the chart. |
protected int |
totalItems
The total number of items added to this chart for a particular sentence (between calls to clear() ). |
protected int |
totalItemsGenerated
The total number of items generated, that is, the total number of items that a decoder attempts to add to this chart (used for debugging). |
Constructor Summary | |
---|---|
protected |
Chart()
Constructs a new chart with the default chart size. |
protected |
Chart(int size)
Constructs a new chart with the specified chart size. |
protected |
Chart(int cellLimit,
double pruneFact)
Constructs a new chart with a default initial chart size, and with the specified cell limit and prune factor. |
protected |
Chart(int size,
int cellLimit,
double pruneFact)
Constructs a new chart with the specified initial chart size, cell limit and prune factor. |
Method Summary | |
---|---|
boolean |
add(int start,
int end,
Item item)
Adds the specified item covering the specified span to this chart. |
protected abstract boolean |
cellLimitShouldApplyTo(Item item)
Returns true if cell limiting should apply to the specified
item. |
void |
clear()
Checks every map of the chart covering a span less than or equal to size and clears it; if a chart entry is null , then a new
map is created. |
void |
dontDoPruning()
Tells this chart not to do any pruning. |
protected void |
dontRelax()
Tells this chart not to use a more relaxed form of pruning (the default behavior). |
void |
doPruning()
Indicates that the chart should prune. |
Iterator |
get(int start,
int end)
Returns an iterator over all chart items (having all labels) covering the specified span. |
Item |
getTopItem(int start,
int end)
Returns the item with the highest log probability covering the specified span, or null if this span has no items. |
double |
getTopLogProb(int start,
int end)
Returns the highest log probability of an item covering the specified span. |
int |
numItems(int start,
int end)
Returns the number of chart items covering the specified span. |
protected boolean |
outsideBeam(Item item,
double topProb)
Returns whether the specified chart item is outside the beam given the specified top log prob. |
void |
postParseCleanup()
Called by Decoder.parse after parsing has finished for a
particular sentence. |
void |
prune(int start,
int end)
Prunes away items in the specified span that are either below the probability threshold of the top-ranked item for that span, or are outside the cell limit, if one has been specified. |
protected void |
reclaimItem(Item item)
Reclaims this chart item. |
protected abstract void |
reclaimItemCollection(Collection c)
A hook called by reclaimItemsInChart() to allow subclasses
to reclaim each span's collection of chart items. |
protected void |
reclaimItemsInChart()
Reclaims all items currently in the chart. |
protected void |
relax()
Tells this chart to use a more relaxed form of pruning (for example, a wider beam in certain circumstances). |
void |
resetTopLogProb(int start,
int end)
Resets the highest log probability of the specified span to be Constants.logOfZero . |
void |
setPruneFactor(double pruneFact)
Sets the prune factor. |
void |
setSize(int size)
Ensures that the size of the chart is at least as large as the specified size. |
void |
setSizeAndClear(int size)
Sets this chart to be the specified size and clears it for parsing sentences of length less than or equal to the specified size. |
protected abstract void |
setUpItemPool()
Sets up the item object pools. |
protected boolean |
toPrune(int start,
int end,
Item item)
Returns true if the specified chart item should not
be added to the specified set of items because its probability is not
within pruneFact of the highest-ranked item. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected static final boolean debugNumPrunedItems
System.err
whenever reclaimItemsInChart()
is invoked.
protected static final boolean debugNumItemsGenerated
System.err
whenever reclaimItemsInChart()
is invoked.
protected Chart.Entry[][] chart
Chart.Entry
objects, each of which contains one
such map, as well as a data member that stores the top log probability of
all the items covering the span of the chart entry.
Chart.Entry
protected int size
setSizeAndClear(int)
protected int cellLimit
Settings.decoderUseCellLimit
protected double pruneFact
protected boolean relax
protected int totalItems
clear()
).
protected transient ObjectPool itemPool
protected int totalItemsGenerated
protected int numPruned
prune(int,int)
method for
that span. The value of this data member after parsing is complete
will reflect the total number of items pruned via calls to this method.
prune(int,int)
protected int numPrePruned
toPrune(int,int,Item)
method.
toPrune(int,int,Item)
protected boolean pruning
doPruning()
,
dontDoPruning()
Constructor Detail |
---|
protected Chart()
protected Chart(int size)
size
- the initial size of this chartprotected Chart(int cellLimit, double pruneFact)
cellLimit
- the limit to the number of items per cellpruneFact
- that log of the prune factorcellLimit
,
pruneFact
protected Chart(int size, int cellLimit, double pruneFact)
size
- the initial size of this chartcellLimit
- the limit to the number of items per cellpruneFact
- that log of the prune factorcellLimit
,
pruneFact
Method Detail |
---|
public void setSizeAndClear(int size)
setSize(size)
and then clear()
.
size
- the size to be set for this chartpublic void setSize(int size)
size
- the size to be set for this chartpublic void clear()
null
, then a new
map is created.
protected void relax()
protected void dontRelax()
relax()
protected boolean outsideBeam(Item item, double topProb)
item
- the item to be tested for inclusion within the beamtopProb
- the log prob of the top-ranked item for the specified item's
span
protected boolean toPrune(int start, int end, Item item)
true
if the specified chart item should not
be added to the specified set of items because its probability is not
within pruneFact
of the highest-ranked item. This method is
guaranteed to be called by add(int,int,Item)
when a sorted set
of chart items already exists (and hence contains at least one chart
item).
start
- the start of the span for the specified itemend
- the end of the span for the specified itemitem
- the item being added to items
true
if the specified chart item should not
be added to the set of items covering the specified spanpublic void prune(int start, int end)
start
- the start of the span in which to prune chart itemsend
- the end of the span in which to prune chart itemscellLimit
,
pruneFact
protected abstract boolean cellLimitShouldApplyTo(Item item)
true
if cell limiting should apply to the specified
item.
item
- the item to be tested
public boolean add(int start, int end, Item item)
Caution: By convention, the caller is responsible for reclaiming
unadded chart items (via reclaimItem(Item)
). However, in the
case where an old item is removed from the chart because a new,
equivalent item has a greater probability, this method does not
immediately reclaim the old item, but rather marks it as "garbage",
via its setGarbage
method. This
behvaior is to prevent the following case. Suppose that the behavior
of this method were to reclaim such "booted" chart items
immediately. Imagine that the caller is attempting to add a
collection of chart items, and that an item in that collection was
added, but then was removed due to a subsequent, equivalent item in
the same collection having greater probability. In this case, the
caller would have no way to know that the previous item in its
collection had been silently reclaimed, so that if it operated over
that collection again, there would be a garbage item that, as
far as it knew, had been added and was still in the chart. By
marking such "booted" items as garbage instead of immediately
reclaiming them, callers can check for items' garbage status when
they repeatedly operate over collections of "added" items.
start
- the index of the first word in the span covered by
item
end
- the index of the last word in the span covered by
item
item
- the item to be added to this chart
true
if item
was added to the
chart, false
otherwisepublic double getTopLogProb(int start, int end)
start
- the start of the span for which to get the top log probend
- the end of the span for which to get the top log prob
public Item getTopItem(int start, int end)
null
if this span has no items.
start
- the start of the span for which to get the top-ranked itemend
- the end of the span for which to get the top-ranked item
public void resetTopLogProb(int start, int end)
Constants.logOfZero
.
start
- the beginning of the span whose highest log prob is to be
resetend
- the end of the span whose highest log prob is to be
resetpublic int numItems(int start, int end)
start
- the start of the span for which to retrieve the number of
itemsend
- the end of the span for which to retrieve the number of items
public Iterator get(int start, int end)
UnsupportedOperationException
will be thrown if
its remove
method is invoked.
start
- the start index of the span for which to get all itemsend
- the end index of the span for which to get all items
protected void reclaimItem(Item item)
item
- the item to be reclaimedpublic void postParseCleanup()
Decoder.parse
after parsing has finished for a
particular sentence. This default implementation simply calls
reclaimItemsInChart()
.
protected void reclaimItemsInChart()
public void setPruneFactor(double pruneFact)
public void doPruning()
public void dontDoPruning()
protected abstract void reclaimItemCollection(Collection c)
reclaimItemsInChart()
to allow subclasses
to reclaim each span's collection of chart items.
c
- the collection of chart items to be reclaimedprotected abstract void setUpItemPool()
|
Parsing Engine | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |