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_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) |
data structure for dag. Adapted from s3_dag.h in s3.5
#define IBM_LATTICE_FORMAT 1 |
#define SPHINX_LATTICE_FORMAT 0 |
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.)
void dag_add_fudge_edges | ( | dag_t * | dagp, | |
int32 | fudge, | |||
int32 | min_ef_range, | |||
void * | lathist, | |||
dict_t * | dict | |||
) |
Add fudges into a DAG
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.
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.
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.
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
dagp | A pointer to a DAG |
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
dagp | A pointer to a DAG |
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
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.
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
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.)
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 | |||
) |
dagp | A pointer to a DAG | |
ascr | The acoustic scores | |
ef | The ending frame | |
byp | A filler link being bypassed by this one |
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
bypass | Find bypass links only? |
bypass | Find bypass links only? |
S3DECODER_EXPORT void hyp_free | ( | srch_hyp_t * | list | ) |
Clean up the hypothesis list