精华内容
下载资源
问答
  • 简单实现LZ77压缩算法

    2020-01-07 16:18:43
    因为哈弗曼编码对于大文件的压缩有很大的局限性 且压缩比十分有限 所以决定根据LZ77算法写一个简单的压缩库 组成 因为时间较为紧张 目前完成了基础的ZIP算法的编写 即根据LZ77算法(滑动窗口压缩)先对压缩文件...

    引言

    因为哈弗曼编码对于大文件的压缩有很大的局限性 且压缩比十分有限 所以决定根据LZ77算法写一个简单的压缩库

    组成

    因为时间较为紧张 目前完成了最基础的ZIP算法的编写 即根据LZ77算法(滑动窗口压缩)先对压缩文件得到一个数据三元组 然后针对数字出现的频率再进行哈弗曼算法 为了更好的压缩比 我并没有先参考的资料中的方法 采用了建三棵哈弗曼树的做法

    效率

    对于一般的文件 压缩比可以达到百分之30到40
    对于重复性较高的文件 压缩比可以达到百分之10到20 甚至更低
    且克服了哈弗曼编码无法压缩大文件的缺点

    不足

    在计算数据三元组的时候使用了一个O(n2)的朴素匹配 使得效率比预想的更为不尽人意 改进之处可以参考LZ4算法 在匹配时使用哈希降低时间复杂度
    因为是压缩库 本来想再顺便写一个打包工具 但是时间临近期末 有点紧张 遂打算假期补上

    使用

    整体使用C++17编写 关键部分提供注释
    只需要把本文件夹放在您的项目中 然后包含"LZL-zip.h"即可

    //默认压缩名称为 xxx.LZL-zip
    g++ -std=c++17 test.cpp -o test
    

    这是源码的地址: https://github.com/Super-long/LZ-zip

    引用
    https://www.cnblogs.com/esingchan/p/3958962.html

    展开全文
  •  哈弗曼编码几乎是所有压缩算法的基础,其实这个算法并不复杂,简单的理解就是,如何用更短的bit来编码数据。  我们知道普通的编码都是定长的,比如常用的ASCII编码,每个字符都是8个bit: 字符 编码 ...
    
    
    2010年03月17日 |本网站遵守CC版权协议 转载请注明出自www.thecodeway.com

        哈弗曼编码几乎是所有压缩算法的基础,其实这个算法并不复杂,简单的理解就是,如何用更短的bit来编码数据
        我们知道普通的编码都是定长的,比如常用的ASCII编码,每个字符都是8个bit:

    字符 编码
    A 00101001
    B 00101010
    C 00101011

        这样,计算机就能很方便的把由0和1组成的数据流解析成原始信息,但我们知道,在很多情况下,数据文件中的字符出现的概率是不均匀的,比如在一篇英语文章中,字母“E”出现的频率最高,“Z”最低,如果我们使用不定长的bit编码,频率高的字母用比较短的编码表示,频率低的字母用长的编码表示,岂不是可以大大缩小文件的空间吗?
        但这就要求编码要符合“前缀编码”的要求,即较短的编码不能是任何较长的编码的前缀,这样解析的时候才不会混淆,比如下面的编码方法就符合前缀原则:

    字符 编码
    A 0
    B 10
    C 110
    D 1110
    E 11110

        根据这个码表,下面一段数据就可以唯一解析成原始信息了:
        1110010101110110111100010 – DABBDCEAAB

        要生成这种编码,最方便的就是用二叉树,考察一下下面这个树


        把要编码的字符放在二叉树的叶子上,所有的左节点是0,右节点是1,从根浏览到叶子上,因为字符只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径,符合前缀原则编码就可以得到

    字符 编码
    A 00
    B 010
    C 011
    D 10
    E 11

        现在我们可以开始考虑压缩的问题,如果有一篇只包含这五个字符的文章,而这几个字符的出现的次数如下:
        A: 6次
        B : 15次
        C: 2次
        D : 9次
        E: 1次
        用过用定长的编码,每个字符3bit,这篇文章总长度为:
        3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99
        而用上面用二叉树生成的编码,总长度为:
        2*6 + 3*15 + 2*2 + 2*9 + 2*1 = 80

        显然,这颗树还可以进一步优化,使得编码更短,比如下面的编码

        生成的数据长度为:
        3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

        可以看出,构造更优的二叉树,原则就是权重越大的叶子,距离根应该越近,而我们的终级目标是生成“最优”的二叉树,最优二叉树必须符合下面两个条件:

    1. 所有上层节点都大于等于下层节点。
    2. 某节点,设其较大的子节点为m,较小的子节点为n,m下的任一层的所有节点都应大于等于n下的该层的所有节点。

        上面这个例子是比较简单的,实际的文件中,一个字节有256种可能的取值,所以二叉树的叶子节点多达256个,最终的树形可能非常复杂,但有一种非常精巧的算法可以快速地建起一棵最优二叉树,这种算法由D.Huffman(戴?哈夫曼)提出,下面我们先来介绍哈弗曼算法的步骤,然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。
        哈夫曼算法的步骤是这样的:

    从各个节点中找出最小的两个节点,给它们建一个父节点,值为这两个节点之和。然后从节点序列中去除这两个节点,加入它们的父节点到序列中。重复上面两个步骤,直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了,它的根就是剩下的这个节点。

        比如上面的例子,哈弗曼树建立的过程如下:

        1) 列出原始的节点数据:

        2) 将最小的两个节点C和E结合起来:

        3) 再将新的节点和A组合起来

        4) 再将D节点加入

        5) 如此循环,最终得到一个最优二叉树

        生成的数据文件长度为:
        3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

        下面我们用逆推法来证明对于各种不同的节点序列,用哈弗曼算法建立起来的树总是一棵最优二叉树:

    • 当这个过程中的节点序列只有两个节点时(比如前例中的15和18),肯定是一棵最优二叉树,一个编码为0,另一个编码为1,无法再进一步优化。
    • 然后往前步进,节点序列中不断地减少一个节点,增加两个节点,在步进过程中将始终保持是一棵最优二叉树,这是因为:
      1. 按照哈弗曼树的建立过程,新增的两个节点是当前节点序列中最小的两个,其他的任何两个节点的父节点都大于(或等于)这两个节点的父节点,只要前一步是最优二叉树,其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层,所以这两个节点一定处在当前二叉树的最低一层。
      2. 这两个新增的节点是最小的,所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。
      3. 只要前一步是最优二叉树,由于这两个新增的节点是最小的,即使同层有其他节点,也无法和同层其他节点重新结合,产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点,它们又小于其他所有节点,只要前一步符合最优二叉树的第二个条件,到这一步仍将符合。

        这样一步步逆推下去,在这个过程中哈弗曼树每一步都始终保持着是一棵最优二叉树。

    展开全文
  • 它没有达到先进的压缩级别(每个三角形可能小于一点,并且为顶点预测提供了很好的机会),但它确实保持了三角形的排序并支持任意拓扑。 在某些情况下,三角形内的顶点会重新排序,但一般的缠绕方向会保持不变。 ...
  • 请找出热门10个检索串。 (2)有一个1G大小一个文件,里面每一行是一个词,词大小不超过16字节,内存限制大小是1M。返回频数最高100个词。 (3)有10个文件,每个文件1G,每个文件每一行存放都是用户...
  • 几种压缩算法的简单比较

    千次阅读 2006-12-13 22:18:00
    原始文件(二进制) : 427字节 WinRAR (zip最好) 291 WinRAR (rar最好) 235 Java.util.Zip 415 Java.util.Gzip 203由此可见 Gzip的压缩文件比RAR更小 
    原始文件(二进制) :    427字节
        WinRAR  (zip最好)         291
        WinRAR (rar最好)         235
        Java.util.Zip                   415
        Java.util.Gzip                 203


    由此可见 Gzip的压缩文件比RAR更小
     
    展开全文
  • RLE算法是最简单的压缩算法,作为学生党做作业不可避免的要去网上找RLE算法的代码,然而网上所有RLE压缩算法的代码都不好使,笔者在网上代码的基础上略加修改,使之粘贴即可使用。源码来自:...

    RLE算法是最简单的压缩算法,作为学生党做作业不可避免的要去网上找RLE算法的代码,然而网上所有RLE压缩算法的代码都不好使,笔者在网上代码的基础上略加修改,使之粘贴即可使用。

    源码来自:http://blog.csdn.net/calcular/article/details/46804919
    算法思想来自:http://blog.csdn.net/orbit/article/details/7062218
    感谢原作者。

    原代码的问题在于,当一个字符超过127次重复之后,编码会出现错误。原作者可能并没有用足够的样本去测试,导致这个bug的出现。

    废话不多说,先上代码。

    bool IsRepeat3(unsigned char *in, int rest)
    {
        if (rest<2) return false;
        else {
            if (*in == *(in + 1) && *in == *(in + 2)) return true;
            else return false;
        }
    }
    
    int GetNoRepeat3(unsigned char *in, int rest)
    {
        if (rest <= 2)
            return rest + 1;
        else {
            int c = 0,
                restc = rest;
            unsigned char *g = in;
            while (!IsRepeat3(g, restc))
            {
                g++;
                restc--;
                c++;
                if (c >= 128)
                    return c;
                if (restc == 0)
                    return c + 1;
    
            }
            return c;
        }
    }
    
    
    
    int Rle_Encode(unsigned char *inbuf, int insize, unsigned char *outbuf1, int outsize)
    {
        unsigned char *src = inbuf;
        unsigned char *outbuf = outbuf1;
        int rest = insize - 1;
        int outrest = outsize;
        int count = -1;
        int flag = 0;
        while (rest >= 0)
        {
            flag = 0;
            count = -1;
            if (IsRepeat3(src, rest))
            {
                while (rest >= 0)
                {
                    if (count == 127) break;
                    if (*src == *(src + 1)) {
                        rest--;
                        count++;
                        src++;
                    }
                    else {
                        count++;
                        if (count == 127) {
                            flag = 1;
                        }
                        break;
                    }
                }
                if (outrest<2)
                    return -1;
                *outbuf = count | 128;
                outbuf++;
                *outbuf = *src;
                outbuf++;
                outrest -= 2;
    
                if (count != 127||flag==1) {
                    src++;
                    rest--;
                }
    
            }
            else
            {
                if (IsRepeat3(src, rest))
                    continue;
                int num = GetNoRepeat3(src, rest);
                int i;
                if (outrest<(num + 1))
                    return -1;
                *outbuf = num-1;
                outbuf++;
                for (i = 0; i<num; i++) {
                    *outbuf = *(src + i);
                    outbuf++;
                }
                src += num;
                rest -= num;
                outrest -= num + 1;
            }
        }
        return outsize - outrest;
    }
    
    int Rle_Decode(unsigned char *inbuf, int insize, unsigned char *outbuf, int outsize)
    {
        int inrest = insize;
        int outrest = outsize;
        int i;
        unsigned char *in = inbuf;
        unsigned char *out = outbuf;
        int  ns;
        unsigned char tmp;
        while (inrest >= 0)
        {
            ns = *in+1;
            if (ns>129) {
                if ((outrest - ns + 128)<0)
                    return -1;
                tmp = *(in + 1);
                for (i = 0; i<ns - 128; i++) {
                    *out = tmp;
                    out++;
                }
                in += 2;
                inrest -= 2;
                outrest -= ns - 128;
    
            }
            else {
                if ((outrest - ns)<0)
                    return -1;
                in++;
                for (i = 0; i<ns; i++) {
                    *out = *in;
                    out++;
                    in++;
                }
                inrest -= 1 + ns;
                outrest -= ns;
            }
        }
        return outsize - outrest;
    }

    简单说下算法的原理。普通的RLE是把aabbccdd变成2a2b2c2d,这样当压缩abcd这样的数据时,不但压缩不了,还会产生冗余,所以我们需要高级点的RLE来解决这个问题。

    我们知道,RLE编码是由一个个length-code字节对组成的,我们这个算法,将length字节的最高位置为标志位,如标志位为1,说明后面的一个byte连续重复X次(aaaaa这样),反之标志位为0,说明后面的X个bytes中,相邻byte互不相同(abcd这种)。标志位的后7位,表示一个X-1的整数(显然,X最大为128),当标志位为1时,X的意义和普通的RLE是一样的,当标志位为0时,X表示接下来X个bytes中相邻byte互不相同。

    举例:aaaabcdefg
    首先是四个连续的a,所以X=4,X-1=3,标志位为1,故length字节应为1000 0011=0x83,code字节为a,至此我们有0x83 a。
    然后是6个相邻byte互不相同的字节,所以X=6,X-1=5,标志位为0,length字节为0x05,后面跟着6个bytes,bcdefg。至此,编码结束,结果为0x83 a 0x05 b c d e f g

    最坏的情况,此算法会带来1/128的冗余,即使如此,比普通RLE 100%的冗余还是好上不少的。

    展开全文
  • 在本文中分析了图象压缩冗余度原理,对LZ系列算法和LZW压缩算法的原理进行了全面深入分析研究,从中可以看到LZW算法有实现简单,通用性好,速度快,压缩效果好等特性,可以满足不同类型图像对无损压缩需要特点...
  • 无损压缩算法专题——RLE算法实现

    千次阅读 2020-01-04 23:16:29
    本文是基于我的另一篇博客《无损压缩算法专题——无损压缩算法介绍》的基础上来实现的,RLE算法最简单的理解就是用(重复数,数据值)这样一个标记来代替待压缩数据中的连续重复的数据,以此来达到数据压缩的目的。...
  • 通用数据压缩算法简介 前言 数据压缩技术始终是让我感觉到比较神秘的数学算法之一, 而当我接触到其具体的算法时候发现其原理是如此的简单所以就写了这篇文件来谈谈自己的感想但由于本文篇幅有限就以只以一个最简单的...
  • 数据压缩算法

    2013-06-29 10:08:43
    通过代码,讲解基本的压缩原理,简单易懂,,代码也容易实现。值得很好的参考。
  • 算法系列之八:RLE行程长度压缩算法

    万次阅读 多人点赞 2011-12-12 00:33:02
    RLE(Run Length Encoding)行程长度压缩算法(也称游程长度压缩算法),是最早出现、也是最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况:一种是连续的重复数据块,另一种是连续的...
  • RLE压缩算法详解

    千次阅读 2012-12-03 13:54:51
     RLE(Run Length Encoding)行程长度压缩算法(也称游程长度压缩算法),是最早出现,也是最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况:一种是连续的重复数据块,另一种是连续...
  • 无损压缩算法.ppt

    2019-12-14 00:58:53
    字典编码 * 南京大学多媒体研究所 * LZW编码 时间 1977年LZ77LZ78 1984年LZW 应用giftif 压缩比1:1.51:1.3 原理 LZW...南京大学多媒体研究所 * LZW编码 试对一个最简单的三字符ABC组成的字符串ABABBABCABABBA进行LZW编
  • 霍夫曼编码是压缩数据的最简单算法之一。 即使它非常古老和简单,它仍然被广泛使用(例如:在JPEG,MPEG等几个阶段中)。 在这个项目中,您将实现霍夫曼编码和解码。 您可以在Wikipedia或任何其他教程中阅读。 您...
  • 字符串压缩算法

    2021-02-04 21:17:18
    字符串压缩算法 记一次面试大厂后总结,第一次接触大公司面试,心中也许是有点紧张,问题回答基本中中肯肯,但是最后现场写程序题一时没做出来,感觉很遗憾。事后将此算法实现,公布于此,警示自己。程序主要是...
  • RLE行程长度压缩算法

    2017-06-08 21:48:36
    RLE(Run Length Encoding)行程长度压缩算法(也称游程长度压缩算法),是最早出现、也是最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况:一种是连续的重复数据块,另一种是连续的...
  • 最近工作正好接触到这一块,试着...” 简单来说,就是尝试用短编码代替长编码达到压缩的目的。LZW其实是三个大牛名字,这个算法最开始是Ziv和Lempel这两个人在1977,1978年发明,在1984年时候由另一位大...
  • 通用压缩算法简介

    千次阅读 2012-02-11 10:07:44
    前言 数据压缩技术始终是让我感觉到比较神秘的数学算法之一,而当我接触到其具体的算法时候,发现其原理是如此的...但由于本文篇幅有限,就以只以一个最简单的LZ77算法作为例子来讲解。 数据压缩技术其应用十分普
  • 通用数据压缩算法简介前言数据压缩技术始终是让我感觉到比较神秘的数学算法之一,而当我接触到其具体的算法时候,发现...但由于本文篇幅有限,就以只以一个最简单的LZ77算法作为例子来讲解。数据压缩技术其应用十分普遍

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 917
精华内容 366
关键字:

最简单的压缩算法