searchlat.c

WinCE平台上的语音识别程序

    }
    if (!node) {
        E_ERROR("Couldn't find <s>.0\n");
        return (0);
    }
    start_node = node;

    /* Find final node </s>.last_frame; nothing can follow this node */
    for (node = latnode_list; node; node = node->next) {
        lef = bptbl[node->lef].frame;
        if ((node->wid == finish_wid) && (lef == last_frame))
            break;
    }
    if (!node) {
        E_ERROR("Couldn't find </s>.%d\n", last_frame);
        return 0;
    }
    final_node = node;
    final_node_ascr = bptbl[node->lef].ascr;

    /*
     * Create precedence links between all possible pairs of nodes.  However,
     * ignore nodes from which </s>.last_frame is not reachable.
     */
    final_node->reachable = TRUE;
    for (to = final_node; to; to = to->next) {
        /* Skip if not reachable; it will never be reachable from </s>.last_frame */
        if (!to->reachable)
            continue;

        /* Find predecessors of to : from->fef+1 <= to->sf <= from->lef+1 */
        for (from = to->next; from; from = from->next) {
            ef = bptbl[from->fef].frame;
            lef = bptbl[from->lef].frame;

            if ((to->sf <= ef) || (to->sf > lef + 1))
                continue;

            /* Find bptable entry for "from" that exactly precedes "to" */
            i = from->fef;
            bp_ptr = bptbl + i;
            for (; i <= from->lef; i++, bp_ptr++) {
                if (bp_ptr->wid != from->wid)
                    continue;
                if (bp_ptr->frame >= to->sf - 1)
                    break;
            }

            if ((i > from->lef) || (bp_ptr->frame != to->sf - 1))
                continue;

            /* Find acoustic score from.sf->to.sf-1 with right context = to */
            if (bp_ptr->r_diph >= 0)
                bss_offset =
                    rc_fwdperm[bp_ptr->r_diph][word_dict->dict_list[to->wid]->
                                               ci_phone_ids[0]];
            else
                bss_offset = 0;
            score =
                (BScoreStack[bp_ptr->s_idx + bss_offset] - bp_ptr->score) +
                bp_ptr->ascr;
            if (score > WORST_SCORE) {
                link_latnodes(from, to, score, bp_ptr->frame);
                from->reachable = TRUE;
            }
        }
    }

    /* There must be at least one path between <s>.0 and </s>.last_frame */
    if (!start_node->reachable) {
        E_ERROR("<s>.0 isolated; unreachable\n");
        return (0);
    }

    /* Now change node->{fef,lef} from bptbl indices to frames. */
    for (node = latnode_list; node; node = node->next) {
        node->fef = bptbl[node->fef].frame;
        node->lef = bptbl[node->lef].frame;
    }

    if ((dumplatdir = cmd_ln_str("-dumplatdir")) != NULL) {
        char latfile[1024];

        sprintf(latfile, "%s/%s.lat", dumplatdir, uttproc_get_uttid());
        dump_lattice(latfile);
    }

    /* Change node->wid to base wid if not reporting actual pronunciations. */
    for (node = latnode_list; node; node = node->next) {
        if (!altpron)
            node->wid = word_dict->dict_list[node->wid]->fwid;
    }

    /* Remove SIL and noise nodes from DAG; extend links through them */
    bypass_filler_nodes();

    /* Free nodes unreachable from </s>, and their links */
    delete_unreachable();

    nn = nl = 0;
    for (node = latnode_list; node; node = node->next) {
        for (link = node->links; link; link = link->next)
            nl++;
        nn++;
    }
    n_node = nn;
    n_link = nl;

    return (1);
}

static void
destroy_lattice(latnode_t * node_list)
{
    latnode_t *node, *tnode;
    latlink_t *link, *tlink;

    for (node = node_list; node; node = tnode) {
        tnode = node->next;
        for (link = node->links; link; link = tlink) {
            tlink = link->next;
            listelem_free(link, sizeof(latlink_t));
        }
        listelem_free(node, sizeof(latnode_t));
    }
}

