← Back to branch summary

~ubuntu-branches/ubuntu/utopic/sphinxtrain/utopic

« back to all changes in this revision

Viewing changes to src/libs/libcommon/quest.c

  • Committer: Package Import Robot
  • Author(s): Samuel Thibault
  • Date: 2013-01-02 04:10:21 UTC
  • Revision ID: package-import@ubuntu.com-20130102041021-ynsizmz33fx02hea
Tags: upstream-1.0.8
Import upstream version 1.0.8

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libs/libcommon/quest.c
 
1
/* ====================================================================
 
2
 * Copyright (c) 1996-2000 Carnegie Mellon University.  All rights 
 
3
 * reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 *
 
9
 * 1. Redistributions of source code must retain the above copyright
 
10
 *    notice, this list of conditions and the following disclaimer. 
 
11
 *
 
12
 * 2. Redistributions in binary form must reproduce the above copyright
 
13
 *    notice, this list of conditions and the following disclaimer in
 
14
 *    the documentation and/or other materials provided with the
 
15
 *    distribution.
 
16
 *
 
17
 * This work was supported in part by funding from the Defense Advanced 
 
18
 * Research Projects Agency and the National Science Foundation of the 
 
19
 * United States of America, and the CMU Sphinx Speech Consortium.
 
20
 *
 
21
 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
 
22
 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
 
23
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 
24
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
 
25
 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
26
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
 
27
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 
28
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 
29
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
 
30
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
 
31
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
32
 *
 
33
 * ====================================================================
 
34
 *
 
35
 */
 
36
/*********************************************************************
 
37
 *
 
38
 * File: quest.c
 
39
 * 
 
40
 * Description: 
 
41
 * 
 
42
 * Author: 
 
43
 * 
 
44
 *********************************************************************/
 
45
 
 
46
 
 
47
#include <s3/quest.h>
 
48
#include <sphinxbase/ckd_alloc.h>
 
49
#include <s3/s3.h>
 
50
 
 
51
#include <string.h>
 
52
#include <assert.h>
 
53
#include <ctype.h>
 
54
 
 
55
char *
 
56
s3parse_quest(pset_t *pset, uint32 n_pset, quest_t *q, char *in_str)
 
57
{
 
58
    char *s, *sp;
 
59
    uint32 i;
 
60
 
 
61
    s = in_str;
 
62
    
 
63
    /* skip leading whitespace */
 
64
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
65
 
 
66
    if (*s == '\0')     /* Nothing to parse */
 
67
        return s;
 
68
 
 
69
    if (*s == '!') {
 
70
        q->neg = TRUE;
 
71
        ++s;
 
72
        if (*s == '\0') {
 
73
            E_ERROR("question syntax error");
 
74
 
 
75
            return NULL;
 
76
        }
 
77
    }
 
78
    else
 
79
        q->neg = FALSE;
 
80
    
 
81
    sp = strchr(s, ' ');
 
82
    if (sp == NULL) {
 
83
        E_ERROR("Expected space after question name\n");
 
84
        return NULL;
 
85
    }
 
86
 
 
87
    *sp = '\0';
 
88
 
 
89
    for (i = 0; i < n_pset; i++) {
 
90
        if (strcmp(s, pset[i].name) == 0) {
 
91
            q->pset = i;
 
92
            q->member = pset[i].member;
 
93
            q->posn   = pset[i].posn;
 
94
 
 
95
            break;
 
96
        }
 
97
    }
 
98
    if (i == n_pset) {
 
99
        E_ERROR("Unknown question %s\n", s);
 
100
 
 
101
        return NULL;
 
102
    }
 
103
 
 
104
    s = sp+1;
 
105
 
 
106
    *sp = ' ';  /* undo set to null */
 
107
 
 
108
    /* skip whitespace */
 
109
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
110
 
 
111
    if (s[0] == '-') {
 
112
        if (s[1] == '1') {
 
113
            q->ctxt = -1;
 
114
        }
 
115
        s += 2;
 
116
    }
 
117
    else if (s[0] == '0') {
 
118
        q->ctxt = 0;
 
119
        s++;
 
120
    }
 
121
    else if (s[0] == '1') {
 
122
        q->ctxt = 1;
 
123
        s++;
 
124
    }
 
125
 
 
126
    /* skip trailing whitespace, if any */
 
127
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
128
 
 
129
    return s;
 
130
}
 
