语音识别HTK代码学习手册.doc

HMM的理论基础
一、 HMM定义
1.       N：模型中状态的数目，记t时刻Markov链所处的状态为
2.       M：每个状态对应的可能的观察数目，记t时刻观察到的观察值为
3.       ：初始状态概率矢量，，，
4.       A：状态转移概率矩阵，，，
5.       B：观察值概率矩阵（适用于离散HMM），，，；对于连续分布的HMM，记t时刻的观察值概率为
一个离散型的HMM模型可以简约的记为。
二、关于语音识别的HMM的三个基本问题
1. 已知观察序列和模型参数，如何有效的计算。
a. 直接计算

            2-1
当N=5，T=100时大概需进行次乘法!
b. 前向算法
定义t时刻的前向变量（forward variable），可以通过迭代的方法来计算各个时刻的前向变量：
1） 初始化（Initialization）
当t=1时
     2-2
2） 递归（Induction）
当时

即：                2-3
3） 终结（Termination）
                     2-4
乘法次数大约为：N2T
c. 后向算法
定义t时刻的后向变量（backward variable），可以通过迭代的方法来计算各个时刻的后向变量：
1）    初始化（Initialization）
当t=T时
，                       2-5
2）    递归（Induction）
当时

即：，           2-6
3）    终结（Termination）
                   2-7
              乘法计算次数约为：N2T
2. 已知观察序列和模型参数，在最佳意义上确定一个状态序列。
定义一个后验概率变量（posteriori probability variable）
           2-7
       则最优序列可以通过，           2-7
求得。不过，这样求得的最优序列有些问题。如果，那么这个最优序列本身就不存在。这里讨论的最佳意义上的最优序列，是使最大化时的确定的状态序列。即，使最大化时确定的状态序列。
       定义为t时刻沿一条路径，且，输出观察序列的最大概率，即： 2-8
       下面介绍迭代计算的Viterbi算法：
1）    初始化（Initialization）
，
回溯变量：，
2）    递归（Induction）

即：                 2-8
                   2-9
3）    终结（Termination）
                   2-10
                    2-11
4）    回溯状态序列
，            2-12
3. 已知观察序列和模型参数，如何调整模型参数使最大。
定义3.1 给定训练序列和模型，时刻Markov链处在状态和时刻处在状态的概率定义如下
       3-1
定义3.2 给定训练序列和模型，时刻Markov链处在状态的概率定义如下
                3-2
定义3.3 给定训练序列和模型，从状态转移出去的概率为
定义3.4给定训练序列和模型，从状态转移到状态的概率为
利用Baum-Welch重估算法可以得到使局部最大时的参数更新公式。
1.  Baum-Welch重估公式的理论基础
引理3.1 设，，为正实数，，，为非负实数，那么，由对数函数的凹特性，有如下结论
         3-3
定义辅助函数如下
           3-4
其中，为更新前模型参数，为更新后模型参数，为训练序列，为可能的状态序列。
利用和引理3.1易得
             3-5
式3-5构成了重估公式得理论基础，对辅助函数，只要能够找到，使，从而，这样，更新后的模型在拟和训练序列方面就比更新前的模型要好，使最大而得到的的参数更新公式就称之为Baum-Welch重估公式。
引理3.2 ，，在的约束条件下，函数的唯一最大值点为 。
证明如下

求最大值
令    得：

，同理可证：
利用凹函数特性可知此最大值唯一。
2.        离散HMM模型的重估公式

