s3_astar.c

来自「CMU大名鼎鼎的SPHINX－3大词汇量连续语音识别系统」· C语言 代码 · 共 1,267 行 · 第 1/3 页

/* ====================================================================
 * Copyright (c) 1995-2004 Carnegie Mellon University.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * This work was supported in part by funding from the Defense Advanced 
 * Research Projects Agency and the National Science Foundation of the 
 * United States of America, and the CMU Sphinx Speech Consortium.
 *
 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * ====================================================================
 *
 */
/*
 * astar.c -- A* DAG search to create N-best lists
 *
 * **********************************************
 * CMU ARPA Speech Project
 *
 * Copyright (c) 1996 Carnegie Mellon University.
 * ALL RIGHTS RESERVED.
 * **********************************************
 * 
 * HISTORY
 * 
 * 27-Feb-1998	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added check in building DAG for avoiding cycles with dagfudge.
 * 
 * 08-Sep-97	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added .Z compression option to lattice and nbest files.
 * 
 * 22-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added -maxedge argument to control memory usage.
 * 		Added -maxlmop and -maxlpf options to control execution time.
 * 		Added -maxppath option to control CPU/memory usage.
 * 
 * 18-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added reporting of acoustic and LM scores for each word in each hyp.
 * 		Changed LM scores in nbest files to be unscaled (i.e., without any
 * 		language weight or insertion penalty.
 * 
 * 09-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added code in dag_link_bypass to update an existing link, if any,
 * 		instead of adding several bypass links between the same two nodes.
 * 		This reduces CPU and memory requirements considerably.
 * 
 * 05-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added -dagfudge and -min_endfr parameter handling.
 * 
 * 28-Oct-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Started, copying from nbest.c.
 */

/** \file s3_astar.c
 * \brief engine for s3.0 astar
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include <s3types.h>
#include "s3_dag.h"
#include <mdef.h>
#include <tmat.h>
#include <dict.h>
#include <lm.h>
#include <fillpen.h>
#include <search.h>
#include <logs3.h>


static dag_t dag;

static s3wid_t startwid;	/* Begin silence */
static s3wid_t finishwid;	/* End silence */

static int32 beam;

/****************************************
 * Globals!   This is a hack!		*
 ****************************************/

dict_t *dict;		/* The dictionary */
lm_t *lm;		/* The Language model */
fillpen_t *fpen;	/* The filler penalty structure. */
s3lmwid_t *dict2lmwid;	/* Mapping from decoding dictionary wid's to lm ones.  They may not be the same! */


static int32 maxlmop;		/* Max LM ops allowed before utterance aborted */
static int32 lmop;		/* #LM ops actually made */
static int32 maxedge;		/* Max #edges in DAG allowed before utterance aborted */


static int32 filler_word (s3wid_t w)
{
    if ((w == startwid) || (w == finishwid))
	return 0;
    if ((w >= dict->filler_start) && (w <= dict->filler_end))
	return 1;
    return 0;
}


/**
 * Link two DAG nodes with the given arguments
 * Return value: 0 if successful, -1 if maxedge limit exceeded.
 */
static int32 dag_link (dagnode_t *pd, dagnode_t *d, int32 ascr)
{
    daglink_t *l;
    
    /* Link d into successor list for pd */
    l = (daglink_t *) listelem_alloc (sizeof(daglink_t));
    l->node = d;
    l->ascr = ascr;
    l->is_filler_bypass = 0;
    l->next = pd->succlist;
    pd->succlist = l;

    l = (daglink_t *) listelem_alloc (sizeof(daglink_t));
    l->node = pd;
    l->ascr = ascr;
    l->is_filler_bypass = 0;
    l->next = d->predlist;
    d->predlist = l;

    dag.nlink++;

    return (dag.nlink > maxedge) ? -1 : 0;
}


/**
 * Add a filler-bypass link between the two nodes or update an existing bypass link if
 * the new score is better.
 * Return value: 0 if successful, -1 if maxedge limit exceeded.
 */