int32
bptbl2latdensity(int32 bptbl_sz, int32 * density)
{
    int32 i, f, sf, ef, wid, lastfr;
    BPTBL_T *bp_ptr;
    latnode_t *node, *node2, *pred, *node2next, *latnodes;

    /* Create lattice nodes; not all these may be useful */
    lastfr = searchFrame();
    latnodes = NULL;

    for (i = 0, bp_ptr = bptbl; i < bptbl_sz; i++, bp_ptr++) {
        sf = (bp_ptr->bp < 0) ? 0 : bptbl[bp_ptr->bp].frame + 1;
        ef = bp_ptr->frame;
        wid = bp_ptr->wid;

        /* Skip non-final </s> entries; note bptable entry for final </s> */
        if ((wid == finish_wid) && (ef < lastfr))
            continue;

        /* Skip if word not in LM */
        if ((!ISA_FILLER_WORD(wid))
            && (!dictwd_in_lm(word_dict->dict_list[wid]->fwid)))
            continue;

        /* See if bptbl entry <wid,sf> already in lattice */
        for (node = latnodes; node; node = node->next) {
            if ((node->wid == wid) && (node->sf == sf))
                break;
        }

        /* For the moment, store bptbl indices in node.{fef,lef} */
        if (node)
            node->lef = ef;
        else {
            /* New node; link to head of list */
            node = (latnode_t *) listelem_alloc(sizeof(latnode_t));
            node->wid = wid;
            node->sf = sf;
            node->fef = node->lef = ef;
            node->reachable = FALSE;
            node->links = NULL;
            node->revlinks = NULL;

            node->next = latnodes;
            latnodes = node;
        }
    }

    /*
     * At this point, latnode_list is ordered such that nodes earlier in the list
     * can follow (in time) those later in the list, but not vice versa.
     */

    /* Merge overlapping instances into one */
    for (node = latnodes; node; node = node->next) {
        pred = node;
        for (node2 = node->next; node2; node2 = node2next) {
            node2next = node2->next;

            if ((node->wid == node2->wid) &&
                (node->sf <= node2->lef) && (node2->sf <= node->lef)) {
                /* Overlapping instances of a word; merge */
                if (node2->sf < node->sf)
                    node->sf = node2->sf;
                if (node2->fef < node->fef)
                    node->fef = node2->fef;
                if (node2->lef > node->lef)
                    node->lef = node2->lef;

                pred->next = node2next;
                listelem_free(node2, sizeof(latnode_t));
            }
            else
                pred = node2;
        }
    }

    for (i = 0; i <= lastfr; i++)
        density[i] = 0;

    for (node = latnodes; node; node = node->next) {
        if (node->lef > node->fef + 2) {        /* A little pruning */
            for (f = node->sf; f <= node->lef; f++)
                (density[f])++;
        }
    }

    while (latnodes) {
        node = latnodes;
        latnodes = latnodes->next;
        listelem_free(node, sizeof(latnode_t));
    }

    return 0;
}

static int32 seg;               /* for traversing hyp[] */

static void
lattice_seg_back_trace(latlink_t * link)
{
    int32 f, latden;
    int32 *lattice_density;

    lattice_density = search_get_lattice_density();

    if (link) {
        lattice_seg_back_trace(link->best_prev);

        if (ISA_REAL_WORD(link->from->wid)) {
            if (seg >= HYP_SZ - 1)
                E_FATAL("**ERROR** Increase HYP_SZ\n");

            hyp[seg].wid = link->from->wid;
            hyp[seg].sf = link->from->sf;
            hyp[seg].ef = link->ef;

            hyp[seg].latden = 0;

            for (f = link->from->sf; f <= link->ef; f++) {
                hyp[seg].latden += lattice_density[f];
            }
            if ((link->ef - link->from->sf + 1) > 0) {
                hyp[seg].latden /= (link->ef - link->from->sf + 1);
            }
            latden = hyp[seg].latden;

            seg++;
            hyp[seg].wid = -1;

            if (cmd_ln_boolean("-backtrace"))
                printf("\t%4d %4d %10d %11d %11d %8d %6d %s\n",
                       link->from->sf, link->ef,
                       (-(link->link_scr)) / (link->ef - link->from->sf +
                                              1), -(link->link_scr),
                       -(link->path_scr), seg_topsen_score(link->from->sf,
                                                           link->ef) /
                       (link->ef - link->from->sf + 1), latden,
                       word_dict->dict_list[link->from->wid]->word);
        }
    }
    else {
        seg = 0;
        hyp[0].wid = -1;

        if (cmd_ln_boolean("-backtrace")) {
            printf
                ("\t%4s %4s %10s %11s %11s %8s %6s %s (Bestpath) (%s)\n",
                 "SFrm", "EFrm", "AScr/Frm", "AScr", "PathScr", "BSDiff",
                 "LatDen", "Word", uttproc_get_uttid());
            printf
                ("\t------------------------------------------------------------------------\n");
        }
    }
}

/*
 * Lattice rescoring:  Goal: Form DAG of nodes based on unique <wid,start-fram> values,
 * and find the best path through the DAG from <<s>,0> to <</s>,last_frame>.
 * Strategy: Find the best score from <<s>,0> to end point of any link and use it to
 * update links further down the path... (reword)
 */
