C语言实现英语信源熵与马尔科夫信源实验详解

简介：面向高校信息论课程、C语言学习与算法实践者，这份资源聚焦英语信源熵计算与一阶马尔科夫信源建模，覆盖课程设计中常见的“熵值求解+序列生成”难题。压缩包共44个文件，整体约4.77MB，包含Visual Studio工程文件、C/C++源码、可执行exe、调试用pdb与编译日志、docx实验报告等，结构清晰，可直接打开工程对照运行。目前已有341人浏览/学习。实验以10段各超1万字符的英文文献为基础，先统一转小写并剔除标点、换行与连续空格，再分别统计26个字母与空格共27个符号的概率得到H1熵；随后计算一阶条件转移概率得到H2熵，并与教材结果对比；同时基于信源概率与马尔科夫概率各随机生成一段英文序列，直观比较可读性。资源内附完整C/C++源码（含必要注释）、可运行演示程序与实验报告docx，可帮助逐步验证算法流程，也能作为课程设计或信息论实验报告的支撑材料。 “C语言-信息论-英语信源熵实验-马尔科夫信源”这个题目，一看就是信息论课程里经典的编程实验。我当年做这个实验的时候，以为只是把公式翻译成代码跑一遍就完事了，结果从文本清洗、频率统计到转移矩阵的实现，每一步都踩了不小的坑。这篇博文就围绕这个实验，把完整的实现思路、核心代码逻辑和若干容易翻车的细节整理出来，给正在做类似课程设计或者想加深对信源熵理解的朋友一个可参考的样本。

1. 实验目标与整体设计思路

1.1 这个实验到底在算什么

先把这个题目的本质说清楚。所谓“英语信源”，就是把一段英文文本看成是一个符号序列的信源输出。信源的每个输出符号，通常就是26个英文字母，也可以把空格、标点纳入考虑范围。我们的任务是：基于一段足够长的英文语料，统计这些符号出现的概率，进而计算信源的熵。

但只算一个熵值还不够，这个实验的核心进阶内容是引入“马尔科夫信源”的概念。一阶马尔科夫信源假设下一个符号的输出概率只依赖当前符号；二阶马尔科夫信源则依赖前两个符号。也就是说，我们要分别求：

• 零阶熵（也就是一阶熵，直接对单字符概率求熵）：反映信源每个符号的平均信息量，不考虑符号之间的关联；
• 一阶马尔科夫条件下的条件熵：根据前一个字符来预测后一个字符，计算平均携带的信息量；
• 二阶马尔科夫条件下的条件熵：考虑前两个字符的上下文信息，计算条件熵。

从直观上讲，英文文本中字母之间是有强关联的，比如“q”后面几乎总是跟着“u”，“t”后面跟着“h”的概率也相当高。所以零阶熵应该最大，一阶条件熵明显下降，二阶条件熵更低。这个趋势就用C语言算出来，用数据展示英语的内在冗余度。

1.2 为什么选C语言而不是Python

很多同学第一反应是：这用Python写多快啊，collections.Counter一行就能统计频率，numpy算矩阵乘法也方便。确实，Python做这种东西开发效率极高。但课程设计指定用C语言，本质上是要你理解数据结构和底层逻辑，而不是调库。

用C语言做这个实验，有几个实实在在的好处：

• 必须自己设计数据结构来存概率表、转移矩阵，对“统计”这件事理解得更深刻；
• 文件读取、字符处理、内存管理都是基本功，能实实在在锻炼编码能力；
• 计算结果可以精确控制，浮点误差的认知也更直观。

其实C语言做这个实验的代码量也不大，核心逻辑撑死两三百行。关键是搞清楚每一步的输入输出是什么，别一上来就闷头写代码。

1.3 从英文文本到熵值：数据流转全貌

整个实验的流程可以分为五个阶段，我习惯用表格把它记下来：

理解了这张表，整个程序就是按部就班的事。接下来第2节先把公式讲清楚，第3节给出C语言关键实现，第4节放实验结果和解读，第5节集中写我遇到的坑和排查思路。

2. 信源熵的核心概念与公式推导

2.1 信息量与熵的定义

信息论里，一个信源符号出现的概率越高，携带的信息量反而越低。如果某个字母出现的概率是p，它的自信息量就是 I(x) = -log2(p)，单位是比特。信源的熵就是所有符号自信息量的数学期望：

H(X) = - Σ p(x_i) * log2(p(x_i))

这里的p(x_i)表示第i个符号出现的概率。对英文信源来说，如果只考虑26个字母，x_i就是a到z。

底数不同，熵的单位不一样。用log2算出来是比特/符号，用ln算出来是奈特/符号。课程设计通常要求用比特，所以直接调用log2函数。如果只支持log10或ln，就用换底公式：log2(x) = log(x) / log(2)。

