searchlat.c

WinCE平台上的语音识别程序

            prev_node = node;
        }

        if (prev_m) {
            node = prev_m->next;
            prev_m->next = node->next;
        }
        else {
            node = nodelist;
            nodelist = node->next;
        }

        node->next = tmplist;
        tmplist = node;
    }

    lattice.latnode_list = tmplist;
}

latnode_t *
search_get_lattice(void)
{
    return (lattice.latnode_list);
}

void
searchlat_init(void)
{
    start_wid = kb_get_word_id(cmd_ln_str("-lmstartsym"));
    finish_wid = kb_get_word_id(cmd_ln_str("-lmendsym"));
    sil_wid = kb_get_word_id("SIL");
    rc_fwdperm = dict_right_context_fwd_perm();
    altpron = cmd_ln_boolean("-reportpron");

    bptbl = search_get_bptable();
    BScoreStack = search_get_bscorestack();

    hyp = search_get_hyp();

    lattice.latnode_list = NULL;
    lattice.final_node = NULL;
}

/* -----------Code for n-best hypotheses, uses the same lattice structure------------- */

/*
 * Tree of all possible paths, rooted at the initial "from" node.  Each partial
 * path (latpath_t) is constructed by extending another partial path--parent--by
 * one node.
 */
typedef struct latpath_s {
    latnode_t *node;            /* Also contains score estimate to final node */
    struct latpath_s *parent;
    struct latpath_s *next;     /* All paths linked linearly, sorted by best score */
    int32 score;                /* Exact score from start node upto node->sf */
} latpath_t;
static latpath_t *path_list;    /* Partial paths to be processed */
static latpath_t *path_tail;    /* Last in path_list */
static latpath_t *paths_done;   /* Partial paths that have been processed */

static int32 n_path;            /* #partial paths in path_list at any time */
static int32 n_hyp_tried;       /* Total #hyps tried */
static int32 n_hyp_reject;      /* #hyps rejected by pruning */
static int32 n_hyp_insert;
static int32 insert_depth;

/* Parameters to prune n-best alternatives search */
#define MAX_PATHS	500     /* Max allowed active paths at any time */
#define MAX_HYP_TRIES	10000

/* Back trace from path to root */
static search_hyp_t *
latpath_seg_back_trace(latpath_t * path)
{
    search_hyp_t *head, *h;

    head = NULL;
    for (; path; path = path->parent) {
        h = (search_hyp_t *) listelem_alloc(sizeof(search_hyp_t));
        h->wid = path->node->wid;
        h->word = kb_get_word_str(h->wid);
        h->sf = path->node->sf;
        h->ef = path->node->fef;    /* Approximately */

        h->next = head;
        head = h;
    }

    return head;
}

/*
 * For each node in any path between from and end of utt, find the best score
 * from "from".sf to end of utt.  (NOTE: Uses bigram probs; this is an estimate
 * of the best score from "from".
 */
static int32
best_rem_score(latnode_t * from)
{
    latlink_t *link;
    int32 bestscore, score;

    if (from->info.rem_score <= 0)
        return (from->info.rem_score);

    /* Best score from "from" to end of utt not known; compute from successors */
    bestscore = WORST_SCORE;
    for (link = from->links; link; link = link->next) {
        score = best_rem_score(link->to);
        score += link->link_scr;
        score += LWMUL(lm_bg_score(from->wid, link->to->wid), lw_factor);
        if (score > bestscore)
            bestscore = score;
    }
    from->info.rem_score = bestscore;

    return (bestscore);
}

/*
 * Insert newpath in sorted (by path score) list of paths.  But if newpath is
 * too far down the list, drop it.
 * total_score = path score (newpath) + rem_score to end of utt.
 */
static void
path_insert(latpath_t * newpath, int32 total_score)
{
    latpath_t *prev, *p;
    int32 i;

    prev = NULL;
    for (i = 0, p = path_list; (i < MAX_PATHS) && p; p = p->next, i++) {
        if ((p->score + p->node->info.rem_score) < total_score)
            break;
        prev = p;
    }

    /* newpath should be inserted between prev and p */
    if (i < MAX_PATHS) {
        /* Insert new partial hyp */
        newpath->next = p;
        if (!prev)
            path_list = newpath;
        else
            prev->next = newpath;
        if (!p)
            path_tail = newpath;

        n_path++;
        n_hyp_insert++;
        insert_depth += i;
    }
    else {
        /* newpath score too low; reject it and also prune paths beyond MAX_PATHS */
        path_tail = prev;
        prev->next = NULL;
        n_path = MAX_PATHS;
        listelem_free(newpath, sizeof(latpath_t));

        n_hyp_reject++;
        for (; p; p = newpath) {
            newpath = p->next;
            listelem_free(p, sizeof(latpath_t));
            n_hyp_reject++;
        }
    }
}