131
 
 
132
static uint32
 
133
count_quest_in_conj(pset_t *pset,
 
134
                    uint32 n_pset,
 
135
                    char *in_str)
 
136
{
 
137
    quest_t tmp;
 
138
    quest_t *q = &tmp;
 
139
    char *t;
 
140
    uint32 n_quest;
 
141
 
 
142
    n_quest = 0;
 
143
 
 
144
    t = in_str;
 
145
 
 
146
    for (; *t != '\0' && isspace((unsigned char)*t); t++);
 
147
    if (*t == ')') {
 
148
        E_ERROR("Empty conjunction\n");
 
149
        
 
150
        return 0;
 
151
    }
 
152
    while (t && *t != ')' && *t != '\0') {
 
153
        t = s3parse_quest(pset, n_pset, q, t);
 
154
        ++n_quest;
 
155
 
 
156
        for (; t && *t != '\0' && isspace((unsigned char)*t); t++);
 
157
    }
 
158
    if (t == NULL) {
 
159
        E_ERROR("Error while parsing conjunction: %s\n", in_str);
 
160
 
 
161
        return 0;
 
162
    }
 
163
    if (*t != ')') {
 
164
        E_ERROR("Error while parsing conjunction: %s\n", in_str);
 
165
        
 
166
        return 0;
 
167
    }
 
168
 
 
169
    return n_quest;
 
170
}
 
171
 
 
172
char *
 
173
s3parse_conj(pset_t *pset,
 
174
             uint32 n_pset,
 
175
             quest_t **term,
 
176
             uint32 *n_simple_q,
 
177
             char *in_str)
 
178
{
 
179
    quest_t *termlst;
 
180
    char *s;
 
181
    uint32 n_quest;
 
182
    uint32 i;
 
183
 
 
184
    s = in_str;
 
185
 
 
186
    if (*s == '\0') return s;
 
187
 
 
188
    /* skip leading whitespace */
 
189
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
190
    
 
191
    if (*s == '\0') return s;
 
192
 
 
193
    if (*s == '(') {
 
194
        ++s;
 
195
    }
 
196
    else {
 
197
        E_ERROR("Expected '(' before conjunction\n");
 
198
 
 
199
        return NULL;
 
200
    }
 
201
 
 
202
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
203
 
 
204
    if (*s == '\0') {
 
205
        E_ERROR("No terms and close paren in conjunction\n", in_str);
 
206
        
 
207
        return NULL;
 
208
    }
 
209
    
 
210
    n_quest = count_quest_in_conj(pset, n_pset, s);
 
211
    *n_simple_q = n_quest;
 
212
 
 
213
    termlst = (quest_t *)ckd_calloc(n_quest, sizeof(quest_t));
 
214
    *term = termlst;
 
215
 
 
216
    for (i = 0; i < n_quest; i++) {
 
217
        s = s3parse_quest(pset, n_pset, &termlst[i], s);
 
218
        for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
219
    }
 
220
 
 
221
    assert(*s == ')');
 
222
 
 
223
    s++;
 
224
 
 
225
    return s;
 
226
}
 
227
 
 
228
static uint32
 
229
s3cnt_q_term(char *in_str)
 
230
{
 
231
    char *s;
 
232
    uint32 n_term;
 
233
 
 
234
    s = in_str;
 
235
 
 
236
    /* skip any leading whitespace */
 
237
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
238
    
 
239
    /* assume everything is well-formed for the moment.
 
240
     * later processing will catch syntax errors
 
241
     * which should be unlikely anyway since this stuff
 
242
     * is most likely machine generated */
 
243
 
 
244
    for (s++, n_term = 0; *s && (s = strchr(s, '(')); n_term++, s++);
 
245
 
 
246
    return n_term;
 
247
}
 
248
 
 
249
int
 
250
s3parse_comp_quest(pset_t *pset,
 
251
                   uint32 n_pset,
 
252
                   comp_quest_t *q,
 
253
                   char *in_str)
 
