2026年单打码理论测试题及答案

2026年单打码理论测试题及答案

一、单项选择题（每题2分，共20分）1.单打码理论中，决定“唯一可译性”的核心条件是A.码长单调递增 B.Kraft不等式取等 C.前缀自由 D.熵最大化2.在二元无记忆信源下，若符号概率为0.7与0.3，则其一阶熵H₁的精确值为A.0.881 B.0.918 C.0.954 D.1.0003.采用Huffman算法构造最优前缀码时，合并节点的选择依据是A.概率最大 B.概率最小 C.码长最短 D.码长最长4.算术编码的区间分割依据是A.累积概率 B.自信息 C.条件熵 D.似然比5.在Lempel-Ziv78算法中，当新增短语长度为3时，指针字段的比特开销为A.⌈log₂(当前词典大小)⌉ B.3 C.8 D.固定126.对于平稳信源，熵率H∞与有限阶熵Hₙ的关系是A.H∞≥Hₙ B.H∞≤Hₙ C.H∞=Hₙ D.无单调关系7.在Golomb码参数m=8时，商值q=5的码字前缀由多少个1构成A.4 B.5 C.6 D.78.若信道码率R大于信道容量C，则根据Shannon有噪编码定理，误码率A.可趋零 B.必趋0.5 C.必趋1 D.存在非零下界9.采用自适应模型时，动态更新概率估计的常用策略是A.Witten-Bell B.几何分布 C.拉普拉斯平滑 D.伯努利近似10.在ANS编码中，状态x的归一化操作实质是A.位重排 B.区间重映射 C.概率缩放 D.熵修正二、填空题（每题2分，共20分）11.若Kraft和为0.995，则该前缀码的冗余度为______比特。12.对符号串“aaabbc”进行Move-to-Front变换后，首字符对应的编码值为______。13.在LZ77滑动窗口大小为4KB、前向缓冲32B时，偏移字段需______比特。14.当信源熵为2.5bit，实际码长2.7bit时，编码效率为______%。15.对于二元对称信道，交叉概率0.11，其信道容量为______bit/符号。16.采用指数哥伦布码k=1时，整数6的码字长度为______比特。17.在tANS实现中，若概率分母取2¹⁶，则状态最大值为______。18.若游程编码输入为“000111100011”，游程长度序列的游程个数为______。19.对于一阶马尔可夫信源，其记忆长度为______符号。20.当算术编码区间下限L=0.3125，区间长度R=0.03125，输出二进制最短码字为______。三、判断题（每题2分，共20分）21.Huffman码在任何非均匀分布下都严格达到熵界。22.算术编码的增量传输特性使其适合流式压缩。23.LZ78的词典一旦建立便不再删除旧条目。24.Golomb码对几何分布信源是渐近最优的。25.熵率越高，说明信源可压缩性越好。26.自适应模型无需预先知道信源统计特性。27.前缀码一定满足Kraft不等式，反之亦然。28.Shannon-Fano编码按概率降序均分构造，故必为最优。29.在ANS中，编码与解码可共享同一状态转移表。30.游程编码对独立同分布信源效果最佳。四、简答题（每题5分，共20分）31.阐述Kraft不等式与唯一可译码的充要关系，并给出证明思路。32.比较LZ77与LZ78在词典构建策略上的差异，并指出各自适用场景。33.说明算术编码中“区间下溢”问题的成因及常用解决技术。34.解释为何高阶上下文模型能提升压缩率，同时指出其代价。五、讨论题（每题5分，共20分）35.结合熵率定义，讨论非平稳信源在无限长观测下是否仍存在可定义的压缩极限，并给出理论依据。36.分析现代视频编码标准中CABAC相比传统Huffman的三项核心优势，并指出其硬件实现难点。37.探讨ANS在分布式存储系统中取代算术编码的潜在利弊，需兼顾压缩率、并行度与容错性。38.论证在量子信源模型下，经典前缀码理论需如何修正，并预测其熵界形式。答案与解析1.C 2.A 3.B 4.A 5.A 6.B 7.B 8.D 9.C 10.B11.0.005 12.0 13.12 14.92.59 15.0.5 16.5 17.65535 18.6 19.1 20.010121.× 22.√ 23.√ 24.√ 25.× 26.√ 27.× 28.× 29.√ 30.×31.Kraft不等式∑2^{-l_i}≤1是前缀码存在的充要条件。证明思路：将码字看作二叉树叶节点，前缀性质保证无祖先-后代重叠，叶节点总概率不超过1；反之，若满足不等式，可按层数递归放置码字，保证不冲突，从而构造出前缀码，进而唯一可译。32.LZ77用滑动窗口内历史文本作词典，输出（偏移,长度,下符）三元组，适合局部重复高的流式数据；LZ78显式建词典树，输出（索引,下符），对长距离重复更敏感，内存随词典增长，适合离线压缩。33.区间下溢指低值区间长度极小，高位相同导致无法继续输出。解决技术：1.采用E3缩放，当区间落入[0.25,0.5)或[0.5,0.75)时倍增并记录待输出位；2.使用整数区间并配合移位保证精度；3.引入区间重整保持有效位数。34.高阶上下文利用前面已编码符号作为条件，概率估计更精准，使平均码长逼近条件熵H(X|Context)，从而提升压缩率；代价是模型参数指数增长，需更大内存与更快适应算法，且对稀疏上下文需平滑处理，否则反增冗余。35.非平稳信源的熵率若定义为limsupHₙ/n，则极限存在但可能随样本路径变化；Cover与Thomas证明，若信源满足渐近均分性（AEP），则存在压缩极限等于熵率；对非平稳遍历信源，可用熵密度率描述，压缩极限为熵密度率的期望，故仍存在可定义极限，但需随机化编码达到。36.CABAC采用二进制算术编码、高阶上下文模型与快速重正化，优势：1.平均码长逼近条件熵，比Huffman节省5–15%码率；2.上下文模型多达60+种，适应局部统计变化；3.支持bypass模式加速符号。硬件难点：1.乘法区间更新需16×16位乘法器，时序紧；2.上下文表双端口读写，并行度受限；3.位打包需处理字节对齐与竞争冒险。37.ANS利：1.反向编码生成单一流，无需区间同步，压缩率与算术编码相当；2.状态转移表查表代替乘法，适合SIMD并行；3.可按块独立编码，容错局部化。弊：1.反向解码增加延迟，不适合超低延迟场景；2.状态表占用缓存，对嵌入式设备压力大；3.一旦表损坏，整块数据失效，需额