2.2 条件熵与马尔科夫链的数学表达

一阶马尔科夫信源的关键是“状态”。对一阶模型，状态就是当前字母本身。从状态a转移到状态b的概率记为P(b|a)，即已知当前字母是a，下一个字母是b的概率。

条件熵的定义是：

H(X2 | X1) = - Σ P(a) Σ P(b|a) * log2(P(b|a))

写得更展开一点，就是先对每个当前字母a求一个“该状态下的条件熵”，再用P(a)作为权重加权平均。这个数值表示：我们知道前一个字母之后，对下一个字母还剩多少不确定性。

二阶马尔科夫模型的状态是双字母组合，比如“th”、“he”、“in”这些。状态数瞬间变成26×26=676个。对应的条件熵为：

H(X3 | X1, X2) = - Σ P(a,b) Σ P(c|a,b) * log2(P(c|a,b))

分子和分母的含义类似，只是条件从单个字母变成了两个字母。从计算量上来说，二阶模型需要统计26×26×26个三字母组合的频率。看起来数量很大，但只要文本够长（几万字符），绝大多数组合都能观测到，统计起来并不慢。

2.3 从概率到代码的映射关系

写代码之前，先把公式中的数学符号翻译成C语言里的变量：

• 字母频率表 freq[26]，存的是int类型计数，转换概率时用 double prob[26]；
• 一阶转移计数矩阵 trans[26][26]，trans[i][j]表示第i个字母后面跟着第j个字母的次数；
• 二阶转移计数可以用一个三维数组 trans2[26][26][26]，但注意它记录的是给定前两个字母（i,j），第三个字母是k的次数。

概率的计算用计数除以总数。一阶状态概率P(a)由freq[a]除以总字符数得到；转移概率P(b|a)由trans[a][b]除以freq[a]得到，注意分母是行和，不是总字符数。这里非常容易写错，很多人直接用总字符数去归一化转移矩阵，算出来的条件熵就会不对。

3. C语言实现的关键环节

3.1 文本读取与预处理

英文文本可能是从网上下载的小说、新闻，或者自己写的段落。原始文本里肯定有大写、小写、标点、数字、空格、换行。做信源统计之前，必须统一清洗。

我的做法是：只保留a-z和A-Z，遇到大写转小写，其余字符全部丢弃。这样信源符号集合就是确定的26个字母，方便用0-25索引表示。丢弃空格是个策略选择，后面会专门讨论。

#include <stdio.h> #include <ctype.h> #define ALPHABET_SIZE 26 #define MAX_BUFFER 1024 int main() { FILE *fp = fopen("english_text.txt", "r"); if (fp == NULL) { perror("无法打开文件"); return 1; } int freq[ALPHABET_SIZE] = {0}; int total = 0; int ch; while ((ch = fgetc(fp)) != EOF) { if (isalpha(ch)) { ch = tolower(ch); freq[ch - 'a']++; total++; } } fclose(fp); printf("总字母数: %d\n", total); return 0; }

上述代码已经把统计频率的核心逻辑完成了。注意fgetc返回的是int而不是char，原因是EOF是一个负整数，用char接收会截断，导致判断失效。这个细节不留意就写出死循环。

3.2 一阶统计与零阶熵的计算

有了freq和total，零阶熵直接套公式：

#include <math.h> double compute_entropy(int freq[], int total) { double H = 0.0; for (int i = 0; i < ALPHABET_SIZE; i++) { if (freq[i] == 0) continue; // 未出现的字母概率为0，不参与求和 double p = (double)freq[i] / total; H -= p * log2(p); } return H; }

关键就是这一句：log2(p)只有在p大于0的时候才有定义，所以对频率为0的字母要跳过。虽然26个英文字母理论上都会出现，但保险起见还是加上判断。

3.3 一阶马尔科夫模型：转移矩阵的构建

统计转移矩阵需要再遍历一次文本。思路是记录前一个字符prev，每读入一个当前字符curr，执行trans[prev][curr]++，然后更新prev=curr。

// 重新打开文件，统计相邻字母对 int trans[ALPHABET_SIZE][ALPHABET_SIZE] = {0}; fp = fopen("english_text.txt", "r"); if (fp == NULL) return 1; int prev = -1; while ((ch = fgetc(fp)) != EOF) { if (isalpha(ch)) { ch = tolower(ch) - 'a'; if (prev != -1) { trans[prev][ch]++; } prev = ch; } } fclose(fp);

这里prev初始化为-1，表示还没有读到有效字母。这样开头第一个字母不会被统计成“前一个字母”，因为它的前面没有上下文。