/* Find all possible extensions to given partial path */
static void
path_extend(latpath_t * path)
{
    latlink_t *link;
    latpath_t *newpath;
    int32 total_score, tail_score;

    /* Consider all successors of path->node */
    for (link = path->node->links; link; link = link->next) {
        /* Skip successor if no path from it reaches the final node */
        if (link->to->info.rem_score <= WORST_SCORE)
            continue;

        /* Create path extension and compute exact score for this extension */
        newpath = (latpath_t *) listelem_alloc(sizeof(latpath_t));
        newpath->node = link->to;
        newpath->parent = path;
        newpath->score = path->score + link->link_scr;
        if (path->parent)
            newpath->score += LWMUL(lm_tg_score(path->parent->node->wid,
                                                path->node->wid,
                                                newpath->node->wid),
                                    lw_factor);
        else
            newpath->score +=
                LWMUL(lm_bg_score(path->node->wid, newpath->node->wid),
                      lw_factor);

        /* Insert new partial path hypothesis into sorted path_list */
        n_hyp_tried++;
        total_score = newpath->score + newpath->node->info.rem_score;

        /* First see if hyp would be worse than the worst */
        if (n_path >= MAX_PATHS) {
            tail_score =
                path_tail->score + path_tail->node->info.rem_score;
            if (total_score < tail_score) {
                listelem_free(newpath, sizeof(latpath_t));
                n_hyp_reject++;
                continue;
            }
        }

        path_insert(newpath, total_score);
    }
}

void
search_hyp_free(search_hyp_t * h)
{
    search_hyp_t *tmp;

    while (h) {
        tmp = h->next;
        listelem_free(h, sizeof(search_hyp_t));
        h = tmp;
    }
}

static int32
hyp_diff(search_hyp_t * hyp1, search_hyp_t * hyp2)
{
    search_hyp_t *h1, *h2;

    for (h1 = hyp1, h2 = hyp2;
         h1 && h2 && (h1->wid == h2->wid); h1 = h1->next, h2 = h2->next);
    return (h1 || h2) ? 1 : 0;
}

/*
 * Get n best alternatives in lattice for the given frame range [sf..ef].
 * w1 and w2 provide left context; w1 may be -1.
 * NOTE: Clobbers any previously returned hypotheses!!
 * Return values: no. of alternative hypotheses returned in alt; -1 if error.
 */
int32
search_get_alt(int32 n,         /* In: No. of alternatives to look for */
               int32 sf, int32 ef,      /* In: Start/End frame */
               int32 w1, int32 w2,      /* In: context words */
               search_hyp_t *** alt_out)
{                               /* Out: array of alternatives */
    latnode_t *node;
    latpath_t *path, *top;
    int32 i, j, scr, n_alt;
    static search_hyp_t **alt = NULL;
    static int32 max_alt_hyp = 0;
    char remLMName[128];
    extern char *get_current_lmname();

    if (n <= 0)
        return -1;

    /* Save currently active LM and switch to the one associated with the lattice */
    strcpy(remLMName, get_current_lmname());
    uttproc_set_lm(altLMName);

    for (i = 0; i < max_alt_hyp; i++) {
        search_hyp_free(alt[i]);
        alt[i] = NULL;
    }

    if (n > max_alt_hyp) {
        if (alt)
            free(alt);
        max_alt_hyp = (n + 255) & 0xffffff00;
        alt = ckd_calloc(max_alt_hyp, sizeof(search_hyp_t *));
    }

    *alt_out = NULL;

    /* If no permanent lattice available to be searched, return */
    if (lattice.latnode_list == NULL) {
        /* MessageBoxX("permanent lattice trouble in searchlat.c"); */
        E_ERROR("NULL lattice\n");
        uttproc_set_lm(remLMName);
        return 0;
    }

    /* Initialize rem_score to default values */
    for (node = lattice.latnode_list; node; node = node->next) {
        if (node == lattice.final_node)
            node->info.rem_score = 0;
        else if (!node->links)
            node->info.rem_score = WORST_SCORE;
        else
            node->info.rem_score = 1;   /* +ve => unknown value */
    }

    /* Create initial partial hypotheses list consisting of nodes starting at sf */
    n_path = 0;
    n_hyp_reject = 0;
    n_hyp_tried = 0;
    n_hyp_insert = 0;
    insert_depth = 0;
    paths_done = NULL;

    path_list = path_tail = NULL;
    for (node = lattice.latnode_list; node; node = node->next) {
        if (node->sf == sf) {
            best_rem_score(node);

            path = (latpath_t *) listelem_alloc(sizeof(latpath_t));
            path->node = node;
            path->parent = NULL;
            scr =
                (w1 < 0) ? lm_bg_score(w2, node->wid) : lm_tg_score(w1, w2,
                                                                    node->
                                                                    wid);
            path->score = scr;

            path_insert(path, scr + node->info.rem_score);
        }
    }

    /* Find n hypotheses */
    for (n_alt = 0;
         path_list && (n_alt < n) && (n_hyp_tried < MAX_HYP_TRIES);) {
        /* Pop the top (best) partial hypothesis */
        top = path_list;
        path_list = path_list->next;
        if (top == path_tail)
            path_tail = NULL;
        n_path--;

        if ((top->node->sf >= ef) || ((top->node == lattice.final_node) &&
                                      (ef > lattice.final_node->sf))) {
            /* Complete hypothesis; generate output, but omit last (bracketing) node */
            alt[n_alt] = latpath_seg_back_trace(top->parent);
            /* alt[n_alt] = latpath_seg_back_trace (top); */

            /* Accept hyp only if non-empty */
            if (alt[n_alt]) {
                /* Check if hypothesis already output */
                for (j = 0; (j < n_alt) && (hyp_diff(alt[j], alt[n_alt]));
                     j++);
                if (j >= n_alt) /* New, distinct alternative hypothesis */
                    n_alt++;
                else {
                    search_hyp_free(alt[n_alt]);
                    alt[n_alt] = NULL;
                }
            }
#if 0
            /* Print path here for debugging */
#endif
        }
        else {
            if (top->node->fef < ef)
                path_extend(top);
        }

        /*
         * Add top to paths already processed; cannot be freed because other paths
         * point to it.
         */
        top->next = paths_done;
        paths_done = top;
    }

#if defined(SEARCH_PROFILE)
    E_INFO
        ("#HYP = %d, #INSERT = %d, #REJECT = %d, Avg insert depth = %.2f\n",
         n_hyp_tried, n_hyp_insert, n_hyp_reject,
         insert_depth / ((double) n_hyp_insert + 1.0));
#endif

    /* Clean up */
    while (path_list) {
        top = path_list;
        path_list = path_list->next;
        listelem_free(top, sizeof(latpath_t));
    }
    while (paths_done) {
        top = paths_done;
        paths_done = paths_done->next;
        listelem_free(top, sizeof(latpath_t));
    }

    *alt_out = alt;

    /* Restore original LM name */
    uttproc_set_lm(remLMName);

    return n_alt;
}

