ParsingChart - Parsing chart structure module
[Syntactic tools level]

Definition and handling of parsing chart data structure. More...

Data Structures

struct  NTItemList
 Non-terminal item list. More...
struct  NTItemDerivationList
 Non-terminal item derivation list. More...
struct  PrefixItemList
 Prefix item list. More...
struct  PrefixItemDerivationList
 Prefix item derivation list. More...
struct  ParsingChartCell
 Parsing chart cell. More...
struct  SentenceCut
 Sentence cutting out. More...
struct  ParsingChart
 Parsing chart. More...
struct  ParsingChartBasis
 Parsing chart basis. More...

Defines

#define MAX_COUNTER_VALUE   ULONG_MAX
 Maximum value at which a Counter value can be set.
#define COUNTER_FMT   "%lu"
 Format specification required to print a Counter value.
#define SENTENCE_CUT_ALLOC_INCREMENT   30
 Number of add elements during a SentenceCut (re)allocation.
#define NT_ITEM_DERIVATION   ((char) 1)
 The value used by ntItemListExploreSubtree to indicate the non-terminal item derivation type.
#define PREFIX_ITEM_DERIVATION   ((char) 2)
 The value used by ntItemListExploreSubtree to indicate the prefix item derivation type.
#define NO_RULE   0
 Ordinal code that identifies the nonexistence of syntactic rule.
#define CHART_CELL(chart, row, column)
 Get a specified parsing chart cell.

Typedefs

typedef unsigned long Counter
 Interpretation counter type.

Functions

void sentenceCutEnlarge (SentenceCut **sentence_cut, size_t *current_size, size_t *allocated_size)
void ntItemListAddUnknownWord (NTItemList **nt_item_list, const unsigned int column, const unsigned int row, const Lexicon *lexicon, const Weight correction_cost, const double equality_ratio)
gboolean ntItemDerivationFollowsPrefixItem (const NTItemDerivationList *nt_item_derivation, const PrefixItemList *prefix_item, const Grammar *grammar, const TreeNode **node)
void parsingChartBasisGetGraphy (const ParsingChartBasis *item, const ParsingChart *chart, GString *buffer)
ParsingChart * parsingChartCreate (const size_t size, const Grammar *used_grammar, const char *sentence, SentenceCut *cutting)
LexicalEntryIndex ntItemDerivationGetNT (const NTItemDerivationList *nt_item_derivation, const Grammar *grammar)
gboolean ntItemDerivationIsRightPart (const NTItemDerivationList *nt_item_derivation, const Grammar *grammar, TreeNode **node)
NTItemList * ntItemListCreate ()
PrefixItemList * prefixItemListCreate (const TreeNode *node)
void ntItemListFree (NTItemList **nt_item_list)
void prefixItemListFree (PrefixItemList **prefix_item_list)
void parsingChartFree (ParsingChart **chart)
size_t parsingChartGetMemorySize (const ParsingChart *chart)
gboolean parsingChartCellContainsNT (const ParsingChart *chart, const char *non_terminal, const unsigned int row, const unsigned int column)
gboolean parsingChartCellContainsP (const ParsingChart *chart, const unsigned int row, const unsigned int column)
void ntItemListExploreSubtree (const NTItemList *nt_item_list, const ParsingChart *chart, PointerStack *context, CharStack *type, Probability *probability, ParsingResult *output)
Probability ntItemDerivationListGetMaxProbability (const NTItemDerivationList *nt_item_derivation, const Grammar *grammar)
Probability prefixItemDerivationListGetMaxProbability (const PrefixItemDerivationList *prefix_item_derivation)
Probability ntItemDerivationListGetSumProbability (const NTItemDerivationList *nt_item_derivation, const Grammar *grammar)
Probability prefixItemDerivationListGetSumProbability (const PrefixItemDerivationList *prefix_item_derivation)
void ntItemListExtractMostProbableSubtree (NTItemList *list, const ParsingChart *chart, ParsingResult *output)
void ntItemListAddPOSFromWord (NTItemList **nt_item_list, const unsigned int column, const unsigned int row, const Lexicon *lexicon, const UniqId id, const Weight correction_cost, const double equality_ratio)
void ntItemListAddLexicalizedItem (NTItemList **nt_item_list, const unsigned int column, const unsigned int row, const Grammar *grammar, const UniqId uid, const Weight correction_cost)
int ntItemDerivationDisplay (const NTItemDerivationList *nt_item_derivation, const ParsingChart *chart, ParsingResult *output)
void ntItemListAddLexicalDerivation (NTItemList **nt_item_list, const unsigned int column, const unsigned int row, const LexicalEntryIndex graphy_identifier, const int part_of_speech, const Weight correction_cost, const Probability probability, const double equality_ratio)

