使用元胞数组的霍夫曼编码

Question

我在霍夫曼编码的最后部分遇到了一些问题。

目前我的代码 table 在元胞数组中

code =
{
  [1,1] = 000
  [1,2] = 001
  [1,3] = 010
  [1,4] = 011
  [1,5] = 100
  ...
}

其中第二个索引表示我的其他元胞数组中的 ascii 字符

huffman_tree =
{
  [1,1] = A
  [1,2] = B
  [1,3] = C
  [1,4] = D
  [1,5] = E
  ...
}

我正在使用以下代码对输入和输出进行编码：

output= [];
for i=1:length(input)
    x = findInArray(huffman_tree, input(i));
    output= [output code(x)];
end


function [index] = findInArray(array, searched)
    index = -1;
    for i=1:length(array)
        if array{i} == searched
            index = i;
        end
    end
end

此时我的代码是 O(n^2) 甚至更糟。我遇到大输入问题 where

length(input) = 1000000

一定有一些更快的方法可以将我的编码 table 的输入转换为输出。

Answer 1

因为您使用的是元胞数组，所以它本来就很慢，所以您别无选择，只能遍历每个元胞。但是，我可以提供一些建议来帮助加快速度。您可以做的是使用 strcmp 来比较字符串。我假设您的元胞数组中的每个字符都表示为一个字符串。 strcmp 能够获取单个字符串并将其自身与字符串元胞数组进行比较。输出将是一个与字符串元胞数组大小相同的数组，如果输入字符串与元胞数组中的某个位置匹配，则输出为逻辑 true，否则为 false。

因为您的霍夫曼词典将包含一组独特的字符，所以每个字符您只能得到一个可能的匹配项。因此，我们可以直接用这个logical数组输出索引码本，检索出你想要的对应码。逻辑索引通过提供与感兴趣的向量长度相同的逻辑向量来工作，并检索对应位置为 true 的那些值。因此，如果我们在逻辑向量中只有一个 true 值，其余元素为 false，这意味着我们将得到相应的元素我们只想要。

因此，我们可以更改您的代码来执行此操作。请注意，我已将循环计数器 i 更改为 idx，因为事实证明，使用 i 作为循环计数器会略微降低代码速度。请参阅 Shai Bagon for more details: Using i and j as variables in Matlab 的 post。此外，我已将 length 调用更改为 numel...主要是因为我不喜欢使用 length...不过只是个人选择。

output = [];
for idx = 1:numel(input)
    output = [output code(strcmp(input(idx), huffman_tree))];
end

试一试上面的代码，看看它的执行速度是否更快。一方面，这将使用额外的 for 循环来搜索匹配项，因为 strcmp 的实现非常有效，因此上面的代码不会是 O(n^2)，但可能会略微比二次方好。

使用元胞数组的霍夫曼编码

Huffman encoding using cell array

matlab

optimization

encoding

huffman-code

cell-array