HTK内存管理
一、     HTK内存管理概述
C语言编程中，遇到的关于内存分配和释放的问题主要有如下两个方面。
第一是指针维护问题。试想，你写的一个程序执行了一系列内存空间分配（通常是由malloc函数完成）操作，为了能够在以后适当的时候（通常是你不再需要那些内存时）可以将分配的内存空间释放（通常是由free函数完成），你必须小心谨慎的维护好这些指向分配的内存空间的指针。有经验的程序员大概都会有这样的感受，维护这些指针并非易事！特别是当程序比较复杂时，尤为如此。如果你一不小心（其实这很容易）丢掉了某些指针，那么操作系统将无法回收那些内存（这便是我们常说的内存泄漏问题），除非你的程序死了。
第二就是关于内存分配释放操作本身。如果你的程序会相当频繁的执行malloc和free函数，那么程序将会费去大量的CPU时间来执行它们。
为了解决以上两个问题，尽可能的提高内存利用率，HTK设计了一个内存管理子系统，利用自定义的堆结构（Heap）来进行内存分配和释放。HTK内存分配和释放的主要思想是一次向操作系统要大一些的内存块，然后在将它分成小块供上层程序使用，不需要时只需释放那个大内存块。
HTK把堆结构分为三大类：
1.       M-HEAPS：元素大小固定，new/free操作执行次序无限制，可全局重置(global reset)。
2.       M-STACK：元素大小可变，最后分配的空间必须先释放，可全局重置。
3.       C-HEAPS：元素大小可变，new/free操作执行次序无限制，全局重置无效（直接使用malloc和free函数）。
二、数据结构
1. 堆数据结构定义
typedef enum{MHEAP,MSTAK,CHEAP} HEAPTYPE; // 堆类型定义
typedef unsigned char* ByteP; // 无符号字符（8位）指针
typedef void* Ptr;
typedef struct _Block *BlockP;
/* MHEAP和MSTAK块数据结构定义 */
typedef struct _Block{  /* MHEAP                           ,MSTACK           */
       size_t numFree;  /* 空闲元素数目                      ,空闲字节数        */
       size_t firstFree;  /* 第一个空闲元素索引           ,栈顶索引                */
       size_t numElem; /* 块分配元素的个数             ,块分配的字节数          */
       ByteP used;       /* 指向元素分配表指针,1bit/元素       ,不使用              */
       Ptr data;       /* 指向数据区指针                    ,指向数据区指针     */
       BlockP next;            /* 指向下一个块指针                  ,指向下一个块指针        */
}Block;
/* 堆数据结构定义 */
       typedef struct{       /* MHEAP                     ,MSTACK           */
       char*    name;     /* 堆的名称                          ,堆的名称                  */
       HEAPTYPE type;    /* 堆的类型                          ,堆的类型                  */
       float    growf;       /* 增长因子                          ,增长因子                 证章 */
       size_t   elemSize;     /* 元素大小                          ,总是1             */
       size_t   minElem;   /**/
       size_t   maxElem;    /* 每个块最大允许分配的元素个数    ,每个块最大允许分配的字
节数 */
       size_t   curElem;      /* 当前块元素个数                    ,当前块字节个数     */
       size_t   totUsed;      /* 已使用的元素总个数               ,以使用的字节总个数 */
       size_t   totAlloc;      /* 分配的元素总数                    ,分配的字节总数     */
       BlockP   heap;             /* 指向当前块的指针                  ,指向当前块的指针   */
       Boolean  protectStk; /* 仅适用于MSTAK */
}MemHeap;
2. 堆数据结构框图

                    M-Heaps内存堆结构示意图
同一个M-Heaps内存堆中分配的元素大小都是一样的。堆结构中的块指针成员变量heap指向数据块链的头。
数据块链中的每个块分配的内存区大小由（字节）计算得到。
每个块中的BYTE型指针成员变量used指向记录元素使用状态的表数据结构，表中第i位记录数据区中第i个元素的使用状态：1表示使用中、0表示空闲。
每个块中的firstFree成员变量的值表示数据区中第一个空闲元素的标号。
每个块中的numFree成员变量的值记录所在块中空闲元素的个数。如果numFree为0表示块满，这时firstFree=numElem。

                      M-Stack内存堆结构示意图
