内存压缩算法

Ⅰ 如何将图片压缩到30K以下

电脑上的画图就可以，步骤如下：

1、将电子版的图片放在桌面上，鼠标放在上面可以看见图片大小。

Ⅱ 压缩内存是什么意思 压缩了有什么好处

摘要：介绍内存压缩技术和一个基于硬件的内存压缩系统模型，探讨内存压缩技术在嵌入式系统中的应用；重点介绍内存压缩系统的硬件要求及操作系统对内存压缩机制的支持；简单介绍内存压缩中常用的算法Lempel-Ziv，并就内存压缩技术在嵌入式系统中的应用问题作一些探讨。
关键词：嵌入式系统 内存压缩 压缩内存控制器 Lempel-Ziv算法

1 内存压缩技术介绍

为节省存储空间或传输带宽，人们已经在计算机系统中广泛地使用了数据压缩技术。在磁介质存储数据或网络传输数据时，人们使用基于硬件或软件的各种压缩技术。当压缩技术在各个领域都很流行时，内存压缩技术却由于其复杂性而一直未得到广泛使用。近年来，由于在并行压缩一解压算法以及在硅密度及速度方面取得的进展，使得内存压缩技术变得可行。

内存压缩技术的主要思想是将数据按照一定的算法压缩后存入压缩内存中，系统从压缩内存中找到压缩过的数据，将其解压后即可以供系统使用。这样既可以增加实际可用的内存空间，又可以减少页面置换所带来的开销，从而以较小的成本提高系统的整体性能。

内存压缩机制是在系统的存储层次中逻辑地加入一层——压缩内存层。系统在该层中以压缩的格式保存物理页面，当页面再次被系统引用时，解压该压缩页后，即可使用。我们将管理这一压缩内存层的相关硬件及软件的集合统称为内存压缩系统。内存压缩系统对于CPU、I/O设备、设备驱动以及应用软件来说是透明的，但是操作系统必须具有管理内存大小变化以及压缩比率变化的功能。

对于大多数的操作系统而言，要实现内存压缩，大部分体系结构都不需要改动。在标准的操作系统中，内存都是通过固定数目的物理页框（page frame）来描述的，由操作系统的VMM来管理。要支持内存压缩，OS要管理的实际内存大小和页框数目是基于内存的压缩比率来确定的。这里的实现内存是指操作系统可的内存大小，它与物理内存的关系如下：假设PM是物理内存，RM（t）是系统在t时刻的实际内存，而CR（t）是压缩比率，在给定时刻t可支持的最大实际内存为RM（t）=CR1（t）×PM。然而，由于应用程序的数据压缩率是不依赖于OS而动态变化的，未压缩的数据可能会耗尽物理内存，因此当物理内存接近耗尽时，操作系统必须采取行动来解决这个问题。

2 内存压缩系统的硬件模型

目前由于内存压缩的思想越来越引起人们的注意市场上也出现了一些基于软件的内存压缩器。这些内存压缩器主要是通过软件对数据进行压缩，但由于访问压缩数据带来的延迟，它在系统性能方面改进并不明显，有些甚至降低了系统性能。本节介绍一种基于硬件的内存压缩系统模型。

图1是一个典型的内存压缩系统的硬件模型，包括了压缩内存、L3高速缓冲、压缩内存控制器等硬件部分。

其中压缩内存（133MHz SDRAM）包含了压缩数据。L3高速缓冲是一个共享的、32MB、4路组相联、可回写的高速缓冲，每行大小为1KB，由两倍数据率（DDR）SDRAM制定。L3高速缓冲包含了未压缩的缓冲行，由于大部分的访问都可以在L3高速缓冲中命中，因此它隐藏了访问压缩主存引起的延迟。L3高速缓冲对于存储分级体系中的上层而言就是主存，它的操作对于其它硬件，包括处理器和I/O来说都是透明的。压缩内存控制器是整个内存压缩系统的控制中心，它负责数据的压缩/解压，监控物理内存的使用情况以及实际地址到物理地址的寻址过程。

