src/libpocketsphinx/lextree.h

Go to the documentation of this file.

/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
 * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * This work was supported in part by funding from the Defense Advanced 
 * Research Projects Agency and the National Science Foundation of the 
 * United States of America, and the CMU Sphinx Speech Consortium.
 *
 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * ====================================================================
 *
 */
/*
 * lextree.h -- 
 * 
 * **********************************************
 * CMU ARPA Speech Project
 *
 * Copyright (c) 1999 Carnegie Mellon University.
 * ALL RIGHTS RESERVED.
 * **********************************************
 * 
 * HISTORY
 * $Log$
 * Revision 1.1  2006/04/05  20:27:30  dhdfu
 * A Great Reorganzation of header files and executables
 * 
 * Revision 1.11  2006/02/23 15:08:24  arthchan2003
 * Merged from the branch SPHINX3_5_2_RCI_IRII_BRANCH:
 *
 * 1, Fixed memory leaks.
 * 2, Add logic for full triphone expansion.  At this point, the
 * propagation of scores in word end is still incorrect. So composite
 * triphone should still be used by default.
 * 3, Removed lextree_copies_hmm_propagate.
 *
 * Revision 1.10.4.6  2005/11/17 06:28:50  arthchan2003
 * Changed the code to used compressed triphones. Not yet correct at this point
 *
 * Revision 1.10.4.5  2005/10/17 04:53:44  arthchan2003
 * Shrub the trees so that the run-time memory could be controlled.
 *
 * Revision 1.10.4.4  2005/10/07 19:34:31  arthchan2003
 * In full cross-word triphones expansion, the previous implementation has several flaws, e.g, 1, it didn't consider the phone beam on cross word triphones. 2, Also, when the cross word triphone phone is used, children of the last phones will be regarded as cross word triphone. So, the last phone should not be evaluated at all.  Last implementation has not safe-guaded that. 3, The rescoring for language model is not done correctly.  What we still need to do: a, test the algorithm in more databases. b,  implement some speed up schemes.
 *
 * Revision 1.10.4.2  2005/09/25 19:23:55  arthchan2003
 * 1, Added arguments for turning on/off LTS rules. 2, Added arguments for turning on/off composite triphones. 3, Moved dict2pid deallocation back to dict2pid. 4, Tidying up the clean up code.
 *
 * Revision 1.10.4.1  2005/06/27 05:37:05  arthchan2003
 * Incorporated several fixes to the search. 1, If a tree is empty, it will be removed and put back to the pool of tree, so number of trees will not be always increasing.  2, In the previous search, the answer is always "STOP P I T G S B U R G H </s>"and filler words never occurred in the search.  The reason is very simple, fillers was not properly propagated in the search at all <**exculamation**>  This version fixed this problem.  The current search will give <sil> P I T T S B U R G H </sil> </s> to me.  This I think it looks much better now.
 *
 * Revision 1.10  2005/06/21 23:32:58  arthchan2003
 * Log. Introduced lextree_init and filler_init to wrap up lextree_build
 * process. Split the hmm propagation to propagation for leaves and
 * non-leaves node.  This allows an easier time for turning off the
 * rescoring stage. However, the implementation is not clever enough. One
 * should split the array to leave array and non-leave array.
 *
 * Revision 1.7  2005/06/16 04:59:10  archan
 * Sphinx3 to s3.generic, a gentle-refactored version of Dave's change in senone scale.
 *
 * Revision 1.6  2005/06/13 04:02:59  archan
 * Fixed most doxygen-style documentation under libs3decoder.
 *
 * Revision 1.5  2005/04/25 23:53:35  archan
 * 1, Some minor modification of vithist_t, vithist_rescore can now support optional LM rescoring, vithist also has its own reporting routine. A new argument -lmrescore is also added in decode and livepretend.  This can switch on and off the rescoring procedure. 2, I am reaching the final difficulty of mode 5 implementation.  That is, to implement an algorithm which dynamically decide which tree copies should be entered.  However, stuffs like score propagation in the leave nodes and non-leaves nodes are already done. 3, As briefly mentioned in 2, implementation of rescoring , which used to happened at leave nodes are now separated. The current implementation is not the most clever one. Wish I have time to change it before check-in to the canonical.
 *
 * Revision 1.4  2005/04/25 19:22:47  archan
 * Refactor out the code of rescoring from lexical tree. Potentially we want to turn off the rescoring if we need.
 *
 * Revision 1.3  2005/03/30 01:22:47  archan
 * Fixed mistakes in last updates. Add
 *
 * 
 * 29-Feb-2000  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
 *              Modified some functions to be able to deal with HMMs with any number
 *              of states.
 * 
 * 07-Jul-1999  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
 *              Added lextree_node_t.ci and lextree_ci_active().
 * 
 * 30-Apr-1999  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
 *              Started.
 */


#ifndef _S3_LEXTREE_H_
#define _S3_LEXTREE_H_

#include <stdio.h>

#include <bitvec.h>
#include <ngram_model.h>
#include <glist.h>

#include "s3types.h"
#include "hmm.h"
#include "tmat.h"
#include "vithist.h"
#include "s3dict.h"
#include "bin_mdef.h"
#include "fillpen.h"

#ifdef __cplusplus
extern "C" {
#endif
#if 0
} /* Fool Emacs into not indenting things. */
#endif

#define LEXTREE_OPERATION_SUCCESS 1
#define LEXTREE_OPERATION_FAILURE 0

