1 /*************************************************************************/
2 /* Copyright (c) 2004 */
3 /* Daniel Sleator, David Temperley, and John Lafferty */
4 /* Copyright (c) 2013 Linas Vepstas */
5 /* All rights reserved */
6 /* */
7 /* Use of the link grammar parsing system is subject to the terms of the */
8 /* license set forth in the LICENSE file included with this software. */
9 /* This license allows free redistribution and use in source and binary */
10 /* forms, with or without modification, subject to certain conditions. */
11 /* */
12 /*************************************************************************/
13
14 /* stuff for transforming a dictionary entry into a disjunct list */
15
16 #include "build-disjuncts.h"
17 #include "connectors.h"
18 #include "dict-common/dict-structures.h" // Exp_struct, lg_exp_stringify
19 #include "dict-common/dict-common.h" // Dictionary
20 #include "disjunct-utils.h"
21 #include "utilities.h"
22
23 /* Temporary connectors used while converting expressions into disjunct lists */
24 typedef struct Tconnector_struct Tconnector;
25 struct Tconnector_struct
26 {
27 Tconnector * next;
28 const Exp *e; /* a CONNECTOR_type element from which to get the connector */
29 int exp_pos; /* the position in the originating expression */
30 };
31
32 typedef struct clause_struct Clause;
33 struct clause_struct
34 {
35 Clause * next;
36 double cost;
37 double maxcost;
38 Tconnector * c;
39 };
40
41 typedef struct
42 {
43 double cost_cutoff;
44 Pool_desc *Tconnector_pool;
45 Pool_desc *Clause_pool;
46 int exp_pos;
47 } clause_context;
48
49 #ifdef DEBUG
50 static void print_Tconnector_list(Tconnector * e);
51 static void print_clause_list(Clause * c);
52 #endif
53
54 #if BUILD_DISJUNCTS_FREE_INETERMEDIATE_MEMOEY /* Undefined - CPU overhead. */
free_Tconnectors(Tconnector * e,Pool_desc * mp)55 static void free_Tconnectors(Tconnector *e, Pool_desc *mp)
56 {
57 Tconnector * n;
58 for(;e != NULL; e=n)
59 {
60 n = e->next;
61 pool_free(mp, e);
62 }
63 }
64
free_clause_list(Clause * c,clause_context * ct)65 static void free_clause_list(Clause *c, clause_context *ct)
66 {
67 Clause *c1;
68 while (c != NULL)
69 {
70 c1 = c->next;
71 free_Tconnectors(c->c, ct->Tconnector_pool);
72 pool_free(ct->Clause_pool, c);
73 c = c1;
74 }
75 }
76 #endif
77
78 #if 0 /* old stuff */
79 /**
80 * reverse the order of the list e. destructive
81 */
82 static Tconnector * Treverse(Tconnector *e)
83 {
84 Tconnector * head, *x;
85 head = NULL;
86 while (e != NULL) {
87 x = e->next;
88 e->next = head;
89 head = e;
90 e = x;
91 }
92 return head;
93 }
94
95 /**
96 * reverse the order of the list e. destructive
97 */
98 static Connector * reverse(Connector *e)
99 {
100 Connector * head, *x;
101 head = NULL;
102 while (e != NULL) {
103 x = e->next;
104 e->next = head;
105 head = e;
106 e = x;
107 }
108 return head;
109 }
110 #endif
111
112 /**
113 * Builds a new list of connectors that is the catenation of e1 with e2.
114 * does not effect lists e1 or e2. Order is maintained.
115 */
catenate(Tconnector * e1,Tconnector * e2,Pool_desc * tp)116 static Tconnector * catenate(Tconnector * e1, Tconnector * e2, Pool_desc *tp)
117 {
118 Tconnector head;
119 Tconnector *preve = &head;
120 Tconnector *newe = &head;
121
122 for (;e1 != NULL; e1 = e1->next)
123 {
124 newe = pool_alloc(tp);
125 *newe = *e1;
126
127 preve->next = newe;
128 preve = newe;
129 }
130 for (;e2 != NULL; e2 = e2->next)
131 {
132 newe = pool_alloc(tp);
133 *newe = *e2;
134
135 preve->next = newe;
136 preve = newe;
137 }
138
139 newe->next = NULL;
140 return head.next;
141 }
142
143 /**
144 * build the connector for the terminal node n
145 */
build_terminal(Exp * e,clause_context * ct)146 static Tconnector * build_terminal(Exp *e, clause_context *ct)
147 {
148 Tconnector *c = pool_alloc(ct->Tconnector_pool);
149 c->e = e;
150 c->next = NULL;
151 c->exp_pos = ct->exp_pos++;
152 return c;
153 }
154
155 /**
156 * Build the clause for the expression e. Does not change e
157 */
build_clause(Exp * e,clause_context * ct)158 static Clause * build_clause(Exp *e, clause_context *ct)
159 {
160 Clause *c = NULL, *c1, *c2, *c3, *c4, *c_head;
161
162 assert(e != NULL, "build_clause called with null parameter");
163 if (e->type == AND_type)
164 {
165 c1 = pool_alloc(ct->Clause_pool);
166 c1->c = NULL;
167 c1->next = NULL;
168 c1->cost = 0.0;
169 c1->maxcost = 0.0;
170 for (Exp *opd = e->operand_first; opd != NULL; opd = opd->operand_next)
171 {
172 c2 = build_clause(opd, ct);
173 c_head = NULL;
174 for (c3 = c1; c3 != NULL; c3 = c3->next)
175 {
176 for (c4 = c2; c4 != NULL; c4 = c4->next)
177 {
178 double maxcost = MAX(c3->maxcost,c4->maxcost);
179 if (maxcost + e->cost > ct->cost_cutoff) continue;
180
181 c = pool_alloc(ct->Clause_pool);
182 c->cost = c3->cost + c4->cost;
183 c->maxcost = maxcost;
184 c->c = catenate(c3->c, c4->c, ct->Tconnector_pool);
185 c->next = c_head;
186 c_head = c;
187 }
188 }
189 #if BUILD_DISJUNCTS_FREE_INETERMEDIATE_MEMOEY /* Undefined - CPU overhead. */
190 free_clause_list(c1, ct);
191 free_clause_list(c2, ct);
192 #endif
193 c1 = c_head;
194 }
195 c = c1;
196 }
197 else if (e->type == OR_type)
198 {
199 c = build_clause(e->operand_first, ct);
200 /* we'll catenate the lists of clauses */
201 for (Exp *opd = e->operand_first->operand_next; opd != NULL; opd = opd->operand_next)
202 {
203 c1 = build_clause(opd, ct);
204 if (c1 == NULL) continue;
205 if (c == NULL)
206 {
207 c = c1;
208 }
209 else
210 {
211 for (c2 = c; ; c2 = c2->next)
212 {
213 if (NULL == c2->next)
214 {
215 c2->next = c1;
216 break;
217 }
218 }
219 }
220 }
221 }
222 else if (e->type == CONNECTOR_type)
223 {
224 c = pool_alloc(ct->Clause_pool);
225 c->c = build_terminal(e, ct);
226 c->cost = 0.0;
227 c->maxcost = 0.0;
228 c->next = NULL;
229 }
230 else
231 {
232 assert(false, "Unknown expression type %d", (int)e->type);
233 }
234
235 /* c now points to the list of clauses */
236 for (c1 = c; c1 != NULL; c1 = c1->next)
237 {
238 c1->cost += e->cost;
239 /* c1->maxcost = MAX(c1->maxcost,e->cost); */
240 /* Above is how Dennis had it. Someone changed it to below.
241 * However, this can sometimes lead to a maxcost that is less
242 * than the cost ! -- which seems wrong to me ... seems Dennis
243 * had it right!?
244 */
245 c1->maxcost += e->cost;
246 /* Note: The above computation is used as a saving shortcut in
247 * build_clause(). If it is changed here, it needs to be changed
248 * there too. */
249 }
250 return c;
251 }
252
253 /**
254 * Build a disjunct list out of the clause list c.
255 * string is the print name of word that generated this disjunct.
256 */
257 static Disjunct *
build_disjunct(Sentence sent,Clause * cl,const char * string,const gword_set * gs,double cost_cutoff,Parse_Options opts)258 build_disjunct(Sentence sent, Clause * cl, const char * string,
259 const gword_set *gs, double cost_cutoff, Parse_Options opts)
260 {
261 Disjunct *dis, *ndis;
262 Pool_desc *connector_pool = NULL;
263
264 dis = NULL;
265 for (; cl != NULL; cl = cl->next)
266 {
267 if (NULL == cl->c) continue; /* no connectors */
268 if (cl->maxcost > cost_cutoff) continue;
269
270 if (NULL == sent) /* For the SAT-parser, until fixed. */
271 {
272 ndis = xalloc(sizeof(Disjunct));
273 }
274 else
275 {
276 ndis = pool_alloc(sent->Disjunct_pool);
277 connector_pool = sent->Connector_pool;
278 }
279 ndis->left = ndis->right = NULL;
280
281 /* Build a list of connectors from the Tconnectors. */
282 for (Tconnector *t = cl->c; t != NULL; t = t->next)
283 {
284 Connector *n = connector_new(connector_pool, t->e->condesc, opts);
285 Connector **loc = ('-' == t->e->dir) ? &ndis->left : &ndis->right;
286
287 n->exp_pos = t->exp_pos;
288 n->multi = t->e->multi;
289 n->next = *loc; /* prepend the connector to the current list */
290 *loc = n; /* update the connector list */
291 }
292
293 ndis->word_string = string;
294 ndis->cost = cl->cost;
295 ndis->originating_gword = (gword_set*)gs; /* XXX remove constness */
296 ndis->next = dis;
297 dis = ndis;
298 }
299 return dis;
300 }
301
build_disjuncts_for_exp(Sentence sent,Exp * exp,const char * word,const gword_set * gs,double cost_cutoff,Parse_Options opts)302 Disjunct *build_disjuncts_for_exp(Sentence sent, Exp* exp, const char *word,
303 const gword_set *gs, double cost_cutoff,
304 Parse_Options opts)
305 {
306 Clause *c;
307 Disjunct * dis;
308 clause_context ct = { 0 };
309
310 ct.cost_cutoff = cost_cutoff;
311 ct.Clause_pool = pool_new(__func__, "Clause",
312 /*num_elements*/4096, sizeof(Clause),
313 /*zero_out*/false, /*align*/false, /*exact*/false);
314 ct.Tconnector_pool = pool_new(__func__, "Tconnector",
315 /*num_elements*/32768, sizeof(Tconnector),
316 /*zero_out*/false, /*align*/false, /*exact*/false);
317
318 // printf("%s\n", lg_exp_stringify(exp));
319 c = build_clause(exp, &ct);
320 // print_clause_list(c);
321 dis = build_disjunct(sent, c, word, gs, cost_cutoff, opts);
322 // print_disjunct_list(dis);
323 pool_delete(ct.Tconnector_pool);
324 pool_delete(ct.Clause_pool);
325 return dis;
326 }
327
328 #ifdef DEBUG
329 /* Misc printing functions, useful for debugging */
330
print_Tconnector_list(Tconnector * t)331 static void print_Tconnector_list(Tconnector *t)
332 {
333 for (; t != NULL; t = t->next)
334 {
335 if (t->e->multi) printf("@");
336 printf("%s", t->e->condesc->string);
337 printf("%c", t->e->dir);
338 if (t->next != NULL) printf(" ");
339 }
340 }
341
print_clause_list(Clause * c)342 GNUC_UNUSED static void print_clause_list(Clause * c)
343 {
344 for (;c != NULL; c=c->next) {
345 printf(" Clause: ");
346 printf("(%4.2f, %4.2f) ", c->cost, c->maxcost);
347 print_Tconnector_list(c->c);
348 printf("\n");
349 }
350 }
351 #endif /* DEBUG */
352