压缩算法面试题常见考点与实战解析

压缩算法面试题为何频频出现

在字节、腾讯、阿里等大厂的后端和算法岗位面试中，压缩算法相关题目几乎成了标配。这不光是因为它能考察候选人对基础数据结构的掌握程度，更因为它贴近实际应用场景——比如网页传输用 Gzip 减少带宽消耗，APP 更新包用 LZMA 提高压缩率。

高频考察点：哈夫曼编码实现思路

面试官常让你手写一个简化版的哈夫曼压缩流程。核心是构造最优前缀码，通过字符频次建最小堆，合并两个最小频次节点直到生成一棵树。

import heapq
from collections import defaultdict

def build_huffman_tree(text):
    freq = defaultdict(int)
    for ch in text:
        freq[ch] += 1
    
    heap = [[weight, [char, ""]] for char, weight in freq.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

这段代码虽然不会直接考全，但建堆、贪心合并、前缀编码生成这些步骤经常被拆开提问。比如问“为什么每次选频率最低的两个？”答不上来就容易挂。

LZW 压缩怎么讲清楚

比起哈夫曼，LZW 更适合处理连续重复模式，GIF 图像格式就用了它。面试时如果被问到“如何用字典做无损压缩”，大概率是在引导你说 LZW。

它的逻辑像记缩写词。一开始字典里有所有单字符，然后扫描输入串，尽可能拼接已存在的词条。一旦遇到新组合，就加入字典并输出原词条编号。

def lzw_compress(uncompressed):
    dict_size = 256
    dictionary = {chr(i): i for i in range(dict_size)}
    
    w = ""
    result = []
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            result.append(dictionary[w])
            dictionary[wc] = dict_size
            dict_size += 1
            w = c
    
    if w:
        result.append(dictionary[w])
    return result

这个实现重点不在背代码，而在于解释清楚“字典动态增长”和“延迟输出”的设计意图。你可以类比微信聊天里的快捷短语，越用越聪明。

实际项目中的取舍：速度 vs 压缩率

有次朋友去面音视频平台，被问到“直播弹幕用什么压缩方式”。这题没标准答案，关键看你怎么分析场景。弹幕量大、实时性高，Zstandard 比 Gzip 更合适，因为压缩解压速度快，延迟低。

类似的，如果你做过日志系统，应该知道 Kafka 默认用 Snappy。不是因为它压缩得最狠，而是 CPU 占用少，机器扛得住高吞吐。

别忽视边界问题

有人写完哈夫曼编码忘了处理空字符串输入，或者 LZW 字典爆内存的情况。面试官一句“如果文本特别长怎么办”，就是在看你有没有工程思维。可以提限制字典大小、启用滑动窗口，甚至降级到简单行程编码。