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 dagnode_s	dagnode_t
typedef 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_t *	find_succlink (dagnode_t *src, dagnode_t *dst, int32 bypass)
daglink_t *	find_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_t *	dag_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_t *	dag_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_t *	dag_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

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

---