s3_dag.c

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

/* ====================================================================
 * 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.
 *
 * ====================================================================
 *
 */
/*
 * dag.c -- DAG search
 *
 * **********************************************
 * CMU ARPA Speech Project
 *
 * Copyright (c) 1996 Carnegie Mellon University.
 * ALL RIGHTS RESERVED.
 * **********************************************
 * 
 * HISTORY
 * 
 * 28-Jul-04    ARCHAN at Carnegie Mellon Unversity
 *              First adapted from s3.              
 * 
 * 08-Sep-97	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added .Z compression option to lattice files.
 * 
 * 04-Jun-97	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added dag_chk_linkscr().
 * 
 * 22-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Implemented -maxedge argument to control memory usage.
 * 
 * 21-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added -maxlmop and -maxlpf options to abort utterance if exceeded.
 * 
 * 08-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added exact reporting of word sequence and scores from dag_search.
 * 		For this, added daglink_t.bypass, daglink_t.lscr, daglink_t.src, and
 * 		added bypass argument to dag_link and dag_bypass_link, and changed
 * 		dag_backtrace to find exact best path.
 * 
 * 05-Nov-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Added -dagfudge and -min_endfr parameter handling.
 * 
 * 03-Sep-96	M K Ravishankar ([e-mail]) at Carnegie Mellon University
 * 		Started.
 */

/** \file s3_dag.c
    \brief Engined for s3.0 dag
 */
#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 */



/* Global variables : Hack! */
dict_t *dict;		/* The dictionary */
fillpen_t *fpen;         /* The fillpenalty data structure */
lm_t *lm;                /* Global variables */
s3lmwid_t *dict2lmwid;	/* Mapping from decoding dictionary wid's to lm ones.  They may not be the same! */


static srch_hyp_t *hyp = NULL;	/* The final recognition result */

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 */


/* Get rid of old hyp, if any */
static void hyp_free ( void )
{
    srch_hyp_t *tmphyp;
    
    while (hyp) {
	tmphyp = hyp->next;
	listelem_free ((char *)hyp, sizeof(srch_hyp_t));
	hyp = tmphyp;
    }
}


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;
}


void dag_init (dict_t* _dict )
{
  dict = _dict;

    /* Some key word ids */
    startwid = dict_wordid (dict, S3_START_WORD);
    finishwid = dict_wordid (dict,S3_FINISH_WORD);
    if ((NOT_S3WID(startwid)) || (NOT_S3WID(finishwid)))
	E_FATAL("%s or %s missing from dictionary\n", S3_START_WORD, S3_FINISH_WORD);

    /* Initialize DAG structure */
    dag.list = NULL;

    /* Set limit on max DAG edges allowed after which utterance is aborted */
    maxedge = *((int32 *) cmd_ln_access ("-maxedge"));
}


/*
 * 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, int32 ef, daglink_t *byp)
{
    daglink_t *l;
    
    /* Link d into successor list for pd */
    if (pd) {	/* Special condition for root node which doesn't have a predecessor */
	l = (daglink_t *) listelem_alloc (sizeof(daglink_t));
	l->node = d;
	l->src = pd;
	l->bypass = byp;	/* This is a FORWARD link!! */
	l->ascr = ascr;
	l->pscr = (int32)0x80000000;
	l->pscr_valid = 0;
	l->history = NULL;
	l->ef = ef;
	l->next = pd->succlist;
	pd->succlist = l;
    }

    /* Link pd into predecessor list for d */
    l = (daglink_t *) listelem_alloc (sizeof(daglink_t));
    l->node = pd;
    l->src = d;
    l->bypass = byp;		/* This is a FORWARD link!! */
    l->ascr = ascr;
    l->pscr = (int32)0x80000000;
    l->pscr_valid = 0;
    l->history = NULL;
    l->ef = ef;
    l->next = d->predlist;
    d->predlist = l;

    dag.nlink++;

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


static daglink_t *find_succlink (dagnode_t *src, dagnode_t *dst)
{
    daglink_t *l;

    for (l = src->succlist; l && (l->node != dst); l = l->next);
    return l;
}


static daglink_t *find_predlink (dagnode_t *src, dagnode_t *dst)
{
    daglink_t *l;

    for (l = src->predlist; l && (l->node != dst); l = l->next);
    return l;
}


/*
 * Like dag_link but check if link already exists.  If so, replace if new score better.
 * Return value: 0 if successful, -1 if maxedge limit exceeded.
 */
static int32 dag_update_link (dagnode_t *pd, dagnode_t *d, int32 ascr,
			      int32 ef, daglink_t *byp)
{
    daglink_t *l, *r;
    l = find_succlink (pd, d);

    if (! l)
	return (dag_link (pd, d, ascr, ef, byp));

    if (l->ascr < ascr) {
	r = find_predlink (d, pd);

	assert (r && (r->ascr == l->ascr));
	l->ascr = r->ascr = ascr;
	l->ef = r->ef = ef;
	l->bypass = r->bypass = byp;
    }
    
    return 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;
}


/*
 * Remove filler nodes from DAG by replacing each link TO a filler with links
 * to its successors.  In principle, successors can be fillers and the process
 * must be repeated.  But removing fillers in the order in which they appear in
 * dag.list ensures that succeeding fillers have already been eliminated.
 * Return value: 0 if successful; -1 if DAG maxedge limit exceeded.
 */