#define LEXTREE_TYPE_FILLER -1
#define LEXTREE_TYPE_UNIGRAM 0
#define LEXTREE_TYPE_BIGRAM 1
#define LEXTREE_TYPE_TRIGRAM 2

#if 0 /*Number reserved but not used */
#define LEXTREE_TYPE_QUADGRAM 3
#define LEXTREE_TYPE_QUINGRAM 4
#endif


/*
 * \struct lextree_node_t
 * One node in a lextree.
 */
typedef struct {
    hmm_t hmm;          
    glist_t children;   
    int32 wid;          
    int32 prob;         
    int32 ssid;         
    s3cipid_t rc;        
    s3cipid_t ci;       
    int8 composite;     
} lextree_node_t;

/* Access macros; not meant for arbitrary use */
#define lextree_node_wid(n)             ((n)->wid)
#define lextree_node_prob(n)            ((n)->prob)
#define lextree_node_ssid(n)            ((n)->ssid)
#define lextree_node_rc(n)              ((n)->rc)
#define lextree_node_composite(n)       ((n)->composite)
#define lextree_node_frame(n)           ((n)->frame)


/*
 * \struct lextree_lcroot_t
 * Root nodes of the lextree valid for a given left context CIphone.
 */
typedef struct {
    s3cipid_t lc;       /* Left context CIphone */
    glist_t root;       /* Its data.ptr are the root nodes (lextree_node_t *) of interest; subset
                           of the entire lextree roots */
} lextree_lcroot_t;

/*
 * \struct lextree_t 
 * Entire lextree.
 */
typedef struct {
    int32 type;         
    glist_t root;       
    lextree_lcroot_t *lcroot;   
    int32 n_lc;         
    int32 n_node;       
    int32 n_alloc_node;   
    int32 n_alloc_blk_sz;   
    bin_mdef_t *mdef;     
    s3dict_t *dict;     
    dict2pid_t *dict2pid;     
    fillpen_t *fp;      
    ngram_model_t *lm;  
    tmat_t *tmat;       
    hmm_context_t *ctx;     
    hmm_context_t *comctx; 
    lextree_node_t **active;            
    lextree_node_t **next_active;       
    int32 n_active;             
    int32 n_next_active;        
    int32 best;         
    int32 wbest;        
    char prev_word[100];      
} lextree_t;

/* Access macros; not meant for arbitrary usage */
#define lextree_type(l)                 ((l)->type)
#define lextree_root(l)                 ((l)->root)
#define lextree_lcroot(l)               ((l)->lcroot)
#define lextree_n_lc(l)                 ((l)->n_lc)
#define lextree_n_node(l)               ((l)->n_node)
#define lextree_n_alloc_node(l)         ((l)->n_alloc_node)
#define lextree_active(l)               ((l)->active)
#define lextree_next_active(l)          ((l)->next_active)
#define lextree_n_active(l)             ((l)->n_active)
#define lextree_n_next_active(l)        ((l)->n_next_active)


lextree_t* lextree_init(
    bin_mdef_t *mdef,
    tmat_t *tmat,
    s3dict_t *dict,
    dict2pid_t *dict2pid,
    fillpen_t *fp,
    ngram_model_t* lm,
    const char *lmname,     
    int32 istreeUgProb, 
    int32 bReport,     
    int32 type        
    );

lextree_t* fillertree_init(bin_mdef_t *mdef, tmat_t *tmat, s3dict_t *dict,
                           dict2pid_t *dict2pid, fillpen_t *fillpen);


void lextree_report(
    lextree_t *ltree 
    );

typedef struct {
    s3wid_t wid;        
    int32 prob;         
} wordprob_t;

/* Free a lextree that was created by lextree_init */
void lextree_free (lextree_t *lextree);

void lextree_utt_end (lextree_t *l);


void lextree_enter (lextree_t *lextree, 
                    s3cipid_t lc,       
                    int32 frame,        
                    int32 inscore,      
                    int32 inhist,       
                    int32 thresh        
    );

void lextree_active_swap (lextree_t *lextree 
    );


void lextree_ssid_active (lextree_t *lextree,   
                          bitvec_t *ssid,       
                          bitvec_t *comssid     
    );

void lextree_ci_active (lextree_t *lextree,     
                        bitvec_t *ci_active     
    );

int32 lextree_hmm_eval (lextree_t *lextree,     
                        int16 *senscr,  
                        int16 *comsen,  
                        int32 f,        
                        FILE *fp        
    );

/*
 * ARCHAN: Starting from Sphinx 3.6, lextree_hmm_propagate is separated to 
 * lextree_hmm_propagate_non_leaves and lextree_hmm_propagate_leaves.  This allows 
 * the rescoring routine to be more easily switched off
 */

int32 lextree_hmm_propagate_non_leaves (lextree_t *lextree,     
                                        int32 cf,               
                                        int32 th,               
                                        int32 pth,              
                                        int32 wth               
    ); 


int32 lextree_hmm_propagate_leaves (lextree_t *lextree, 
                                    vithist_t *vh,      
                                    int32 cf,            
                                    int32 wth           
    ); 


void lextree_hmm_histbin (lextree_t *lextree,   
                          int32 bestscr,        
                          int32 *bin,           
                          int32 nbin,           
                          int32 bw              
    );

void lextree_dump (lextree_t *lextree,  
                   FILE *fp,           
                   int32 fmt           
    );

int32 num_lextree_links(lextree_t *ltree 
    );
#if 0
{ /* Stop indent from complaining */
#endif
#ifdef __cplusplus
}
#endif

#endif

---