三、算法
1.    接口描述
1.      定义：Export-->void InitMem(void)
说明：初始化全局MSTAK堆变量gstack和全局CHEAP堆变量gcheap。该函数必须在调用任何其它堆操作函数前调用。
参数：无
返回值：无
2.      定义：Export-->void CreateHeap(MemHeap *x , char *name , HeapType type , size_t elemSize , float growf , size_t numElem , size_t maxElem)
说明：创建一个名称为name、类型为type的内存堆，elemSize指定内存堆中元素的大小，numElem指定块中元素默认个数。如果，内存堆的类型是MSTAK或CHEAP，则elemSize必须为1。
参数：  x：               指向给定的内存堆                 [In,Out]
         name：         堆的名称                                 [In]
              type：          堆类型                                     [In]
              elemSize：   对于MHEAP表示堆的每个块中元素的大小，对于
MSTAK和CHEAP，elemSize必须设为1              [In]
             growf：       
             numElem：  堆的每个块默认分配的元素个数                            [In]
             maxElem：  堆的每个块最大允许分配的元素个数                    [In]
返回值：无
3.       定义：Export-->void ResetHeap(MemHeap *x)
说明：释放内存堆x中所有元素，对CHEAP内存堆无效。
参数：  x：               指向给定的内存堆                 [In,Out]
返回值：无
4.       定义：Export-->void DeleteHeap(MemHeap *x)
说明：释放内存堆x中所有元素，并删除内存堆x。
参数：  x：               指向给定的内存堆                 [In,Out]
返回值：无
5.       定义：Export-->Ptr New(MemHeap *x , size_t size)
说明：从内存堆x中分配一大小为size的新元素并返回其指针。如果x类型为MHEAP则忽略参数size。如果分配失败，程序将会异常退出，所以返回值永远不会为NULL。
参数：  x：               指向给定的内存堆                 [In,Out]
              size：           指定分配的元素大小             [In]
返回值：返回指向新分配的元素的指针
6.      定义：void BlockRecorder(BlockP *p , int n)
说明：对于MHEAP堆，从块p向后搜索有n个以上（包括n个）元素的块，并将其移至块链表头。对于MSTAK堆，从块p向后搜索有n个以上（包括n个）字节数的块，并将其移至块链表头。
参数：  p                   指向给定的块                         [In,Out]
              n                   对于MHEAP，表示元素个数；对于MSTAK，表示字节
数。                                         [In]
返回值：无
7.      定义：void* GetElem(BlockP p , size_t elemSize , HeapType type)
说明：如果type为MHEAP则从块p中返回一空闲元素指针，并将其在使用状态表中的对应项置1。如果type为MSTAK则从块p中返回一大小为elemSize字节数的区域指针，并对块p中firstFree和numFree变量进行相应的修改。
参数：  p：               指向给定的块                         [In]
              elemSize：   元素大小                                 [In]
              type：          所属堆的类型                         [In]
返回值：如果成功，则返回大小为elemSize字节数的数据区，否则返回
NULL。
8.      定义：BlockP AllocBlock(size_t size , size_t num , HeapType type)
说明：分配一个数据区大小为size*num字节数的块，在进行必要的初始化后，返回该块的指针。
参数：  size：           元素大小                                 [In]
              num：           元素个数                                 [In]
              type：          所属堆的类型                         [In]
返回值：如果分配成功，则返回块指针，否则程序异常退出。
9.       定义：size_t Mround(size_t size)
说明：返回大小>=size并且整除FWORD（8）的值。
参数：  size               输入大小                                 [In]
返回值：返回计算的大小
10.    定义：Export-->Ptr CNew(MemHeap *x , size_t size)
说明：从内存堆x中分配一大小为size的新元素清0后返回其指针。如果x类型为MHEAP则忽略参数size。如果分配失败，程序将会异常退出，所以返回值永远不会为NULL。
参数：  x：               指向给定的内存堆                 [In,Out]
              size：           指定分配的元素大小             [In]