254
{
 
255
    char *s;
 
256
    uint32 i;
 
257
 
 
258
    s = in_str;
 
259
 
 
260
    for (; *s != '\0' && isspace((unsigned char)*s); s++);
 
261
 
 
262
    if (*s == '\0') {
 
263
        E_ERROR("Empty string seen for composite question\n");
 
264
 
 
265
        return S3_ERROR;
 
266
    }
 
267
 
 
268
    if (*s != '(') {
 
269
        E_ERROR("Composite question does not begin with '(' : %s\n",
 
270
                in_str);
 
271
        
 
272
        return S3_ERROR;
 
273
    }
 
274
        
 
275
    q->sum_len  = s3cnt_q_term(in_str);
 
276
    q->conj_q   = (quest_t **)ckd_calloc(q->sum_len, sizeof(quest_t *));
 
277
    q->prod_len = (uint32 *)ckd_calloc(q->sum_len, sizeof(uint32));
 
278
 
 
279
    ++s;        /* skip the open paren */
 
280
 
 
281
    i = 0;
 
282
    do {
 
283
        s = s3parse_conj(pset,
 
284
                         n_pset,
 
285
                         &q->conj_q[i],
 
286
                         &q->prod_len[i],
 
287
                         s);
 
288
        ++i;
 
289
    } while (s && *s && *s == '(');
 
290
 
 
291
    if (s == NULL) {
 
292
        E_ERROR("Error while parsing %s\n", in_str);
 
293
 
 
294
        return S3_ERROR;
 
295
    }
 
296
 
 
297
    return S3_SUCCESS;
 
298
}
 
299
 
 
300
static void
 
301
parse_simple_q(quest_t *q,
 
302
               char *q_str)
 
303
{
 
304
    int i;
 
305
    int len;
 
306
    uint32 pset;
 
307
 
 
308
    assert(q != NULL);
 
309
    assert(q_str != NULL);
 
310
 
 
311
    len = strlen(q_str);
 
312
 
 
313
    /* skip leading whitespace */
 
314
    for (i = 0; i < len && isspace((unsigned char)q_str[i]); i++);
 
315
 
 
316
    if (i == len)
 
317
        return;
 
318
 
 
319
    if (q_str[i] == '~') {
 
320
        q->neg = TRUE;
 
321
        i++;
 
322
    }
 
323
    else {
 
324
        q->neg = FALSE;
 
325
    }
 
326
 
 
327
    pset = atoi(&q_str[i]);
 
328
 
 
329
    if (pset >= 400) {
 
330
        q->ctxt = 1;
 
331
        pset -= 400;
 
332
    }
 
333
    else if (pset < 400) {
 
334
        q->ctxt = -1;
 
335
    }
 
336
 
 
337
    q->pset = pset;
 
338
 
 
339
    /* HACK to get around WDBNDRY question context */
 
340
    if (pset < 3)
 
341
        q->ctxt = 0;
 
342
}
 
343
 
 
344
char *
 
345
parse_conj(quest_t **term,
 
346
           uint32 *n_simple_q,
 
347
           char *q_str)
 
348
{
 
349
    char *t, *eot;
 
350
    int n_q;
 
351
    char t_str[64];
 
352
    char *simp_q_str;
 
353
    quest_t *out;
 
354
    int i;
 
355
    
 
356
    /* copy the next product into t_str */
 
357
    eot = strchr(q_str, '|');
 
358
 
 
359
    if (eot) {
 
360
        strncpy(t_str, q_str, (eot - q_str));
 
361
        t_str[(eot - q_str)] = '\0';
 
362
    }
 
363
    else {
 
364
        strcpy(t_str, q_str);
 
365
    }
 
366
 
 
367
    /* count the # of terms in the product */
 
368
    t = t_str-1;
 
369
    n_q = 1;
 
370
    do {
 
371
        t = strchr(t+1, '&');
 
372
        if (t) {
 
373
            n_q++;
 
374
        }
 
375
    } while (t);
 
376
 
 
377
    /* allocate a simple question for each term in product */
 
378
    out = ckd_calloc(n_q, sizeof(quest_t));
 
379
 
 
380
    *term = out;
 
381
    *n_simple_q = n_q;
 
382
    
 
383
    /* parse each simple question */
 
384
    simp_q_str = strtok(t_str, "&");
 
385
    i = 0;
 
386
    do {
 
387
        parse_simple_q(&out[i], simp_q_str);
 
388
        simp_q_str = strtok(NULL, "&");
 
389
        i++;
 
390
    } while (simp_q_str);
 
391
 
 
392
    return eot;
 
393
}
 
394
 
 
395
uint32
 
396
cnt_q_term(char *q_str)
 