static int32 dag_link_bypass (dagnode_t *pd, dagnode_t *d, int32 ascr)
{
    daglink_t *l;
    
    /* Find the existing bypass link, if any, between pd and d */
    for (l = pd->succlist; l && ((! l->is_filler_bypass) || (l->node != d)); l = l->next);

    if (! l) {
	/* No existing bypass link; create one from pd to d */
	l = (daglink_t *) listelem_alloc (sizeof(daglink_t));
	l->node = d;
	l->ascr = ascr;
	l->is_filler_bypass = 1;
	l->next = pd->succlist;
	pd->succlist = l;
	
	dag.nlink++;
	dag.nbypass++;
    } else if (l->ascr < ascr) {
	/* Link pd -> d exists; update link score for it */
	l->ascr = ascr;
    }

    return (dag.nlink > maxedge) ? -1 : 0;
}


static int32 dag_param_read (FILE *fp, char *param, int32 *lineno)
{
    char line[1024], wd[1024];
    int32 n;
    
    while (fgets (line, 1024, fp) != NULL) {
	(*lineno)++;
	if (line[0] == '#')
	    continue;
	if ((sscanf (line, "%s %d", wd, &n) == 2) && (strcmp (wd, param) == 0))
	    return n;
    }
    return -1;
}


#if 0
static void daglinks_dump (dagnode_t *d)
{
    daglink_t *l;
    
    for (l = d->succlist; l; l = l->next)
	printf ("%6d %5d %12d %s\n", l->node->seqid, l->node->sf, l->ascr,
		dict_wordstr (dict, l->node->wid));
}
#endif


/**
 * Mark every node that has a path to the argument dagnode as "reachable".
 */
static void dag_mark_reachable (dagnode_t *d)
{
    daglink_t *l;
    
    d->reachable = 1;
    for (l = d->predlist; l; l = l->next)
	if (! l->node->reachable)
	    dag_mark_reachable (l->node);
}


static void dag_remove_unreachable ( void )
{
    dagnode_t *d;
    daglink_t *l, *pl, *nl;
    
    for (d = dag.list; d; d = d->alloc_next) {
	if (! d->reachable) {
	    /* Remove successor node links */
	    for (l = d->succlist; l; l = nl) {
		nl = l->next;
		listelem_free ((char *) l, sizeof(daglink_t));
	    }
	    d->succlist = NULL;

	    /* Remove predecessor links */
	    for (l = d->predlist; l; l = nl) {
		nl = l->next;
		listelem_free ((char *) l, sizeof(daglink_t));
	    }
	    d->predlist = NULL;
	} else {
	    /* Remove successor links to unreachable nodes; predecessors are reachable */
	    pl = NULL;
	    for (l = d->succlist; l; l = nl) {
		nl = l->next;
		if (! l->node->reachable) {
		    if (! pl)
			d->succlist = nl;
		    else
			pl->next = nl;
		    listelem_free ((char *) l, sizeof(daglink_t));
		} else
		    pl = l;
	    }
	}
    }
}


/**
 * Add auxiliary links bypassing filler nodes in DAG.  In principle, a new such
 * auxiliary link can end up at ANOTHER filler node, and the process must be repeated
 * for complete transitive closure.  But removing fillers in the order in which they
 * appear in dag.list ensures that succeeding fillers have already been bypassed.
 * (See comment before dag_load.)
 * Return value: 0 if successful; -1 if DAG maxedge limit exceeded.
 */
static int32 dag_bypass_filler_nodes ( void )
{
    dagnode_t *d, *pnode, *snode;
    daglink_t *plink, *slink;
    int32 scr;
    
    /* Create additional links in DAG bypassing filler nodes */
    for (d = dag.list; d; d = d->alloc_next) {
	if (! filler_word (d->wid))	/* No need to bypass this node */
	    continue;
	
	/* For each link TO d add a link to d's successors */
	for (plink = d->predlist; plink; plink = plink->next) {
	    pnode = plink->node;
	    scr = plink->ascr + fillpen(fpen, dict_basewid (dict, d->wid));
	    
	    /* Link this predecessor of d to successors of d */
	    for (slink = d->succlist; slink; slink = slink->next) {
		snode = slink->node;

		/* Link only to non-filler successors; fillers have been bypassed */
		if (! filler_word (snode->wid))
		    if (dag_link_bypass (pnode, snode, scr + slink->ascr) < 0)
			return -1;
	    }
	}
    }

    return 0;
}