返回值：     返回指向新分配的元素的指针
11.    定义：Export-->void Dispose(MemHeap* x , void *p)
说明：从内存堆x中释放元素p
参数：  x                   指向给定的内存堆                 [In,Out]
              p                   元素指针                                 [In]
返回值：     无
2.    接口实现
1. 内存堆创建算法CreateHeap
void CreateHeap(MemHeap *x, char *name, HeapType type, size_t elemSize,
                float growf, size_t numElem, size_t maxElem)
{
     // 一致性检查
     if (growf < 0.0) //growf必须大于等于0
          HError(5170, "CreateHeap: -ve grow factor in heap %s",name);
     if (numElem>maxElem) //默认的元素个数不能大于最大允许的元素个数
         HError(5170,"CreateHeap: init num elem > max elem in heap %s",name);
     if (elemSize <= 0) //元素大小必须大于0
         HError(5170,"CreateHeap: elem size = %u in heap %s",elemSize,name);
     if (type == MSTAK && elemSize !=1) //MSTAK的elemSize必须为1
         HError(5170,"CreateHeap: elem size = %u in MSTAK heap %s",elemSize,name);
     x->name = (char *)malloc(strlen(name)+1); //为内存堆名称分配内存
     strcpy(x->name, name);
     x->type               = type;
     x->growf              = growf;
     x->elemSize   = elemSize;
     x->maxElem = maxElem;
     x->curElem   = x->minElem = numElem;
     x->totUsed    = x->totAlloc = 0;
     x->heap         = NULL;
     x->protectStk        = (x==&gstack)? FALSE : protectStaks;
     RecordHeap(x); //记录内存堆x
     if (trace&T_TOP)
{
         switch (type)
{
                case MHEAP: c='M';    break;
                case MSTAK: c='S';    break;
                case CHEAP: c='C';     break;
         }
         printf("HMem: Create Heap %s[%c] %u %.1f %u %u\n", name, c,
             elemSize, growf, numElem, maxElem);
     }
}
1.      内存堆的Trace
为了跟踪内存堆的使用情况，HTK使用一个叫MemHeapRec的数据结构来记录创建的内存堆。MemHeapRec的数据结构如下所示：
typedef struct _MemHeapRec {
            MemHeap *heap;                      // 指向内存堆的指针
            struct _MemHeapRec *next;              // 指向下一个MemHeapRec
} MemHeapRec;
static MemHeapRec *heapList = NULL; //全局变量, MemHeapRec链表
       MemHeapRec主要通过RecordHeap和UnRecordHeap两个函数来完成内存堆的记录和擦除操作。算法描述如下：
static void RecordHeap(MemHeap *x) //将内存堆x加入到heapList链表中
{
            MemHeapRec *p;
         if (( p = (MemHeapRec *)malloc(sizeof(MemHeapRec))) == NULL)
          HError(5105,"RecordHeap: Cannot allocate memory for MemHeapRec");
        p->heap = x;
              //将p插入到heapList链表头前
        p->next = heapList;
        heapList = p;
}
static void UnRecordHeap(MemHeap *x) //从heapList中擦除内存堆x记录
{
            MemHeapRec *p, *q;
         p = heapList;
            q = NULL;
              // 从heapList链头向后寻找内存堆x
            while (p != NULL && p->heap != x)
            {
                q = p;
                p = p->next;
            }
if (p == NULL)
                HError(5171,"UnRecordHeap: heap %s not found",x->name); //没有找到
              //将p从heapList中摘除
            if (p == heapList)
                heapList = p->next;
            else
                q->next = p->next;
            free(p); //释放p
}
2. 内存堆重置算法ResetHeap

