压缩算法简介

2024-06-22 14:36
文章标签 简介 压缩算法

本文主要是介绍压缩算法简介，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 概述

压缩算法是一种通过减少数据量来节省存储空间或传输数据的技术。压缩算法可以分为两种类型：有损压缩和无损压缩。
有损压缩算法会牺牲一定的数据精度或质量，在压缩数据的同时丢失一些信息。这种算法适用于音频、视频等多媒体数据，例如JPEG和MP3等格式。
无损压缩算法则能够完全还原原始数据，不会造成数据丢失。这种算法适用于需要准确还原数据的场景，如文档、代码等，例如ZIP和GZIP等格式。
常见的压缩算法包括哈夫曼编码、Lempel-Ziv算法、Run-Length Encoding（RLE）等。这些算法通过不同的方式对数据进行编码和解码，以实现数据压缩和解压缩的目的。

2 压缩算法的应用

压缩算法在各种领域广泛应用，包括但不限于以下几个方面：
文件传输和存储：压缩算法可以减少文件的大小，使文件传输更加高效快速。在网络传输、电子邮件附件、云存储等场景下，压缩算法可以节省带宽和存储空间。
多媒体数据：音频、视频等多媒体数据通常是体积较大的，使用压缩算法可以减少文件大小，提高数据的传输速度和播放效果。常见的视频压缩算法包括H.264、HEVC等；音频压缩算法包括MP3、AAC等。
数据库压缩：在数据库管理系统中，数据通常存储在磁盘上，通过压缩算法可以减少数据占用的存储空间，并提高数据库的性能和响应速度。
图像处理：在数字图像处理中，压缩算法可以减小图像文件的大小，在图像传输和存储中起到重要作用。常见的图像压缩算法包括JPEG、PNG等。
网页内容压缩：为了减少网页加载时间和用户访问流量，网站通常会使用压缩算法对HTML、CSS、JavaScript等网页内容进行压缩，提高用户体验和网站性能。
总的来说，压缩算法在信息技术领域的各个方面都有广泛的应用，可以有效地节省存储空间、提高数据传输效率和优化性能。

3适合ARM跑的压缩算法

ARM架构是一种广泛应用于移动设备、嵌入式系统和物联网设备中的处理器架构。在运行在ARM处理器上的设备或系统上选择合适的压缩算法，需要考虑算法的性能、资源消耗和适应性。
以下是一些适合与ARM跑的压缩算法：
Zstandard（Zstd）：Zstandard是一种快速的压缩算法，性能优秀，并且可以在ARM处理器上高效运行。它具有适应性强，可以在不同的场景下应用，如数据传输、数据库压缩等。
LZ4：LZ4是一种高速压缩算法，适合于需要快速压缩和解压的场景。它具有低延迟和高吞吐量的特点，适合在ARM处理器上运行。LZ4是一种LZ系列压缩算法，着重于压缩和解压的速度，压缩率相对较低。LZ4压缩率较低，算法复杂度和内存消耗中等，但是压缩和解压速度，尤其是解压速度远超其他算法。因为其综合性能优秀，在Linux、Android中的内存压缩技术一般使用LZ4压缩算法。LZ4 HC，有着更好的压缩率，但是算法复杂度大幅提升，且压缩速度也大幅减慢，但是依然有着很好的解
Brotli：Brotli是由Google开发的一种通用压缩算法，特点是高压缩率和较好的性能。它在文件传输、网络传输等场景下表现优异，也可以在ARM处理器上高效运行。
Snappy：Snappy是Google开发的一种快速压缩算法，适合于需要高速压缩和解压的场景。它在ARM处理器上表现优秀，适用于数据传输、日志压缩等应用。
Deflate（如zlib）：Deflate是一种常见的无损压缩算法，广泛应用于各种领域。zlib是实现Deflate算法的一个流行库，也可以在ARM处理器上使用，并具有较好的性能。
这些压缩算法在ARM处理器上都有良好的性能表现，可以根据具体的应用场景和需求选择合适的算法。值得注意的是，优化算法的实现、调整参数和选择合适的压缩级别，也可以进一步提高在ARM处理器上的性能表现。
Huffman霍夫曼(Huffman)编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。霍夫曼编码使用的编码表，使用霍夫曼树来进行存储，让出现概率最高的编码最容易查找，以提升解码速度。霍夫曼编码算法的压缩率分布在20%-90%，因为要扫描整个数据来构建霍夫曼树，所以其压缩速度较慢，且需要一定的内存来存储编码表，但是解压速度较快。霍夫曼的算法复杂度较简单。
RLE(Run Length Encoding)，也称为行程编码，压缩算法是一种无损压缩算法。算法特点：简单、易实现。使用RLE压缩方法可以将 RRRRRGGBBBBBBABCD 压缩为 5R2G6B1A1B1C1D。基于RLE算法升级，可以将RRRRRGGBBBBBBABCD可以压缩为b’\x85R\x82G\x86B\x03ABCD’，0x85表示后面有5个相同的字符，0x03表示后面有3个不连续的字符。RLE的实现非常简单，针对一些图片颜色少或重复字符多的文件有非常好的压缩率，RLE的适用场景比较少，通用压缩率较差。
LZ77是一种基于字典的算法，它将长字符串（也称为短语）编码成短小的标记，用小标记代替字典中的短语，从而达到压缩的目的。LZ77算法的压缩率、速度、内存消费都是中等，但是代码复杂度较低，适用于MCU的使用。
LZO压缩算法采用(重复长度L，指回距离D)代替当前已经在历史字符串中出现过的字符串。LZO致力于解压速度，不同的参数下的LZO压缩率不同。LZO内存消耗中等，解压速度较快，压缩速度较快，但是代码复杂度较低，适用于Bootloader等追求压缩率和解压速度的场景。