Detailed Description

Definition and handling of parsing chart data structure.

SlpTK Library 0.6.0

Required header
<parsingchart.h>
Author:
Jean-Cedric Chappelier (creation on 11.04.1997)

Antonin Merçay (revision on 20.01.2005)

Date:
2 March 2005
Version:
0.6.0

Define Documentation

#define CHART_CELL ( chart,
row,
column   ) 

Get a specified parsing chart cell.

Return the parsing chart cell indexed by a given row index (from 1 to chart->chart_size) and column index (from 1 to chart->chart_size - row + 1)

See also:
ParsingChart

Function Documentation

int ntItemDerivationDisplay ( const NTItemDerivationList *  nt_item_derivation,
const ParsingChart *  chart,
ParsingResult *  output 
)

Output informations relative to a non-terminal item derivation in several result formats. Only the assigned fields of output parameter are considered, i.e. unassigned ParsingResult fields are not treated

Parameters:
[in] nt_item_derivation The non-terminal item derivation to display
[in] chart The source parsing chart
[out] output The structure where to output
Returns:
The left character shifting required by the subsequent result display
Former(s) function(s):
Affiche_Element_L1

gboolean ntItemDerivationFollowsPrefixItem ( const NTItemDerivationList *  nt_item_derivation,
const PrefixItemList *  prefix_item,
const Grammar *  grammar,
const TreeNode **  node 
)

Check if a given non-terminal item derivation corresponds to a syntactic rule right part of a given prefix item derivation. If it's the case, the tree node argument provided is set to the corresponding position in the rules tree.

Parameters:
[in] nt_item_derivation The non-terminal derivation to consider
[in] prefix_item The prefix item to consider
[in] grammar The source grammar
[out] node The tree node to set
Returns:
TRUE if the checked condition is met, FALSE otherwise
Former(s) function(s):
L1_est_suivant_de_L2

LexicalEntryIndex ntItemDerivationGetNT ( const NTItemDerivationList *  nt_item_derivation,
const Grammar *  grammar 
)

Return the non-terminal associated to non-terminal item derivation

Parameters:
[in] nt_item_derivation The input derivation
[in] grammar The source grammar
Returns:
The internal ordinal code of the searched non-terminal
Former(s) function(s):
Recupere_NT

gboolean ntItemDerivationIsRightPart ( const NTItemDerivationList *  nt_item_derivation,
const Grammar *  grammar,
TreeNode **  node 
)

Check if an item non-terminal item derivation corresponds to the right part of a syntactic rule. If it's the case, set the given node to the corresponding position in the rule left part tree. Otherwise, set the node to NULL.

Parameters:
[in] nt_item_derivation The item derivation to consider
[in] grammar The source grammar
[out] node The grammar rules tree node to set
Returns:
TRUE if the checked condition is met, FALSE otherwise
Former(s) function(s):
est_partie_droite

Probability ntItemDerivationListGetMaxProbability ( const NTItemDerivationList *  nt_item_derivation,
const Grammar *  grammar 
)

Compute the maximal probability associated to a non-terminal item derivation

Parameters:
[in] nt_item_derivation The non-terminal item derivation to consider
[in] grammar The source grammar
Returns:
The associated maximal probability
See also:
ntItemDerivationListGetSumProbability()
Former(s) function(s):
Proba_Max_Element_L1

Probability ntItemDerivationListGetSumProbability ( const NTItemDerivationList *  nt_item_derivation,
const Grammar *  grammar 
)

Compute the sum of the probability associated to a non-terminal item derivation

Parameters:
[in] nt_item_derivation The non-terminal item derivation to consider
[in] grammar The source grammar
Returns:
The associated sum of probabilities
See also:
ntItemDerivationListGetMaxProbability()
Former(s) function(s):
Proba_Somme_Element_L1

void ntItemListAddLexicalDerivation ( NTItemList **  nt_item_list,
const unsigned int  column,
const unsigned int  row,
const LexicalEntryIndex  graphy_identifier,
const int  part_of_speech,
const Weight  correction_cost,
const Probability  probability,
const double  equality_ratio 
)

Add a lexical derivation to a non-terminal item list. The function associates information about new lexical element to a given parsing chart cell

Parameters:
[out] nt_item_list The non-terminal item list where to add
[in] column The considered parsing chart column
[in] row The considered parsing chart row
[in] graphy_identifier The unique graphy identifier of the added derivation
[in] part_of_speech The part of speech index of the added derivation
[in] correction_cost The correction cost between the original sentence and the added lexical element
[in] probability The probability of the added derivation
[in] equality_ratio The ratio used to compare interpretation probabilities equality
See also:
ntItemListAddPOSFromWord() ntItemListAddLexicalizedItem()
Former(s) function(s):
Ajoute_Une_Cms_L1

