47 #include <sphinxbase/ckd_alloc.h>
48 #include <sphinxbase/err.h>
51 #include "fsg_lextree.h"
77 static void fsg_psubtree_free(
fsg_pnode_t *alloc_head);
97 silcipid = bin_mdef_silphone(lextree->
mdef);
98 assert(silcipid >= 0);
99 n_ci = bin_mdef_n_ciphone(lextree->
mdef);
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);
113 for (s = 0; s < fsg->n_state; s++) {
115 for (itor = fsg_model_arcs(fsg, s); itor; itor = fsg_arciter_next(itor)) {
116 fsg_link_t *l = fsg_arciter_get(itor);
119 if (fsg_link_wid(l) >= 0) {
120 dictwid = dict_wordid(lextree->
dict,
121 fsg_model_word_str(lextree->
fsg, l->wid));
130 if (fsg_model_is_filler(fsg, fsg_link_wid(l))) {
132 lextree->
rc[fsg_link_from_state(l)][silcipid] = 1;
133 lextree->
lc[fsg_link_to_state(l)][silcipid] = 1;
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;
149 lextree->
lc[fsg_link_from_state(l)][silcipid] = 1;
150 lextree->
rc[fsg_link_from_state(l)][silcipid] = 1;
162 for (s = 0; s < fsg->n_state; s++) {
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) {
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];
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];
186 for (s = 0; s < fsg->n_state; s++) {
188 for (i = 0; i < n_ci; i++) {
189 if (lextree->
lc[s][i]) {
190 lextree->
lc[s][j] = i;
194 lextree->
lc[s][j] = -1;
197 for (i = 0; i < n_ci; i++) {
198 if (lextree->
rc[s][i]) {
199 lextree->
rc[s][j] = i;
203 lextree->
rc[s][j] = -1;
213 int32 wip, int32 pip)
221 lextree->root = ckd_calloc(fsg_model_n_state(fsg),
223 lextree->alloc_head = ckd_calloc(fsg_model_n_state(fsg),
226 lextree->
dict = dict;
228 lextree->
mdef = mdef;
233 fsg_lextree_lc_rc(lextree);
239 lextree->n_pnode = 0;
241 for (s = 0; s < fsg_model_n_state(fsg); s++) {
243 fsg_psubtree_init(lextree, fsg, s, &(lextree->alloc_head[s]));
245 for (pn = lextree->alloc_head[s]; pn; pn = pn->alloc_next) {
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",
256 E_INFO(
"Allocated %d bytes (%d KiB) for lextree leafnodes\n",
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);
290 for (s = 0; s < fsg_model_n_state(lextree->
fsg); s++)
291 fsg_psubtree_free(lextree->alloc_head[s]);
293 ckd_free_2d(lextree->
lc);
294 ckd_free_2d(lextree->
rc);
295 ckd_free(lextree->root);
296 ckd_free(lextree->alloc_head);
309 glist_free(glist->glist);
310 nxtglist = glist->next;
315 glist_free(glist->glist);
316 nxtglist = glist->next;
328 for (i = 0; i < FSG_PNODE_CTXT_BVSZ; i++)
329 ctxt->bv[i] = 0xffffffff;
353 fsg_link_t * fsglink,
354 int16 *lclist, int16 *rclist,
365 int32 n_ci, p, lc, rc;
366 glist_t lc_pnodelist;
367 glist_t rc_pnodelist;
369 int n_lc_alloc = 0, n_int_alloc = 0, n_rc_alloc = 0;
371 silcipid = bin_mdef_silphone(lextree->
mdef);
372 n_ci = bin_mdef_n_ciphone(lextree->
mdef);
374 wid = fsg_link_wid(fsglink);
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);
381 assert(lclist[0] >= 0);
382 assert(rclist[0] >= 0);
388 int ci = dict_first_phone(lextree->
dict, dictwid);
390 if (dict_filler_word(lextree->
dict, dictwid)) {
397 for (i = 0; lclist[i] >= 0; i++) {
399 ssid = dict2pid_lrdiph_rc(lextree->
d2p, ci, lc, silcipid);
400 tmatid = bin_mdef_pid2tmatid(lextree->
mdef, dict_first_phone(lextree->
dict, dictwid));
402 for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
405 if (hmm_nonmpx_ssid(&pnode->hmm) == ssid) {
407 fsg_pnode_add_ctxt(pnode, lc);
415 pnode->ctx = lextree->
ctx;
416 pnode->next.fsglink = fsglink;
419 + lextree->wip + lextree->pip;
420 pnode->ci_ext = dict_first_phone(lextree->
dict, dictwid);
423 pnode->sibling = root;
424 fsg_pnode_add_ctxt(pnode, lc);
425 pnode->alloc_next = head;
430 hmm_init(lextree->
ctx, &pnode->hmm, FALSE, ssid, tmatid);
433 glist_add_ptr(lc_pnodelist, (
void *) pnode);
437 glist_free(lc_pnodelist);
440 ssid = bin_mdef_pid2ssid(lextree->
mdef, ci);
441 tmatid = bin_mdef_pid2tmatid(lextree->
mdef, ci);
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;
451 pnode->sibling = root;
453 pnode->alloc_next = head;
458 hmm_init(lextree->
ctx, &pnode->hmm, FALSE, ssid, tmatid);
468 for (p = 0; p < pronlen; p++) {
475 for (glist = *curglist;
476 glist && glist->glist && glist->ci != ci && glist->rc != rc;
479 if (glist && glist->ci == ci && glist->rc == rc && glist->glist) {
481 E_DEBUG(2,(
"Found match for (%d,%d)\n", ci, rc));
482 lc_pnodelist = glist->glist;
494 glist->next = *curglist;
499 lc_pnodelist = glist->glist = NULL;
502 for (i = 0; lclist[i] >= 0; i++) {
504 ssid = dict2pid_ldiph_lc(lextree->
d2p, ci, rc, lc);
505 tmatid = bin_mdef_pid2tmatid(lextree->
mdef, dict_first_phone(lextree->
dict, dictwid));
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)
521 pnode->ctx = lextree->
ctx;
525 pnode->logs2prob = lextree->wip + lextree->pip;
526 pnode->ci_ext = dict_first_phone(lextree->
dict, dictwid);
529 pnode->sibling = root;
530 pnode->alloc_next = head;
535 hmm_init(lextree->
ctx, &pnode->hmm, FALSE, ssid, tmatid);
538 glist_add_ptr(lc_pnodelist, (
void *) pnode);
539 ssid_pnode_map[j] = pnode;
541 fsg_pnode_add_ctxt(pnode, lc);
544 glist->glist = lc_pnodelist;
549 else if (p != pronlen - 1) {
553 tmatid = bin_mdef_pid2tmatid(lextree->
mdef,
dict_pron (lextree->
dict, dictwid, p));
555 pnode = pred->next.succ;
556 pnodeyoungest = pnode;
557 while (pnode && (hmm_nonmpx_ssid(&pnode->hmm) != ssid || pnode->leaf)) {
558 pnode = pnode->sibling;
560 if (pnode && (hmm_nonmpx_ssid(&pnode->hmm) == ssid && !pnode->leaf)) {
562 E_DEBUG(2,(
"Found match for %d\n", ci));
569 pnode->ctx = lextree->
ctx;
570 pnode->logs2prob = lextree->pip;
574 pnode->sibling = pnodeyoungest;
576 for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
578 pred->next.succ = pnode;
582 pred->next.succ = pnode;
584 pnode->alloc_next = head;
588 hmm_init(lextree->
ctx, &pnode->hmm, FALSE, ssid, tmatid);
595 memset((
void *) ssid_pnode_map, 0,
599 tmatid = bin_mdef_pid2tmatid(lextree->
mdef,
dict_pron (lextree->
dict, dictwid, p));
601 for (i = 0; rclist[i] >= 0; i++) {
604 j = rssid->
cimap[rc];
605 ssid = rssid->
ssid[j];
606 pnode = ssid_pnode_map[j];
613 pnode->ctx = lextree->
ctx;
616 pnode->logs2prob = (fsg_link_logs2prob(fsglink) >>
SENSCR_SHIFT)
621 pnode->sibling = rc_pnodelist ?
623 pnode->next.fsglink = fsglink;
624 pnode->alloc_next = head;
628 hmm_init(lextree->
ctx, &pnode->hmm, FALSE, ssid, tmatid);
631 glist_add_ptr(rc_pnodelist, (
void *) pnode);
632 ssid_pnode_map[j] = pnode;
635 assert(hmm_nonmpx_ssid(&pnode->hmm) == ssid);
637 fsg_pnode_add_ctxt(pnode, rc);
641 for (gn = lc_pnodelist; gn; gn = gnode_next(gn)) {
643 if (!pred->next.succ)
644 pred->next.succ = (
fsg_pnode_t *) gnode_ptr(rc_pnodelist);
648 while (succ->sibling) succ = succ->sibling;
649 succ->sibling = (
fsg_pnode_t*) gnode_ptr(rc_pnodelist);
657 if (!pred->next.succ)
658 pred->next.succ = (
fsg_pnode_t *) gnode_ptr(rc_pnodelist);
662 while (succ->sibling) succ = succ->sibling;
663 succ->sibling = (
fsg_pnode_t *) gnode_ptr(rc_pnodelist);
669 ckd_free((
void *) ssid_pnode_map);
671 glist_free(rc_pnodelist);
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));
685 fsg_model_t * fsg, int32 from_state,
696 assert(*alloc_head == NULL);
698 n_ci = bin_mdef_n_ciphone(lextree->
mdef);
699 if (n_ci > (FSG_PNODE_CTXT_BVSZ * 32)) {
701 (
"#phones > %d; increase FSG_PNODE_CTXT_BVSZ and recompile\n",
702 FSG_PNODE_CTXT_BVSZ * 32);
705 for (dst = 0; dst < fsg_model_n_state(fsg); dst++) {
707 for (gn = fsg_model_trans(fsg, from_state, dst); gn;
708 gn = gnode_next(gn)) {
710 fsglink = (fsg_link_t *) gnode_ptr(gn);
712 assert(fsg_link_wid(fsglink) >= 0);
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],
723 E_DEBUG(2,(
"State %d has %d outgoing arcs\n", from_state, n_arc));
725 fsg_glist_linklist_free(glist);
737 next = head->alloc_next;
738 hmm_deinit(&head->hmm);
750 for (i = 0; i <= node->ppos; i++)
753 fprintf(fp,
"%p.@", node);
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) {
761 for (i = 0; i < FSG_PNODE_CTXT_BVSZ; i++)
762 fprintf(fp,
"%08x", node->ctxt.bv[i]);
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);
771 fprintf(fp,
" %p.NXT", node->next.succ);
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;
792 fsg_psubtree_dump_node(tree, root, fp);
795 if (root->ppos == 0 && root->sibling) {
796 fsg_psubtree_dump(tree, root->sibling,fp);
801 succ = root->next.succ;
803 fsg_psubtree_dump(tree, succ,fp);
804 succ = succ->sibling;
807 if (root->ppos == 0) {
808 fsg_psubtree_dump(tree, root->sibling,fp);
818 hmm_clear(&pnode->hmm);