4性能排序

在实际应用中，不同的压缩算法因为适用场景、数据类型、硬件平台等因素的不同，其性能表现也会有所差异。以下是一些常见的压缩算法按照一般趋势的性能排序：
压缩率（从高到低）：
有损压缩：JPEG2000 > WebP > H.265 (HEVC) > H.264 (AVC) > JPEG
无损压缩：FLIF > Brotli > Zstandard > LZMA (7-Zip) > DEFLATE (zlib)
压缩速度（从快到慢）：
Snappy > LZ4 > Zstandard > Deflate (zlib) > Brotli
这里的快慢仅作为一般参考，具体情况因数据大小、数据类型、硬件性能等因素可能有所不同。
解压速度（从快到慢）：
Snappy > LZ4 > Zstandard > Deflate (zlib) > Brotli
同样，解压速度也会受到实际场景的影响，不同算法适用于不同的应用需求。
内存消耗（从少到多）：
Snappy > LZ4 > Zstandard > Deflate (zlib) > Brotli
内存消耗较低的压缩算法可以在受限制的环境下更好地工作，如嵌入式设备等。

5 压缩算法代码示例

以下是一个简单的使用zlib库进行数据压缩和解压缩的C语言示例代码：


```c```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <zlib.h>#define CHUNK 16384int compress_data(unsigned char* data, int data_len, unsigned char* compressed_data, int* compressed_len) {z_stream strm;strm.zalloc = Z_NULL;strm.zfree = Z_NULL;strm.opaque = Z_NULL;if(deflateInit(&strm, Z_BEST_COMPRESSION) != Z_OK) {return -1;}strm.avail_in = data_len;strm.next_in = data;strm.avail_out = *compressed_len;strm.next_out = compressed_data;int ret = deflate(&strm, Z_FINISH);*compressed_len = strm.total_out;deflateEnd(&strm);return ret == Z_STREAM_END ? 0 : -1;
}int decompress_data(unsigned char* compressed_data, int compressed_len, unsigned char* decompressed_data, int* decompressed_len) {z_stream strm;strm.zalloc = Z_NULL;strm.zfree = Z_NULL;strm.opaque = Z_NULL;if(inflateInit(&strm) != Z_OK) {return -1;}strm.avail_in = compressed_len;strm.next_in = compressed_data;strm.avail_out = *decompressed_len;strm.next_out = decompressed_data;int ret = inflate(&strm, Z_NO_FLUSH);*decompressed_len = strm.total_out;inflateEnd(&strm);return ret == Z_STREAM_END ? 0 : -1;
}int main() {unsigned char data[] = "Hello, this is a test message!";int data_len = strlen(data);int compressed_size = compressBound(data_len);unsigned char compressed_data[compressed_size];int compressed_len = compressed_size;if(compress_data(data, data_len, compressed_data, &compressed_len) == 0) {printf("Data compressed successfully!\n");printf("Compressed data size: %d\n", compressed_len);unsigned char decompressed_data[data_len];int decompressed_len = data_len;if(decompress_data(compressed_data, compressed_len, decompressed_data, &decompressed_len) == 0) {printf("Data decompressed successfully!\n");printf("Decompressed data: %s\n", decompressed_data);} else {printf("Error decompressing data!\n");}} else {printf("Error compressing data!\n");}return 0;
}

