使用元胞数组的霍夫曼编码
Huffman encoding using cell array
我在霍夫曼编码的最后部分遇到了一些问题。
目前我的代码 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 的输入转换为输出。
因为您使用的是元胞数组,所以它本来就很慢,所以您别无选择,只能遍历每个元胞。但是,我可以提供一些建议来帮助加快速度。您可以做的是使用 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)
,但可能会略微比二次方好。
我在霍夫曼编码的最后部分遇到了一些问题。
目前我的代码 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 的输入转换为输出。
因为您使用的是元胞数组,所以它本来就很慢,所以您别无选择,只能遍历每个元胞。但是,我可以提供一些建议来帮助加快速度。您可以做的是使用 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)
,但可能会略微比二次方好。