语音识别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-22） 递归（Induction）当时 即： 2-33） 终结（Termination） 2-4乘法次数大约为：N2Tc. 后向算法定义t时刻的后向变量（backward variable），可以通过迭代的方法来计算各个时刻的后向变量：1） 初始化（Initialization）当t=T时， 2-52） 递归（Induction）当时 即：， 2-63） 终结（Termination） 2-7 乘法计算次数约为：N2T2. 已知观察序列和模型参数，在最佳意义上确定一个状态序列。定义一个后验概率变量（posteriori probability variable） 2-7 则最优序列可以通过， 2-7求得。不过，这样求得的最优序列有些问题。如果，那么这个最优序列本身就不存在。这里讨论的最佳意义上的最优序列，是使最大化时的确定的状态序列。即，使最大化时确定的状态序列。 定义为t时刻沿一条路径，且，输出观察序列的最大概率，即： 2-8 下面介绍迭代计算的Viterbi算法：1） 初始化（Initialization），回溯变量：，2） 递归（Induction）即： 2-8 2-93） 终结（Termination） 2-10 2-114） 回溯状态序列， 2-123. 已知观察序列和模型参数，如何调整模型参数使最大。定义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 enumMHEAP,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/元素 ,不使用 */ Ptrdata; /* 指向数据区指针 ,指向数据区指针 */ 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. 内存堆创建算法CreateHeapvoid CreateHeap(MemHeap *x, char *name, HeapType type, size_t elemSize, float growf, size_t numElem, size_t maxElem) / 一致性检查 if (growf maxElem) /默认的元素个数不能大于最大允许的元素个数 HError(5170,CreateHeap: init num elem max elem in heap %s,name); if (elemSize 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 %un, 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); /释放p2. 内存堆重置算法ResetHeap将p从heapList中摘除void ResetHeap(MemHeap *x) BlockP cur,next;switch(x-type) case MHEAP:if (trace&T_TOP) printf(HMem: ResetHeap %sMn, 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 %sSn, 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. 内存堆删除算法DeleteHeapvoid 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 %sn, x-name);UnRecordHeap(x); /擦除内存堆x的Trace free(x-name); /释放分配的名称内存4. 从内存堆分配空间的算法New、CNewstatic 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 bytesn, 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 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; /第一个空闲元素索引号 p-usedp-firstFree/8 |= 1firstFree&7); /使用状态表中对应位置1 p-numFree-; /在使用状态表中寻找下一个空闲块 if (p-numFree 0) for (i=p-firstFree+1; inumElem;i+) if (p-usedi/8 & (1 firstFree = i; break; else p-firstFree = p-numElem; /firstFree=最大元素索引号+1 return (void *)(ByteP)p-data+index*elemSize); /返回分配的数据区指针 case MSTAK: /从栈顶取elemSize字节数的区域 if (p-numFree firstFree; p-firstFree += elemSize; p-numFree = p-numFree - elemSize; return (void *)(ByteP)p-data + index); /返回分配的数据区指针 default: HError(5190,GetElem: bad type %d, type); return NULL;#define FWORD 8 / size of a full word = 基本的分配量size_t MRound(size_t size) return (size % FWORD) = 0) ? size : (size/FWORD + 1) * FWORD;void *New(MemHeap *x, size_t size) /返回从内存堆x分配大小为size的新元素指针 void *q; BlockP newp; size_t num,bytes,*ip,chdr; Boolean noSpace; Ptr *pp; /一致性检查 if (x-elemSize name=NULL) ? Unnamed : x-name); switch(x-type) case MHEAP: /如果能从现有的块中找到空闲元素，则返回其指针。否则，就分配一个数据/区大小由curElem，growf以及maxElem决定的新块。 if (size != 0 & size != x-elemSize) /检查size的合法性 HError(5173,New: MHEAP req for %u size elem from heap %s size %u, size , x-name , x-elemSize); noSpace = x-totUsed = x-totAlloc; /如果totUsed=totAlloc则没有空闲元素 if (noSpace | (q = GetElem(x-heap , x-elemSize , x-type) = NULL) if (!noSpace) BlockReorder(&(x-heap), 1); /x-heap没有空闲元素，则向后寻找 if (noSpace | (q = GetElem(x-heap, x-el