397
{
 
398
    char *t;
 
399
    uint32 n_term;
 
400
 
 
401
    t = q_str-1;
 
402
    n_term = 1;
 
403
 
 
404
    do {
 
405
        t = strchr(t+1, '|');
 
406
        if (t) ++n_term;
 
407
    } while (t);
 
408
 
 
409
    return n_term;
 
410
}
 
411
 
 
412
void
 
413
parse_compound_q(comp_quest_t *q,
 
414
                 char *q_str)
 
415
{
 
416
    char *rem_q_str;
 
417
    uint32 i;
 
418
 
 
419
    q->sum_len = cnt_q_term(q_str);
 
420
    q->conj_q = ckd_calloc(q->sum_len, sizeof(quest_t *));
 
421
    q->prod_len = ckd_calloc(q->sum_len, sizeof(uint32));
 
422
 
 
423
    i = 0;
 
424
    rem_q_str = q_str-1;
 
425
    do {
 
426
        rem_q_str = parse_conj(&q->conj_q[i],
 
427
                               &q->prod_len[i],
 
428
                               rem_q_str+1);
 
429
        ++i;
 
430
    } while (rem_q_str);
 
431
}
 
432
 
 
433
void
 
434
print_quest(FILE *fp,
 
435
            pset_t *pset,
 
436
            quest_t *q)
 
437
{
 
438
    if (pset == NULL) {
 
439
        fprintf(fp, "%s%d %d",
 
440
                (q->neg ? "!" : ""),
 
441
                q->pset,
 
442
                q->ctxt);
 
443
    }
 
444
    else {
 
445
        fprintf(fp, "%s%s %d",
 
446
                (q->neg ? "!" : ""),
 
447
                pset[q->pset].name,
 
448
                q->ctxt);
 
449
    }
 
450
}
 
451
 
 
452
int
 
453
eval_quest(quest_t *q,
 
454
           uint32 *feat,
 
455
           uint32 n_feat)
 
456
{
 
457
    uint32 ctxt;
 
458
    int ret = FALSE;
 
459
 
 
460
    ctxt = q->ctxt + 1;
 
461
 
 
462
    if (q->member)
 
463
        ret = q->member[feat[ctxt]];
 
464
    else if (q->posn)
 
465
        ret = q->posn[feat[n_feat-1]];
 
466
    else {
 
467
        E_FATAL("Ill-formed question\n");
 
468
    }
 
469
    
 
470
    if (q->neg) ret = !ret;
 
471
 
 
472
#if 0
 
473
    E_INFO("eval: (%s%u %d) %u -> %u\n",
 
474
           (q->neg ? "!" : ""),
 
475
           q->pset,
 
476
           q->ctxt,
 
477
           (q->member ? q->member[feat[ctxt]] :
 
478
            q->posn[feat[n_feat-1]]),
 
479
           ret);
 
480
#endif
 
481
    
 
482
    return ret;
 
483
}
 
484
 
 
485
int
 
486
eval_comp_quest(comp_quest_t *q,
 
487
                uint32 *feat,
 
488
                uint32 n_feat)
 
489
{
 
490
    int i, j;
 
491
 
 
492
    for (i = 0; i < q->sum_len; i++) {
 
493
        for (j = 0; j < q->prod_len[i]; j++) {
 
494
            if (!eval_quest(&q->conj_q[i][j], feat, n_feat))
 
495
                break;
 
496
        }
 
497
 
 
498
        /* One of the terms in the disjunction
 
499
        * is satisfied; so the whole is satisfied */
 
500
        if (j == q->prod_len[i])
 
501
            return TRUE;
 
502
    }
 
503
 
 
504
    /* visited all terms in the disjunction and none
 
505
     * were satisified; so neither is the disjunction */
 
506
    return FALSE;
 
507
}
 
508
 
 
509
void
 
510
print_comp_quest(FILE *fp,
 
511
                 pset_t *pset,
 
512
                 comp_quest_t *q)
 
513
{
 
514
    int i, j;
 
515
 
 
516
    fprintf(fp, "(");
 
517
    for (i = 0; i < q->sum_len; i++) {
 
518
        fprintf(fp, "(");
 
519
        print_quest(fp, pset, &q->conj_q[i][0]);
 
520
        
 
521
        for (j = 1; j < q->prod_len[i]; j++) {
 
522
            fprintf(fp, " ");
 
523
            print_quest(fp, pset, &q->conj_q[i][j]);
 
524
        }
 
525
        fprintf(fp, ")");
 
526
    }
 
527
    fprintf(fp, ")");
 
528
}
 
