00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */ 00002 /* ==================================================================== 00003 * Copyright (c) 1995-2004 Carnegie Mellon University. All rights 00004 * reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 00010 * 1. Redistributions of source code must retain the above copyright 00011 * notice, this list of conditions and the following disclaimer. 00012 * 00013 * 2. Redistributions in binary form must reproduce the above copyright 00014 * notice, this list of conditions and the following disclaimer in 00015 * the documentation and/or other materials provided with the 00016 * distribution. 00017 * 00018 * This work was supported in part by funding from the Defense Advanced 00019 * Research Projects Agency and the National Science Foundation of the 00020 * United States of America, and the CMU Sphinx Speech Consortium. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 00023 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 00024 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 00025 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY 00026 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00027 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00028 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00029 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00030 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00032 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00033 * 00034 * ==================================================================== 00035 * 00036 */ 00037 /* 00038 * dag.h -- Library for DAG 00039 * 00040 * ********************************************** 00041 * CMU ARPA Speech Project 00042 * 00043 * Copyright (c) 1996 Carnegie Mellon University. 00044 * ALL RIGHTS RESERVED. 00045 * ********************************************** 00046 * 00047 * HISTORY 00048 * 00049 * $Log: dag.h,v $ 00050 * Revision 1.2 2006/02/23 05:22:32 arthchan2003 00051 * Merged from branch SPHINX3_5_2_RCI_IRII_BRANCH: 1, Fixed bugs from last check in, lw should be * instead of +, 2, Moved most of the functions from flat_fwd.c and s3_dag.c to here. Things that required specified will be prefixed. 00052 * 00053 * Revision 1.1.4.5 2005/11/17 06:25:04 arthchan2003 00054 * 1, Added structure to record node-based ascr and lscr. 2, Added a version of dag_link that copies the langauge model score as well. 00055 * 00056 * Revision 1.1.4.4 2005/09/25 19:20:43 arthchan2003 00057 * Added hooks in dag_node and dag_link. Probably need some time to use it various routines of ours. 00058 * 00059 * Revision 1.1.4.3 2005/09/11 23:07:28 arthchan2003 00060 * srch.c now support lattice rescoring by rereading the generated lattice in a file. When it is operated, silence cannot be unlinked from the dictionary. This is a hack and its reflected in the code of dag, kbcore and srch. code 00061 * 00062 * Revision 1.1.4.2 2005/09/11 02:56:47 arthchan2003 00063 * Log. Incorporated all dag related functions from s3_dag.c and 00064 * flat_fwd.c. dag_search, dag_add_fudge, dag_remove_filler is now 00065 * shared by dag and decode_anytopo. (Hurray!). s3_astar.c still has 00066 * special functions and it probably unavoidable. 00067 * 00068 * Revision 1.1.4.1 2005/07/17 05:44:31 arthchan2003 00069 * Added dag_write_header so that DAG header writer could be shared between 3.x and 3.0. However, because the backtrack pointer structure is different in 3.x and 3.0. The DAG writer still can't be shared yet. 00070 * 00071 * Revision 1.1 2005/06/21 22:37:47 arthchan2003 00072 * Build a stand-alone wrapper for direct acyclic graph, it is now shared across dag/astar and decode_anytopo. This eliminate about 500 lines of code in decode_anytopo/dag and astar. However, its existence still can't exterminate code duplication between dag/decode_anytopo. That effectively means we have many refactoring to do. Things that are still pretty difficult to merge include dag_search(decode_anytopo/dag) and dag_read (dag/astar). 00073 * 00074 * Revision 1.2 2005/06/03 06:45:28 archan 00075 * 1, Fixed compilation of dag_destroy, dag_dump and dag_build. 2, Changed RARG to REQARG. 00076 * 00077 * Revision 1.1 2005/06/03 05:46:19 archan 00078 * Refactoring across dag/astar/decode_anytopo. Code is not fully tested. 00079 * There are several changes I have done to refactor the code across 00080 * dag/astar/decode_anyptop. A new library called dag.c is now created 00081 * to include all routines that are shared by the three applications that 00082 * required graph operations. 00083 * 1, dag_link is now shared between dag and decode_anytopo. Unfortunately, astar was using a slightly different version of dag_link. At this point, I could only rename astar'dag_link to be astar_dag_link. 00084 * 2, dag_update_link is shared by both dag and decode_anytopo. 00085 * 3, hyp_free is now shared by misc.c, dag and decode_anytopo 00086 * 4, filler_word will not exist anymore, dict_filler_word was used instead. 00087 * 5, dag_param_read were shared by both dag and astar. 00088 * 6, dag_destroy are now shared by dag/astar/decode_anytopo. Though for some reasons, even the function was not called properly, it is still compiled in linux. There must be something wrong at this point. 00089 * 7, dag_bestpath and dag_backtrack are now shared by dag and decode_anytopo. One important thing to notice here is that decode_anytopo's version of the two functions actually multiply the LM score or filler penalty by the language weight. At this point, s3_dag is always using lwf=1. 00090 * 8, dag_chk_linkscr is shared by dag and decode_anytopo. 00091 * 9, decode_anytopo nows supports another three options -maxedge, -maxlmop and -maxlpf. Their usage is similar to what one could find dag. 00092 * 00093 * Notice that the code of the best path search in dag and that of 2-nd 00094 * stage of decode_anytopo could still have some differences. It could 00095 * be the subtle difference of handling of the option -fudge. I am yet 00096 * to know what the true cause is. 00097 * 00098 * Some other small changes include 00099 * -removal of startwid and finishwid asstatic variables in s3_dag.c. dict.c now hide these two variables. 00100 * 00101 * There are functions I want to merge but I couldn't and it will be 00102 * important to say the reasons. 00103 * i, dag_remove_filler_nodes. The version in dag and decode_anytopo 00104 * work slightly differently. The decode_anytopo's one attached a dummy 00105 * predecessor after removal of the filler nodes. 00106 * ii, dag_search.(s3dag_dag_search and s3flat_fwd_dag_search) The handling of fudge is differetn. Also, decode_anytopo's one now depend on variable lattice. 00107 * iii, dag_load, (s3dag_dag_load and s3astar_dag_load) astar and dag seems to work in a slightly different, one required removal of arcs, one required bypass the arcs. Don't understand them yet. 00108 * iv, dag_dump, it depends on the variable lattice. 00109 * 00110 */ 00111 00112 #ifndef _LIBFBS_DAG_H_ 00113 #define _LIBFBS_DAG_H_ 00114 00115 #include <stdio.h> 00116 00117 #include <listelem_alloc.h> 00118 #include <s3types.h> 00119 #include <cmd_ln.h> 00120 #include <logmath.h> 00121 00122 #include "search.h" 00123 #include "dict.h" 00124 #include "lm.h" 00125 #include "fillpen.h" 00126 00127 00128 #ifdef __cplusplus 00129 extern "C" { 00130 #endif 00131 #if 0 00132 /* Fool Emacs. */ 00133 } 00134 #endif 00135 00136 #define SPHINX_LATTICE_FORMAT 0 00137 #define IBM_LATTICE_FORMAT 1 00138 00139 00148 typedef struct dagnode_s { 00149 s3wid_t wid; 00150 int32 seqid; 00151 s3frmid_t sf; 00152 s3frmid_t fef, lef; 00153 struct dagnode_s *alloc_next; 00154 struct daglink_s *succlist; 00155 struct daglink_s *predlist; 00156 int32 node_ascr; 00157 int32 node_lscr; 00158 void *hook; 00159 uint8 reachable; 00163 } dagnode_t; 00164 00170 typedef struct daglink_s { 00171 dagnode_t *node; 00173 dagnode_t *src; 00174 struct daglink_s *next; 00175 struct daglink_s *history; 00176 struct daglink_s *bypass; 00180 int32 ascr; 00183 int32 lscr; 00184 int32 pscr; 00185 int32 hscr; 00187 s3frmid_t ef; 00190 int16 pscr_valid; 00192 void *hook; 00194 } daglink_t; 00195 00204 typedef struct { 00205 dagnode_t *list; 00206 dagnode_t *root; 00207 dagnode_t *end; 00209 daglink_t entry; 00210 daglink_t final; 00212 s3wid_t orig_exitwid; 00214 int32 nfrm; 00215 int32 nlink; 00216 int32 nnode; 00217 int32 nbypass; 00219 int32 maxedge; 00223 int32 lmop; 00224 int32 maxlmop; 00227 int32 filler_removed; 00228 int32 fudged; 00230 void *hook; 00232 cmd_ln_t *config; 00233 listelem_alloc_t *node_alloc; 00234 listelem_alloc_t *link_alloc; 00235 logmath_t *logmath; 00236 } dag_t; 00237 00238 00240 S3DECODER_EXPORT 00241 void hyp_free (srch_hyp_t *list); 00242 00244 void dag_init(dag_t* dagp, cmd_ln_t *config, logmath_t *logmath); 00245 00246 00250 S3DECODER_EXPORT 00251 int32 dag_link (dag_t * dagp, 00252 dagnode_t *pd, 00253 dagnode_t *d, 00254 int32 ascr, 00255 int32 lscr, 00256 int32 ef, 00257 daglink_t *byp 00258 ); 00259 00260 00261 daglink_t *find_succlink (dagnode_t *src, 00262 dagnode_t *dst, 00263 int32 bypass 00264 ); 00265 00266 daglink_t *find_predlink (dagnode_t *src, 00267 dagnode_t *dst, 00268 int32 bypass 00269 ); 00270 00271 int32 dag_update_link (dag_t* dagp, 00272 dagnode_t *pd, 00273 dagnode_t *d, 00274 int32 ascr, 00275 int32 ef, 00276 daglink_t *byp 00277 ); 00278 00282 int32 dag_param_read (FILE *fp, 00283 char *param, 00284 int32 *lineno 00285 ); 00286 00287 00292 int32 dag_bestpath ( 00293 dag_t* dagp, 00294 daglink_t *l, 00295 dagnode_t *src, 00296 float64 lwf, 00297 dict_t *dict, 00298 lm_t *lm, 00299 s3lmwid32_t *dict2lmwid 00300 ); 00301 00302 00306 int32 dag_chk_linkscr ( 00307 dag_t *dagp 00308 ); 00309 00312 S3DECODER_EXPORT 00313 int32 dag_destroy ( 00314 dag_t *dagp 00315 ); 00316 00322 S3DECODER_EXPORT 00323 void dag_compute_hscr(dag_t *dag, dict_t *dict, lm_t *lm, float64 lwf); 00324 00329 S3DECODER_EXPORT 00330 srch_hyp_t *dag_backtrace (srch_hyp_t **hyp, 00331 daglink_t *l, 00332 float64 lwf, 00333 dict_t* dict, 00334 fillpen_t* fpen 00335 ); 00336 00340 S3DECODER_EXPORT 00341 void dag_write_header(FILE *fp, cmd_ln_t *config); 00342 00346 S3DECODER_EXPORT 00347 int32 dag_write(dag_t * dag, 00348 const char *filename, 00349 lm_t * lm, 00350 dict_t * dict); 00351 00355 S3DECODER_EXPORT 00356 int32 dag_write_htk(dag_t *dag, 00357 const char *filename, 00358 const char *uttid, 00359 lm_t * lm, 00360 dict_t * dict); 00361 00362 00373 S3DECODER_EXPORT 00374 srch_hyp_t *dag_search (dag_t *dagp, 00375 char *utt, 00376 float64 lwf, 00377 dagnode_t *final, 00378 dict_t *dict, 00379 lm_t *lm, 00380 fillpen_t *fpen 00381 ); 00382 00387 void dag_add_fudge_edges (dag_t* dagp, 00388 int32 fudge, 00389 int32 min_ef_range, 00390 void *lathist, 00392 dict_t *dict 00393 ); 00394 00395 00403 S3DECODER_EXPORT 00404 int32 dag_bypass_filler_nodes (dag_t* dagp, 00405 float64 lwf, 00406 dict_t *dict, 00407 fillpen_t *fpen 00408 ); 00409 00413 S3DECODER_EXPORT 00414 void dag_remove_bypass_links(dag_t *dag); 00415 00419 S3DECODER_EXPORT 00420 void dag_remove_unreachable(dag_t *dag); 00421 00435 S3DECODER_EXPORT 00436 dag_t * dag_load(char *file, 00437 int32 maxedge, 00438 float32 logbase, 00439 int32 fudge, 00440 dict_t * dict, 00441 fillpen_t * fpen, 00442 cmd_ln_t *config, 00443 logmath_t *logmath 00444 ); 00445 00446 #ifdef __cplusplus 00447 } 00448 #endif 00449 00450 00451 #endif