数据压缩过程是这样的：压缩内存控制将1KB的高速缓冲行压缩后写入压缩内存中，然后将它们从压缩内存中读出后解压。其压缩算法就是Lempel-Ziv算法，我们会在下一部分介绍这个算法。压缩机制将压缩的数据块以不同的长度格式存放到内存中。压缩内存的存储单元是一个256字节的区域。按照压缩比率不同，一个1KB的内存块（正好是L3每行的大小）可以占据0～4个压缩区域。

压缩内存控制器必须根据长度格式的不同将系统总线上的实际地址翻译成物理内存的中的物理地址。实际地址是出现在处理器外部总线上常规地址。篁 址用来录十压缩内存的256字节区域。实际地址空间存在于L1/L2/L3高速缓冲中，用于立即访问。而其余的内存内容部分以压缩形式存在于物理内存中。内存控制器通过查询压缩翻译表（CTT）执行从实际地址到物理地址的翻译，这个表被保留在物理内存的某个位置。图2是CTT表的格式及内存控制器的寻址模式。

每个1KB内存块的实际地址映射到CTT的一项，而CTT每项共16字节，包括四个物理区域地址，每个地址指向物理内存听一个256字节区域。对于少于120位的块，如一个全为零的块，则使用一种特殊的CTT格式，称为通用行格式。在这种格式中，压缩数据全部存放在CTT项中，代替了四个地址指针。因此，一个1KB的通用块仅占用物理内存中的16字节，其压缩比率达到64：1。

压缩内存控制器中有一系列的寄存器用于监控物理内存使用。Sectors Used Register(SUR)向操作系统报告压缩内存的使用情况。The Sectors Used Threshold Registers,SUTHR和SUTLR，用于设置内存耗尽情况的中断入口点。SUTLR寄存器是PCI中断电路INTA的入口，而SUTHR寄存器是NMI中断的入口。当SUR超过了SUTLR的值，内存控制器产生一个中断，则操作系统采取措施来阻止内存消耗。

在实际地址到物理地址的转换中，一个有用的方法是快速页操作。它允许控制器仅修改CTT项的四个指针，从而将4KB的页面内容换出或清空。快速页操作通过将与4KB页面相关的CTT项全部修改通用行格式（即全为零），从而将这4KB页面的内容全部清空。同样，一对页面可以通过交换它们相关的CTT项的区域指针来交换页面内容。由于没有大量的数据移动发生，快速页面操作速度相当快。

压缩内存控制器的压缩/解压功能是基于LempelZiv算法来进行的，因此下一节将简单介绍一下该算法的思想。

3 内存压缩算法Lempel-Ziv

绝大多数的压缩算法，包括用得特别流行的Lempel-Ziv压缩算法家庭，都是基于对原子记录（Token）字符串的完全重复检测。这个算法虽然不是最好的算法，但是，Lempel-Ziv算法强调的是算法的简单与取得高压缩率的速率，因此它还是在内存压缩中得到了广泛的应用。

Lemple-Ziv算法（简称LZ）是编码时将一个位串分成词组，然后将数据流描述成一系列的对。每个对组成一个新的词组，它包含一个数字（前一个词组的标识）和一个位（被附加到前一个词组上）。这种编码方式很庞大，可是一旦应用到适合的字符串，它就是相当有效率的编码方式。下面举例说明这种算法是如何编码的。

++表示连接（010++1=0101），U=0010001101是未被压缩的字符串。C是压缩后的字符串。P（x）表示词组数x。先看一下U=0010001101发现，它可以被写为U=0++010001101，因此得到P（1）=P(0)++0。现在继续将其写为U=0++02++0001101，可得到P(2)=P（1）++1。现在我们已经将P（2）描述为上一词组和一个新的位的组合。下一步，U=0++01++00++01101，并得到P（3）=P（1）++0。现在我们注意到，有U=0++01+00+011++01，而P（4）=011=P(2)++1，最后得到P（5）=P(1)++1。运算的步骤如表1所列。

一旦创建了表1，就有了整个编码的图表。要创建Lempel-Ziv数据流，则依照公式创建对。如果公式是P(x)=P(A)++B，则每个对为（A++B）。因此P（1）=P(0)++0变为（00++0），P（2）=P(1)++0变为（01++0），依此类推，将所有这些对连接起来，就得到了最后的字符串，结果如表2所列。这样，C就变成000011010101011，看来比U要长得多。但这里由于U的长度短，因此未能看出优势，而且包含P（0）的公式都没有压缩，所以也引起了长度增加。

