霍夫曼编码在MATLAB中的实现 - 传输字典/树

Question

我正在使用MATLAB压缩任意向量，该软件提供了用于Huffman编码的工厂方法：huffmandict、huffmanenco和huffmandeco。

huffmandict函数生成一个查找表，将要编码的信号中的每个符号映射到其对应的码字，以便在对信号进行编码和解码时使用。

当您知道输入向量时，生成字典是微不足道的。但是，假设我正在压缩以从Alice发送到Bob - 我不能假设Bob也知道字典 - 因此Alice需要将字典与Huffman代码一起发送！

在MATLAB中是否有一种生成位流表示字典的方法，以便在另一端解码？

我的想法是，如果N是已编码字典的长度，则生成的代码如下：

(N encoded as 8 bits)(huffman dict encoded in N bits)(huffman code)

似乎很奇怪，MATLAB提供了相当强大的编码工厂方法，但是却没有费心让它在数字传输中实际可用，需要进行大量额外的工作。

我理解在理论上，通常会构建哈夫曼树 - 有没有一种方法可以在MATLAB中生成这样的树，然后将这样的树转换回字典？

- Jay

---

不是最有效的方法，但将字典保存为文件然后重新读入内存很容易。例如：save('dict.mat','dict','-v6'); f = fopen('dict.mat','rb'); data = uint8(fread(f)); fclose(f); 然后将 data 传输到接收端。在接收端写回文件并加载：f = fopen('dict.mat','wb'); fwrite(data); load('dict.mat'); fclose(f); - jodag

jsonencode / jsondecode 怎么样？ - nekomatic

Answer 1

我知道JPEG和gzip中使用的两种高效的代码表达方法，但据我了解，它们要求字典是规范的，也就是说，右侧（以1开头）的每个分支都必须更长。因此，您需要将代码转换为规范形式，因为有2^n（n为码字数）种设计。规范具有相同的预期长度。然后，您可以通过其分支的长度来表示每个符号，限制在合理的数量，例如2^4（表示每个符号的4位）。好的，让我们来看一下要发送的向量的代码：

for i = 1:size(dict,1)
    L(i) = numel(dict{i,2})
end

在接收方，你需要多做一些工作（我假设你的编码标签有一定的固定顺序）：

k = 0;
for l = 1:16
    k = k * 2;
    for j = find(L==l)
        d{j,1} = j;
        d{j,2} = de2bi(k, 'left-msb', l);
        k = k + 1;
    end
end

要将树转换为规范形式，您只需要将其转换为向量格式，然后再转换回来。

- mnz