static int32 dag_remove_filler_nodes ( void )
{
    dagnode_t *d, *pnode, *snode;
    daglink_t *plink, *slink;
    int32 ascr=0;
    
    assert(dag.list);

    for (d = dag.list; d; d = d->alloc_next) {

	if (! filler_word (d->wid))
	    continue;
	

	/* Replace each link TO d with links to d's successors */
	for (plink = d->predlist; plink; plink = plink->next) {
	    pnode = plink->node;

	    ascr = plink->ascr; 
	    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 eliminated */
		if (! filler_word (snode->wid)) {
		    /* Update because a link may already exist */
		    if (dag_update_link (pnode, snode,
					 ascr + slink->ascr, plink->ef, slink) < 0)
			return -1;
		}
	    }
	}
    }
    return 0;
}


/*
 * 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 s3dag_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;
    
    dag.list = NULL;
    dag.nlink = 0;
    dag.nbypass =0;
    
    tail = NULL;
    darray = NULL;
    lat = NULL;
    frm2lat = NULL;
    lineno = 0;
    
    E_INFO("Reading DAG file: %s\n", file);
    if ((fp = fopen_compchk (file, &ispipe)) == NULL) {
	E_ERROR("fopen_compchk(%s) failed\n", file);
	return -1;
    }
    
    /* Read and verify logbase (ONE BIG HACK!!) */
    if (fgets (line, sizeof(line), fp) == NULL) {
	E_ERROR ("Premature EOF(%s)\n", file);
	goto load_error;
    }
    if (strncmp (line, "# getcwd: ", 10) != 0) {
	E_ERROR ("%s does not begin with '# getcwd: '\n", file);
	goto load_error;
    }
    if (fgets (line, sizeof(line), fp) == NULL) {
	E_ERROR ("Premature EOF(%s)\n", file);
	goto load_error;
    }
    if ((strncmp (line, "# -logbase ", 11) != 0) || (sscanf (line+11, "%f", &lb) != 1)) {
	E_WARN ("%s: Cannot find -logbase in header\n", file);
    } else {
	f32arg = *((float32 *) cmd_ln_access ("-logbase"));
	if ((lb <= 1.0) || (lb > 2.0) || (f32arg <= 1.0) || (f32arg > 2.0))
	    E_ERROR ("%s: logbases out of range; cannot be verified\n", file);
	else {
	    int32 orig, this;
	    float64 diff;
	    
	    orig = logs3 (lb - 1.0);
	    this = logs3 (f32arg - 1.0);
	    diff = ((orig - this) * 1000.0) / orig;
	    if (diff < 0)
		diff = -diff;
	    
	    if (diff > 1.0)		/* Hack!! Hardwired tolerance limits on logbase */
		E_ERROR ("%s: logbase inconsistent: %e\n", file, lb);
	}
    }
    

    /* Min. endframes value that a node must persist for it to be not ignored */
    min_ef_range = *((int32 *) cmd_ln_access ("-min_endfr"));
    
    /* Read Frames parameter */
    nfrm = dag_param_read (fp, "Frames", &lineno);
    if (nfrm <= 0) {
	E_ERROR("Frames parameter missing or invalid\n");
	goto load_error;
    }
    dag.nfrm = nfrm;

    
    /* Read Nodes parameter */
    lineno = 0;
    nnode = dag_param_read (fp, "Nodes", &lineno);
    if (nnode <= 0) {
	E_ERROR("Nodes parameter missing or invalid\n");
	goto load_error;
    }
    
    /* Read nodes */
    darray = (dagnode_t **) ckd_calloc (nnode, sizeof(dagnode_t *));
    for (i = 0; i < nnode; i++) {
	if (fgets (line, 1024, fp) == NULL) {
	    E_ERROR ("Premature EOF(%s)\n", file);
	    goto load_error;
	}
	lineno++;
	
	if ((k = sscanf (line, "%d %s %d %d %d", &seqid, wd, &sf, &fef, &lef)) != 5) {
	    E_ERROR("Bad line: %s\n", line);
	    goto load_error;
	}

	w = dict_wordid (dict,wd);
	if (NOT_S3WID(w)) {
	    E_ERROR("Unknown word: %s\n", line);
	    goto load_error;
	}
	
	if (seqid != i) {
	    E_ERROR("Seqno error: %s\n", line);
	    goto load_error;
	}
	
	d = (dagnode_t *) listelem_alloc (sizeof(dagnode_t));
	darray[i] = d;
	
	d->wid = w;
	d->seqid = seqid;
	d->sf = sf;
	d->fef = fef;
	d->lef = lef;
	d->reachable = 0;
	d->succlist = NULL;
	d->predlist = NULL;
	d->alloc_next = NULL;
	
	if (! dag.list)
	    dag.list = d;
	else
	    tail->alloc_next = d;
	tail = d;
    }

    /* Read initial node ID */
    k = dag_param_read (fp, "Initial", &lineno);
    if ((k < 0) || (k >= nnode)) {
	E_ERROR("Initial node parameter missing or invalid\n");
	goto load_error;
    }
    dag.entry.node = darray[k];
    dag.entry.ascr = 0;
    dag.entry.next = NULL;
    dag.entry.pscr_valid = 0;
    
    /* Read final node ID */
    k = dag_param_read (fp, "Final", &lineno);
    if ((k < 0) || (k >= nnode)) {
	E_ERROR("Final node parameter missing or invalid\n");
	goto load_error;
    }
    dag.exit.node = darray[k];
    dag.exit.ascr = 0;
    dag.exit.next = NULL;
    dag.exit.pscr_valid = 0;
    dag.exit.bypass = NULL;