将p从heapList中摘除
void ResetHeap(MemHeap *x)
{
            BlockP cur,next;
switch(x->type)
            {
            case MHEAP:
if (trace&T_TOP)
                     printf("HMem: ResetHeap %s[M]\n", x->name);
cur = x->heap; //cur指向块链表头
                //删除所有的块
                while (cur != NULL)
                   {
                     next = cur->next;
                     free(cur->data); //释放cur块数据区内存
                           free(cur->used); //释放cur块元素使用状态表内存
                     free(cur); //释放cur块
                           cur = next; //cur指向下一个块
                }
                x->curElem = x->minElem;
                x->totAlloc = 0;
                   x->heap = NULL;
         break;
     case MSTAK:   
          if (trace&T_TOP)
              printf("HMem: ResetHeap %s[S]\n", x->name);
cur=x->heap; //cur指向块链表头
         if (cur != NULL)
            {
              // 删掉除第一个块以外的所有块
              while (cur->next != NULL)
                    {
                  next = cur->next;
                  x->totAlloc = x->totAlloc-cur->numElem;
                  free(cur->data);
                            free(cur);
                  cur = next;
              }
              x->heap = cur;
         }
         x->curElem = x->minElem;
         if (cur != NULL)
            {
              cur->numFree = cur->numElem;
              cur->firstFree = 0;
         }
      break;
     case CHEAP:
      HError(5172,"ResetHeap: cannot reset C heap");
     }
     x->totUsed = 0;
}
3. 内存堆删除算法DeleteHeap
void DeleteHeap(MemHeap *x) //删除指定的内存堆x
{
            if (x->type == CHEAP)
                HError(5172,"DeleteHeap: cant delete C Heap %s",x->name);
            ResetHeap(x); //释放所有的数据块
            if (x->heap != NULL)
            {
                free(x->heap->data);
                free(x->heap);
            }
            if (trace&T_TOP)
printf("HMem: DeleteHeap %s\n", x->name);
UnRecordHeap(x); //擦除内存堆x的Trace
            free(x->name); //释放分配的名称内存
}
4. 从内存堆分配空间的算法New、CNew
static BlockP AllocBlock(size_t size, size_t num, HeapType type) //分配块
{
            BlockP p;
            ByteP c;
            int i;
            if (trace&T_TOP)
printf("HMem: AllocBlock of %u bytes\n", num*size);
if ((p = (BlockP) malloc(sizeof(Block))) == NULL) //分配块空间
                HError(5105,"AllocBlock: Cannot allocate Block");
            if ((p->data = (void *)malloc(size*num)) == NULL) //分配块的数据区空间
                HError(5105,"AllocBlock: Cannot allocate block data of %u bytes",size*num);
            switch (type)
            {
            case MHEAP:
                if ((p->used = (ByteP)malloc((num+7)/8)) == NULL)//分配使用状态表空间
                     HError(5105, "AllocBlock: Cannot allocate block used array");
                     //使用状态表中所有项赋0
                for (i=0,c=p->used; i < (num+7)/8; i++,c++)
                          *c = 0;
                break;
            case MSTAK:
                p->used = NULL;
                break;
            default:
                HError(5190,"AllocBlock: bad type %d",type);
            }
            p->numElem = p->numFree = num;
            p->firstFree = 0;
            p->next = NULL;
            return p;
}

AllocBlock分配的MHEAP块示意图
       //BlockReorder: 从块p向后寻找>=n个空闲元素的块，并将其移至块链表头
static void BlockReorder(BlockP *p, int n)
{
            BlockP head, cur, prev;
         if (p == NULL)
                   return;
            head = cur = *p;
            prev = NULL;
            while (cur != NULL)
            {
                if (cur->numFree >= n)
                   {
//找到，那么就将其移至块链表头
                     if (prev != NULL)
                           {
                         prev->next = cur->next;
                         cur->next = head;
                     }
                     *p = cur;
                     return;
                }
                prev = cur;
                cur = cur->next;
            }
}
       //GetElem: 从块中分配新元素
static void *GetElem(BlockP p, size_t elemSize, HeapType type)
{
            int i,index;
            if (p == NULL)
                   return NULL;
            switch (type)
            {
            case MHEAP:
                if (p->numFree == 0)
                          return NULL;
                index = p->firstFree; /