void
search_save_lattice(void)
{
    if (lattice.latnode_list)
        destroy_lattice(lattice.latnode_list);

    lattice.latnode_list = latnode_list;
    lattice.start_node = start_node;
    lattice.final_node = final_node;
    latnode_list = NULL;
}

void
search_delete_saved_lattice(void)
{
    if (lattice.latnode_list) {
        destroy_lattice(lattice.latnode_list);
        lattice.latnode_list = NULL;
        lattice.start_node = NULL;
        lattice.final_node = NULL;
    }
}

char *
searchGetAltLMName(void)
{
    return altLMName;
}

int32
searchSetAltUttid(char *uttid)
{
    int32 i;

    for (i = 0; i < MAX_LAT_QUEUE; i++) {
        if (strcmp(latQueue[i].uttid, uttid) == 0) {
            lattice.latnode_list = latQueue[i].lattice.latnode_list;
            lattice.start_node = latQueue[i].lattice.start_node;
            lattice.final_node = latQueue[i].lattice.final_node;

            /* We also need to add code to set the language model for this uttid. */
            strcpy(altLMName, latQueue[i].lmName);

            /* return success because we found utt for this uttid. */
            return 0;
        }
    }

    /* return failure because we could not find alts for the desired utt. */
    return 1;
}

void
searchSaveLatQueue(char *uttid, char *lmName)
{
    int32 i, found, addIndex, minIndex = 0;     /* FIXME: good default? */

    if (!latQueueInit) {
        for (i = 0; i < MAX_LAT_QUEUE; i++) {
            /* latQueue[i].lattice = NULL; *//* Why is this commented out? */
            latQueue[i].uttid[0] = '\0';
            latQueue[i].lmName[0] = '\0';
            latQueue[i].addIndex = -1;
        }
        latQueueInit = 1;
    }

    /* Find the next empty queue slot or the oldest uttid if all slots are full */
    for (addIndex = 100000, found = -1, i = 0; i < MAX_LAT_QUEUE; i++) {
        if (latQueue[i].addIndex == -1) {
            found = i;
            break;
        }
        else {
            if (latQueue[i].addIndex < addIndex) {
                addIndex = latQueue[i].addIndex;
                minIndex = i;
            }
        }
    }

    /* No empty slots, so free a slot so we can reuse it. */
    if (found == -1) {
        destroy_lattice(latQueue[minIndex].lattice.latnode_list);
        latQueue[minIndex].lattice.latnode_list = NULL;
        latQueue[minIndex].lattice.start_node = NULL;
        latQueue[minIndex].lattice.final_node = NULL;
        found = minIndex;
    }

    /* Finally place a copy of the relevant data in the queue */
    latQueue[found].lattice.latnode_list = latnode_list;
    latQueue[found].lattice.start_node = start_node;
    latQueue[found].lattice.final_node = final_node;
    strcpy(latQueue[found].lmName, lmName);
    strcpy(latQueue[found].uttid, uttid);
    latQueue[found].addIndex = latQueueAddIndex++;

    latnode_list = NULL;
}