PocketSphinx  0.6
fsg_lextree.c
Go to the documentation of this file.
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3  * Copyright (c) 1999-2010 Carnegie Mellon University. All rights
4  * reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  *
18  *
19  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
20  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
23  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  *
31  * ====================================================================
32  *
33  */
41 /* System headers. */
42 #include <stdio.h>
43 #include <string.h>
44 #include <assert.h>
45 
46 /* SphinxBase headers. */
47 #include <sphinxbase/ckd_alloc.h>
48 #include <sphinxbase/err.h>
49 
50 /* Local headers. */
51 #include "fsg_lextree.h"
52 
53 #define __FSG_DBG__ 0
54 
55 /* A linklist structure that is actually used to build local lextrees at grammar nodes */
56 typedef struct fsg_glist_linklist_t {
57  int32 ci, rc;
58  glist_t glist;
59  struct fsg_glist_linklist_t *next;
61 
68 static fsg_pnode_t *fsg_psubtree_init(fsg_lextree_t *tree,
69  fsg_model_t *fsg,
70  int32 from_state,
71  fsg_pnode_t **alloc_head);
72 
77 static void fsg_psubtree_free(fsg_pnode_t *alloc_head);
78 
83 static void fsg_psubtree_dump(fsg_lextree_t *tree, fsg_pnode_t *alloc_head, FILE *fp);
84 
88 static void
89 fsg_lextree_lc_rc(fsg_lextree_t *lextree)
90 {
91  int32 s, i, j;
92  int32 n_ci;
93  fsg_model_t *fsg;
94  int32 silcipid;
95  int32 len;
96 
97  silcipid = bin_mdef_silphone(lextree->mdef);
98  assert(silcipid >= 0);
99  n_ci = bin_mdef_n_ciphone(lextree->mdef);
100 
101  fsg = lextree->fsg;
102  /*
103  * lextree->lc[s] = set of left context CIphones for state s. Similarly, rc[s]
104  * for right context CIphones.
105  */
106  lextree->lc = ckd_calloc_2d(fsg->n_state, n_ci + 1, sizeof(**lextree->lc));
107  lextree->rc = ckd_calloc_2d(fsg->n_state, n_ci + 1, sizeof(**lextree->rc));
108  E_INFO("Allocated %d bytes (%d KiB) for left and right context phones\n",
109  fsg->n_state * (n_ci + 1) * 2,
110  fsg->n_state * (n_ci + 1) * 2 / 1024);
111 
112 
113  for (s = 0; s < fsg->n_state; s++) {
114  fsg_arciter_t *itor;
115  for (itor = fsg_model_arcs(fsg, s); itor; itor = fsg_arciter_next(itor)) {
116  fsg_link_t *l = fsg_arciter_get(itor);
117  int32 dictwid;
119  if (fsg_link_wid(l) >= 0) {
120  dictwid = dict_wordid(lextree->dict,
121  fsg_model_word_str(lextree->fsg, l->wid));
122 
123  /*
124  * Add the first CIphone of l->wid to the rclist of state s, and
125  * the last CIphone to lclist of state d.
126  * (Filler phones are a pain to deal with. There is no direct
127  * marking of a filler phone; but only filler words are supposed to
128  * use such phones, so we use that fact. HACK!! FRAGILE!!)
129  */
130  if (fsg_model_is_filler(fsg, fsg_link_wid(l))) {
131  /* Filler phone; use silence phone as context */
132  lextree->rc[fsg_link_from_state(l)][silcipid] = 1;
133  lextree->lc[fsg_link_to_state(l)][silcipid] = 1;
134  }
135  else {
136  len = dict_pronlen(lextree->dict, dictwid);
137  lextree->rc[fsg_link_from_state(l)][dict_pron(lextree->dict, dictwid, 0)] = 1;
138  lextree->lc[fsg_link_to_state(l)][dict_pron(lextree->dict, dictwid, len - 1)] = 1;
139  }
140  }
141 
142  /*
143  * Add SIL phone to the lclist and rclist of each state. Strictly
144  * speaking, only needed at start and final states, respectively, but
145  * all states considered since the user may change the start and final
146  * states. In any case, most applications would have a silence self
147  * loop at each state, hence these would be needed anyway.
148  */
149  lextree->lc[fsg_link_from_state(l)][silcipid] = 1;
150  lextree->rc[fsg_link_from_state(l)][silcipid] = 1;
151  }
152  }
153 
154  /*
155  * Propagate lc and rc lists past null transitions. (Since FSG contains
156  * null transitions closure, no need to worry about a chain of successive
157  * null transitions. Right??)
158  *
159  * This can't be joined with the previous loop because we first calculate
160  * contexts and only then we can propagate them.
161  */
162  for (s = 0; s < fsg->n_state; s++) {
163  fsg_arciter_t *itor;
164  for (itor = fsg_model_arcs(fsg, s); itor; itor = fsg_arciter_next(itor)) {
165  fsg_link_t *l = fsg_arciter_get(itor);
166  if (fsg_link_wid(l) < 0) {
167 
168  /*
169  * lclist(d) |= lclist(s), because all the words ending up at s, can
170  * now also end at d, becoming the left context for words leaving d.
171  */
172  for (i = 0; i < n_ci; i++)
173  lextree->lc[fsg_link_to_state(l)][i] |= lextree->lc[fsg_link_from_state(l)][i];
174  /*
175  * Similarly, rclist(s) |= rclist(d), because all the words leaving d
176  * can equivalently leave s, becoming the right context for words
177  * ending up at s.
178  */
179  for (i = 0; i < n_ci; i++)
180  lextree->rc[fsg_link_from_state(l)][i] |= lextree->rc[fsg_link_to_state(l)][i];
181  }
182  }
183  }
184 
185  /* Convert the bit-vector representation into a list */
186  for (s = 0; s < fsg->n_state; s++) {
187  j = 0;
188  for (i = 0; i < n_ci; i++) {
189  if (lextree->lc[s][i]) {
190  lextree->lc[s][j] = i;
191  j++;
192  }
193  }
194  lextree->lc[s][j] = -1; /* Terminate the list */
195 
196  j = 0;
197  for (i = 0; i < n_ci; i++) {
198  if (lextree->rc[s][i]) {
199  lextree->rc[s][j] = i;
200  j++;
201  }
202  }
203  lextree->rc[s][j] = -1; /* Terminate the list */
204  }
205 }
206 
207 /*
208  * For now, allocate the entire lextree statically.
209  */
211 fsg_lextree_init(fsg_model_t * fsg, dict_t *dict, dict2pid_t *d2p,
212  bin_mdef_t *mdef, hmm_context_t *ctx,
213  int32 wip, int32 pip)
214 {
215  int32 s, n_leaves;
216  fsg_lextree_t *lextree;
217  fsg_pnode_t *pn;
218 
219  lextree = ckd_calloc(1, sizeof(fsg_lextree_t));
220  lextree->fsg = fsg;
221  lextree->root = ckd_calloc(fsg_model_n_state(fsg),
222  sizeof(fsg_pnode_t *));
223  lextree->alloc_head = ckd_calloc(fsg_model_n_state(fsg),
224  sizeof(fsg_pnode_t *));
225  lextree->ctx = ctx;
226  lextree->dict = dict;
227  lextree->d2p = d2p;
228  lextree->mdef = mdef;
229  lextree->wip = wip;
230  lextree->pip = pip;
231 
232  /* Compute lc and rc for fsg. */
233  fsg_lextree_lc_rc(lextree);
234 
235  /* Create lextree for each state, i.e. an HMM network that
236  * represents words for all arcs exiting that state. Note that
237  * for a dense grammar such as an N-gram model, this will
238  * rapidly exhaust all available memory. */
239  lextree->n_pnode = 0;
240  n_leaves = 0;
241  for (s = 0; s < fsg_model_n_state(fsg); s++) {
242  lextree->root[s] =
243  fsg_psubtree_init(lextree, fsg, s, &(lextree->alloc_head[s]));
244 
245  for (pn = lextree->alloc_head[s]; pn; pn = pn->alloc_next) {
246  lextree->n_pnode++;
247  if (pn->leaf)
248  ++n_leaves;
249  }
250  }
251  E_INFO("%d HMM nodes in lextree (%d leaves)\n",
252  lextree->n_pnode, n_leaves);
253  E_INFO("Allocated %d bytes (%d KiB) for all lextree nodes\n",
254  lextree->n_pnode * sizeof(fsg_pnode_t),
255  lextree->n_pnode * sizeof(fsg_pnode_t) / 1024);
256  E_INFO("Allocated %d bytes (%d KiB) for lextree leafnodes\n",
257  n_leaves * sizeof(fsg_pnode_t),
258  n_leaves * sizeof(fsg_pnode_t) / 1024);
259 
260 #if __FSG_DBG__
261  fsg_lextree_dump(lextree, stdout);
262 #endif
263 
264  return lextree;
265 }
266 
267 
268 void
269 fsg_lextree_dump(fsg_lextree_t * lextree, FILE * fp)
270 {
271  int32 s;
272 
273  for (s = 0; s < fsg_model_n_state(lextree->fsg); s++) {
274  fprintf(fp, "State %5d root %p\n", s, lextree->root[s]);
275  fsg_psubtree_dump(lextree, lextree->alloc_head[s], fp);
276  }
277  fflush(fp);
278 }
279 
280 
281 void
283 {
284  int32 s;
285 
286  if (lextree == NULL)
287  return;
288 
289  if (lextree->fsg)
290  for (s = 0; s < fsg_model_n_state(lextree->fsg); s++)
291  fsg_psubtree_free(lextree->alloc_head[s]);
292 
293  ckd_free_2d(lextree->lc);
294  ckd_free_2d(lextree->rc);
295  ckd_free(lextree->root);
296  ckd_free(lextree->alloc_head);
297  ckd_free(lextree);
298 }
299 
300 /******************************
301  * psubtree stuff starts here *
302  ******************************/
303 
304 void fsg_glist_linklist_free(fsg_glist_linklist_t *glist)
305 {
306  if (glist) {
307  fsg_glist_linklist_t *nxtglist;
308  if (glist->glist)
309  glist_free(glist->glist);
310  nxtglist = glist->next;
311  while (nxtglist) {
312  ckd_free(glist);
313  glist = nxtglist;
314  if (glist->glist)
315  glist_free(glist->glist);
316  nxtglist = glist->next;
317  }
318  ckd_free(glist);
319  }
320  return;
321 }
322 
323 void
325 {
326  int32 i;
327 
328  for (i = 0; i < FSG_PNODE_CTXT_BVSZ; i++)
329  ctxt->bv[i] = 0xffffffff;
330 }
331 
332 
333 /*
334  * fsg_pnode_ctxt_sub(fsg_pnode_ctxt_t * src, fsg_pnode_ctxt_t * sub)
335  * This has been moved into a macro in fsg_psubtree.h
336  * because it is called so frequently!
337  */
338 
339 
340 /*
341  * Add the word emitted by the given transition (fsglink) to the given lextree
342  * (rooted at root), and return the new lextree root. (There may actually be
343  * several root nodes, maintained in a linked list via fsg_pnode_t.sibling.
344  * "root" is the head of this list.)
345  * lclist, rclist: sets of left and right context phones for this link.
346  * alloc_head: head of a linear list of all allocated pnodes for the parent
347  * FSG state, kept elsewhere and updated by this routine.
348  */
349 static fsg_pnode_t *
350 psubtree_add_trans(fsg_lextree_t *lextree,
351  fsg_pnode_t * root,
352  fsg_glist_linklist_t **curglist,
353  fsg_link_t * fsglink,
354  int16 *lclist, int16 *rclist,
355  fsg_pnode_t ** alloc_head)
356 {
357  int32 silcipid; /* Silence CI phone ID */
358  int32 pronlen; /* Pronunciation length */
359  int32 wid; /* FSG (not dictionary!!) word ID */
360  int32 dictwid; /* Dictionary (not FSG!!) word ID */
361  int32 ssid; /* Senone Sequence ID */
362  int32 tmatid;
363  gnode_t *gn;
364  fsg_pnode_t *pnode, *pred, *head;
365  int32 n_ci, p, lc, rc;
366  glist_t lc_pnodelist; /* Temp pnodes list for different left contexts */
367  glist_t rc_pnodelist; /* Temp pnodes list for different right contexts */
368  int32 i, j;
369  int n_lc_alloc = 0, n_int_alloc = 0, n_rc_alloc = 0;
370 
371  silcipid = bin_mdef_silphone(lextree->mdef);
372  n_ci = bin_mdef_n_ciphone(lextree->mdef);
373 
374  wid = fsg_link_wid(fsglink);
375  assert(wid >= 0); /* Cannot be a null transition */
376  dictwid = dict_wordid(lextree->dict,
377  fsg_model_word_str(lextree->fsg, wid));
378  pronlen = dict_pronlen(lextree->dict, dictwid);
379  assert(pronlen >= 1);
380 
381  assert(lclist[0] >= 0); /* At least one phonetic context provided */
382  assert(rclist[0] >= 0);
383 
384  head = *alloc_head;
385  pred = NULL;
386 
387  if (pronlen == 1) { /* Single-phone word */
388  int ci = dict_first_phone(lextree->dict, dictwid);
389  /* Only non-filler words are mpx */
390  if (dict_filler_word(lextree->dict, dictwid)) {
391  /*
392  * Left diphone ID for single-phone words already assumes SIL is right
393  * context; only left contexts need to be handled.
394  */
395  lc_pnodelist = NULL;
396 
397  for (i = 0; lclist[i] >= 0; i++) {
398  lc = lclist[i];
399  ssid = dict2pid_lrdiph_rc(lextree->d2p, ci, lc, silcipid);
400  tmatid = bin_mdef_pid2tmatid(lextree->mdef, dict_first_phone(lextree->dict, dictwid));
401  /* Check if this ssid already allocated for some other context */
402  for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
403  pnode = (fsg_pnode_t *) gnode_ptr(gn);
404 
405  if (hmm_nonmpx_ssid(&pnode->hmm) == ssid) {
406  /* already allocated; share it for this context phone */
407  fsg_pnode_add_ctxt(pnode, lc);
408  break;
409  }
410  }
411 
412  if (!gn) { /* ssid not already allocated */
413  pnode =
414  (fsg_pnode_t *) ckd_calloc(1, sizeof(fsg_pnode_t));
415  pnode->ctx = lextree->ctx;
416  pnode->next.fsglink = fsglink;
417  pnode->logs2prob =
418  (fsg_link_logs2prob(fsglink) >> SENSCR_SHIFT)
419  + lextree->wip + lextree->pip;
420  pnode->ci_ext = dict_first_phone(lextree->dict, dictwid);
421  pnode->ppos = 0;
422  pnode->leaf = TRUE;
423  pnode->sibling = root; /* All root nodes linked together */
424  fsg_pnode_add_ctxt(pnode, lc); /* Initially zeroed by calloc above */
425  pnode->alloc_next = head;
426  head = pnode;
427  root = pnode;
428  ++n_lc_alloc;
429 
430  hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, tmatid);
431 
432  lc_pnodelist =
433  glist_add_ptr(lc_pnodelist, (void *) pnode);
434  }
435  }
436 
437  glist_free(lc_pnodelist);
438  }
439  else { /* Filler word; no context modelled */
440  ssid = bin_mdef_pid2ssid(lextree->mdef, ci); /* probably the same... */
441  tmatid = bin_mdef_pid2tmatid(lextree->mdef, ci);
442 
443  pnode = (fsg_pnode_t *) ckd_calloc(1, sizeof(fsg_pnode_t));
444  pnode->ctx = lextree->ctx;
445  pnode->next.fsglink = fsglink;
446  pnode->logs2prob = (fsg_link_logs2prob(fsglink) >> SENSCR_SHIFT)
447  + lextree->wip + lextree->pip;
448  pnode->ci_ext = silcipid; /* Presents SIL as context to neighbors */
449  pnode->ppos = 0;
450  pnode->leaf = TRUE;
451  pnode->sibling = root;
452  fsg_pnode_add_all_ctxt(&(pnode->ctxt));
453  pnode->alloc_next = head;
454  head = pnode;
455  root = pnode;
456  ++n_int_alloc;
457 
458  hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, tmatid);
459  }
460  }
461  else { /* Multi-phone word */
462  fsg_pnode_t **ssid_pnode_map; /* Temp array of ssid->pnode mapping */
463  ssid_pnode_map =
464  (fsg_pnode_t **) ckd_calloc(n_ci, sizeof(fsg_pnode_t *));
465  lc_pnodelist = NULL;
466  rc_pnodelist = NULL;
467 
468  for (p = 0; p < pronlen; p++) {
469  int ci = dict_pron(lextree->dict, dictwid, p);
470  if (p == 0) { /* Root phone, handle required left contexts */
471  /* Find if we already have an lc_pnodelist for the first phone of this word */
472  fsg_glist_linklist_t *glist;
473 
474  rc = dict_pron(lextree->dict, dictwid, 1);
475  for (glist = *curglist;
476  glist && glist->glist && glist->ci != ci && glist->rc != rc;
477  glist = glist->next)
478  ;
479  if (glist && glist->ci == ci && glist->rc == rc && glist->glist) {
480  /* We've found a valid glist. Hook to it and move to next phoneme */
481  E_DEBUG(2,("Found match for (%d,%d)\n", ci, rc));
482  lc_pnodelist = glist->glist;
483  /* Set the predecessor node for the future tree first */
484  pred = (fsg_pnode_t *) gnode_ptr(lc_pnodelist);
485  continue;
486  }
487  else {
488  /* Two cases that can bring us here
489  * a. glist == NULL, i.e. end of current list. Create new entry.
490  * b. glist->glist == NULL, i.e. first entry into list.
491  */
492  if (glist == NULL) { /* Case a; reduce it to case b by allocing glist */
493  glist = (fsg_glist_linklist_t*) ckd_calloc(1, sizeof(fsg_glist_linklist_t));
494  glist->next = *curglist;
495  *curglist = glist;
496  }
497  glist->ci = ci;
498  glist->rc = rc;
499  lc_pnodelist = glist->glist = NULL; /* Gets created below */
500  }
501 
502  for (i = 0; lclist[i] >= 0; i++) {
503  lc = lclist[i];
504  ssid = dict2pid_ldiph_lc(lextree->d2p, ci, rc, lc);
505  tmatid = bin_mdef_pid2tmatid(lextree->mdef, dict_first_phone(lextree->dict, dictwid));
506  /* Compression is not done by d2p, so we do it
507  * here. This might be slow, but it might not
508  * be... we'll see. */
509  pnode = ssid_pnode_map[0];
510  for (j = 0; j < n_ci && ssid_pnode_map[j] != NULL; ++j) {
511  pnode = ssid_pnode_map[j];
512  if (hmm_nonmpx_ssid(&pnode->hmm) == ssid)
513  break;
514  }
515  assert(j < n_ci);
516  if (!pnode) { /* Allocate pnode for this new ssid */
517  pnode =
518  (fsg_pnode_t *) ckd_calloc(1,
519  sizeof
520  (fsg_pnode_t));
521  pnode->ctx = lextree->ctx;
522  /* This bit is tricky! For now we'll put the prob in the final link only */
523  /* pnode->logs2prob = (fsg_link_logs2prob(fsglink) >> SENSCR_SHIFT)
524  + lextree->wip + lextree->pip; */
525  pnode->logs2prob = lextree->wip + lextree->pip;
526  pnode->ci_ext = dict_first_phone(lextree->dict, dictwid);
527  pnode->ppos = 0;
528  pnode->leaf = FALSE;
529  pnode->sibling = root; /* All root nodes linked together */
530  pnode->alloc_next = head;
531  head = pnode;
532  root = pnode;
533  ++n_lc_alloc;
534 
535  hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, tmatid);
536 
537  lc_pnodelist =
538  glist_add_ptr(lc_pnodelist, (void *) pnode);
539  ssid_pnode_map[j] = pnode;
540  }
541  fsg_pnode_add_ctxt(pnode, lc);
542  }
543  /* Put the lc_pnodelist back into glist */
544  glist->glist = lc_pnodelist;
545 
546  /* The predecessor node for the future tree is the root */
547  pred = root;
548  }
549  else if (p != pronlen - 1) { /* Word internal phone */
550  fsg_pnode_t *pnodeyoungest;
551 
552  ssid = dict2pid_internal(lextree->d2p, dictwid, p);
553  tmatid = bin_mdef_pid2tmatid(lextree->mdef, dict_pron (lextree->dict, dictwid, p));
554  /* First check if we already have this ssid in our tree */
555  pnode = pred->next.succ;
556  pnodeyoungest = pnode; /* The youngest sibling */
557  while (pnode && (hmm_nonmpx_ssid(&pnode->hmm) != ssid || pnode->leaf)) {
558  pnode = pnode->sibling;
559  }
560  if (pnode && (hmm_nonmpx_ssid(&pnode->hmm) == ssid && !pnode->leaf)) {
561  /* Found the ssid; go to next phoneme */
562  E_DEBUG(2,("Found match for %d\n", ci));
563  pred = pnode;
564  continue;
565  }
566 
567  /* pnode not found, allocate it */
568  pnode = (fsg_pnode_t *) ckd_calloc(1, sizeof(fsg_pnode_t));
569  pnode->ctx = lextree->ctx;
570  pnode->logs2prob = lextree->pip;
571  pnode->ci_ext = dict_pron(lextree->dict, dictwid, p);
572  pnode->ppos = p;
573  pnode->leaf = FALSE;
574  pnode->sibling = pnodeyoungest; /* May be NULL */
575  if (p == 1) { /* Predecessor = set of root nodes for left ctxts */
576  for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
577  pred = (fsg_pnode_t *) gnode_ptr(gn);
578  pred->next.succ = pnode;
579  }
580  }
581  else { /* Predecessor = word internal node */
582  pred->next.succ = pnode;
583  }
584  pnode->alloc_next = head;
585  head = pnode;
586  ++n_int_alloc;
587 
588  hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, tmatid);
589 
590  pred = pnode;
591  }
592  else { /* Leaf phone, handle required right contexts */
593  /* Note, leaf phones are not part of the tree */
594  xwdssid_t *rssid;
595  memset((void *) ssid_pnode_map, 0,
596  n_ci * sizeof(fsg_pnode_t *));
597  lc = dict_pron(lextree->dict, dictwid, p-1);
598  rssid = dict2pid_rssid(lextree->d2p, ci, lc);
599  tmatid = bin_mdef_pid2tmatid(lextree->mdef, dict_pron (lextree->dict, dictwid, p));
600 
601  for (i = 0; rclist[i] >= 0; i++) {
602  rc = rclist[i];
603 
604  j = rssid->cimap[rc];
605  ssid = rssid->ssid[j];
606  pnode = ssid_pnode_map[j];
607 
608  if (!pnode) { /* Allocate pnode for this new ssid */
609  pnode =
610  (fsg_pnode_t *) ckd_calloc(1,
611  sizeof
612  (fsg_pnode_t));
613  pnode->ctx = lextree->ctx;
614  /* We are plugging the word prob here. Ugly */
615  /* pnode->logs2prob = lextree->pip; */
616  pnode->logs2prob = (fsg_link_logs2prob(fsglink) >> SENSCR_SHIFT)
617  + lextree->pip;
618  pnode->ci_ext = dict_pron(lextree->dict, dictwid, p);
619  pnode->ppos = p;
620  pnode->leaf = TRUE;
621  pnode->sibling = rc_pnodelist ?
622  (fsg_pnode_t *) gnode_ptr(rc_pnodelist) : NULL;
623  pnode->next.fsglink = fsglink;
624  pnode->alloc_next = head;
625  head = pnode;
626  ++n_rc_alloc;
627 
628  hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, tmatid);
629 
630  rc_pnodelist =
631  glist_add_ptr(rc_pnodelist, (void *) pnode);
632  ssid_pnode_map[j] = pnode;
633  }
634  else {
635  assert(hmm_nonmpx_ssid(&pnode->hmm) == ssid);
636  }
637  fsg_pnode_add_ctxt(pnode, rc);
638  }
639 
640  if (p == 1) { /* Predecessor = set of root nodes for left ctxts */
641  for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
642  pred = (fsg_pnode_t *) gnode_ptr(gn);
643  if (!pred->next.succ)
644  pred->next.succ = (fsg_pnode_t *) gnode_ptr(rc_pnodelist);
645  else {
646  /* Link to the end of the sibling chain */
647  fsg_pnode_t *succ = pred->next.succ;
648  while (succ->sibling) succ = succ->sibling;
649  succ->sibling = (fsg_pnode_t*) gnode_ptr(rc_pnodelist);
650  /* Since all entries of lc_pnodelist point
651  to the same array, sufficient to update it once */
652  break;
653  }
654  }
655  }
656  else { /* Predecessor = word internal node */
657  if (!pred->next.succ)
658  pred->next.succ = (fsg_pnode_t *) gnode_ptr(rc_pnodelist);
659  else {
660  /* Link to the end of the sibling chain */
661  fsg_pnode_t *succ = pred->next.succ;
662  while (succ->sibling) succ = succ->sibling;
663  succ->sibling = (fsg_pnode_t *) gnode_ptr(rc_pnodelist);
664  }
665  }
666  }
667  }
668 
669  ckd_free((void *) ssid_pnode_map);
670  /* glist_free(lc_pnodelist); Nope; this gets freed outside */
671  glist_free(rc_pnodelist);
672  }
673 
674  E_DEBUG(2,("Allocated %d HMMs (%d lc, %d rc, %d internal)\n",
675  n_lc_alloc + n_rc_alloc + n_int_alloc,
676  n_lc_alloc, n_rc_alloc, n_int_alloc));
677  *alloc_head = head;
678 
679  return root;
680 }
681 
682 
683 static fsg_pnode_t *
684 fsg_psubtree_init(fsg_lextree_t *lextree,
685  fsg_model_t * fsg, int32 from_state,
686  fsg_pnode_t ** alloc_head)
687 {
688  int32 dst;
689  gnode_t *gn;
690  fsg_link_t *fsglink;
691  fsg_pnode_t *root;
692  int32 n_ci, n_arc;
693  fsg_glist_linklist_t *glist = NULL;
694 
695  root = NULL;
696  assert(*alloc_head == NULL);
697 
698  n_ci = bin_mdef_n_ciphone(lextree->mdef);
699  if (n_ci > (FSG_PNODE_CTXT_BVSZ * 32)) {
700  E_FATAL
701  ("#phones > %d; increase FSG_PNODE_CTXT_BVSZ and recompile\n",
702  FSG_PNODE_CTXT_BVSZ * 32);
703  }
704  n_arc = 0;
705  for (dst = 0; dst < fsg_model_n_state(fsg); dst++) {
706  /* Add all links from from_state to dst */
707  for (gn = fsg_model_trans(fsg, from_state, dst); gn;
708  gn = gnode_next(gn)) {
709  /* Add word emitted by this transition (fsglink) to lextree */
710  fsglink = (fsg_link_t *) gnode_ptr(gn);
711 
712  assert(fsg_link_wid(fsglink) >= 0); /* Cannot be a null trans */
713 
714  E_DEBUG(2,("Building lextree for arc from %d to %d: %s\n",
715  from_state, dst, fsg_model_word_str(fsg, fsg_link_wid(fsglink))));
716  root = psubtree_add_trans(lextree, root, &glist, fsglink,
717  lextree->lc[from_state],
718  lextree->rc[dst],
719  alloc_head);
720  ++n_arc;
721  }
722  }
723  E_DEBUG(2,("State %d has %d outgoing arcs\n", from_state, n_arc));
724 
725  fsg_glist_linklist_free(glist);
726 
727  return root;
728 }
729 
730 
731 static void
732 fsg_psubtree_free(fsg_pnode_t * head)
733 {
734  fsg_pnode_t *next;
735 
736  while (head) {
737  next = head->alloc_next;
738  hmm_deinit(&head->hmm);
739  ckd_free(head);
740  head = next;
741  }
742 }
743 
744 void fsg_psubtree_dump_node(fsg_lextree_t *tree, fsg_pnode_t *node, FILE *fp)
745 {
746  int32 i;
747  fsg_link_t *tl;
748 
749  /* Indentation */
750  for (i = 0; i <= node->ppos; i++)
751  fprintf(fp, " ");
752 
753  fprintf(fp, "%p.@", node); /* Pointer used as node
754  * ID */
755  fprintf(fp, " %5d.SS", hmm_nonmpx_ssid(&node->hmm));
756  fprintf(fp, " %10d.LP", node->logs2prob);
757  fprintf(fp, " %p.SIB", node->sibling);
758  fprintf(fp, " %s.%d", bin_mdef_ciphone_str(tree->mdef, node->ci_ext), node->ppos);
759  if ((node->ppos == 0) || node->leaf) {
760  fprintf(fp, " [");
761  for (i = 0; i < FSG_PNODE_CTXT_BVSZ; i++)
762  fprintf(fp, "%08x", node->ctxt.bv[i]);
763  fprintf(fp, "]");
764  }
765  if (node->leaf) {
766  tl = node->next.fsglink;
767  fprintf(fp, " {%s[%d->%d](%d)}",
768  fsg_model_word_str(tree->fsg, tl->wid),
769  tl->from_state, tl->to_state, tl->logs2prob);
770  } else {
771  fprintf(fp, " %p.NXT", node->next.succ);
772  }
773  fprintf(fp, "\n");
774 
775  return;
776 }
777 
778 void
779 fsg_psubtree_dump(fsg_lextree_t *tree, fsg_pnode_t *root, FILE * fp)
780 {
781  fsg_pnode_t *succ;
782 
783  if (root == NULL) return;
784  if (root->ppos == 0) {
785  while(root->sibling && root->sibling->next.succ == root->next.succ) {
786  fsg_psubtree_dump_node(tree, root, fp);
787  root = root->sibling;
788  }
789  fflush(fp);
790  }
791 
792  fsg_psubtree_dump_node(tree, root, fp);
793 
794  if (root->leaf) {
795  if (root->ppos == 0 && root->sibling) { // For single-phone words
796  fsg_psubtree_dump(tree, root->sibling,fp);
797  }
798  return;
799  }
800 
801  succ = root->next.succ;
802  while(succ) {
803  fsg_psubtree_dump(tree, succ,fp);
804  succ = succ->sibling;
805  }
806 
807  if (root->ppos == 0) {
808  fsg_psubtree_dump(tree, root->sibling,fp);
809  fflush(fp);
810  }
811 
812  return;
813 }
814 
815 void
817 {
818  hmm_clear(&pnode->hmm);
819 }