Classes | Macros | Typedefs | Functions
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

Macros

#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

Macro Definition 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
fudgeAn initialized DAG Number of fudges
min_ef_rangeMinimum ending frame ranges
lathistlattice history, compilation problem cause me to cast it as void. It should be in latticehist_t
dictDictionary
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
hypA pointer of a pointer to the hypothesis
lA pointer to the final link
lwfThe language weight factor
dictThe dictionary
fpenThe 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
dagpA pointer to a DAG
lBackward link!
srcSource node for backward link l
lwfLanguage weight multiplication factor
dictThe dictionary
lmThe LM
dict2lmwidA 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
dagpDAG
lwflanguage weight factor
dictDictionary
fpenThe 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
dagpA 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
dagpA 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
dagpA pointer to a DAG
ascrThe acoustic score
lscrThe language score (0 if none)
efThe 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
fileInput: File to lod from
maxedgeMaximum # of edges
logbaseLogbase in float
fudgeThe number of fudges added
dictDictionary
fpenFiller penalty structure
int32 dag_param_read ( FILE *  fp,
char *  param,
int32 *  lineno 
)

Routine to read the dag header

Parameters
paramfile pointer
linenoThe 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
dagpThe initalized directed acyclic graph to search
uttThe utterance ID
lwfLM weight
finalThe final node, see source code in flat_fwd.c and dag.c
dictDict
lmLM
fpenFillpen
int32 dag_update_link ( dag_t dagp,
dagnode_t pd,
dagnode_t d,
int32  ascr,
int32  ef,
daglink_t byp 
)
Parameters
dagpA pointer to a DAG
ascrThe acoustic scores
efThe ending frame
bypA 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
bypassFind bypass links only?
daglink_t* find_succlink ( dagnode_t src,
dagnode_t dst,
int32  bypass 
)
Parameters
bypassFind bypass links only?
S3DECODER_EXPORT void hyp_free ( srch_hyp_t list)

Clean up the hypothesis list