/**
 * For each link compute the heuristic score (hscr) from the END of the link to the
 * end of the utterance; i.e. the best score from the end of the link to the dag
 * exit node.
 */
static void dag_compute_hscr ( void )
{
    dagnode_t *d, *d1, *d2;
    daglink_t *l1, *l2;
    s3wid_t bw0, bw1, bw2;
    int32 hscr, best_hscr;
    
    for (d = dag.list; d; d = d->alloc_next) {
	bw0 = filler_word (d->wid) ? BAD_S3WID : dict_basewid (dict, d->wid);

	/* For each link from d, compute heuristic score */
	for (l1 = d->succlist; l1; l1 = l1->next) {
	    assert (l1->node->reachable);

	    d1 = l1->node;
	    if (d1 == dag.exit.node)
		l1->hscr = 0;
	    else {
		bw1 = filler_word (d1->wid) ? BAD_S3WID : dict_basewid (dict, d1->wid);
		if (NOT_S3WID(bw1)) {
		    bw1 = bw0;
		    bw0 = BAD_S3WID;
		}
		
		best_hscr = (int32)0x80000000;
		for (l2 = d1->succlist; l2; l2 = l2->next) {
		    d2 = l2->node;
		    if (filler_word (d2->wid))
			continue;
		    
		    bw2 = dict_basewid (dict, d2->wid);
		    hscr = l2->hscr + l2->ascr + lm_tg_score (lm, dict2lmwid[bw0], dict2lmwid[bw1], dict2lmwid[bw2], bw2);
		    
		    if (hscr > best_hscr)
			best_hscr = hscr;
		}

		l1->hscr = best_hscr;
	    }
	}
    }
}


static void dag_remove_bypass_links ( void )
{
    dagnode_t *d;
    daglink_t *l, *pl, *nl;
    
    for (d = dag.list; d; d = d->alloc_next) {
	pl = NULL;
	for (l = d->succlist; l; l = nl) {
	    nl = l->next;
	    if (l->is_filler_bypass) {
		if (! pl)
		    d->succlist = nl;
		else
		    pl->next = nl;
		listelem_free ((char *) l, sizeof(daglink_t));
	    } else
		pl = l;
	}
    }
}


/**
 * Load a DAG from a file: each unique <word-id,start-frame> is a node, i.e. with
 * a single start time but it can represent several end times.  Links are created
 * whenever nodes are adjacent in time.
 * dagnodes_list = linear list of DAG nodes allocated, ordered such that nodes earlier
 * in the list can follow nodes later in the list, but not vice versa:  Let two DAG
 * nodes d1 and d2 have start times sf1 and sf2, and end time ranges [fef1..lef1] and
 * [fef2..lef2] respectively.  If d1 appears later than d2 in dag.list, then
 * fef2 >= fef1, because d2 showed up later in the word lattice.  If there is a DAG
 * edge from d1 to d2, then sf1 > fef2.  But fef2 >= fef1, so sf1 > fef1.  Reductio ad
 * absurdum.
 * Return value: 0 if successful, -1 otherwise.
 */
int32 s3astar_dag_load (char *file)
{
    FILE *fp;
    char line[16384], wd[1024];
    int32 nfrm, nnode, sf, fef, lef, ef, lineno;
    int32 i, j, k, l, final, seqid, from, to, ascr;
    int32 fudge, min_ef_range;
    dagnode_t *d, *pd, *tail, **darray;
    s3wid_t w;
    struct lat_s {
	dagnode_t *node;
	int32 ef;
	int32 ascr;
    } *lat;		/* Lattice (bptable) entries in each frame */
    int32 *frm2lat;	/* frm2lat[f] = first lattice entry for frame f */
    float32 lb, f32arg;
    int32 ispipe;
    
    /* Set limit on max DAG edges allowed after which utterance is aborted */
    maxedge = *((int32 *) cmd_ln_access ("-maxedge"));
    
    dag.list = NULL;
    dag.nlink = 0;
    dag.nbypass = 0;
    
    tail = NULL;
    darray = NULL;
    lat = NULL;
    frm2lat = NULL;
    lineno = 0;