在这个示例代码中，我们使用了zlib库提供的函数进行数据压缩和解压缩操作。压缩函数 compress_data 将输入数据进行压缩，并将压缩后的数据存储在 compressed_data 中，返回压缩后的数据长度；解压缩函数 decompress_data 对压缩后的数据进行解压缩，并将解压缩后的数据存储在 decompressed_data 中，返回解压缩后的数据长度。在主函数中，我们对一个简单的字符串进行压缩和解压缩操作，并输出结果。

请注意，这段示例代码使用了zlib库，因此在编译时需要链接zlib库。在Linux系统下，可以使用 -lz 选项进行链接。

以下是一个简单的C语言示例代码，实现了Huffman算法进行数据压缩和解压缩的功能：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_TREE_HT 100// 结点结构体
typedef struct MinHeapNode {char data;unsigned freq;struct MinHeapNode *left, *right;
} MinHeapNode;// 最小堆结构体
typedef struct MinHeap {unsigned size;unsigned capacity;MinHeapNode **array;
} MinHeap;// 创建新结点
MinHeapNode* newNode(char data, unsigned freq) {MinHeapNode* node = (MinHeapNode*)malloc(sizeof(MinHeapNode));node->left = node->right = NULL;node->data = data;node->freq = freq;return node;
}// 创建最小堆
MinHeap* createMinHeap(unsigned capacity) {MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (MinHeapNode**)malloc(minHeap->capacity * sizeof(MinHeapNode*));return minHeap;
}// 交换两个结点
void swapMinHeapNodes(MinHeapNode** a, MinHeapNode** b) {MinHeapNode* t = *a;*a = *b;*b = t;
}// 最小堆调整
void minHeapify(MinHeap* minHeap, int idx) {int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)smallest = left;if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)smallest = right;if (smallest != idx) {swapMinHeapNodes(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 获取最小结点
MinHeapNode* extractMin(MinHeap* minHeap) {MinHeapNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入结点
void insertMinHeap(MinHeap* minHeap, MinHeapNode* minHeapNode) {++minHeap->size;int i = minHeap->size - 1;while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = minHeapNode;
}// 创建和构建最小堆
MinHeap* buildMinHeap(char data[], int freq[], int size) {MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;for (int i = size / 2 - 1; i >= 0; --i)minHeapify(minHeap, i);return minHeap;
}// 检查结点是否是叶子结点
int isLeaf(MinHeapNode* root) {return !(root->left) && !(root->right);
}// 构建霍夫曼树
MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {MinHeapNode *left, *right, *top;MinHeap* minHeap = buildMinHeap(data, freq, size);while (minHeap->size != 1) {left = extractMin(minHeap);right = extractMin(minHeap);top = newNode('$', left->freq + right->freq);top->left = left;top->right = right;insertMinHeap(minHeap, top);}return extractMin(minHeap);
}// 打印霍夫曼编码
void printCodes(MinHeapNode* root, int arr[], int top) {if (root->left) {arr[top] = 0;printCodes(root->left, arr, top + 1);}if (root->right) {arr[top] = 1;printCodes(root->right, arr, top + 1);}if (isLeaf(root)) {printf("%c: ", root->data);for (int i = 0; i < top; ++i)printf("%d", arr[i]);printf("\n");}
}// 压缩数据
void huffmanCompression(char data[]) {int freq[256] = {0};int n = strlen(data);for (int i = 0; i < n; ++i)++freq[data[i]];char arr[256];int freq2[256];int size = 0;for (int i = 0; i < 256; ++i) {if (freq[i] != 0) {arr[size] = (char)i;freq2[size] = freq[i];++size;}}MinHeapNode* root = buildHuffmanTree(arr, freq2, size);int arr2[MAX_TREE_HT], top = 0;printCodes(root, arr2, top);
}int main() {char data[] = "hello world";huffmanCompression(data);return 0;
}

这个示例代码演示了使用Huffman算法对输入的数据进行压缩，并打印出各个字符的Huffman编码。huffmanCompression 函数首先统计输入数据中每个字符的出现频率，并构建Huffman树，然后通过递归遍历Huffman树获取每个字符的Huffman编码并打印出来。在 main 函数中，我们对一个简单的字符串进行了压缩，并输出了每个字符的Huffman编码。

需要注意的是，这个示例代码仅演示了Huffman算法的基本压缩原理，实际应用中可能需要对数据内容、编码方式等进行更多处理和优化。

以下是一个简单的C语言示例代码，实现了Huffman算法进行数据解压缩的功能：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 结点结构体
typedef struct MinHeapNode {char data;struct MinHeapNode *left, *right;
} MinHeapNode;// 解压缩数据
void huffmanDecompression(char data[], MinHeapNode* root) {int n = strlen(data);MinHeapNode* current = root;for (int i = 0; i < n; ++i) {if (data[i] == '0') {current = current->left;} else {current = current->right;}if (current->left == NULL && current->right == NULL) {printf("%c", current->data);current = root;}}
}int main() {// 构造Huffman树MinHeapNode *root = (MinHeapNode*)malloc(sizeof(MinHeapNode));root->left = root->right = NULL;MinHeapNode *A = (MinHeapNode*)malloc(sizeof(MinHeapNode));A->data = 'A';A->left = A->right = NULL;MinHeapNode *B = (MinHeapNode*)malloc(sizeof(MinHeapNode));B->data = 'B';B->left = B->right = NULL;MinHeapNode *C = (MinHeapNode*)malloc(sizeof(MinHeapNode));C->data = 'C';C->left = C->right = NULL;root->left = A;root->right = B;A->left = C;A->right = NULL;B->left = B->right = NULL;C->left = C->right = NULL;// 待解压缩的数据char data[] = "00100110001";// 解压缩数据huffmanDecompression(data, root);return 0;
}

在这个简单的示例代码中，我们首先构建了一个简单的Huffman树，然后定义了一个待解压缩的数据字符串。huffmanDecompression 函数接受压缩后的数据和Huffman树的根结点作为参数，通过逐位解析压缩后的数据，按照Huffman树逐步走到叶子结点，从而解压缩出原始数据并打印。

在 main 函数中，我们构造了一个简单的Huffman树，并指定了一个简单的待解压缩的数据字符串，然后调用 huffmanDecompression 函数进行解压缩操作。解压缩过程中，输出的字符序列应该是根据Huffman树进行解码后的原始数据。

需要注意的是，这个示例代码中的Huffman树和待解压缩的数据都是固定的，实际应用中可能需要根据具体的压缩数据和Huffman树结构进行相应的解压缩处理。

这篇关于压缩算法简介的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1084561。

相关文章

ASIO网络调试助手之一：简介

ASIO网络调试助手之一：简介

多年前，写过几篇《Boost.Asio C++网络编程》的学习文章，一直没机会实践。最近项目中用到了Asio，于是抽空写了个网络调试助手。 开发环境： Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议： UDP + TCP Client + TCP Server 独立的Asio（http://www.think-async.com）只包含了头文件，不依
阅读更多...
业务协同平台--简介

业务协同平台--简介

一、使用场景         1.多个系统统一在业务协同平台定义协同策略，由业务协同平台代替人工完成一系列的单据录入         2.同时业务协同平台将执行任务推送给pda、pad等执行终端，通知各人员、设备进行作业执行         3.作业过程中，可设置完成时间预警、作业节点通知，时刻了解作业进程         4.做完再给你做过程分析，给出优化建议         就问你这一套下
阅读更多...
容器编排平台Kubernetes简介

容器编排平台Kubernetes简介

目录 什么是K8s 为什么需要K8s 什么是容器(Contianer) K8s能做什么？ K8s的架构原理  控制平面(Control plane)         kube-apiserver         etcd         kube-scheduler         kube-controller-manager         cloud-controlle
阅读更多...
【Tools】AutoML简介

【Tools】AutoML简介

摇来摇去摇碎点点的金黄 伸手牵来一片梦的霞光 南方的小巷推开多情的门窗 年轻和我们歌唱 摇来摇去摇着温柔的阳光 轻轻托起一件梦的衣裳 古老的都市每天都改变模样                      🎵 方芳《摇太阳》 AutoML（自动机器学习）是一种使用机器学习技术来自动化机器学习任务的方法。在大模型中的AutoML是指在大型数据集上使用自动化机器学习技术进行模型训练和优化。
阅读更多...
SaaS、PaaS、IaaS简介

SaaS、PaaS、IaaS简介

云计算、云服务、云平台……现在“云”已成了一个家喻户晓的概念，但PaaS, IaaS 和SaaS的区别估计还没有那么多的人分得清，下面就分别向大家普及一下它们的基本概念： SaaS 软件即服务 SaaS是Software-as-a-Service的简称，意思是软件即服务。随着互联网技术的发展和应用软件的成熟， 在21世纪开始兴起的一种完全创新的软件应用模式。 它是一种通过Internet提供
阅读更多...
LIBSVM简介

LIBSVM简介

LIBSVM简介 支持向量机所涉及到的数学知识对一般的化学研究者来说是比较难的，自己编程实现该算法难度就更大了。但是现在的网络资源非常发达，而且国际上的科学研究者把他们的研究成果已经放在网络上，免费提供给用于研究目的，这样方便大多数的研究者，不必要花费大量的时间理解SVM算法的深奥数学原理和计算机程序设计。目前有关SVM计算的相关软件有很多，如LIBSVM、mySVM、SVMLight等，这些
阅读更多...
urllib与requests爬虫简介

urllib与requests爬虫简介

urllib与requests爬虫简介 – 潘登同学的爬虫笔记 文章目录 urllib与requests爬虫简介 -- 潘登同学的爬虫笔记第一个爬虫程序 urllib的基本使用Request对象的使用urllib发送get请求实战-喜马拉雅网站 urllib发送post请求 动态页面获取数据请求 SSL证书验证伪装自己的爬虫-请求头 urllib的底层原理伪装自己的爬虫-设置代理爬虫coo
阅读更多...
新一代车载(E/E)架构下的中央计算载体---HPC软件架构简介

新一代车载(E/E)架构下的中央计算载体---HPC软件架构简介

老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 屏蔽力是信息过载时代一个人的特殊竞争力，任何消耗你的人和事，多看一眼都是你的不对。非必要不费力证明自己，无利益不试图说服别人，是精神上的节能减排。 无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事.而不是让内心的烦躁、焦虑、毁掉你本就不多的热情和定力。 时间不知不觉中，快要来到夏末秋初。一年又过去了一大半，成
阅读更多...
AI学习指南深度学习篇-带动量的随机梯度下降法简介

AI学习指南深度学习篇-带动量的随机梯度下降法简介

AI学习指南深度学习篇 - 带动量的随机梯度下降法简介 引言 在深度学习的广阔领域中，优化算法扮演着至关重要的角色。它们不仅决定了模型训练的效率，还直接影响到模型的最终表现之一。随着神经网络模型的不断深化和复杂化，传统的优化算法在许多领域逐渐暴露出其不足之处。带动量的随机梯度下降法（Momentum SGD）应运而生，并被广泛应用于各类深度学习模型中。 在本篇文章中，我们将深入探讨带动量的随
阅读更多...
OpenGL ES学习总结：基础知识简介

OpenGL ES学习总结：基础知识简介

什么是OpenGL ES? OpenGL ES (为OpenGL for Embedded System的缩写） 为适用于嵌入式系统的一个免费二维和三维图形库。 为桌面版本OpenGL 的一个子集。 OpenGL ES管道(Pipeline) OpenGL ES 1.x 的工序是固定的，称为Fix-Function Pipeline,可以想象一个带有很多控制开关的机器，尽管加工
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2