为什么函数huffmandeco对大索引类型有倍频程误差

Question

我有一个小的MatLab脚本，我试图理解它。它作用不大。它只从文件中读取文本，并使用霍夫曼函数对其进行编码和解码。但它在解码时抛出了一个错误：

"错误：内存不足或维度对于Octave的索引类型太大
错误：从huffmandeco>调用；第95行第19列的dict2tree"；

我不知道为什么，因为我调试了它，没有看到大的索引类型。

我添加了根据输入文本计算p的部分。

%text is a random input text file in ASCII
%calculate the relative frequency of every Symbol
for i=0:127
nlet=length(find(text==i));
p(i+1)=nlet/length(text);
end
symb = 0:127;
dict = huffmandict(symb,p); % Create dictionary
compdata = huffmanenco(fdata,dict); % Encode the data
dsig = huffmandeco(compdata,dict); % Decode the Huffman code

我可以用八度音阶代替MatLab。我不知道，是否有意外的错误。我在Win10上使用Octave版本6.2.0。我尝试了大数据的版本，它没有改变任何东西
也许有人知道这种情况下的错误？

编辑：我再次调试了代码。在函数huffmandeco中，我发现了以下函数：

function tree = dict2tree (dict)
L = length (dict);
lengths = zeros (1, L);
## the depth of the tree is limited by the maximum word length.
for i = 1:L
lengths(i) = length (dict{i});
endfor
m = max (lengths);
tree = zeros (1, 2^(m+1)-1)-1;
for i = 1:L
pointer = 1;
word    = dict{i};
for bit = word
pointer = 2 * pointer + bit;
endfor
tree(pointer) = i;
endfor
endfunction

在这种情况下，最大长度m为82。因此，函数计算：
tree=zeros(1,2^(82+1(-1(-1。
因此，很明显，错误调用的索引类型太大
但必须有解决方案或其他错误，因为代码之前已经过测试。

Answer 1

我还没有仔细浏览代码，知道为什么，但huffmandict并没有像它声称的那样忽略零概率符号。我也没有找到Savannah的错误报告，但我也没有彻底搜索。

解决方法是将符号列表及其概率限制为仅实际出现的符号。使用containers.Map将是理想的，但在Octave中，您可以使用unique:的几个输出来实现这一点

% Create a symbol table of the unique characters in the input string
% and the indices into the table for each character in the string.
[symbols, ~, inds] = unique(textstr);
inds = inds.';   % just make it easier to read

对于字符串

textstr = 'Random String Input.';

结果是：

>> symbols
symbols =  .IRSadgimnoprtu
>> inds
inds =
Columns 1 through 19:
4    6   11    7   12   10    1    5   15   14    9   11    8    1    3   11   13   16   15
Column 20:
2

因此，输入字符串中的第一个符号是symbols(4)，第二个是symbols(6)，依此类推

从那里，您只需使用symbols和inds来创建字典并对信号进行编码/解码。下面是一个快速演示脚本：

textstr = 'Random String Input.';
fprintf("Starting string: %sn", textstr);
% Create a symbol table of the unique characters in the input string
% and the indices into the table for each character in the string.
[symbols, ~, inds] = unique(textstr);
inds = inds.';   % just make it easier to read
% Calculate the frequency of each symbol in table
% max(inds) == numel(symbols)
p = histc(inds, 1:max(inds))/numel(inds);
dict = huffmandict(symbols, p);
compdata = huffmanenco(inds, dict);
dsig = huffmandeco(compdata, dict);
fprintf("Decoded string: %sn", symbols(dsig));

输出：

Starting string: Random String Input.
Decoded string: Random String Input.

要对原始输入字符串以外的字符串进行编码，您必须将字符映射到符号索引(显然，要确保字符串中的所有符号都实际存在于符号表中(：

>> [~, s_idx] = ismember('trogdor', symbols)
s_idx =
15   14   12    8    7   12   14
>> compdata = huffmanenco(s_idx, dict);
>> dsig = huffmandeco(compdata, dict);
>> fprintf("Decoded string: %sn", symbols(dsig));
Decoded string: trogdor