void ntItemListAddLexicalizedItem ( NTItemList **  nt_item_list,
const unsigned int  column,
const unsigned int  row,
const Grammar *  grammar,
const UniqId  uid,
const Weight  correction_cost 
)

Add a lexicalized item (rule non-terminal which is in fact a vocabulary word) to a non-terminal item list. This function add a unique fictitious non-terminal that only matches with the considered word graphy

Parameters:
[in] nt_item_list The non-terminal item list where to add
[in] column The considered parsing chart column
[in] row The considered parsing chart row
[in] grammar The source grammar
[in] uid The uniq id of the word in the vocabulary lexicon
[in] correction_cost The correction cost between the added string and the original sentence
See also:
ntItemListAddLexicalDerivation() ntItemListAddPOSFromWord()
Former(s) function(s):
partiellement_lexical

void ntItemListAddPOSFromWord ( NTItemList **  nt_item_list,
const unsigned int  column,
const unsigned int  row,
const Lexicon *  lexicon,
const UniqId  id,
const Weight  correction_cost,
const double  equality_ratio 
)

Add to a non-terminal item list all the parts of speech associated to a given string (i.e. graphy)

Parameters:
[in] nt_item_list The non-terminal item list where to add
[in] column The considered parsing chart column
[in] row The considered parsing chart row
[in] lexicon The source vocabulary lexicon
[in] id The lexicon index of the provided string
[in] correction_cost The correction cost between the provided string and the original sentence
[in] equality_ratio The ratio used to compare interpretation probabilities equality
See also:
ntItemListAddLexicalDerivation() ntItemListAddLexicalizedItem()
Former(s) function(s):
ajoute_chaine_lexicale_L1

void ntItemListAddUnknownWord ( NTItemList **  nt_item_list,
const unsigned int  column,
const unsigned int  row,
const Lexicon *  lexicon,
const Weight  correction_cost,
const double  equality_ratio 
)

Add all the open parts of speech to a non-terminal item list with the purpose of resolving an unknown word

Parameters:
[in] nt_item_list The considered non-terminal item list
[in] column The parsing chart column
[in] row The parsing chart row
[in] lexicon The source vocabulary lexicon
[in] correction_cost The arbitrary lexical correction cost
Todo:
correction_cost definition to validate
Parameters:
[in] equality_ratio The ratio used to compare interpretation probabilities equality
Former(s) function(s):
ajoute_mot_inconnu_L1

NTItemList * ntItemListCreate (  ) 

Instantiate and initialize a new non-terminal item list

Returns:
The created non-terminal item list
See also:
prefixItemListCreate()
Former(s) function(s):
cree_new_liste_L1

void ntItemListExploreSubtree ( const NTItemList *  nt_item_list,
const ParsingChart *  chart,
PointerStack *  context,
CharStack *  type,
Probability *  probability,
ParsingResult *  output 
)

Extract the next subtree stored by non-terminal item list. When iteratively called, this function allows to explore all the analysis tree stored by a parsing chart. Two provided stacks stores the informations about the next available tree:

Remarks:
If the result in the form of brick list is required by the output parameter, this function may allocates a string (Brick::original_word) that must be freed once this information is not more necessary
Parameters:
[in] nt_item_list The starting non-terminal item list
[in] chart les infos néssaires relatives à la phrase
[in] context The stack of items used to save exploring state
[in] type The stack of item types used to save exploring state
[out] probability The probability of the extracted subtree
[out] output The parsing result where to output
See also:
ntItemDerivationDisplay()
Former(s) function(s):
parcours_iteratif_sous_arbre_L1

void ntItemListExtractMostProbableSubtree ( NTItemList *  list,
const ParsingChart *  chart,
ParsingResult *  output 
)

Extract the most probable analysis subtree stored by a non-terminal item list

Remarks:
If the result in the form of brick list is required by the output parameter, this function may allocates a string (Brick::original_word) that must be freed once this information is not more necessary
Parameters:
[in] list The starting non-terminal item list
[in] chart The source parsing chart
[out] output The structure where to output
See also:
ntItemListExploreSubtree()
Former(s) function(s):
extrait_plus_probable_sous_arbre_L1

void ntItemListFree ( NTItemList **  nt_item_list  ) 

Free the memory allocated to a non-terminal item list (destructor)

Parameters:
[in] nt_item_list The non-terminal item list to free
See also:
ntItemListCreate()
Former(s) function(s):
libere_liste_L1

