简介一套基于自适应霍夫曼编码的 MATLAB 实现面向信号编码领域完成文本压缩编码与解码的完整流程。资源适合本科、硕士阶段教学与科研使用也可作为信息论、数据压缩或信号编码课程的课设参考。压缩包共11个文件其中9个m脚本涵盖概率模型维护、霍夫曼树动态更新、编码与解码等多个核心子函数2个txt序列作为测试输入整体约5KB代码量精简但模块划分清晰可在 MATLAB 2019a 中直接运行并观察每一步概率与编码结果。已有200人学习浏览且所用自适应霍夫曼算法可根据实时统计动态调整编码表较传统静态方法更贴近流式压缩应用场景。通过脚本注释与实验序列读者既能掌握自适应编码的算法实现细节也能在此基础上扩展为课程设计、论文复现或进一步性能测试的代码基础。1. 文本编码里自适应霍夫曼为什么值得自己拆一遍文本编码里最常见的做法是先统计每个字符出现次数再按静态霍夫曼构建前缀码代价是统计和编码要扫描两遍码表还得随码流一起送出去。自适应霍夫曼FGK算法把这两步并成一步编码器一边读取文本一边更新二叉树解码器用相同规则同步重建不需要接收任何频率表。这对流式传输、实时文本处理和短消息场景非常友好也把“编码器与解码器状态同步”这个工程问题摆到了台面上。这套MATLAB实现包含完整的编码、解码函数和测试文本在MATLAB 2019a下可以跑通适合信息论与数字信号处理课程的实验复现也适合想抠FGK算法工程细节的开发者。2. 从静态霍夫曼到FGK算法自适应树的更新规则与兄弟性质2.1 静态霍夫曼的两遍扫描开销在哪里静态霍夫曼的工作流是先完整读一遍输入文本统计每个符号的频率再根据频率构造二叉树让每个符号落到唯一一条路径上。编码时查树生成码流解码时需要码表或者树结构否则无法还原。这意味着发送端必须把频表、树形或者码表附加进信道短消息场景下这个“头”可能比负载还大。更麻烦的是统计阶段意味着必须拿到全部数据才能开始编码流式场景下拿到第1个字符和拿到第100万个字符几乎没有区别都得等文件结束才动手。自适应霍夫曼换了一个思路一棵初始只包含根节点的树每处理一个字符就动态调整编码输出的码流完全由当前树形决定。也就是说编码与统计同时进行解码端没有收到任何额外的频表却能从同样的起始状态开始沿着同样的字符事件逐步重放出一模一样的树。代价是更新逻辑比静态版本复杂得多且编码端和解码端的每一步都必须严格同步。2.2 NYT节点新字符第一次出现时的编码通道静态霍夫曼编码时所有字符都已经存在于树中。自适应霍夫曼树是逐步生长的新字符第一次出现时树里还没有它的叶子这时候靠NYTNot Yet Transmitted节点兜底。它的编码规则可以浓缩成下面这张表。编码器遇到的情况输出内容输出后的树操作字符已在树中且是叶节点该叶节点的路径码如左0右1该叶节点权重加1向上回溯字符不在树中先输出当前NYT节点的路径码再输出该字符的固定长度原始编码如ASCII的8 bit将NYT节点分裂为内部节点挂两个叶子新字符叶子和新的NYT节点权重更新后违反兄弟性质无额外输出只调整树形找到同权重可交换节点进行交换再继续向上举个例子编码字符串aab。初始树只有一个根节点根节点就是NYT。第一次碰到aNYT路径为空直接输出a的ASCII码01100001。树随后分裂成内部节点加两个叶子假设a挂在左枝新NYT挂在右枝。第二次碰到aa已经有了叶子输出它的路径0。第三次碰到bb从未出现过先输出当前NYT节点的路径1再输出b的ASCII码01100010。整个码流串起来就是011000010101100010。解码端读到0就沿着左枝走发现是a叶子读到1就意识到NYT分支后面跟着8 bit字符从而重建出b。没有NYT就不会知道哪些bit是路径、哪些bit是裸字符。2.2.1 NYT节点分裂时权重如何分配我一般会看到两种处理一种把新字符叶子权重置为1新NYT节点权重置为0也有的实现把新NYT权重也置为1。权重为1的写法在解码端更容易统一判断“NYT也是叶节点”但排序和交换时要额外区分NYT节点的符号标记。权重为0的写法更贴近“NYT表示未出现集合”的语义。无论选哪种编码器和解码器必须一致否则第一次出现新字符时的树形就分叉了。比较省事的方案是新叶子权重从0开始这样后续updatetree从叶子一路自增父节点权重自然就包含了这次新字符的出现次数如果新叶子权重从1开始则要注意跳过叶子本身避免同一个字符被计数两次。2.3 Sibling Property先交换还是先自增FGK算法要求树在每一步更新后都满足Sibling Property每个非根节点都有兄弟并且所有节点可以按权重从大到小排序父节点的权重严格等于两个子节点权重之和。权重更新会打破这种平衡。比如某个节点的权重从2变成3它可能就比原本排在前面的节点更重了字面意义上树仍然是平衡二叉树但已经不再满足“兄弟权重顺序”约束需要找同级节点做交换。% updatetree.m 的更新骨架简化示意 function tree fgkUpdate(tree, idx) % idx 是本次出现字符的叶节点下标 while idx 1 target findSameWeightBlock(tree, idx); % 找同权重块中最靠后的节点 if target ~ idx tree swapNode(tree, idx, target); % 先交换 end tree.nodes(idx).weight tree.nodes(idx).weight 1; % 自增 idx tree.nodes(idx).parent; % 向根回溯 end end这里有个细节代码里先找同权重块、完成交换再对当前下标自增。如果反过来先自增再做交换目标节点的权重已经变化很容易把“同权重”的判断搞错最后出现父节点权重小于子节点的脏状态。同一个树更新函数在解码端也被调用任何交换顺序上的不一致都会让两棵树的形态从第一次分裂起就开始错位。MATLAB里没有指针语义tree必须以返回值形式传出来否则函数内部改了节点主调方还拿着旧结构体这是这套代码里常见的隐性错误来源。提示调试时把每一层的parent下标、left、right、weight都打印出来就能很快定位是交换顺序问题还是父指针修正问题。3. MATLAB工程拆解huffadaptencod.m 与 updatetree.m 的编码链路3.1 压缩包里的文件各自承担什么职责拿到这个zip后不要急着双击运行先对照文件名把链路理顺。工程里既有huffadaptencod.m、huffadaptdecod.m这样的自适应主流程也有huffencode.m、huffdecode.m这类静态方法辅助文件。下面这张表是文件职责梳理。文件职责定位备注huffadapt.m / huffadaptencod.m自适应霍夫曼编码入口逐字符读入输出码流huffadaptdecod.m自适应霍夫曼解码入口从同一初始树重建文本updatetree.m节点权重更新与交换编码解码共用probmodel.m概率模型初始化负责建立初始树与符号映射huff.m / huffman.m辅助函数多用于树遍历、路径获取或静态对照huffencode.m / huffdecode.m静态霍夫曼编解码用于和自适应版本对比seq.txt / seq1.txt测试文本两个不同长度的输入样例从命名推断probmodel.m大概率不只是计算频率而是把“树初始化”和“符号到节点的映射表”包装在一起。这样编码器拿到文本后第一件事不是统计而是调probmodel返回一棵只含根节点的树。3.2 编码主循环从文本到01串自适应编码的主循环看起来简单关键全在“当前树是什么样”。下面是按这个工程思路还原出来的循环代码。% huffadaptencod.m 的核心流程 function bitStream huffadaptencod(inputText) tree probmodel(); % 初始化树一个根节点附带NYT标记 bitStream ; % 积累编码结果 for i 1:numel(inputText) ch inputText(i); nytIdx findNYT(tree); % NYT节点的下标 leafIdx findSymbol(tree, ch, nytIdx); if ~isempty(leafIdx) pathCode getPathCode(tree, leafIdx); bitStream [bitStream, pathCode]; tree updatetree(tree, leafIdx); else pathCode getPathCode(tree, nytIdx); rawCode dec2bin(double(ch), 8); bitStream [bitStream, pathCode, rawCode]; tree insertNewSymbol(tree, ch); % 分裂NYT并挂新叶子 tree updatetree(tree, findSymbol(tree, ch)); end end end逻辑说明findSymbol查找字符时用NYT下标作为边界避免把NYT节点当成真实符号。输出路径码时getPathCode从叶子向根回溯把“父节点到当前节点的左右关系”逆序拼接最终得到从根到叶子的0/1序列。dec2bin(double(ch),8)把字符转成固定8位二进制字符串。注意如果输入包含中文double(ch)会超过255这里按单字节ASCII设计中文字符需要先转换成字节流再处理。参数说明bitStream变量在MATLAB里用字符串拼接待编码文本很长时会不断动态分配内存效率偏低。工程规模不大时可用长文本建议改成cell数组暂存最后一次性拼起来。findSymbol与findNYT属于probmodel或辅助函数返回的下标在MATLAB结构体树中下标就是节点在struct数组里的位置。3.3 updatetree.m 为什么是编码解码共用的关键自适应霍夫曼能省掉频表本质原因是编解码端共享同一份更新规则。updatetree.m里的交换逻辑如果写错编码端不会立刻报错只会生成一个“看似正常但解码端无法还原”的码流。调这类错误比调崩溃错误痛苦得多所以务必在debug时输出每一层的parent下标、left/right、weight。% updatetree.m 中交换节点的习惯写法 function tree swapNode(tree, a, b) % 交换两个节点在结构体数组中的位置 tmp tree.nodes(a); tree.nodes(a) tree.nodes(b); tree.nodes(b) tmp; % 交换后必须修正父节点指向 for child [tree.nodes(a).left, tree.nodes(a).right] if child ~ 0 tree.nodes(child).parent a; end end for child [tree.nodes(b).left, tree.nodes(b).right] if child ~ 0 tree.nodes(child).parent b; end end end注意这个交换修正了父子关系的指向。如果交换后忘了更新子节点的parent字段后续getPathCode回溯时就会走到错误的父链上解码端会从某一个字符开始出现路径错乱。实际工程中还需要处理a或b本身是叶节点的情形此时没有必要修正left/right只修正parent即可。3.4 probmodel.m 与初始树的形态probmodel这个名字容易让人误解为静态概率统计在自适应框架里它初始化的是“未出现符号的备用通道”。初始树只有根节点根被标记为NYT。树内每个节点持有weight、parent、left、right、symbol五个字段symbol在普通叶子中保存字符值在NYT节点取特殊值比如0。插入新符号时原NYT节点被替换为内部节点它的左儿子或右儿子按约定来挂新字符叶子另一个儿子挂新的NYT节点。新叶子权重从0开始分裂后调用updatetree从新叶子向根自增这样一次新字符出现只把父链上每个节点加1不会重复计数。解码端的逻辑必须完全一致读到NYT路径后插入同样的分裂再把新叶子的参与做一遍更新。两端的树如果没有裂变成同一个形状后续所有字符的路径都会错位。所以probmodel其实承担的是“状态初始器”的角色而不是传统意义上的概率估计。4. 解码镜像与误差传播huffadaptdecod.m 的同步机制4.1 为什么没有频率表也能还原自适应解码器的输入只有bit流没有频表、没有码表、也没有原始字符集合。它靠的是“树形随时间演化的确定性”从同一棵初始树开始对每个bit都严格遵循同一套行走规则。读到叶节点输出对应符号并调用与编码端完全相同的updatetree读到NYT按固定长度读取后续原始字符再执行分裂和更新。整个过程编码器解码器像两个并行进程每个输入bit驱动的状态更新都一模一样。说白了解码端维护的不是一张查表而是一台与编码端同步的状态机。4.2 解码端的三种判定当前节点类型读取动作输出调用动作非叶子节点继续读取下一个bit选择子树无无普通叶节点无该叶子对应的字符权重更新NYT叶节点再读固定8 bit新字符分裂NYT并插入新叶子看起来容易实际容易踩坑的地方是路径码是变长的解码端必须一个bit一个bit往树的深层走直到命中叶子才能停下。如果误把两条相邻码流中间的边界当成了bit位边界树走不到合法叶子整个后续解析全部错位。这也是自适应解码和定长编码解码的最大差别。4.3 解码主循环代码% huffadaptdecod.m 的核心流程 function outText huffadaptdecod(bitStream) tree probmodel(); outText ; pos 1; L numel(bitStream); while pos L idx 1; % 从根开始 while tree.nodes(idx).left ~ 0 % 非叶子就一直往下走 if bitStream(pos) 0 idx tree.nodes(idx).left; else idx tree.nodes(idx).right; end pos pos 1; end if tree.nodes(idx).symbol ~ 0 % 普通叶子 outText(end1) tree.nodes(idx).symbol; tree updatetree(tree, idx); else % NYT叶子读后面8 bit ch char(bin2dec(bitStream(pos:pos7))); pos pos 8; outText(end1) ch; tree insertNewSymbol(tree, ch); newIdx findSymbol(tree, ch); tree updatetree(tree, newIdx); end end end逻辑说明内层while碰到普通叶子时直接输出碰到NYT时symbol字段的值为0空符号标记于是从当前位置再切8个bit出来作为字符。bin2dec接收的是字符数组形式的01串bitStream如果是数值数组需要先转成char才能这样切片。pos指针在整个解码过程中始终指向待读入的bit位置它是解码端唯一的游标。参数说明这里对NYT节点判定用的是symbol0。如果工程中实际用别的数值表示空符号或者把0当成了合法字符比如字符串中含有空字符这个判断就要改成额外维护一个NYT下标集合。seq.txt和seq1.txt都是常规英文文本不涉及这个边界情况。32到126的可见ASCII字符和换行符都不会与0冲突。4.4 在MATLAB 2019a下跑通测试样例% 命令行执行验证编解码一致性 seq fileread(seq.txt); code huffadaptencod(seq); recover huffadaptdecod(code); isequal(seq, recover) % 返回逻辑值1 fprintf(载入字符数: %d\n, numel(seq)); fprintf(编码bit数: %d\n, numel(code));这段命令先读入seq.txt整段文本用自适应编码得到01串再解码并比对。如果返回1说明树更新、NYT分裂和路径编码在两端完全一致。如果返回0优先检查updatetree里的交换顺序以及分裂后新旧NYT的父指针是否修正。换用seq1.txt再跑一遍可以顺便观察文本长度与编码bit数的关系为实验报告里的压缩率曲线准备数据。5. 验证编码效率、排错MATLAB版本差异与字节流打包5.1 把自适应编码和静态编码放同一把尺子上比压缩效果不能只看“能不能还原”。把字符数相同的文本分别丢给静态霍夫曼和自适应霍夫曼观察码长差距才算真正把实验做完整。静态版本一次统计后生成的树接近最优自适应版本在编码过程中逐步收敛文本较短时自适应编码经常比静态编码多出几个bit的NYT开销文本越长差距越小。% 码长对比脚本huffencode按实际函数签名调整 seq fileread(seq1.txt); adaptBits numel(huffadaptencod(seq)); staticBits numel(huffencode(seq)); % 若返回码表则自行加权求码长 fprintf(adaptive: %d bits\n, adaptBits); fprintf(static: %d bits\n, staticBits);逻辑说明如果huffencode返回的是码字表而非码流就遍历原文本、把每个字符的码字长度累加。这样得到的静态码长不包含频表开销静态编码的实际传输还要加上码表长度自适应编码则没有这笔额外传输成本实验对比时要注明口径。5.2 MATLAB版本与中文文本的坑MATLAB 2019a之后char数组和string类型混用导致的错误很常见。fileread返回char向量但如果你在命令行里先构造了string再传给编码函数numel行为、索引行为都不一样for循环在string上会按“一个字符串元素”处理。统一用char入参最省事。不要指望像操作Python脚本那样让Codex直接按Python习惯生成MATLAB的霍夫曼实现就能跑自适应树的更新顺序任何偏差都会导致编解码静默错位。中文场景下我会先做一步字节化例如把原文按UTF-8转成uint8数组把每个字节当成一个符号去编码解码后再恢复成字符避免double算出的码值超过255。5.3 把01字符串收进内存和磁盘自适应编码算出的码流默认是01字符串直接存盘会膨胀8倍必须打包成二进制。这一步对实验和实际传输都很有必要。% 将01字符串按8bit一组转成uint8数组 code huffadaptencod(seq); padLen mod(8 - mod(numel(code), 8), 8); codePad [code, repmat(0, 1, padLen)]; byteData uint8(bin2dec(reshape(codePad, 8, [])));逻辑说明reshape把补零后的01串按行切成每8个字符一块bin2dec把每块二进制字符串转成十进制数字再转成uint8数组。补零只发生在最后一块解码时要知道原始码长最常见做法是在打包字节流前用固定4字节记录numel(code)。如果是MATLAB里自用不落盘也可以把bitStream存成logical数组占1字节而不是1个char能省下不少内存。最后补一个对固定字符集场景很实用的小技巧如果待压缩文本只会出现有限几种符号比如基因序列只有ACGT四个字母那就不需要从一棵只有根的树开始。初始化probmodel时直接把四个叶子放进树里让它们一出生就有固定路径编码时直接跳过NYT路径和裸ASCII输出节省掉整个“首次出现”阶段的额外bit开销同时所有手工验证逻辑都能沿用上面的代码。本文还有配套的精品资源点击获取 自适应霍夫曼编码FGK算法详解与MATLAB实现
简介一套基于自适应霍夫曼编码的 MATLAB 实现面向信号编码领域完成文本压缩编码与解码的完整流程。资源适合本科、硕士阶段教学与科研使用也可作为信息论、数据压缩或信号编码课程的课设参考。压缩包共11个文件其中9个m脚本涵盖概率模型维护、霍夫曼树动态更新、编码与解码等多个核心子函数2个txt序列作为测试输入整体约5KB代码量精简但模块划分清晰可在 MATLAB 2019a 中直接运行并观察每一步概率与编码结果。已有200人学习浏览且所用自适应霍夫曼算法可根据实时统计动态调整编码表较传统静态方法更贴近流式压缩应用场景。通过脚本注释与实验序列读者既能掌握自适应编码的算法实现细节也能在此基础上扩展为课程设计、论文复现或进一步性能测试的代码基础。1. 文本编码里自适应霍夫曼为什么值得自己拆一遍文本编码里最常见的做法是先统计每个字符出现次数再按静态霍夫曼构建前缀码代价是统计和编码要扫描两遍码表还得随码流一起送出去。自适应霍夫曼FGK算法把这两步并成一步编码器一边读取文本一边更新二叉树解码器用相同规则同步重建不需要接收任何频率表。这对流式传输、实时文本处理和短消息场景非常友好也把“编码器与解码器状态同步”这个工程问题摆到了台面上。这套MATLAB实现包含完整的编码、解码函数和测试文本在MATLAB 2019a下可以跑通适合信息论与数字信号处理课程的实验复现也适合想抠FGK算法工程细节的开发者。2. 从静态霍夫曼到FGK算法自适应树的更新规则与兄弟性质2.1 静态霍夫曼的两遍扫描开销在哪里静态霍夫曼的工作流是先完整读一遍输入文本统计每个符号的频率再根据频率构造二叉树让每个符号落到唯一一条路径上。编码时查树生成码流解码时需要码表或者树结构否则无法还原。这意味着发送端必须把频表、树形或者码表附加进信道短消息场景下这个“头”可能比负载还大。更麻烦的是统计阶段意味着必须拿到全部数据才能开始编码流式场景下拿到第1个字符和拿到第100万个字符几乎没有区别都得等文件结束才动手。自适应霍夫曼换了一个思路一棵初始只包含根节点的树每处理一个字符就动态调整编码输出的码流完全由当前树形决定。也就是说编码与统计同时进行解码端没有收到任何额外的频表却能从同样的起始状态开始沿着同样的字符事件逐步重放出一模一样的树。代价是更新逻辑比静态版本复杂得多且编码端和解码端的每一步都必须严格同步。2.2 NYT节点新字符第一次出现时的编码通道静态霍夫曼编码时所有字符都已经存在于树中。自适应霍夫曼树是逐步生长的新字符第一次出现时树里还没有它的叶子这时候靠NYTNot Yet Transmitted节点兜底。它的编码规则可以浓缩成下面这张表。编码器遇到的情况输出内容输出后的树操作字符已在树中且是叶节点该叶节点的路径码如左0右1该叶节点权重加1向上回溯字符不在树中先输出当前NYT节点的路径码再输出该字符的固定长度原始编码如ASCII的8 bit将NYT节点分裂为内部节点挂两个叶子新字符叶子和新的NYT节点权重更新后违反兄弟性质无额外输出只调整树形找到同权重可交换节点进行交换再继续向上举个例子编码字符串aab。初始树只有一个根节点根节点就是NYT。第一次碰到aNYT路径为空直接输出a的ASCII码01100001。树随后分裂成内部节点加两个叶子假设a挂在左枝新NYT挂在右枝。第二次碰到aa已经有了叶子输出它的路径0。第三次碰到bb从未出现过先输出当前NYT节点的路径1再输出b的ASCII码01100010。整个码流串起来就是011000010101100010。解码端读到0就沿着左枝走发现是a叶子读到1就意识到NYT分支后面跟着8 bit字符从而重建出b。没有NYT就不会知道哪些bit是路径、哪些bit是裸字符。2.2.1 NYT节点分裂时权重如何分配我一般会看到两种处理一种把新字符叶子权重置为1新NYT节点权重置为0也有的实现把新NYT权重也置为1。权重为1的写法在解码端更容易统一判断“NYT也是叶节点”但排序和交换时要额外区分NYT节点的符号标记。权重为0的写法更贴近“NYT表示未出现集合”的语义。无论选哪种编码器和解码器必须一致否则第一次出现新字符时的树形就分叉了。比较省事的方案是新叶子权重从0开始这样后续updatetree从叶子一路自增父节点权重自然就包含了这次新字符的出现次数如果新叶子权重从1开始则要注意跳过叶子本身避免同一个字符被计数两次。2.3 Sibling Property先交换还是先自增FGK算法要求树在每一步更新后都满足Sibling Property每个非根节点都有兄弟并且所有节点可以按权重从大到小排序父节点的权重严格等于两个子节点权重之和。权重更新会打破这种平衡。比如某个节点的权重从2变成3它可能就比原本排在前面的节点更重了字面意义上树仍然是平衡二叉树但已经不再满足“兄弟权重顺序”约束需要找同级节点做交换。% updatetree.m 的更新骨架简化示意 function tree fgkUpdate(tree, idx) % idx 是本次出现字符的叶节点下标 while idx 1 target findSameWeightBlock(tree, idx); % 找同权重块中最靠后的节点 if target ~ idx tree swapNode(tree, idx, target); % 先交换 end tree.nodes(idx).weight tree.nodes(idx).weight 1; % 自增 idx tree.nodes(idx).parent; % 向根回溯 end end这里有个细节代码里先找同权重块、完成交换再对当前下标自增。如果反过来先自增再做交换目标节点的权重已经变化很容易把“同权重”的判断搞错最后出现父节点权重小于子节点的脏状态。同一个树更新函数在解码端也被调用任何交换顺序上的不一致都会让两棵树的形态从第一次分裂起就开始错位。MATLAB里没有指针语义tree必须以返回值形式传出来否则函数内部改了节点主调方还拿着旧结构体这是这套代码里常见的隐性错误来源。提示调试时把每一层的parent下标、left、right、weight都打印出来就能很快定位是交换顺序问题还是父指针修正问题。3. MATLAB工程拆解huffadaptencod.m 与 updatetree.m 的编码链路3.1 压缩包里的文件各自承担什么职责拿到这个zip后不要急着双击运行先对照文件名把链路理顺。工程里既有huffadaptencod.m、huffadaptdecod.m这样的自适应主流程也有huffencode.m、huffdecode.m这类静态方法辅助文件。下面这张表是文件职责梳理。文件职责定位备注huffadapt.m / huffadaptencod.m自适应霍夫曼编码入口逐字符读入输出码流huffadaptdecod.m自适应霍夫曼解码入口从同一初始树重建文本updatetree.m节点权重更新与交换编码解码共用probmodel.m概率模型初始化负责建立初始树与符号映射huff.m / huffman.m辅助函数多用于树遍历、路径获取或静态对照huffencode.m / huffdecode.m静态霍夫曼编解码用于和自适应版本对比seq.txt / seq1.txt测试文本两个不同长度的输入样例从命名推断probmodel.m大概率不只是计算频率而是把“树初始化”和“符号到节点的映射表”包装在一起。这样编码器拿到文本后第一件事不是统计而是调probmodel返回一棵只含根节点的树。3.2 编码主循环从文本到01串自适应编码的主循环看起来简单关键全在“当前树是什么样”。下面是按这个工程思路还原出来的循环代码。% huffadaptencod.m 的核心流程 function bitStream huffadaptencod(inputText) tree probmodel(); % 初始化树一个根节点附带NYT标记 bitStream ; % 积累编码结果 for i 1:numel(inputText) ch inputText(i); nytIdx findNYT(tree); % NYT节点的下标 leafIdx findSymbol(tree, ch, nytIdx); if ~isempty(leafIdx) pathCode getPathCode(tree, leafIdx); bitStream [bitStream, pathCode]; tree updatetree(tree, leafIdx); else pathCode getPathCode(tree, nytIdx); rawCode dec2bin(double(ch), 8); bitStream [bitStream, pathCode, rawCode]; tree insertNewSymbol(tree, ch); % 分裂NYT并挂新叶子 tree updatetree(tree, findSymbol(tree, ch)); end end end逻辑说明findSymbol查找字符时用NYT下标作为边界避免把NYT节点当成真实符号。输出路径码时getPathCode从叶子向根回溯把“父节点到当前节点的左右关系”逆序拼接最终得到从根到叶子的0/1序列。dec2bin(double(ch),8)把字符转成固定8位二进制字符串。注意如果输入包含中文double(ch)会超过255这里按单字节ASCII设计中文字符需要先转换成字节流再处理。参数说明bitStream变量在MATLAB里用字符串拼接待编码文本很长时会不断动态分配内存效率偏低。工程规模不大时可用长文本建议改成cell数组暂存最后一次性拼起来。findSymbol与findNYT属于probmodel或辅助函数返回的下标在MATLAB结构体树中下标就是节点在struct数组里的位置。3.3 updatetree.m 为什么是编码解码共用的关键自适应霍夫曼能省掉频表本质原因是编解码端共享同一份更新规则。updatetree.m里的交换逻辑如果写错编码端不会立刻报错只会生成一个“看似正常但解码端无法还原”的码流。调这类错误比调崩溃错误痛苦得多所以务必在debug时输出每一层的parent下标、left/right、weight。% updatetree.m 中交换节点的习惯写法 function tree swapNode(tree, a, b) % 交换两个节点在结构体数组中的位置 tmp tree.nodes(a); tree.nodes(a) tree.nodes(b); tree.nodes(b) tmp; % 交换后必须修正父节点指向 for child [tree.nodes(a).left, tree.nodes(a).right] if child ~ 0 tree.nodes(child).parent a; end end for child [tree.nodes(b).left, tree.nodes(b).right] if child ~ 0 tree.nodes(child).parent b; end end end注意这个交换修正了父子关系的指向。如果交换后忘了更新子节点的parent字段后续getPathCode回溯时就会走到错误的父链上解码端会从某一个字符开始出现路径错乱。实际工程中还需要处理a或b本身是叶节点的情形此时没有必要修正left/right只修正parent即可。3.4 probmodel.m 与初始树的形态probmodel这个名字容易让人误解为静态概率统计在自适应框架里它初始化的是“未出现符号的备用通道”。初始树只有根节点根被标记为NYT。树内每个节点持有weight、parent、left、right、symbol五个字段symbol在普通叶子中保存字符值在NYT节点取特殊值比如0。插入新符号时原NYT节点被替换为内部节点它的左儿子或右儿子按约定来挂新字符叶子另一个儿子挂新的NYT节点。新叶子权重从0开始分裂后调用updatetree从新叶子向根自增这样一次新字符出现只把父链上每个节点加1不会重复计数。解码端的逻辑必须完全一致读到NYT路径后插入同样的分裂再把新叶子的参与做一遍更新。两端的树如果没有裂变成同一个形状后续所有字符的路径都会错位。所以probmodel其实承担的是“状态初始器”的角色而不是传统意义上的概率估计。4. 解码镜像与误差传播huffadaptdecod.m 的同步机制4.1 为什么没有频率表也能还原自适应解码器的输入只有bit流没有频表、没有码表、也没有原始字符集合。它靠的是“树形随时间演化的确定性”从同一棵初始树开始对每个bit都严格遵循同一套行走规则。读到叶节点输出对应符号并调用与编码端完全相同的updatetree读到NYT按固定长度读取后续原始字符再执行分裂和更新。整个过程编码器解码器像两个并行进程每个输入bit驱动的状态更新都一模一样。说白了解码端维护的不是一张查表而是一台与编码端同步的状态机。4.2 解码端的三种判定当前节点类型读取动作输出调用动作非叶子节点继续读取下一个bit选择子树无无普通叶节点无该叶子对应的字符权重更新NYT叶节点再读固定8 bit新字符分裂NYT并插入新叶子看起来容易实际容易踩坑的地方是路径码是变长的解码端必须一个bit一个bit往树的深层走直到命中叶子才能停下。如果误把两条相邻码流中间的边界当成了bit位边界树走不到合法叶子整个后续解析全部错位。这也是自适应解码和定长编码解码的最大差别。4.3 解码主循环代码% huffadaptdecod.m 的核心流程 function outText huffadaptdecod(bitStream) tree probmodel(); outText ; pos 1; L numel(bitStream); while pos L idx 1; % 从根开始 while tree.nodes(idx).left ~ 0 % 非叶子就一直往下走 if bitStream(pos) 0 idx tree.nodes(idx).left; else idx tree.nodes(idx).right; end pos pos 1; end if tree.nodes(idx).symbol ~ 0 % 普通叶子 outText(end1) tree.nodes(idx).symbol; tree updatetree(tree, idx); else % NYT叶子读后面8 bit ch char(bin2dec(bitStream(pos:pos7))); pos pos 8; outText(end1) ch; tree insertNewSymbol(tree, ch); newIdx findSymbol(tree, ch); tree updatetree(tree, newIdx); end end end逻辑说明内层while碰到普通叶子时直接输出碰到NYT时symbol字段的值为0空符号标记于是从当前位置再切8个bit出来作为字符。bin2dec接收的是字符数组形式的01串bitStream如果是数值数组需要先转成char才能这样切片。pos指针在整个解码过程中始终指向待读入的bit位置它是解码端唯一的游标。参数说明这里对NYT节点判定用的是symbol0。如果工程中实际用别的数值表示空符号或者把0当成了合法字符比如字符串中含有空字符这个判断就要改成额外维护一个NYT下标集合。seq.txt和seq1.txt都是常规英文文本不涉及这个边界情况。32到126的可见ASCII字符和换行符都不会与0冲突。4.4 在MATLAB 2019a下跑通测试样例% 命令行执行验证编解码一致性 seq fileread(seq.txt); code huffadaptencod(seq); recover huffadaptdecod(code); isequal(seq, recover) % 返回逻辑值1 fprintf(载入字符数: %d\n, numel(seq)); fprintf(编码bit数: %d\n, numel(code));这段命令先读入seq.txt整段文本用自适应编码得到01串再解码并比对。如果返回1说明树更新、NYT分裂和路径编码在两端完全一致。如果返回0优先检查updatetree里的交换顺序以及分裂后新旧NYT的父指针是否修正。换用seq1.txt再跑一遍可以顺便观察文本长度与编码bit数的关系为实验报告里的压缩率曲线准备数据。5. 验证编码效率、排错MATLAB版本差异与字节流打包5.1 把自适应编码和静态编码放同一把尺子上比压缩效果不能只看“能不能还原”。把字符数相同的文本分别丢给静态霍夫曼和自适应霍夫曼观察码长差距才算真正把实验做完整。静态版本一次统计后生成的树接近最优自适应版本在编码过程中逐步收敛文本较短时自适应编码经常比静态编码多出几个bit的NYT开销文本越长差距越小。% 码长对比脚本huffencode按实际函数签名调整 seq fileread(seq1.txt); adaptBits numel(huffadaptencod(seq)); staticBits numel(huffencode(seq)); % 若返回码表则自行加权求码长 fprintf(adaptive: %d bits\n, adaptBits); fprintf(static: %d bits\n, staticBits);逻辑说明如果huffencode返回的是码字表而非码流就遍历原文本、把每个字符的码字长度累加。这样得到的静态码长不包含频表开销静态编码的实际传输还要加上码表长度自适应编码则没有这笔额外传输成本实验对比时要注明口径。5.2 MATLAB版本与中文文本的坑MATLAB 2019a之后char数组和string类型混用导致的错误很常见。fileread返回char向量但如果你在命令行里先构造了string再传给编码函数numel行为、索引行为都不一样for循环在string上会按“一个字符串元素”处理。统一用char入参最省事。不要指望像操作Python脚本那样让Codex直接按Python习惯生成MATLAB的霍夫曼实现就能跑自适应树的更新顺序任何偏差都会导致编解码静默错位。中文场景下我会先做一步字节化例如把原文按UTF-8转成uint8数组把每个字节当成一个符号去编码解码后再恢复成字符避免double算出的码值超过255。5.3 把01字符串收进内存和磁盘自适应编码算出的码流默认是01字符串直接存盘会膨胀8倍必须打包成二进制。这一步对实验和实际传输都很有必要。% 将01字符串按8bit一组转成uint8数组 code huffadaptencod(seq); padLen mod(8 - mod(numel(code), 8), 8); codePad [code, repmat(0, 1, padLen)]; byteData uint8(bin2dec(reshape(codePad, 8, [])));逻辑说明reshape把补零后的01串按行切成每8个字符一块bin2dec把每块二进制字符串转成十进制数字再转成uint8数组。补零只发生在最后一块解码时要知道原始码长最常见做法是在打包字节流前用固定4字节记录numel(code)。如果是MATLAB里自用不落盘也可以把bitStream存成logical数组占1字节而不是1个char能省下不少内存。最后补一个对固定字符集场景很实用的小技巧如果待压缩文本只会出现有限几种符号比如基因序列只有ACGT四个字母那就不需要从一棵只有根的树开始。初始化probmodel时直接把四个叶子放进树里让它们一出生就有固定路径编码时直接跳过NYT路径和裸ASCII输出节省掉整个“首次出现”阶段的额外bit开销同时所有手工验证逻辑都能沿用上面的代码。本文还有配套的精品资源点击获取