Lempel-Ziv字符串的解码是很简单的，就是抓住其中的对，对照表1进行重构。

表1 编码过程

步 骤 值 公 式 U

0 - P(0) 0010001101
1 0 P(1)=P(0)++0 0++010001101
2 01 P(2)=P(1)++1 0++01++00++01101
3 00 P(3)=P(1)++0 0++01++00++01101
4 011 P(4)=P(2)++1 0++01++00++011++01
5 01 P(5)=P(1)++1 0++01++00++011++01

表2 如何创建编码字符串

公 式 P(1)=P(0)++0 P(2)=P(1)++1 P(3)=P(1)++0 P(4)=P(2)++1 P(5)=P(1)++1
对 00++0=000 01++1=011 01++0=010 10=++1=101 01++1=011
C
000++011++010++101++011=000011010101011

4 操作系统对内存压缩的支持

在压缩内存系统中，内存大小指的是实际内存大小，它比物理内存大。在引导时，BIOS向操作系统报告的内存大小就比实际安装的物理内存要大。例如，硬件原型安装的是512MB的SDRAM，但BIOS向操作系统报告的内存大小为1GB。当应用程序数据以2：1或更高的比率压缩时，实际内存的工作方式与一般操作系统的内存工作方式是相同的。但当应用程序以未压缩数据来填充内存时（如一个zip文件不可能达到2：1的压缩比率），由于一般的OS只看到实际地址空间，因此不能意识到物理内存已经耗尽。例如，一个操作系统的实际内存为1024MB，而牧师内存为512MB。这时实际内存已经分配了600MB，系统显示还有424MB的空闲内存。但是由于已分配内存的压缩率很低，此时物理内存的耗用已经接近512MB。如果再近一步地分配内存，那么系统就会因为物理内存的耗尽而崩溃，尽管它仍然显示还有424MB的空闲内存。这种情况下，必须由操作系统提供对压缩内存进行管理的支持。

由于内存压缩是一个比较新的概念，一般的情况作系统都没有这样的机制来区分实际地址和物理地址，也不能处理“物理内存耗尽”的情况。不过，只要对操作系统内核做一些小的改动或者在操作系统之上增加一个设备驱动程序，即可达到目的。

一般来说，要从以下几方面对压缩内存进行管理。

（1）监控物理内存使用情况

通过轮询或中断法，查看物理内存的使用情况，并在物理内存耗尽前给出警告。压缩内存管理例程是通过压缩内存控制器中的一些寄存器来实现对物理内存的监控。SUR报告物理内存的使用情况，SUTHR和SUTLR用于设置中断临界值。压缩内存管理算法是基于物理内存使用的四种状态，分别为steady、acquire、danger和interrupt，其临界值的关系是mc_th_acquire<mc_th_danger<mc_th_interrupt。

我们可以使用轮询和中断相结合的方法进行监控，并对物理内存使用的变化作出反应。通过时钟中断来驱动轮例程，该例程每10ms读取一次SUR的值，并将它与系统设定的临界值比较。当系统处于steady状态时，不用采取任何行动；当使用超过mc_th_acquire，应该增加nr_rsrv_pages来限制内存分配，但这并未引起内存缺乏；当使用超过mc_th_danger，应该增加nr_rsrv_pages到引起内存缺乏，并导致页面分配器和置换进程回收内存页面，一旦进入到该状态，物理内存管理例程会唤醒置换进程回收内存。

（2）回收内存以及清空空闲页面内容以减少使用

以标准的Linux内核为例，操作系统中有两具主要的变量来管理内存太少的情形。这两个变量是nr_free_pages和struct freepages。为了检测内存是否已耗尽，在分配内存前要进行检查。

if(nr_free_pages<freepages.min){

/*内存太少，回收页面*/

}

else

