dag.h File Reference

data structure for dag. Adapted from s3_dag.h in s3.5 More...

#include <stdio.h>
#include <listelem_alloc.h>
#include <s3types.h>
#include <cmd_ln.h>
#include <logmath.h>
#include "search.h"
#include "dict.h"
#include "lm.h"
#include "fillpen.h"

Go to the source code of this file.

Classes

struct  dagnode_s
struct  daglink_s
struct  dag_t

Defines

#define SPHINX_LATTICE_FORMAT   0
#define IBM_LATTICE_FORMAT   1

Typedefs

typedef struct dagnode_s dagnode_t
typedef struct daglink_s daglink_t

Functions

S3DECODER_EXPORT void hyp_free (srch_hyp_t *list)
void dag_init (dag_t *dagp, cmd_ln_t *config, logmath_t *logmath)
S3DECODER_EXPORT int32 dag_link (dag_t *dagp, dagnode_t *pd, dagnode_t *d, int32 ascr, int32 lscr, int32 ef, daglink_t *byp)
daglink_tfind_succlink (dagnode_t *src, dagnode_t *dst, int32 bypass)
daglink_tfind_predlink (dagnode_t *src, dagnode_t *dst, int32 bypass)
int32 dag_update_link (dag_t *dagp, dagnode_t *pd, dagnode_t *d, int32 ascr, int32 ef, daglink_t *byp)
int32 dag_param_read (FILE *fp, char *param, int32 *lineno)
int32 dag_bestpath (dag_t *dagp, daglink_t *l, dagnode_t *src, float64 lwf, dict_t *dict, lm_t *lm, s3lmwid32_t *dict2lmwid)
int32 dag_chk_linkscr (dag_t *dagp)
S3DECODER_EXPORT int32 dag_destroy (dag_t *dagp)
S3DECODER_EXPORT void dag_compute_hscr (dag_t *dag, dict_t *dict, lm_t *lm, float64 lwf)
S3DECODER_EXPORT srch_hyp_tdag_backtrace (srch_hyp_t **hyp, daglink_t *l, float64 lwf, dict_t *dict, fillpen_t *fpen)
S3DECODER_EXPORT void dag_write_header (FILE *fp, cmd_ln_t *config)
S3DECODER_EXPORT int32 dag_write (dag_t *dag, const char *filename, lm_t *lm, dict_t *dict)
S3DECODER_EXPORT int32 dag_write_htk (dag_t *dag, const char *filename, const char *uttid, lm_t *lm, dict_t *dict)
S3DECODER_EXPORT srch_hyp_tdag_search (dag_t *dagp, char *utt, float64 lwf, dagnode_t *final, dict_t *dict, lm_t *lm, fillpen_t *fpen)
void dag_add_fudge_edges (dag_t *dagp, int32 fudge, int32 min_ef_range, void *lathist, dict_t *dict)
S3DECODER_EXPORT int32 dag_bypass_filler_nodes (dag_t *dagp, float64 lwf, dict_t *dict, fillpen_t *fpen)
S3DECODER_EXPORT void dag_remove_bypass_links (dag_t *dag)
S3DECODER_EXPORT void dag_remove_unreachable (dag_t *dag)
S3DECODER_EXPORT dag_tdag_load (char *file, int32 maxedge, float32 logbase, int32 fudge, dict_t *dict, fillpen_t *fpen, cmd_ln_t *config, logmath_t *logmath)

Detailed Description

data structure for dag. Adapted from s3_dag.h in s3.5


Define Documentation

#define IBM_LATTICE_FORMAT   1
#define SPHINX_LATTICE_FORMAT   0

Typedef Documentation

typedef struct daglink_s daglink_t
typedef struct dagnode_s dagnode_t

DAG structure representation of word lattice. A unique <wordid,startframe> is a node. Edges are formed if permitted by time adjacency. (See comment before dag_build.)


Function Documentation

void dag_add_fudge_edges ( dag_t dagp,
int32  fudge,
int32  min_ef_range,
void *  lathist,
dict_t dict 
)

Add fudges into a DAG

Parameters:
fudge An initialized DAG Number of fudges
min_ef_range Minimum ending frame ranges
lathist lattice history, compilation problem cause me to cast it as void. It should be in latticehist_t
dict Dictionary
S3DECODER_EXPORT srch_hyp_t* dag_backtrace ( srch_hyp_t **  hyp,
daglink_t l,
float64  lwf,
dict_t dict,
fillpen_t fpen 
)

Recursive backtrace through DAG (from final node to root) using daglink_t.history. Restore bypassed links during backtrace.

Parameters:
hyp A pointer of a pointer to the hypothesis
l A pointer to the final link
lwf The language weight factor
dict The dictionary
fpen The filler penalty structure
int32 dag_bestpath ( dag_t dagp,
daglink_t l,
dagnode_t src,
float64  lwf,
dict_t dict,
lm_t lm,
s3lmwid32_t dict2lmwid 
)

Recursive step in dag_search: best backward path from src to root beginning with l.

