model.h

General Hidden Markov Model Library 一个通用的隐马尔科夫模型的C代码库

/*******************************************************************************
*
*       This file is part of the General Hidden Markov Model Library,
*       GHMM version 0.8_beta1, see http://ghmm.org
*
*       Filename: ghmm/ghmm/model.h
*       Authors:  Benhard Knab, Bernd Wichern, Benjamin Georgi,
*                 Alexander Schliep, Janne Grunau
*
*       Copyright (C) 1998-2004 Alexander Schliep 
*       Copyright (C) 1998-2001 ZAIK/ZPR, Universitaet zu Koeln
*	Copyright (C) 2002-2004 Max-Planck-Institut fuer Molekulare Genetik, 
*                               Berlin
*                                   
*       Contact: [e-mail]             
*
*       This library is free software; you can redistribute it and/or
*       modify it under the terms of the GNU Library General Public
*       License as published by the Free Software Foundation; either
*       version 2 of the License, or (at your option) any later version.
*
*       This library is distributed in the hope that it will be useful,
*       but WITHOUT ANY WARRANTY; without even the implied warranty of
*       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
*       Library General Public License for more details.
*
*       You should have received a copy of the GNU Library General Public
*       License along with this library; if not, write to the Free
*       Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*
*       This file is version $Revision: 1790 $ 
*                       from $Date: 2006-11-15 11:43:16 +0100 (Wed, 15 Nov 2006) $
*             last change by $Author: grunau $.
*
*******************************************************************************/
#ifndef GHMM_MODEL_H
#define GHMM_MODEL_H

#include "ghmm.h"