int32
lattice_rescore(lw_t lwf)
{
    latnode_t *node;
    latlink_t *link;
    latlink_t *q_head, *q_tail;
    int32 score, bw0, bw1, bw2;
    int32 fr;
    char *res;
    char *orig_lmname = NULL;

    sil_pen = search_get_sil_penalty();
    filler_pen = search_get_filler_penalty();
    lw_factor = lwf;

    start_wid = search_get_current_startwid();

    if (latnode_list) {
        destroy_lattice(latnode_list);
        latnode_list = NULL;
    }

    if (rescore_lmname) {
        orig_lmname = get_current_lmname();

        if (lm_set_current(rescore_lmname) < 0) {
            E_ERROR("lm_set_current(%s) failed\n", rescore_lmname);
            free(rescore_lmname);
            rescore_lmname = NULL;
        }
    }

    if (!build_lattice(search_get_bptable_size())) {
        E_INFO("build_lattice() failed\n");

        destroy_lattice(latnode_list);
        latnode_list = NULL;

        if (rescore_lmname) {
            free(rescore_lmname);
            rescore_lmname = NULL;

            if (orig_lmname)
                lm_set_current(orig_lmname);
        }

        return -1;
    }

    /* Initialize node fanin counts and path scores */
    for (node = latnode_list; node; node = node->next)
        node->info.fanin = 0;
    for (node = latnode_list; node; node = node->next) {
        for (link = node->links; link; link = link->next) {
            (link->to->info.fanin)++;
            link->path_scr = (int32) 0x80000000;
        }
    }

    /*
     * Form initial queue of optimal partial paths; = links out of start_node.
     * Path score includes LM score for the "to" node of the last link in the
     * path, but not the acoustic score for that node.
     */
    q_head = q_tail = NULL;
    for (link = start_node->links; link; link = link->next) {
        assert(!(ISA_FILLER_WORD(link->to->wid)));

        if (altpron) {
            bw1 = word_dict->dict_list[start_wid]->fwid;
            bw2 = word_dict->dict_list[link->to->wid]->fwid;

            link->path_scr =
                link->link_scr + LWMUL(lm_bg_score(bw1, bw2), lwf);
        }
        else
            link->path_scr = link->link_scr +
                LWMUL(lm_bg_score(start_wid, link->to->wid), lwf);

        link->best_prev = NULL;

        if (!q_head)
            q_head = link;
        else
            q_tail->q_next = link;
        q_tail = link;
    }
    q_tail->q_next = NULL;

    /* Extend partial paths in queue as long as queue not empty */
    while (q_head) {
        /* Update path score for all possible links out of q_head->to */
        node = q_head->to;

#if 0
        printf("QHD %s.%d -> %s.%d (%d, %d)\n",
               word_dict->dict_list[q_head->from->wid]->word, q_head->from->sf,
               word_dict->dict_list[node->wid]->word, node->sf,
               q_head->link_scr, q_head->path_scr);
#endif

        for (link = node->links; link; link = link->next) {
            assert(!(ISA_FILLER_WORD(link->to->wid)));

            if (altpron) {
                bw0 = word_dict->dict_list[q_head->from->wid]->fwid;
                bw1 = word_dict->dict_list[node->wid]->fwid;
                bw2 = word_dict->dict_list[link->to->wid]->fwid;

                score = q_head->path_scr + link->link_scr +
                    LWMUL(lm_tg_score(bw0, bw1, bw2), lwf);
            }
            else
                score = q_head->path_scr + link->link_scr +
                    LWMUL(lm_tg_score
                          (q_head->from->wid, node->wid, link->to->wid),
                          lwf);

            if (score > link->path_scr) {
                link->path_scr = score;
                link->best_prev = q_head;
            }
        }

        if (--(node->info.fanin) == 0) {
            /*
             * Links out of node (q_head->to) updated wrt all incoming links at node.
             * They all now have optimal partial path scores; insert them in optimal
             * partial path queue.
             */
            for (link = node->links; link; link = link->next) {
                q_tail->q_next = link;
                q_tail = link;
            }
            q_tail->q_next = NULL;
        }

        q_head = q_head->q_next;
    }

    /*
     * Rescored all paths to </s>.last_frame; now traceback optimal path.  First,
     * find the best link entering </s>.last_frame.
     */
    {
        latlink_t *best = NULL;

        score = (int32) 0x80000000;
        for (node = latnode_list; node; node = node->next) {
            for (link = node->links; link; link = link->next)
                if ((link->to == final_node) && (link->path_scr > score)) {
                    score = link->path_scr;
                    best = link;
                }
        }

        assert(best != NULL);
        lattice_seg_back_trace(best);

        search_remove_context(hyp);
        search_hyp_to_str();

        /* NB: best->path_scr doesn't include acoustic score for the final </s>! */
        search_set_hyp_total_score(best->path_scr + final_node_ascr);

        search_result(&fr, &res);
        E_INFO("BESTPATH: %s (%s %d)\n",
               res, uttproc_get_uttid(), best->path_scr + final_node_ascr);

        E_INFO("%8d nodes, %d links searched\n\n", n_node, n_link);
    }

    if (rescore_lmname) {
        free(rescore_lmname);
        rescore_lmname = NULL;

        if (orig_lmname)
            lm_set_current(orig_lmname);
    }

    return 0;
}

/*
 * Sort lattice nodes according to extent of end frames.
 */
void
sort_lattice(void)
{
    latnode_t *nodelist, *tmplist;
    int32 m;

    nodelist = lattice.latnode_list;
    tmplist = NULL;

    while (nodelist) {
        latnode_t *prev_node = NULL;
        latnode_t *prev_m = NULL;
        latnode_t *node;

        m = (int32) 0x7fffffff;
        for (node = nodelist; node; node = node->next) {
            if ((node->lef - node->fef + 1) < m) {
                m = node->lef - node->fef + 1;
                prev_m = prev_node;
            }