Returns:
0 if successful, -1 otherwise.
Parameters:
dagp A pointer to a DAG
l Backward link!
src Source node for backward link l
lwf Language weight multiplication factor
dict The dictionary
lm The LM
dict2lmwid A map from dictionary id to lm id, should use wid2lm insteead
S3DECODER_EXPORT int32 dag_bypass_filler_nodes ( dag_t dagp,
float64  lwf,
dict_t dict,
fillpen_t fpen 
)

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.

Returns:
: 0 if successful; -1 if DAG maxedge limit exceeded.
Parameters:
dagp DAG
lwf language weight factor
dict Dictionary
fpen The filler penalty
int32 dag_chk_linkscr ( dag_t dagp  ) 

Check whether the link score is larger than zero

Returns:
0 if not, return -1 otherwise.
Parameters:
dagp A pointer to a DAG
S3DECODER_EXPORT void dag_compute_hscr ( dag_t dag,
dict_t dict,
lm_t lm,
float64  lwf 
)

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.

S3DECODER_EXPORT int32 dag_destroy ( dag_t dagp  ) 

destroy a dag

Parameters:
dagp A pointer to a DAG
void dag_init ( dag_t dagp,
cmd_ln_t *  config,
logmath_t *  logmath 
)

Initialize a dag_t

S3DECODER_EXPORT int32 dag_link ( dag_t dagp,
dagnode_t pd,
dagnode_t d,
int32  ascr,
int32  lscr,
int32  ef,
daglink_t byp 
)

Link two DAG nodes with the given arguments

Returns:
0 if successful, -1 if maxedge limit exceeded.
Parameters:
dagp A pointer to a DAG
ascr The acoustic score
lscr The language score (0 if none)
ef The ending frame

Referenced by flat_fwd_dag_add_fudge_edges().

S3DECODER_EXPORT dag_t* dag_load ( char *  file,
int32  maxedge,
float32  logbase,
int32  fudge,
dict_t dict,
fillpen_t fpen,
cmd_ln_t *  config,
logmath_t *  logmath 
)

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.

Returns:
: 0 if successful, -1 otherwise.
Parameters:
file Input: File to lod from
maxedge Maximum # of edges
logbase Logbase in float
fudge The number of fudges added
dict Dictionary
fpen Filler penalty structure
int32 dag_param_read ( FILE *  fp,
char *  param,
int32 *  lineno 
)

Routine to read the dag header

Parameters:
param file pointer
lineno The parameter name IN/Out The pointer of line no
S3DECODER_EXPORT void dag_remove_bypass_links ( dag_t dag  ) 

Remove links created by dag_bypass_filler_nodes().

S3DECODER_EXPORT void dag_remove_unreachable ( dag_t dag  ) 

Remove nodes from which the final exit node is not reachable.

S3DECODER_EXPORT srch_hyp_t* dag_search ( dag_t dagp,
char *  utt,
float64  lwf,
dagnode_t final,
dict_t dict,
lm_t lm,
fillpen_t fpen 
)

Search a dag given language model (lm) and filler penalty struct (fpen) Final global best path through DAG constructed from the word lattice. Assumes that the DAG has already been constructed and is consistent with the word lattice. The search uses a recursive algorithm to find the best (reverse) path from the final DAG node to the root: The best path from any node (beginning with a particular link L) depends on a similar best path for all links leaving the endpoint of L. (This is sufficient to handle trigram LMs.)

Parameters:
dagp The initalized directed acyclic graph to search
utt The utterance ID
lwf LM weight
final The final node, see source code in flat_fwd.c and dag.c
dict Dict
lm LM
fpen Fillpen
int32 dag_update_link ( dag_t dagp,
dagnode_t pd,
dagnode_t d,
int32  ascr,
int32  ef,
daglink_t byp 
)
Parameters:
dagp A pointer to a DAG
ascr The acoustic scores
ef The ending frame
byp A filler link being bypassed by this one
S3DECODER_EXPORT int32 dag_write ( dag_t dag,
const char *  filename,
lm_t lm,
dict_t dict 
)

Write a DAG (without segment scores) in Sphinx3 format

S3DECODER_EXPORT void dag_write_header ( FILE *  fp,
cmd_ln_t *  config 
)

writing the header of dag in Sphinx 3's format

S3DECODER_EXPORT int32 dag_write_htk ( dag_t dag,
const char *  filename,
const char *  uttid,
lm_t lm,
dict_t dict 
)

Write a DAG (without segment scores) in HTK format

daglink_t* find_predlink ( dagnode_t src,
dagnode_t dst,
int32  bypass 
)
Parameters:
bypass Find bypass links only?
daglink_t* find_succlink ( dagnode_t src,
dagnode_t dst,
int32  bypass 
)
Parameters:
bypass Find bypass links only?
S3DECODER_EXPORT void hyp_free ( srch_hyp_t list  ) 

Clean up the hypothesis list


Generated on 7 Mar 2010 by  doxygen 1.6.1