• Main Page
  • Data Structures
  • Files
  • File List
  • Globals

src/libpocketsphinx/fsg_lextree.c

Go to the documentation of this file.
00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
00002 /* ====================================================================
00003  * Copyright (c) 1999-2010 Carnegie Mellon University.  All rights
00004  * reserved.
00005  *
00006  * Redistribution and use in source and binary forms, with or without
00007  * modification, are permitted provided that the following conditions
00008  * are met:
00009  *
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer. 
00012  *
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in
00015  *    the documentation and/or other materials provided with the
00016  *    distribution.
00017  *
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
00020  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
00021  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00022  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
00023  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00024  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
00025  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
00026  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
00027  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
00028  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
00029  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00030  *
00031  * ====================================================================
00032  *
00033  */
00041 /* System headers. */
00042 #include <stdio.h>
00043 #include <string.h>
00044 #include <assert.h>
00045 
00046 /* SphinxBase headers. */
00047 #include <ckd_alloc.h>
00048 #include <err.h>
00049 
00050 /* Local headers. */
00051 #include "fsg_lextree.h"
00052 
00053 #define __FSG_DBG__             0
00054 
00055 /* A linklist structure that is actually used to build local lextrees at grammar nodes */
00056 typedef struct fsg_glist_linklist_t {
00057     int32    ci, rc, lc;
00058     glist_t  glist;
00059     struct   fsg_glist_linklist_t *next;
00060 } fsg_glist_linklist_t;
00061 
00068 static fsg_pnode_t *fsg_psubtree_init(fsg_lextree_t *tree,
00069                                       fsg_model_t *fsg,
00070                                       int32 from_state,
00071                                       fsg_pnode_t **alloc_head);
00072 
00077 static void fsg_psubtree_free(fsg_pnode_t *alloc_head);
00078 
00083 static void fsg_psubtree_dump(fsg_lextree_t *tree, fsg_pnode_t *alloc_head, FILE *fp);
00084 
00088 static void
00089 fsg_lextree_lc_rc(fsg_lextree_t *lextree)
00090 {
00091     int32 s, d, i, j;
00092     int32 n_ci;
00093     gnode_t *gn;
00094     fsg_model_t *fsg;
00095     fsg_link_t *l;
00096     int32 silcipid;
00097     int32 len;
00098 
00099     silcipid = bin_mdef_silphone(lextree->mdef);
00100     assert(silcipid >= 0);
00101     n_ci = bin_mdef_n_ciphone(lextree->mdef);
00102 
00103     fsg = lextree->fsg;
00104     /*
00105      * lextree->lc[s] = set of left context CIphones for state s.  Similarly, rc[s]
00106      * for right context CIphones.
00107      */
00108     lextree->lc = ckd_calloc_2d(fsg->n_state, n_ci + 1, sizeof(**lextree->lc));
00109     lextree->rc = ckd_calloc_2d(fsg->n_state, n_ci + 1, sizeof(**lextree->rc));
00110     E_INFO("Allocated %d bytes (%d KiB) for left and right context phones\n",
00111            fsg->n_state * (n_ci + 1) * 2,
00112            fsg->n_state * (n_ci + 1) * 2 / 1024);
00113 
00114     for (s = 0; s < fsg->n_state; s++) {
00115         for (d = 0; d < fsg->n_state; d++) {
00116             for (gn = fsg->trans[s][d]; gn; gn = gnode_next(gn)) {
00117                 int32 dictwid; 
00119                 l = (fsg_link_t *) gnode_ptr(gn);
00120                 assert(l->wid >= 0);
00121                 dictwid = dict_wordid(lextree->dict,
00122                                         fsg_model_word_str(lextree->fsg, l->wid));
00123 
00124                 /*
00125                  * Add the first CIphone of l->wid to the rclist of state s, and
00126                  * the last CIphone to lclist of state d.
00127                  * (Filler phones are a pain to deal with.  There is no direct
00128                  * marking of a filler phone; but only filler words are supposed to
00129                  * use such phones, so we use that fact.  HACK!!  FRAGILE!!)
00130                  */
00131                 if (fsg_model_is_filler(fsg, l->wid)) {
00132                     /* Filler phone; use silence phone as context */
00133                     lextree->rc[s][silcipid] = 1;
00134                     lextree->lc[d][silcipid] = 1;
00135                 }
00136                 else {
00137                     len = dict_pronlen(lextree->dict, dictwid);
00138                     lextree->rc[s][dict_pron(lextree->dict, dictwid, 0)] = 1;
00139                     lextree->lc[d][dict_pron(lextree->dict, dictwid, len - 1)] = 1;
00140                 }
00141             }
00142         }
00143 
00144         /*
00145          * Add SIL phone to the lclist and rclist of each state.  Strictly
00146          * speaking, only needed at start and final states, respectively, but
00147          * all states considered since the user may change the start and final
00148          * states.  In any case, most applications would have a silence self
00149          * loop at each state, hence these would be needed anyway.
00150          */
00151         lextree->lc[s][silcipid] = 1;
00152         lextree->rc[s][silcipid] = 1;
00153     }
00154 
00155     /*
00156      * Propagate lc and rc lists past null transitions.  (Since FSG contains
00157      * null transitions closure, no need to worry about a chain of successive
00158      * null transitions.  Right??)
00159      */
00160     for (s = 0; s < fsg->n_state; s++) {
00161         for (d = 0; d < fsg->n_state; d++) {
00162             l = fsg->null_trans[s][d];
00163             if (l) {
00164                 /*
00165                  * lclist(d) |= lclist(s), because all the words ending up at s, can
00166                  * now also end at d, becoming the left context for words leaving d.
00167                  */
00168                 for (i = 0; i < n_ci; i++)
00169                     lextree->lc[d][i] |= lextree->lc[s][i];
00170                 /*
00171                  * Similarly, rclist(s) |= rclist(d), because all the words leaving d
00172                  * can equivalently leave s, becoming the right context for words
00173                  * ending up at s.
00174                  */
00175                 for (i = 0; i < n_ci; i++)
00176                     lextree->rc[s][i] |= lextree->rc[d][i];
00177             }
00178         }
00179     }
00180 
00181     /* Convert the bit-vector representation into a list */
00182     for (s = 0; s < fsg->n_state; s++) {
00183         j = 0;
00184         for (i = 0; i < n_ci; i++) {
00185             if (lextree->lc[s][i]) {
00186                 lextree->lc[s][j] = i;
00187                 j++;
00188             }
00189         }
00190         lextree->lc[s][j] = -1;     /* Terminate the list */
00191 
00192         j = 0;
00193         for (i = 0; i < n_ci; i++) {
00194             if (lextree->rc[s][i]) {
00195                 lextree->rc[s][j] = i;
00196                 j++;
00197             }
00198         }
00199         lextree->rc[s][j] = -1;     /* Terminate the list */
00200     }
00201 }
00202 
00203 /*
00204  * For now, allocate the entire lextree statically.
00205  */
00206 fsg_lextree_t *
00207 fsg_lextree_init(fsg_model_t * fsg, dict_t *dict, dict2pid_t *d2p,
00208                  bin_mdef_t *mdef, hmm_context_t *ctx,
00209                  int32 wip, int32 pip)
00210 {
00211     int32 s;
00212     fsg_lextree_t *lextree;
00213     fsg_pnode_t *pn;
00214 
00215     lextree = ckd_calloc(1, sizeof(fsg_lextree_t));
00216     lextree->fsg = fsg;
00217     lextree->root = ckd_calloc(fsg_model_n_state(fsg),
00218                                sizeof(fsg_pnode_t *));
00219     lextree->alloc_head = ckd_calloc(fsg_model_n_state(fsg),
00220                                      sizeof(fsg_pnode_t *));
00221     lextree->ctx = ctx;
00222     lextree->dict = dict;
00223     lextree->d2p = d2p;
00224     lextree->mdef = mdef;
00225     lextree->wip = wip;
00226     lextree->pip = pip;
00227 
00228     /* Compute lc and rc for fsg. */
00229     fsg_lextree_lc_rc(lextree);
00230 
00231     /* Create lextree for each state, i.e. an HMM network that
00232      * represents words for all arcs exiting that state.  Note that
00233      * for a dense grammar such as an N-gram model, this will
00234      * rapidly exhaust all available memory. */
00235     lextree->n_pnode = 0;
00236     for (s = 0; s < fsg_model_n_state(fsg); s++) {
00237         lextree->root[s] =
00238             fsg_psubtree_init(lextree, fsg, s, &(lextree->alloc_head[s]));
00239 
00240         for (pn = lextree->alloc_head[s]; pn; pn = pn->alloc_next)
00241             lextree->n_pnode++;
00242     }
00243     E_INFO("%d HMM nodes in lextree\n", lextree->n_pnode);
00244     E_INFO("Allocated %d bytes (%d KiB) for lextree nodes\n",
00245            lextree->n_pnode * sizeof(fsg_pnode_t),
00246            lextree->n_pnode * sizeof(fsg_pnode_t) / 1024);
00247 
00248 #if __FSG_DBG__
00249     fsg_lextree_dump(lextree, stdout);
00250 #endif
00251 
00252     return lextree;
00253 }
00254 
00255 
00256 void
00257 fsg_lextree_dump(fsg_lextree_t * lextree, FILE * fp)
00258 {
00259     int32 s;
00260 
00261     for (s = 0; s < fsg_model_n_state(lextree->fsg); s++) {
00262         fprintf(fp, "State %5d root %p\n", s, lextree->root[s]);
00263         fsg_psubtree_dump(lextree, lextree->alloc_head[s], fp);
00264     }
00265     fflush(fp);
00266 }
00267 
00268 
00269 void
00270 fsg_lextree_free(fsg_lextree_t * lextree)
00271 {
00272     int32 s;
00273 
00274     if (lextree == NULL)
00275         return;
00276 
00277     if (lextree->fsg)
00278         for (s = 0; s < fsg_model_n_state(lextree->fsg); s++)
00279             fsg_psubtree_free(lextree->alloc_head[s]);
00280 
00281     ckd_free_2d(lextree->lc);
00282     ckd_free_2d(lextree->rc);
00283     ckd_free(lextree->root);
00284     ckd_free(lextree->alloc_head);
00285     ckd_free(lextree);
00286 }
00287 
00288 /******************************
00289  * psubtree stuff starts here *
00290  ******************************/
00291 
00292 void fsg_glist_linklist_free(fsg_glist_linklist_t *glist)
00293 {
00294     if (glist) {
00295         fsg_glist_linklist_t *nxtglist;
00296         if (glist->glist)
00297             glist_free(glist->glist);
00298         nxtglist = glist->next;
00299         while (nxtglist) {
00300             ckd_free(glist);
00301             glist = nxtglist;
00302             if (glist->glist)
00303                 glist_free(glist->glist);
00304             nxtglist = glist->next;
00305         }
00306         ckd_free(glist);
00307     }
00308     return;
00309 }
00310 
00311 void
00312 fsg_pnode_add_all_ctxt(fsg_pnode_ctxt_t * ctxt)
00313 {
00314     int32 i;
00315 
00316     for (i = 0; i < FSG_PNODE_CTXT_BVSZ; i++)
00317         ctxt->bv[i] = 0xffffffff;
00318 }
00319 
00320 
00321 /*
00322  * fsg_pnode_ctxt_sub(fsg_pnode_ctxt_t * src, fsg_pnode_ctxt_t * sub)
00323  * This has been moved into a macro in fsg_psubtree.h 
00324  * because it is called so frequently!
00325  */
00326 
00327 
00328 /*
00329  * Add the word emitted by the given transition (fsglink) to the given lextree
00330  * (rooted at root), and return the new lextree root.  (There may actually be
00331  * several root nodes, maintained in a linked list via fsg_pnode_t.sibling.
00332  * "root" is the head of this list.)
00333  * lclist, rclist: sets of left and right context phones for this link.
00334  * alloc_head: head of a linear list of all allocated pnodes for the parent
00335  * FSG state, kept elsewhere and updated by this routine.
00336  */
00337 static fsg_pnode_t *
00338 psubtree_add_trans(fsg_lextree_t *lextree, 
00339                    fsg_pnode_t * root,
00340                    fsg_glist_linklist_t **curglist,
00341                    fsg_link_t * fsglink,
00342                    int16 *lclist, int16 *rclist,
00343                    fsg_pnode_t ** alloc_head)
00344 {
00345     int32 silcipid;             /* Silence CI phone ID */
00346     int32 pronlen;              /* Pronunciation length */
00347     int32 wid;                  /* FSG (not dictionary!!) word ID */
00348     int32 dictwid;              /* Dictionary (not FSG!!) word ID */
00349     int32 ssid;                 /* Senone Sequence ID */
00350     gnode_t *gn;
00351     fsg_pnode_t *pnode, *pred, *head;
00352     int32 n_ci, p, lc, rc;
00353     glist_t lc_pnodelist;       /* Temp pnodes list for different left contexts */
00354     glist_t rc_pnodelist;       /* Temp pnodes list for different right contexts */
00355     int32 i, j;
00356 
00357     silcipid = bin_mdef_silphone(lextree->mdef);
00358     n_ci = bin_mdef_n_ciphone(lextree->mdef);
00359 
00360     wid = fsg_link_wid(fsglink);
00361     assert(wid >= 0);           /* Cannot be a null transition */
00362     dictwid = dict_wordid(lextree->dict,
00363                           fsg_model_word_str(lextree->fsg, wid));
00364     pronlen = dict_pronlen(lextree->dict, dictwid);
00365     assert(pronlen >= 1);
00366 
00367     assert(lclist[0] >= 0);     /* At least one phonetic context provided */
00368     assert(rclist[0] >= 0);
00369 
00370     head = *alloc_head;
00371     pred = NULL;
00372 
00373     if (pronlen == 1) {         /* Single-phone word */
00374         int ci = dict_first_phone(lextree->dict, dictwid);
00375         /* Only non-filler words are mpx */
00376         if (dict_filler_word(lextree->dict, dictwid)) {
00377             /*
00378              * Left diphone ID for single-phone words already assumes SIL is right
00379              * context; only left contexts need to be handled.
00380              */
00381             lc_pnodelist = NULL;
00382 
00383             for (i = 0; lclist[i] >= 0; i++) {
00384                 lc = lclist[i];
00385                 ssid = dict2pid_lrdiph_rc(lextree->d2p, ci, lc, silcipid);
00386                 /* Check if this ssid already allocated for some other context */
00387                 for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
00388                     pnode = (fsg_pnode_t *) gnode_ptr(gn);
00389 
00390                     if (hmm_nonmpx_ssid(&pnode->hmm) == ssid) {
00391                         /* already allocated; share it for this context phone */
00392                         fsg_pnode_add_ctxt(pnode, lc);
00393                         break;
00394                     }
00395                 }
00396 
00397                 if (!gn) {      /* ssid not already allocated */
00398                     pnode =
00399                         (fsg_pnode_t *) ckd_calloc(1, sizeof(fsg_pnode_t));
00400                     pnode->ctx = lextree->ctx;
00401                     pnode->next.fsglink = fsglink;
00402                     pnode->logs2prob =
00403                         fsg_link_logs2prob(fsglink) + lextree->wip + lextree->pip;
00404                     pnode->ci_ext = dict_first_phone(lextree->dict, dictwid);
00405                     pnode->ppos = 0;
00406                     pnode->leaf = TRUE;
00407                     pnode->sibling = root;      /* All root nodes linked together */
00408                     fsg_pnode_add_ctxt(pnode, lc);      /* Initially zeroed by calloc above */
00409                     pnode->alloc_next = head;
00410                     head = pnode;
00411                     root = pnode;
00412 
00413                     hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, pnode->ci_ext);
00414 
00415                     lc_pnodelist =
00416                         glist_add_ptr(lc_pnodelist, (void *) pnode);
00417                 }
00418             }
00419 
00420             glist_free(lc_pnodelist);
00421         }
00422         else {                  /* Filler word; no context modelled */
00423             ssid = bin_mdef_pid2ssid(lextree->mdef, ci); /* probably the same... */
00424 
00425             pnode = (fsg_pnode_t *) ckd_calloc(1, sizeof(fsg_pnode_t));
00426             pnode->ctx = lextree->ctx;
00427             pnode->next.fsglink = fsglink;
00428             pnode->logs2prob = fsg_link_logs2prob(fsglink) + lextree->wip + lextree->pip;
00429             pnode->ci_ext = silcipid;   /* Presents SIL as context to neighbors */
00430             pnode->ppos = 0;
00431             pnode->leaf = TRUE;
00432             pnode->sibling = root;
00433             fsg_pnode_add_all_ctxt(&(pnode->ctxt));
00434             pnode->alloc_next = head;
00435             head = pnode;
00436             root = pnode;
00437 
00438             hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, pnode->ci_ext);
00439         }
00440     }
00441     else {                      /* Multi-phone word */
00442         fsg_pnode_t **ssid_pnode_map;       /* Temp array of ssid->pnode mapping */
00443         ssid_pnode_map =
00444             (fsg_pnode_t **) ckd_calloc(n_ci, sizeof(fsg_pnode_t *));
00445         lc_pnodelist = NULL;
00446         rc_pnodelist = NULL;
00447 
00448         for (p = 0; p < pronlen; p++) {
00449             int ci = dict_pron(lextree->dict, dictwid, p);
00450             if (p == 0) {       /* Root phone, handle required left contexts */
00451                 /* Find if we already have an lc_pnodelist for the first phone of this word */
00452                 fsg_glist_linklist_t *predglist=*curglist;
00453                 fsg_glist_linklist_t *glist=*curglist;
00454 
00455                 rc = dict_pron(lextree->dict, dictwid, 1);
00456                 while (glist && glist->glist && glist->ci != ci && glist->rc != rc){
00457                     glist = glist->next;
00458                 }
00459                 if (glist && glist->ci == ci && glist->rc == rc && glist->glist) {
00460                     /* We've found a valid glist. Hook to it and move to next phoneme */
00461                     lc_pnodelist = glist->glist;
00462                     /* Set the predecessor node for the future tree first */
00463                     pred = (fsg_pnode_t *) gnode_ptr(lc_pnodelist);
00464                     continue;
00465                 }
00466                 else {
00467                     /* Two cases that can bring us here
00468                      * a. glist == NULL, i.e. end of current list. Create new entry.
00469                      * b. glist->glist == NULL, i.e. first entry into list.
00470                      */
00471                     if (!glist) { /* Case a; reduce it to case b by allocing glist */
00472                         glist = (fsg_glist_linklist_t*) ckd_calloc(1, sizeof(fsg_glist_linklist_t));
00473                         glist->next = predglist;
00474                         *curglist = glist;
00475                     }
00476                     glist->ci = ci;
00477                     glist->rc = rc;
00478                     glist->lc = -1;
00479                     lc_pnodelist = glist->glist = NULL; /* Gets created below */
00480                 }
00481 
00482                 for (i = 0; lclist[i] >= 0; i++) {
00483                     lc = lclist[i];
00484                     ssid = dict2pid_ldiph_lc(lextree->d2p, ci, rc, lc);
00485                     /* Compression is not done by d2p, so we do it
00486                      * here.  This might be slow, but it might not
00487                      * be... we'll see. */
00488                     pnode = ssid_pnode_map[0];
00489                     for (j = 0; j < n_ci && ssid_pnode_map[j] != NULL; ++j) {
00490                         pnode = ssid_pnode_map[j];
00491                         if (hmm_nonmpx_ssid(&pnode->hmm) == ssid)
00492                             break;
00493                     }
00494                     assert(j < n_ci);
00495                     if (!pnode) {       /* Allocate pnode for this new ssid */
00496                         pnode =
00497                             (fsg_pnode_t *) ckd_calloc(1,
00498                                                        sizeof
00499                                                        (fsg_pnode_t));
00500                         pnode->ctx = lextree->ctx;
00501                         /* This bit is tricky! For now we'll put the prob in the final link only */
00502                         /* pnode->logs2prob = fsg_link_logs2prob(fsglink)
00503                            + lextree->wip + lextree->pip; */
00504                         pnode->logs2prob = lextree->wip + lextree->pip;
00505                         pnode->ci_ext = dict_first_phone(lextree->dict, dictwid);
00506                         pnode->ppos = 0;
00507                         pnode->leaf = FALSE;
00508                         pnode->sibling = root;  /* All root nodes linked together */
00509                         pnode->alloc_next = head;
00510                         head = pnode;
00511                         root = pnode;
00512 
00513                         hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, pnode->ci_ext);
00514 
00515                         lc_pnodelist =
00516                             glist_add_ptr(lc_pnodelist, (void *) pnode);
00517                         ssid_pnode_map[j] = pnode;
00518                     }
00519                     fsg_pnode_add_ctxt(pnode, lc);
00520                 }
00521                 /* Put the lc_pnodelist back into glist */
00522                 glist->glist = lc_pnodelist;
00523 
00524                 /* The predecessor node for the future tree is the root */
00525                 pred = root;
00526             }
00527             else if (p != pronlen - 1) {        /* Word internal phone */
00528                 fsg_pnode_t    *pnodeyoungest;
00529 
00530                 ssid = dict2pid_internal(lextree->d2p, dictwid, p);
00531                 /* First check if we already have this ssid in our tree */
00532                 pnode = pred->next.succ;
00533                 pnodeyoungest = pnode; /* The youngest sibling */
00534                 while (pnode && (hmm_nonmpx_ssid(&pnode->hmm) != ssid || pnode->leaf)) {
00535                     pnode = pnode->sibling;
00536                 }
00537                 if (pnode && (hmm_nonmpx_ssid(&pnode->hmm) == ssid && !pnode->leaf)) {
00538                     /* Found the ssid; go to next phoneme */
00539                     pred = pnode;
00540                     continue;
00541                 }
00542 
00543                 /* pnode not found, allocate it */
00544                 pnode = (fsg_pnode_t *) ckd_calloc(1, sizeof(fsg_pnode_t));
00545                 pnode->ctx = lextree->ctx;
00546                 pnode->logs2prob = lextree->pip;
00547                 pnode->ci_ext = dict_pron(lextree->dict, dictwid, p);
00548                 pnode->ppos = p;
00549                 pnode->leaf = FALSE;
00550                 pnode->sibling = pnodeyoungest; /* May be NULL */
00551                 if (p == 1) {   /* Predecessor = set of root nodes for left ctxts */
00552                     for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
00553                         pred = (fsg_pnode_t *) gnode_ptr(gn);
00554                         pred->next.succ = pnode;
00555                     }
00556                 }
00557                 else {          /* Predecessor = word internal node */
00558                     pred->next.succ = pnode;
00559                 }
00560                 pnode->alloc_next = head;
00561                 head = pnode;
00562 
00563                 hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, pnode->ci_ext);
00564 
00565                 pred = pnode;
00566             }
00567             else {              /* Leaf phone, handle required right contexts */
00568                 /* Note, leaf phones are not part of the tree */
00569                 xwdssid_t *rssid;
00570                 memset((void *) ssid_pnode_map, 0,
00571                        n_ci * sizeof(fsg_pnode_t *));
00572                 lc = dict_pron(lextree->dict, dictwid, p-1);
00573                 rssid = dict2pid_rssid(lextree->d2p, ci, lc);
00574 
00575                 for (i = 0; rclist[i] >= 0; i++) {
00576                     rc = rclist[i];
00577 
00578                     j = rssid->cimap[rc];
00579                     ssid = rssid->ssid[j];
00580                     pnode = ssid_pnode_map[j];
00581 
00582                     if (!pnode) {       /* Allocate pnode for this new ssid */
00583                         pnode =
00584                             (fsg_pnode_t *) ckd_calloc(1,
00585                                                        sizeof
00586                                                        (fsg_pnode_t));
00587                         pnode->ctx = lextree->ctx;
00588                         /* We are plugging the word prob here. Ugly */
00589                         /* pnode->logs2prob = lextree->pip; */
00590                         pnode->logs2prob = fsg_link_logs2prob(fsglink) + lextree->pip;
00591                         pnode->ci_ext = dict_pron(lextree->dict, dictwid, p);
00592                         pnode->ppos = p;
00593                         pnode->leaf = TRUE;
00594                         pnode->sibling = rc_pnodelist ?
00595                             (fsg_pnode_t *) gnode_ptr(rc_pnodelist) : NULL;
00596                         pnode->next.fsglink = fsglink;
00597                         pnode->alloc_next = head;
00598                         head = pnode;
00599 
00600                         hmm_init(lextree->ctx, &pnode->hmm, FALSE, ssid, pnode->ci_ext);
00601 
00602                         rc_pnodelist =
00603                             glist_add_ptr(rc_pnodelist, (void *) pnode);
00604                         ssid_pnode_map[j] = pnode;
00605                     }
00606                     else {
00607                         assert(hmm_nonmpx_ssid(&pnode->hmm) == ssid);
00608                     }
00609                     fsg_pnode_add_ctxt(pnode, rc);
00610                 }
00611 
00612                 if (p == 1) {   /* Predecessor = set of root nodes for left ctxts */
00613                     for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
00614                         pred = (fsg_pnode_t *) gnode_ptr(gn);
00615                         if (!pred->next.succ)
00616                             pred->next.succ = (fsg_pnode_t *) gnode_ptr(rc_pnodelist);
00617                         else {
00618                             /* Link to the end of the sibling chain */
00619                             fsg_pnode_t *succ = pred->next.succ;
00620                             while (succ->sibling) succ = succ->sibling;
00621                             succ->sibling = (fsg_pnode_t*) gnode_ptr(rc_pnodelist);
00622                             /* Since all entries of lc_pnodelist point
00623                                to the same array, sufficient to update it once */
00624                             break; 
00625                         }
00626                     }
00627                 }
00628                 else {          /* Predecessor = word internal node */
00629                     if (!pred->next.succ)
00630                         pred->next.succ = (fsg_pnode_t *) gnode_ptr(rc_pnodelist);
00631                     else {
00632                         /* Link to the end of the sibling chain */
00633                         fsg_pnode_t *succ = pred->next.succ;
00634                         while (succ->sibling) succ = succ->sibling;
00635                         succ->sibling = (fsg_pnode_t *) gnode_ptr(rc_pnodelist);
00636                     }
00637                 }
00638             }
00639         }
00640 
00641         ckd_free((void *) ssid_pnode_map);
00642         /* glist_free(lc_pnodelist);  Nope; this gets freed outside */
00643         glist_free(rc_pnodelist);
00644     }
00645 
00646     *alloc_head = head;
00647 
00648     return root;
00649 }
00650 
00651 
00652 static fsg_pnode_t *
00653 fsg_psubtree_init(fsg_lextree_t *lextree,
00654                   fsg_model_t * fsg, int32 from_state,
00655                   fsg_pnode_t ** alloc_head)
00656 {
00657     int32 dst;
00658     gnode_t *gn;
00659     fsg_link_t *fsglink;
00660     fsg_pnode_t *root;
00661     int32 n_ci;
00662     fsg_glist_linklist_t *glist = NULL;
00663 
00664     root = NULL;
00665     assert(*alloc_head == NULL);
00666 
00667     n_ci = bin_mdef_n_ciphone(lextree->mdef);
00668     if (n_ci > (FSG_PNODE_CTXT_BVSZ * 32)) {
00669         E_FATAL
00670             ("#phones > %d; increase FSG_PNODE_CTXT_BVSZ and recompile\n",
00671              FSG_PNODE_CTXT_BVSZ * 32);
00672     }
00673     for (dst = 0; dst < fsg_model_n_state(fsg); dst++) {
00674         /* Add all links from from_state to dst */
00675         for (gn = fsg_model_trans(fsg, from_state, dst); gn;
00676              gn = gnode_next(gn)) {
00677             /* Add word emitted by this transition (fsglink) to lextree */
00678             fsglink = (fsg_link_t *) gnode_ptr(gn);
00679 
00680             assert(fsg_link_wid(fsglink) >= 0);     /* Cannot be a null trans */
00681 
00682             root = psubtree_add_trans(lextree, root, &glist, fsglink,
00683                                       lextree->lc[from_state],
00684                                       lextree->rc[dst],
00685                                       alloc_head);
00686         }
00687     }
00688 
00689     fsg_glist_linklist_free(glist);
00690 
00691     return root;
00692 }
00693 
00694 
00695 static void
00696 fsg_psubtree_free(fsg_pnode_t * head)
00697 {
00698     fsg_pnode_t *next;
00699 
00700     while (head) {
00701         next = head->alloc_next;
00702         hmm_deinit(&head->hmm);
00703         ckd_free(head);
00704         head = next;
00705     }
00706 }
00707 
00708 void fsg_psubtree_dump_node(fsg_lextree_t *tree, fsg_pnode_t *node, FILE *fp)
00709 {    
00710     int32 i;
00711     fsg_link_t *tl;
00712 
00713     /* Indentation */
00714     for (i = 0; i <= node->ppos; i++)
00715         fprintf(fp, "  ");
00716 
00717     fprintf(fp, "%p.@", node);    /* Pointer used as node
00718                          * ID */
00719     fprintf(fp, " %5d.SS", hmm_nonmpx_ssid(&node->hmm));
00720     fprintf(fp, " %10d.LP", node->logs2prob);
00721     fprintf(fp, " %p.SIB", node->sibling);
00722     fprintf(fp, " %s.%d", bin_mdef_ciphone_str(tree->mdef, node->ci_ext), node->ppos);
00723     if ((node->ppos == 0) || node->leaf) {
00724         fprintf(fp, " [");
00725         for (i = 0; i < FSG_PNODE_CTXT_BVSZ; i++)
00726             fprintf(fp, "%08x", node->ctxt.bv[i]);
00727         fprintf(fp, "]");
00728     }
00729     if (node->leaf) {
00730         tl = node->next.fsglink;
00731         fprintf(fp, " {%s[%d->%d](%d)}",
00732                 fsg_model_word_str(tree->fsg, tl->wid),
00733                 tl->from_state, tl->to_state, tl->logs2prob);
00734     } else {
00735         fprintf(fp, " %p.NXT", node->next.succ);
00736     }
00737     fprintf(fp, "\n");
00738 
00739     return;
00740 }
00741 
00742 void 
00743 fsg_psubtree_dump(fsg_lextree_t *tree, fsg_pnode_t *root, FILE * fp)
00744 {
00745     fsg_pnode_t *succ;
00746 
00747     if (root == NULL) return;
00748     if (root->ppos == 0) {
00749         while(root->sibling && root->sibling->next.succ == root->next.succ) {
00750             fsg_psubtree_dump_node(tree, root, fp);
00751             root = root->sibling;
00752         }
00753         fflush(fp);
00754     }
00755     
00756     fsg_psubtree_dump_node(tree, root, fp);
00757 
00758     if (root->leaf) {
00759         if (root->ppos == 0 && root->sibling) { // For single-phone words
00760             fsg_psubtree_dump(tree, root->sibling,fp);
00761         }
00762         return;
00763     }
00764 
00765     succ = root->next.succ;
00766     while(succ) {
00767         fsg_psubtree_dump(tree, succ,fp);
00768         succ = succ->sibling;
00769     }
00770 
00771     if (root->ppos == 0) {
00772         fsg_psubtree_dump(tree, root->sibling,fp);
00773         fflush(fp);
00774     }
00775 
00776     return;
00777 }
00778 
00779 void
00780 fsg_psubtree_pnode_deactivate(fsg_pnode_t * pnode)
00781 {
00782     hmm_clear(&pnode->hmm);
00783 }

Generated on Sat Jan 8 2011 for PocketSphinx by  doxygen 1.7.1