{/*可以进行分配*/

在内存压缩系统中，通过增加一个新变量nr_rsrv_pages来完成此功能。这样就使最小空闲页面数量变为：freepages.min"=freepages.min+nr_rsrv_pages。

通过动态地调整nr_rsrv_pages变量，压缩内存管理例程可以人为地造成内存缺乏的现象，从而引起置换进程回收页面，此时会将调用进程暂时挂起。回收内存包含缩减各种缓冲，并将进程页面置换到磁盘上。当页面返回到空闲页面池时，它们会被清零。我们可以使用前面提到的快速页面操作来减少清空页面操作所带来的开销。

（3）阻塞CPU周期以减少物理内存使用率

当物理内存使用超过监界值mc_th_interrupt，控制器就中断处理器，nr_rsrv_pages进一步增加，然后CPU blocker就开始运行。我们在轮询机制的基础上还使用了中断机制，因为中断机制比轮询机制更加快速。如果在10ms的间隔中，物理内存使用突然上升，硬件中断会比轮询例程更早检测到这一情况。为了更加安全，我们使用CPUblocker来阻塞引起物理内存使用的进程。CPU blocker是空闲线程，它们可以使CPU空忙。由于页面被置换到磁盘是以机器速度运行的，而物理内存使用却可以以内存访问速度运行，速度从而得到增加。当牧师内存使用持续增加，以至换页也无法缓解时，进程需要被阻塞。我们就通过启动CPUblocker来阻塞CPU周期直到换页机制能有效地降低物理内存使用。CPUblocker不会阻塞中断，而且每40ms它就会让出CPU以免其它进程被饿死。

5 内存压缩技术在嵌入式系统中的应用

嵌入式系统是一种特殊的计算机系统，它是一个更大的系统或设备的一部分。通常，一个嵌入式系统是驻留在单处理机底板上的，其应用程序存储在ROM中。事实上，所有具有数字接口的设备——监视器、微波炉、VCRs、汽车等，都使用了嵌入式系统。一些嵌入式系统包含了操作系统，称为嵌入式操作系统。为了满足嵌入式应用的特殊要求，嵌入式微处理器虽然在功能上和标准微处理器基本是一样的，但和工业控制计算机相比，嵌入式微处理器具有体积小、重量轻、成本低、可靠性中，内存仍然是珍贵的资源，因此研究内存压缩技术在嵌入式系统中的应用具有一定的价值。

内存压缩的思想在一些嵌入式操作系统中，实际上已经得到了体现。例如在VxWorks中，当操作系统下载到目标机上时，其中一种方式是将引导程序和VxWorks映像都存放在ROM中。为了将其解压后再从ROM拷贝到RAM。这种基于软件的压缩方式，可以节省ROM空间，但其引导过程相对较慢。

以上的内存压缩技术在ROM中得到了应用，但对于RAM来讲，基于软件内存压缩技术，由于其访问压缩数据可能造成的延迟和不确定性，会对嵌入式系统的实时性造成和。因此它与虚拟内存技术一样，在嵌入式系统中未得到广泛应用。

本文所介绍的内存压缩系统是基于硬件的。在相同基准下，测试结果显示出，该系统的运行速度比标准系统的运行速度快1.3倍。如果要实现相同大小的内存，采用内存压缩系统的硬件费用比购买RAM的费用要低，而且内存越大，其节省的费用越多，可以达到一半的价钱。因此笔者认为在内存资源极其宝贵的嵌入式系统中，实现基于硬件的内存压缩系统具有较大的价值。

结语

本文介绍的内存压缩系统是基于专门的硬件支持，即L3高速缓冲和内存控制器。在目前大多数Pentium以上架构的硬件平台上，只需要对操作系统内核做一些小的屐，或者增加一个设备驱动及服务程序，即可完成此项功能。由于嵌入式系统对实时性的要求，基于硬件的内存压缩技术可以在增大可用内存的同时不影响系统的实时性，其硬件费用相对RAM的价格更低，具有一定的实用价值。

Ⅲ 压缩文件的运行原理

有损压缩和无损压缩。 如果您从互联网上下载了许多程序和文件，可能会遇到很多ZIP文件。这种压缩机制是一种很方便的发明，尤其是对网络用户，因为它可以减小文件中的比特和字节总数，猜桐使文件能够通过较慢的互联网连接实现更快传输，此外还可以减少文件的磁盘占用空间。在下载了文件后，计算机可使用WinZip或Stuffit这样的程序来展开文件，将其复原到原始大小。如果一切正常，展开的文件与压缩前的原桐档始文件将完全相同。
乍一听好像很神秘：您是怎样减少比特和字节的数量并将它们原封不动地还原回去的呢？等一切水落石出之后，您会发现这个过程背后的基本理念其实非常简单明了。在本文中，我们将讨论这种通过简单压缩来明显减小文件的方法。
大多数计算机文件类型都包含相当多的冗余内容——它们会反复列出一些相同的信息。文件压缩程序就是要消除这种冗余现象。与反复列出某一块信息不同，文件压缩程序只列出该信息一次，然后当它在原始程序中出现时再重新引用它。
以我们熟悉的信息类型——单词——为例子。
肯尼迪（John F. Kennedy）在1961年的就职演说中曾说过下面这段着名的话：
Ask not what your country can do for you——ask what you can do for your country.（不要问国家能为你做些什么，而应该问自己能为国家做些什么。）
这段话有17个单词，包含61个字母、16个空格、1个破折号和1个句点。如果每个字母、空格或标点都占用1个内存单元，那么文件的总大小为79个单元。为了减小文件的大小，我们需要找出冗余的部分。
我们立刻发现：
如果忽略大小写字母间的区别，这个句子几乎有一半是冗余的。九个单词（ask、not、what、your、country、can、do、for、you）几乎提供了组成整句话所需的所有东西。为了构造出另一半句子，我们只需要拿出前半段句子中的单词，然后加上空格和标点就行了。
大多数压缩程序使用基于自适应字典的LZ算法来缩小文件。“LZ”指的是此算法的发明者Lempel和Ziv，“字典”指的是对数据块进行归类的方法。
排列字典的机制有很多种，它也可以像编号列表那样简单。在我们检查肯尼迪这句着名讲话时，可以挑出重复的单词，并将它们放到编号索引中。然后，我们直接写入编号而不是写入整个单词。
因此，如果我们的字典是：
ask
what
your
country
can
do
for
you
我们的句子现在就应该是这样的：
1 not 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4
如果您了解这种机制，那么只需使用该字典和编号模式即可轻松重新构造出原始句子。这就是在展开某个下载文件时，计算机中的解压缩程序所做的工作。你可能还遇到过能够自行解压缩的压缩文件。若要创建这种文件，编程人员需要在被压缩的文件中设置一个简单的解压缩程序。在下载完毕后，它可以自动重新构造出原始文件。
但是使用这种机制究竟能够节省多少空间呢？“1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4”当然短于“Ask not what your country can do for you-- ask what you can do for your country.”，但应注意的是，我们需要随文件一起保存这个字典。
在实际压缩方案中，计算出各种文件需求是一个相当复杂的过程。让我们回过头考虑一下上面的例子。每个字符和空格都占用1个内存单元，整个原句要占用79个单元。压缩后的句子（包括空格）占用了37个单元，而字典（单词和编号）也占用了37个单元。也就是说，文件的大小为74个单元，因此我们并没有把文件大小减少很多。
但这只是一个句子的情况！可以想象的是，如果用该压缩程序处理完肯尼迪讲话的其余部分，我们会发现这些单词以及其他单词重复了更多次。而且，正如下一节所言，为了得到尽可能高的组织效率，可以对字典进行重写。
在上一个的例子中，我们挑出了所有重复的单词并将它们放在一个字典中。对于我们来说，这是最显而易见的字典编写方法。但是压缩程序却不这样认为：它对单词没有概念——它只会寻找各个模式。为了尽可能减小文件的大小，它会仔细挑选出最优模式。
如果从这穗轮坦个角度处理该句子，我们最终会得到一个完全不同的字典。
如果压缩程序扫描肯尼迪的这句话，它遇到的第一个冗余部分只有几个字母长。在ask not what your中，出现了一个重复的模式，即字母t后面跟一个空格——在not和what中。如果压缩程序将此模式写入字典，则每次出现“t”后面跟一个空格的情况时，它会写入一个“1”。但是在这个短句中，此模式的出现次数不够多，不足以将其保留为字典中的一个条目，因此程序最终会覆盖它。
程序接下来注意到的内容是ou，在your和country中都出现了它。如果这是一篇较长的文档，将此模式写入字典会节省大量空间——在英语中ou是一个十分常见的字母组合。但是在压缩程序看完整个句子后，它立即发现了一个更好的字典条目选择：不仅ou发生了重复，而且your和country整个单词都发生了重复，并且它们实际上是作为一个短语your country一起发生重复的。在本例中，程序会用your country条目覆盖掉字典中的ou条目。
短语can do for也发生了重复，一次后面跟着your，另一次跟着you，因此我们又发现can do for you也是一种重复模式。这样，我们可以用一个数字来代替15个字符（包含空格），而your country只允许我们用一个数字代替13个字符（包含空格），所以程序会用r country条目覆盖your country条目，然后再写入一个单独的can do for you条目。程序通过这种方式继续工作，挑出所有重复的信息，然后计算应该将哪一种模式写入字典。基于自适应字典的LZ算法中的“自适应”部分指的就是这种重写字典的能力。程序执行此工作的过程实际上非常复杂。
无论使用什么方法，这种深入搜索机制都能比仅仅挑出单词这种方法更有效率地对文件进行压缩。如果使用我们上面提取出的模式，然后用“__”代替空格，最终将得到下面这个更大的字典：
ask__
what__&shy;
you
r__country
__can__do__for__you
而句子则较短：
“1not__2345__--__12354”
句子现在占用18个内存单元，字典占用41个单元。所以，我们将文件总大小从79个单元压缩到了59个单元！这仅仅是压缩句子的一种方法，而且不一定是最高效的方法。（您能找到更好的方法吗?）
文件压缩率取决于多种因素，包括文件类型、文件大小和压缩方案。
在世界上的大多数语言中，某些字母和单词经常以相同的模式一起出现。正是由于这种高冗余性，而导致文本文件的压缩率会很高。通常大小合适的文本文件的压缩率可以达到50%或更高。大多数编程语言的冗余度也很高，因为它们的命令相对较少，并且命令经常采用一种设定的模式。对于包含大量不重复信息的文件（例如图像或MP3文件），则不能使用这种机制来获得很高的压缩率，因为它们不包含重复多次的模式。
如果文件有大量重复模式，那么压缩率通常会随着文件大小的增加而增加。从我们的例子中就可以看出这一点——如果我们摘录的肯尼迪讲话再长一些，您会发现又多次出现了我们字典中的模式，因此能够通过每个字典条目节省更多的文件空间。此外，对于更大的文件，还可能出现具有更大普遍性的模式，从而能够创建出效率更高的字典。
此外，文件压缩效率还取决于压缩程序使用的具体算法。有些程序能够在某些类型的文件中更好地寻找到模式，因此能更有效地压缩这些类型的文件。其他一些压缩程序在字典中又使用了字典，这使它们在压缩大文件时表现很好，但是在压缩较小的文件时效率不高。尽管这一类的所有压缩程序都基于同一个基本理念，但是它们的执行方式却各不相同。程序开发人员始终在尝试建立更好的压缩机制。 我们在上文中讨论的压缩类型称为无损压缩，因为您重新创建的文件与原始文件完全相同。所有无损压缩都基于这样一种理念：将文件变为“较小”的形式以利于传输或存储，并在另一方收到它后复原以便重新使用它。
有损压缩则与此大不相同。这些程序直接去除“不必要”的信息，对文件进行剪裁以使它变得更小。这种类型的压缩大量应用于减小位图图像的文件大小，因为位图图像的体积通常非常庞大。为了了解有损压缩的工作原理，让我们看看你的计算机如何对一张扫描的照片进行压缩。
对于此类文件，无损压缩程序的压缩率通常不高。尽管图片的大部分看起来都是相同的——例如，整个天空都是蓝色的——但是大部分像素之间都存在微小的差异。为了使图片变得更小同时不降低其分辨率，您必须更改某些像素的颜色值。如果图片中包含大量的蓝色天空，程序会挑选一种能够用于所有像素的蓝色。然后，程序重写该文件，所有天空像素的值都使用此信息。如果压缩方案选择得当，您不会注意到任何变化，但是文件大小会显着减小。
当然，对于有损压缩，在文件压缩后您无法将其复原成原始文件的样子。您必须接受压缩程序对原始文件的重新解释。因此，如果需要完全重现原来的内容（例如软件应用程序、数据库和总统就职演说），则不应该使用这种压缩形式。