dag.h

Go to the documentation of this file.
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

Generated on 7 Mar 2010 by  doxygen 1.6.1