#ifdef __cplusplus
extern "C" {
#endif

/**@name HMM-Modell */
/*@{ (Doc++-Group: model) */

/** @name ghmm_dstate
    The basic structure, keeps all parameters that belong to a state. 
*/
typedef struct {
  /** Initial probability */
  double pi;
  /** Output probability */
  double *b;

  /** IDs of the following states */
  int *out_id;
  /** IDs of the previous states */
  int *in_id;

  /** transition probabilities to successor states. */
  double *out_a;
  /** transition probabilities from predecessor states. */
  double *in_a;

  /** Number of successor states */
  int out_states;
  /** Number of precursor states */
  int in_states;
  /** if fix == 1 --> b stays fix during the training */
  int fix;
  /** contains a description of the state (null terminated utf-8)*/
  unsigned char * desc;
  /** x coordinate position for graph representation plotting **/
  int xPosition;
  /** y coordinate position for graph representation plotting **/
  int yPosition;
} ghmm_dstate;



/** @name ghmm_dmodel
    The complete HMM. Contains all parameters, that define a HMM.
*/
typedef struct {
  /** Number of states */
  int N;
  /** Number of outputs */
  int M;
  /** Vector of the states */
  ghmm_dstate *s;
  /** The a priori probability for the model.
      A value of -1 indicates that no prior is defined. 
      Note: this is not to be confused with priors on emission
      distributions*/
  double prior;

  /* contains a arbitrary name for the model (null terminated utf-8) */
  unsigned char * name;

  /** Contains bit flags for varios model extensions such as
      kSilentStates, kTiedEmissions (see ghmm.h for a complete list)
  */
  int model_type;

  /** Flag variables for each state indicating whether it is emitting
      or not. 
      Note: silent != NULL iff (model_type & kSilentStates) == 1  */
  int *silent;
  /*AS*/
  /** Int variable for the maximum level of higher order emissions */
  int maxorder;
  /** saves the history of emissions as int, 
      the nth-last emission is (emission_history * |alphabet|^n+1) % |alphabet|
      see ...*/
  int emission_history;
  
  /** Flag variables for each state indicating whether the states emissions
      are tied to another state. Groups of tied states are represented
      by their tie group leader (the lowest numbered member of the group).
      
      tied_to[s] == kUntied  : s is not a tied state
      
      tied_to[s] == s        : s is a tie group leader
      
      tied_to[t] == s        : t is tied to state s (t>s)
      
      Note: tied_to != NULL iff (model_type & kTiedEmissions) != 0  */
  int *tied_to;

  /** Note: State store order information of the emissions.
      Classic HMMS have emission order 0, that is the emission probability
      is conditioned only on the state emitting the symbol.

      For higher order emissions, the emission are conditioned on the state s
      as well as the previous emission_order[s] observed symbols.

      The emissions are stored in the state's usual double* b. The order is
      set order.

      Note: order != NULL iff (model_type & kHigherOrderEmissions) != 0  */
  int * order;

  /** ghmm_dbackground is a pointer to a
      ghmm_dbackground structure, which holds (essentially) an
      array of background distributions (which are just vectors of floating
      point numbers like state.b).
      
      For each state the array background_id indicates which of the background
      distributions to use in parameter estimation. A value of kNoBackgroundDistribution
      indicates that none should be used.
      
      
      Note: background_id != NULL iff (model_type & kHasBackgroundDistributions) != 0  */
  int *background_id;
  ghmm_dbackground* bp;

  /** (WR) added these variables for topological ordering of silent states 
      Condition: topo_order != NULL iff (model_type & kSilentStates) != 0  */
  int *topo_order;
  int topo_order_length;
  
  /** pow_lookup is a array of precomputed powers
      It contains in the i-th entry M (alphabet size) to the power of i
      The last entry is maxorder+1 */
  int *pow_lookup;

  /** Store for each state a class label. Limits the possibly state sequence

      Note: label != NULL iff (model_type & kLabeledStates) != 0  */
  int* label;
  ghmm_alphabet* label_alphabet;

  ghmm_alphabet* alphabet;
} ghmm_dmodel;

#ifdef __cplusplus
}
#endif
/*
  Important: The inclusion of sequence.h ist not done before this point in
  order to avoid error by compiling.
*/
#include "sequence.h"
#include "scanner.h"
#ifdef __cplusplus
extern "C" {
#endif

/*----------------------------------------------------------------------------*/
/** 
    binary algorithm to compute powers of integers efficiently
    see Knuth, TAOCP, Vol 2, 4.6.3 
    uses if appropiate lookup table from struct ghmm_dmodel */
   int ghmm_ipow(const ghmm_dmodel * mo, int x, unsigned int n);


/*----------------------------------------------------------------------------*/
/** Allocates a ghmm_dmodel with following parameters:
    @return pointer to a ghmm_dmodel or NULL on error
    @param M           number of emissions
    @param N           number of states
    @param modeltype   model_type of the model, used to allocate optional arrays
    @param inDegVec    vector of in degrees of the states
    @param outDegVec   vector of out degrees of the states */
  ghmm_dmodel * ghmm_dmodel_calloc(int M, int N, int modeltype, int * inDegVec,
				 int * outDegVec);

/*----------------------------------------------------------------------------*/
/** Frees the memory of a model.
    @return 0 for succes; -1 for error
    @param mo:  address of pointer to a ghmm_dmodel */
  int ghmm_dmodel_free (ghmm_dmodel ** mo);

/** 
    Produces simple left-right models given sequences. The sequences
    are not read in from file, but exists already as a structur.
    @return vector of models
    @param s:          scanner
    @param new_models: number of models to produce */
  ghmm_dmodel **ghmm_dmodel_from_sequence (ghmm_dseq * sq, long *mo_number);

/**
   Copies a given model. Allocates the necessary memory.
   @return copy of the model
   @param mo:  model to copy */
  ghmm_dmodel *ghmm_dmodel_copy (const ghmm_dmodel * mo);

/**
   Tests if all standardization requirements of model are fulfilled. 
   (That is, if the sum of the probabilities is 1).
   @return 0 for success; -1 for error
   @param mo:  ghmm_dmodel to test */
  int ghmm_dmodel_check (const ghmm_dmodel * mo);

/**
   Tests if number of states and number of outputs in the models match.
   @return 0 for succes; -1 for error
   @param mo:           vector of models
   @param model_number: numbr of models */
  int ghmm_dmodel_check_compatibility (ghmm_dmodel ** mo, int model_number);

/**
   Test if to models are compatible. That means their states and outputs match.
   @return 0 for succes; -1 for error
   @param mo:     first ghmm_dmodel
   @param m2:     second ghmm_dmodel */
int ghmm_dmodel_check_compatibel_models (const ghmm_dmodel * mo, const ghmm_dmodel * m2);

/**
   Produces a model, which generates the given sequence with probability 1.
   The model is a strict left-right model with one state for each element 
   in the sequence and the output in state i is the i-th value in the sequence 
   with probability 1. The model also has a final state, a state with no output.
   @return         pointer to the produced ghmm_dmodel 
   @param seq:      sequence
   @param seq_len:  length of the sequence
   @param anz_symb: number of symbols in the sequence
*/
  ghmm_dmodel *ghmm_dmodel_generate_from_sequence (const int *seq, int seq_len,
                                       int anz_symb);

/** 
    Produces sequences to a given model. All memory that is needed for the 
    sequences is allocated inside the function. It is possible to define
    the length of the sequences global (global_len > 0) or it can be set 
    inside the function, when a final state in the model is reach (a state
    with no output). If the model has no final state, the sequences will
    have length MAX_SEQ_LEN.
    @return             pointer to an array of sequences
    @param mo:          model
    @param seed:        initial parameter for the random value generator
                        (an integer). If seed == 0, then the random value
			generator is not initialized.
    @param global_len:  length of sequences (=0: automatically via final states)
    @param seq_number:  number of sequences
*/
  ghmm_dseq *ghmm_dmodel_generate_sequences (ghmm_dmodel * mo, int seed, int global_len,
                                        long seq_number, int Tmax);

/**
   Calculates the sum log( P( O | lambda ) ).
   Sequences, that can not be generated from the given ghmm_dmodel, are neglected.
   @return    log(P)
   @param mo model
   @param sq sequences       
*/
  double ghmm_dmodel_likelihood (ghmm_dmodel * mo, ghmm_dseq * sq);

/**
    Get transition probabality from state 'i' to state 'j' to value 'prob'.
    NOTE: No internal checks
    @return  transition probability from state i to state j
    @param mo model