有了trans矩阵，一阶条件熵的计算方法如下：先算每个字母作为前一个字符的概率P(i)，即行和除以总字符数，然后对每一行计算该行的条件熵。逻辑上相当于先对每行做归一化，得到P(j|i)，再代入公式。

double compute_first_order_entropy(int trans[][ALPHABET_SIZE], int total) { double H = 0.0; // 先统计每个状态的总转移次数（即行和） int row_sum[ALPHABET_SIZE] = {0}; for (int i = 0; i < ALPHABET_SIZE; i++) { for (int j = 0; j < ALPHABET_SIZE; j++) { row_sum[i] += trans[i][j]; } } // 对每个状态i，计算其在所有转移中的占比作为P(i) // 这里用行和 / (总字符数 - 1)，因为最后一次转移没有后继 for (int i = 0; i < ALPHABET_SIZE; i++) { if (row_sum[i] == 0) continue; double p_state = (double)row_sum[i] / (total - 1); double h_given_i = 0.0; for (int j = 0; j < ALPHABET_SIZE; j++) { if (trans[i][j] == 0) continue; double p_trans = (double)trans[i][j] / row_sum[i]; h_given_i -= p_trans * log2(p_trans); } H += p_state * h_given_i; } return H; }

注意分母用的是total-1而不是total。因为总共有total个字母，相邻字符对最多只有total-1对。按理说行和加起来应该恰好等于total-1，用total还是total-1差别其实很小，但严谨度上total-1更正确。

3.4 二阶马尔科夫模型：双字母状态的条件熵

二阶模型比一阶模型复杂在状态空间变大。我们需要统计trans2[prev2][prev1][curr]，意思是给定前两个字母（prev2, prev1），当前字母是curr的次数。

int trans2[ALPHABET_SIZE][ALPHABET_SIZE][ALPHABET_SIZE] = {0}; fp = fopen("english_text.txt", "r"); if (fp == NULL) return 1; int prev2 = -1, prev1 = -1; while ((ch = fgetc(fp)) != EOF) { if (isalpha(ch)) { ch = tolower(ch) - 'a'; if (prev1 != -1 && prev2 != -1) { trans2[prev2][prev1][ch]++; } prev2 = prev1; prev1 = ch; } } fclose(fp);

二维状态的转移计数矩阵是26×26行，每行对应一个双字母组合（比如“th”），每列对应下一个字母，总维度26×26×26 = 17576个int。内存占用约70KB，完全没问题。但要注意全局变量或静态变量存放，分配在栈上可能会爆栈，特别是某些本地IDE默认栈空间比较小的时候。

二阶条件熵的计算类似一阶，只是把“状态”换成双字母组合（i,j），把行和替换成形如prev2=i, prev1=j的所有转移次数总和。核心代码就不再完整贴出来了，逻辑完全一致，只是多一层循环。

4. 实验数据与结果解读

4.1 使用什么文本作为信源样本

我试验用的文本是《爱丽丝漫游奇境记》的英文原文，大概15万字符，去掉标点和空格后还剩约13万字母。这个长度完全足够支撑一阶和二阶统计的可靠性。文本再短一点，比如几千字符，也能够算出结果，但二阶状态中大量组合没有出现，条件熵会偏低，产生误导。

选择文本的原则是：最好用真实、自然的英文文本。小说、新闻、维基百科词条都比自己编的几句话好。不要用代码注释或编程语言自带示例文本，因为那种语料和自然英语的统计特性差异很大。

4.2 实测结果与典型数值对照

我自己跑出来的数据大概是这样的（不同语料会有浮动）：

零阶熵4.16比特意味着如果完全忽略字母间的依赖，平均每个字母需要约4.16比特编码。而包含空格的英文信源零阶熵通常在4.2比特左右，如果扩展到27个符号会略高一点。已知前一个字母后，不确定性下降到3.69比特；已知前两个字母后，进一步下降到3.21比特。

这个下降趋势证实了英文存在大量冗余。熵从4.16降到3.21，说明仅靠前面两个字母的上下文，每个字母的平均信息量就能减少接近1个比特。如果再考虑整词、整句、语义层面的约束，真正的信息率还会低得多。这也是为什么压缩算法能对英文文本取得可观压缩比的根本原因。

4.3 从熵值看英语的冗余度

看到这个结果，可以进一步做一个简单计算。如果信息率是每秒10个字母，那么每秒传递的真实信息量大约是3.21×10 = 32.1比特（用二阶模型估算）。但实际上，英语书面文本的真实信息率远低于这个数——因为单词之间的语法、语义约束更强。一个直观的例子是，你看到“I am going to the”之后，基本能猜到下一个词是某个地点名词。这种可预测性就对应冗余。

课程设计报告里，如果能把熵值的下降趋势解释清楚，并且联系到数据压缩、信道编码中的“冗余度”概念，会非常加分。千万别只贴三个数字就完事。

5. 常见问题与调试经验实录

5.1 浮点计算与零概率处理

统计概率时最常见的错误是直接用int除法。C语言里写 p = freq[i] / total 得到的是整数商，永远等于0。必须先转型成double，例如 p = (double)freq[i] / total。

另一个坑是概率为0的情况。log2(0)在数学上无定义，代码里会遇到“NaN”（非数值）和“-inf”（负无穷）的诡异结果。所以我前面强调，遇到计数为0的项要直接跳过。

我在调试时还发现过一个问题：某些字母在短文本里完全没有出现，这会让熵值偏低。解决办法有两个：一是换更长的文本；二是在报告中说明语料规模。不要为了“好看”而人为往频率表里加噪声，那样反而不真实。

5.2 文本清洗的边界问题：空格和标点怎么处理

这是实验设计里最需要想清楚的问题。我在前面选择了只保留26个字母，但很多教材上的经典英文信源模型是把空格也算进去的，信源符号集合变为27个。空格是英语中出现频率最高的符号之一，约占总字符数的18%到20%。如果去掉空格，英文字母的频率分布会和包含空格时不同。

我的建议是：如果题目没有明确要求，可以两种都实现，在报告中对比说明。尤其当你发现算出来的零阶熵和教科书上的4.2有出入时，多半就是空格的处理方式不同。

标点符号通常不建议纳入。英语标点的种类多、频率低，统计意义不大，还会让信源模型复杂化。但如果你对某个特定文本（比如对话体小说）的标点规律感兴趣，也可以单独做扩展实验。

5.3 内存与栈空间的考量

二阶状态若用int trans2[26][26][26]，在函数内普通声明，有可能把栈撑爆。我的做法是：

• 放在函数外作为全局变量（静态存储区）；
• 或者使用static局部变量；
• 或者动态分配malloc/hand。

另外一个优化手段：二阶矩阵中很多组合实际上不会出现。如果语料只有几千字符，可能超过一半的格子都是0。此时可以考虑用稀疏存储结构（比如哈希表），但课程设计不追求性能极致，而且稠密的三维数组写起来更直白、不容易出错，所以我建议直接开满。

5.4 调试技巧：先用小样本验证

我在正式跑大文本之前，自己造了一个只有几十个字符的小样本，比如“hello world hello world”，手算一遍它的零阶熵和一阶条件熵，然后用程序输出对比。

比如“hello world”清洗掉空格后是“helloworld”，字母频率如下：

总字符数10，零阶熵为：

H = -(1/10log2(1/10) * 4 + 3/10log2(3/10) + 2/10*log2(2/10))

算出来约2.52比特。如果程序输出和手算一致，说明核心逻辑正确，再换成大文本才放心。这个习惯帮我排掉了很多低级错误——比如变量名写错、循环边界多算一个、把行和当总数等等。

5.5 实验结果不理想时的排查方向

如果你跑出来的熵下降趋势不对，或者数值明显异常，我建议按以下顺序排查：

• 先检查文件读取是否完整，打印total看字符总数是否合理；
• 再检查频次表，看排名是不是e、t、a、o、i、n等常见字母靠前。如果出现“z”最多，说明文本清洗或索引计算可能写错了；
• 检查转移矩阵的行和是否等于对应字母的频次减掉某种修正值。如果不相等，说明转移统计时的prev逻辑有bug；
• 最后再用小样本验证一遍。

另外还要注意：二次遍历文件时，如果第一次fgetc已经读到文件末尾，第二次打开文件要重新fopen，否则读不到内容。很多初学者在这里翻车，第二次遍历结果全为0，然后就怀疑算法错了。

6. 一点个人心得

整个实验做下来，我对“熵”这个抽象概念有了实感。熵不是课本上一个干巴巴的公式，而是可以通过代码真实算出来的、反映文本内在规律的数字。从零阶熵到一阶、二阶条件熵的逐级下降，让我直观感受到语言作为一种信源的冗余和结构。

另外，这个实验其实有很多扩展方向可以玩。比如把文本换成中文，需要先做分词编码；或者只用某个作家的作品统计风格特征；再或者把二阶扩展到三阶，观察熵的收敛趋势。这些扩展代码量都不大，但实验报告档次会明显不一样。

最后再分享一个小技巧：如果你用的是VS Code配C语言环境，记得在编译时加上-lm参数链接数学库，否则log2函数会报undefined reference错误。这个小问题，当年卡了我将近二十分钟。

本文还有配套的精品资源，点击获取