Edinburgh Speech Tools 2.4-release
 
Loading...
Searching...
No Matches
EST_SCFG_Chart.h
1/*************************************************************************/
2/* */
3/* Centre for Speech Technology Research */
4/* University of Edinburgh, UK */
5/* Copyright (c) 1997 */
6/* All Rights Reserved. */
7/* */
8/* Permission is hereby granted, free of charge, to use and distribute */
9/* this software and its documentation without restriction, including */
10/* without limitation the rights to use, copy, modify, merge, publish, */
11/* distribute, sublicense, and/or sell copies of this work, and to */
12/* permit persons to whom this work is furnished to do so, subject to */
13/* the following conditions: */
14/* 1. The code must retain the above copyright notice, this list of */
15/* conditions and the following disclaimer. */
16/* 2. Any modifications must be clearly marked as such. */
17/* 3. Original authors' names are not deleted. */
18/* 4. The authors' names are not used to endorse or promote products */
19/* derived from this software without specific prior written */
20/* permission. */
21/* */
22/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30/* THIS SOFTWARE. */
31/* */
32/*************************************************************************/
33/* Author : Alan W Black */
34/* Date : June 1997 */
35/*-----------------------------------------------------------------------*/
36/* */
37/* A SCFG chart parser, general functions */
38/* */
39/*=======================================================================*/
40#ifndef __EST_SCFG_CHART_H__
41#define __EST_SCFG_CHART_H__
42
43#include "EST_String.h"
44#include "EST_simplestats.h"
45#include "EST_string_aux.h"
46#include "EST_SCFG.h"
47#include "ling_class/EST_Relation.h"
48
50
51/** An internal class for \Ref{EST_SCFG_Chart} for representing edges
52 in the chart during parsing with SCFGs.
53
54 A standard Earley type chart edge, with representations for two
55 daughters and a position or what has been recognised. A probability
56 is also included.
57*/
59 private:
60 int p_d1;
61 int p_d2;
62 int p_pos;
63 double p_prob;
64 public:
65 /**@name Constructor and initialisation functions */
66 //@{
68 EST_SCFG_Chart_Edge(double prob, int d1, int d2, int pos);
70 //@}
71
72 /// Postion, 0 1 or 2, where 0 is empty, 1 is incomplete 2 is complete.
73 int pos(void) { return p_pos; }
74 /// Edge probability
75 double prob(void) { return p_prob; }
76 /// (Non)terminal of daughter 1
77 int d1() { return p_d1; }
78 /// (Non)terminal of daughter 2
79 int d2() { return p_d2; }
80
81};
82
83/** A class for parsing with a probabilistic grammars.
84
85 The chart (sort of closer to CKY table) consists of indexes of
86 edges indexed by vertex number of mother non-terminal.
87
88 The initial values (well-formed substring table) are taken from
89 an \Ref{EST_Stream} with a given feature. The grammar may be
90 specified as LISP rules or as an already constructed \Ref{EST_SCFG}.
91
92 This produces a single best parse. It treats the grammar as
93 strictly context free in that the probability of a nonterminal
94 over vertex n to m, is the sum of all the possible analyses
95 of that sub-tree. Only the best analysis is kept for the
96 resulting parse tree.
97
98 @author Alan W Black (awb@cstr.ed.ac.uk): October 1997
99*/
101 private:
102 /// pointer to grammar
103 EST_SCFG *grammar;
104 /// TRUE is grammar was created internally, FALSE is can't be freed
105 int grammar_local;
106 /// Number of vertices (number of words + 1)
107 int n_vertices;
108 /// Index of edges by vertex start x vertex end x nonterminal
109 EST_SCFG_Chart_Edge ****edges;
110 /// Index of basic symbols indexed by (start) vertex.
111 EST_SCFG_Chart_Edge **wfst;
112 /// An empty edge, denotes 0 probability edge.
113 EST_SCFG_Chart_Edge *emptyedge;
114
115 // Find the best analysis of nonterminal {\tt p} from {\tt start}
116 // to {\tt end}. Used after parsing
117 double find_best_tree(int start,int end,int p)
119 if ((r=edges[start][end][p]) != 0) return r->prob();
120 else return find_best_tree_cal(start,end,p); }
121 // Calculate best tree/probability
122 double find_best_tree_cal(int start,int end,int p);
123 void setup_edge_table();
124 void delete_edge_table();
125 LISP print_edge(int start, int end, int name, EST_SCFG_Chart_Edge *e);
126 // Extract edge from chart and add it to stream
127 void extract_edge(int start, int end, int p,
129 EST_Item *s,
130 EST_Item **word);
131 // Build parse from distinguished symbol alone
132 void extract_forced_parse(int start, int end, EST_Item *s, EST_Item *w);
133 public:
134 /**@name Constructor and initialisation functions */
135 //@{
138 //@}
139
140 /**@name Grammar and parse string initialisation functions */
141 //@{
142 /// Initialize from LISP rules set
143 void set_grammar_rules(LISP r);
144 /// Initialize from existing \Ref{EST_SCFG} grammar
145 void set_grammar_rules(EST_SCFG &grammar);
146 /** Initialize for parsing from relation using {\tt name} feature
147 setting up the "Well Formed Substring Table" */
148 void setup_wfst(EST_Relation *s,const EST_String &name="name");
149 /** Initialize for parsing from s to e using {\tt name} feature
150 setting up the "Well Formed Substring Table" */
151 void setup_wfst(EST_Item *s, EST_Item *e,const EST_String &name="name");
152 //@}
153
154 /**@name parsing functions */
155 //@{
156 /// Parses the loaded WFST with the loaded grammar.
157 void parse();
158 /// Return the parse in full LISP form.
159 LISP find_parse();
160 /// Extract parse tree and add it to syn linking leafs to word
161 void extract_parse(EST_Relation *syn,EST_Relation *word,int force=0);
162 /// Extract parse tree and add it to syn linking leafs to items s to e
163 void extract_parse(EST_Relation *syn,EST_Item *s,
164 EST_Item *e,int force=0);
165 //@}
166};
167
168/** Build a relation from a LISP list of items.
169*/
170void EST_SCFG_chart_load_relation(EST_Relation *s,LISP sent);
171
172/** Parse a given string using the given grammar.
173*/
174LISP scfg_parse(LISP string,LISP grammar);
175/** Parse the given string using the given \Ref{EST_SCFG}.
176*/
177LISP scfg_parse(LISP string,EST_SCFG &grammar);
178/** Parse named features in (list) relation Word into (tree)
179 ** relation Syntax
180 */
181void scfg_parse(class EST_Relation *Word, const EST_String &name,
182 class EST_Relation *Syntax, EST_SCFG &grammar);
183
184#endif
int pos(void)
Postion, 0 1 or 2, where 0 is empty, 1 is incomplete 2 is complete.
double prob(void)
Edge probability.
int d1()
(Non)terminal of daughter 1
int d2()
(Non)terminal of daughter 2
void extract_parse(EST_Relation *syn, EST_Relation *word, int force=0)
Extract parse tree and add it to syn linking leafs to word.
void setup_wfst(EST_Relation *s, const EST_String &name="name")
void parse()
Parses the loaded WFST with the loaded grammar.
LISP find_parse()
Return the parse in full LISP form.
void set_grammar_rules(LISP r)
Initialize from LISP rules set.