529
 
 
530
int
 
531
is_subset(quest_t *a,
 
532
          quest_t *b,
 
533
          uint32 n_phone)
 
534
{
 
535
    uint32 p;
 
536
    int f_a, f_b;
 
537
 
 
538
    if (a->member && b->member) {
 
539
        if (a->ctxt != b->ctxt)
 
540
            return FALSE;
 
541
 
 
542
        for (p = 0; p < n_phone; p++) {
 
543
            if (a->neg)
 
544
                f_a = !a->member[p];
 
545
            else
 
546
                f_a = a->member[p];
 
547
            
 
548
            if (b->neg)
 
549
                f_b = !b->member[p];
 
550
            else
 
551
                f_b = b->member[p];
 
552
            
 
553
            if (f_a && (f_a != f_b)) {
 
554
                break;
 
555
            }
 
556
        }
 
557
        if (p != n_phone)
 
558
            return FALSE;
 
559
        else
 
560
            return TRUE;
 
561
    }
 
562
    else if ((a->member && b->posn) ||
 
563
             (a->posn && b->member)) {
 
564
        /* one question about word boundary
 
565
         * and the other is about phone context
 
566
         * so not a subset */
 
567
        return FALSE;
 
568
    }
 
569
    else if (a->posn && b->posn) {
 
570
        /* Not handled at the moment */
 
571
        return FALSE;
 
572
    }
 
573
    return FALSE;
 
574
}
 
575
 
 
576
 
 
577
int
 
578
simplify_conj(quest_t *conj,
 
579
              uint32 n_term,
 
580
              uint32 n_phone)
 
581
{
 
582
    uint32 i, j;
 
583
    int *del, exist_del = FALSE;
 
584
 
 
585
    assert(n_term != 0);
 
586
 
 
587
    if (n_term == 1)    /* Only one term; nothing to do */
 
588
        return 1;
 
589
 
 
590
    del = ckd_calloc(n_term, sizeof(int));
 
591
 
 
592
    /* Search for all pairs (i,j) where
 
593
     * term_i is a subset of term_j.  Mark
 
594
     * all such term_j's for deletion since
 
595
     * term_i && term_j == term_i */
 
596
    for (i = 0; i < n_term; i++) {
 
597
        for (j = 0; j < n_term; j++) {
 
598
            if ((i != j) && (!del[i] || !del[j])) {
 
599
                if (is_subset(&conj[i], &conj[j], n_phone)) {
 
600
                    /* mark the superset for deletion */
 
601
                    del[j] = TRUE;
 
602
                    exist_del = TRUE;
 
603
                }
 
604
            }
 
605
        }
 
606
    }
 
607
 
 
608
    /* compact the conjunction by removing
 
609
     * term_j's that are marked for deletion.
 
610
     */
 
611
    for (i = 0, j = 0; j < n_term; i++, j++) {
 
612
        if (del[j]) {
 
613
            /* move j to the next
 
614
             * non-deleted term (if any) */
 
615
            for (j++; del[j] && (j < n_term); j++);
 
616
            
 
617
            if (j == n_term)
 
618
                break;
 
619
        }
 
620
        if (i != j) {
 
621
            conj[i] = conj[j];
 
622
        }
 
623
    }
 
624
 
 
625
    ckd_free(del);
 
626
 
 
627
    return i;   /* return new n_term */
 
628
}
 
629
 
 
630
int
 
631
simplify_comp_quest(comp_quest_t *q,
 
632
                    uint32 n_phone)
 
633
{
 
634
    int i;
 
635
    int ret = FALSE;
 
636
    int prod_len;
 
637
 
 
638
    for (i = 0; i < q->sum_len; i++) {
 
639
        prod_len = simplify_conj(q->conj_q[i], q->prod_len[i], n_phone);
 
640
        if (prod_len < q->prod_len[i]) {
 
641
            assert(!(prod_len > q->prod_len[i]));
 
642
            
 
643
            q->prod_len[i] = prod_len;
 
644
 
 
645
            ret = TRUE;
 
646
        }
 
647
    }
 
648
 
 
649
    /* TRUE if there is at least one term in the composite
 
650
     * question that was simplified */
 
651
    return ret;
 
652
}