void parsingChartBasisGetGraphy ( const ParsingChartBasis *  item,
const ParsingChart *  chart,
GString *  buffer 
)

Extract the sentence sequence associated to a parsing chart basis

Parameters:
[in] item The cell to consider
[in] chart The source parsing chart
[out] buffer The string buffer where to output
See also:
ntItemDerivationDisplay()
Former(s) function(s):
get_mot

gboolean parsingChartCellContainsNT ( const ParsingChart *  chart,
const char *  non_terminal,
const unsigned int  row,
const unsigned int  column 
)

Check if a parsing chart cell contains a given non-terminal

Parameters:
[in] chart The parsing chart to consider
[in] non_terminal The searched non-terminal
[in] row The row index of the parsing chart (from 1 to size)
[in] column The column index of the parsing chart (from 1 to size - row + 1)
Returns:
The check condition is met (TRUE) or not (FALSE)
See also:
parsingChartCellContainsP()
Former(s) function(s):
Case_Contient_NT

gboolean parsingChartCellContainsP ( const ParsingChart *  chart,
const unsigned int  row,
const unsigned int  column 
)

Check if a parsing chart cell contains the top level non-terminal

Parameters:
[in] chart The parsing chart to consider
[in] row The row index of the parsing chart (from 1 to size)
[in] column The column index of the parsing chart (from 1 to size - row + 1)
Returns:
The check condition is met (TRUE) or not (FALSE)
See also:
parsingChartCellContainsNT()
Former(s) function(s):
Case_Contient_P

ParsingChart * parsingChartCreate ( const size_t  size,
const Grammar *  used_grammar,
const char *  sentence,
SentenceCut *  cutting 
)

Instantiate and initialize a new parsing chart

Parameters:
[in] size The number of line and column of the chart
[in] used_grammar The grammar to use to fill the chart
[in] sentence The sentence to be analyzed by the chart
[in] cutting The cutting of the sentence
Returns:
The created parsing chart
See also:
parsingChartFree()
Former(s) function(s):
Cree_Table_Cyk

void parsingChartFree ( ParsingChart **  chart  ) 

Free the memory allocated to a parsing chart (parsing chart destructor). The ParsingChart::cells and ParsingChart::cutting fields are desallocates, but not ParsingChart::sentence and ParsingChart::grammar.

Parameters:
[in] chart The parsing chart to free
See also:
parsingChartCreate()
Former(s) function(s):
Libere_Table_CYK

size_t parsingChartGetMemorySize ( const ParsingChart *  chart  ) 

Return the memory size allocated to parsing chart

Parameters:
[in] chart The parsing chart to consider
Returns:
The memory size in bytes
Former(s) function(s):
Taille_Table_CYK

Probability prefixItemDerivationListGetMaxProbability ( const PrefixItemDerivationList *  prefix_item_derivation  ) 

Computes the maximal probability associated to a prefix item derivation

Parameters:
[in] prefix_item_derivation The prefix item derivation to consider
Returns:
The associated maximal probability
See also:
prefixItemDerivationListGetSumProbability()
Former(s) function(s):
Proba_Max_Element_L2

Probability prefixItemDerivationListGetSumProbability ( const PrefixItemDerivationList *  prefix_item_derivation  ) 

Compute the sum of the probabilities associated to a prefix item derivation

Parameters:
[in] prefix_item_derivation The prefix item derivation to consider
Returns:
The associated sum of probabilities
See also:
prefixItemDerivationListGetMaxProbability()
Former(s) function(s):
Proba_Somme_Element_L2

PrefixItemList * prefixItemListCreate ( const TreeNode *  node  ) 

Instantiate and initialize a new prefix item list

Parameters:
[in] node The value of the associated grammar node
Returns:
The created prefix item list
See also:
ntItemListCreate()
Former(s) function(s):
cree_new_liste_L2

void prefixItemListFree ( PrefixItemList **  prefix_item_list  ) 

Free the memory allocated to a prefix item list (destructor)

Parameters:
[in] prefix_item_list The prefix item list to free
See also:
prefixItemListCreate()
Former(s) function(s):
libere_liste_L2

void sentenceCutEnlarge ( SentenceCut **  sentence_cut,
size_t *  current_size,
size_t *  allocated_size 
)

Enlarge from one element the size of a sentence cutting

Remarks:
If the size of the sentence cutting before the operation is equal to the allocated size, the solution set is reallocated
Parameters:
sentence_cut The sentence cutting set to enlarge
current_size The number of elements currently used (incremented after function completion)
allocated_size The number of elements currently allocated (may be increased after function completion)
Former(s) function(s):
augmente_decoup

Generated on Thu Mar 22 17:46:31 2007 for SlpTk by  doxygen 1.4.7