估算可压缩性的更快、更准确的算法
- 比使用Shannon熵判断2到4倍更快、更准确。它基于Huffman编码方法。
- 回答的时间复杂度不取决于符号频率的数值，而是取决于唯一符号的数量。Shannon熵计算log(频率)，因此频率越高，计算这个值所需的时间也越长。在当前的方法中，避免了对频率值进行数学运算。
- 出于与上述原因相同的原因，精度也更高，因为我们避免了对浮点数的依赖，仅依赖于求和和乘法运算以及实际的Huffman编码如何对总压缩大小产生贡献。
- 相同的算法可以增强以在较短的时间内生成实际的Huffman编码，这不涉及像树、堆或优先队列这样的复杂数据结构。对于我们的不同要求，我们只使用相同的符号频率数组。
以下算法指定了如何计算存储在映射数组中的文件符号频率值的可压缩性。时间比较图表
int compressed_file_size_in_bits = 0, n=256;
insertionSort(map, 256);
for (j = 0; j < n; j++)
if (map[j] != 0)
break;
for (i = j; i + 1 < n; i++) {
j = i + 1;
compressed_file_size_in_bits = compressed_file_size_in_bits + map[i] + map[j];
map[i + 1] = map[i] + map[j];
Adjust_first_element(map + i + 1, n - i - 1);
}
printf("Entropy per byte %f ", compressed_file_size_in_bits * (1.0) / file_len);
void insertionSort(long arr[], long n) {
long i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void Adjust_first_element(long arr[], long n) {
long i, key, j = 1;
key = arr[0];
while (j < n && arr[j] < key) {
arr[j - 1] = arr[j];
j = j + 1;
}
arr[j - 1] = key;
}
使用上述算法构建代码
使用上述算法构建代码是一个字符串操作问题，我们从每个符号都没有代码开始。然后，我们遵循与压缩文件大小/可压缩性计算相同的算法。此外，我们只需不断维护代码演变的历史记录。在迭代频率数组完成后，我们最终的代码包含每个符号的不同Huffman代码的演变，并存储在代码数组的顶部索引中。
此时，一个字符串解析算法可以解析这种演变，并为每个符号生成单独的代码。整个过程不涉及树、堆或优先队列。只需要一次迭代通过频率数组（在大多数情况下为大小256）即可生成代码的演变以及最终压缩大小值。
void generate_code(long map[], int l, int r) {
int i, j, k, compressed_file_size_in_bits = 0;
insertionSort(map + l, r - l);
for (i = l; i + 1 <= r; i++) {
j = i + 1;
compressed_file_size = compressed_file_size_in_bits + map[i] + map[j];
char code[50] = "(";
strcat(code, codes[i]);
strcat(code, "0");
strcat(code, ",");
strcat(code, codes[j]);
strcat(code, "1");
strcat(code, ")");
map[i + 1] = map[i] + map[j];
strcpy(codes[i + 1], code);
int n = r - l;
Adjust_first_element(map + i + 1, n - i - 1, i + 1);
}
}
void insertionSort(long arr[], long n) {
long i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void Adjust_first_element(long arr[], long n, int start) {
long i, key, j = 1;
char temp_arr[250];
key = arr[0];
strcpy(temp_arr, codes[start]);
while (j < n && arr[j] < key) {
arr[j - 1] = arr[j];
strcpy(codes[j - 1 + start], codes[j + start]);
j = j + 1;
}
arr[j - 1] = key;
strcpy(codes[j - 1 + start], temp_arr);
}
