精华内容
下载资源
问答
  • Hive的数据压缩与数据存储

    万次阅读 2019-12-12 15:22:01
    一、hive的数据压缩 MR支持的压缩编码 压缩配置参数 开启Map输出阶段压缩 开启Reduce输出阶段压缩 二、hive的数据存储格式 列式存储和行式存储 TEXTFILE格式 ORC格式 PARQUET格式 三、存储和压缩结合 一...

    目录

    一、hive的数据压缩

    MR支持的压缩编码

    压缩配置参数

    开启Map输出阶段压缩

    开启Reduce输出阶段压缩

    二、hive的数据存储格式

    列式存储和行式存储

     TEXTFILE格式

    ORC格式

    PARQUET格式

    三、存储和压缩结合


    一、hive的数据压缩

    在实际工作当中,hive当中处理的数据,一般都需要经过压缩,前期我们在学习hadoop的时候,已经配置过hadoop的压缩,我们这里的hive也是一样的可以使用压缩来节省我们的MR处理的网络带宽

    MR支持的压缩编码

    压缩格式

    工具

    算法

    文件扩展名

    是否可切分

    DEFAULT

    DEFAULT

    .deflate

    Gzip

    gzip

    DEFAULT

    .gz

    bzip2

    bzip2

    bzip2

    .bz2

    LZO

    lzop

    LZO

    .lzo

    LZ4

    LZ4

    .lz4

    Snappy

    Snappy

    .snappy

    为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器,如下表所示

    压缩格式

    对应的编码/解码器

    DEFLATE

    org.apache.hadoop.io.compress.DefaultCodec

    gzip

    org.apache.hadoop.io.compress.GzipCodec

    bzip2

    org.apache.hadoop.io.compress.BZip2Codec

    LZO

    com.hadoop.compression.lzo.LzopCodec

    LZ4

    org.apache.hadoop.io.compress.Lz4Codec

    Snappy

    org.apache.hadoop.io.compress.SnappyCodec

    压缩性能的比较

    压缩算法

    原始文件大小

    压缩文件大小

    压缩速度

    解压速度

    gzip

    8.3GB

    1.8GB

    17.5MB/s

    58MB/s

    bzip2

    8.3GB

    1.1GB

    2.4MB/s

    9.5MB/s

    LZO

    8.3GB

    2.9GB

    49.3MB/s

    74.6MB/s

    在64位模式下的core i7处理器的单核上,Snappy的压缩速度约为250 MB/秒或更高,而解压速度约为500 MB/秒或更高。

     

    压缩配置参数

    要在Hadoop中启用压缩,可以配置如下参数(mapred-site.xml文件中):

    参数

    默认值

    阶段

    建议

    io.compression.codecs  

    (在core-site.xml中配置)

    org.apache.hadoop.io.compress.DefaultCodec, org.apache.hadoop.io.compress.GzipCodec, org.apache.hadoop.io.compress.BZip2Codec,

    org.apache.hadoop.io.compress.Lz4Codec

    输入压缩

    Hadoop使用文件扩展名判断是否支持某种编解码器

    mapreduce.map.output.compress

    false

    mapper输出

    这个参数设为true启用压缩

    mapreduce.map.output.compress.codec

    org.apache.hadoop.io.compress.DefaultCodec

    mapper输出

    使用LZOLZ4snappy编解码器在此阶段压缩数据

    mapreduce.output.fileoutputformat.compress

    false

    reducer输出

    这个参数设为true启用压缩

    mapreduce.output.fileoutputformat.compress.codec

    org.apache.hadoop.io.compress. DefaultCodec

    reducer输出

    使用标准工具或者编解码器,如gzipbzip2

    mapreduce.output.fileoutputformat.compress.type

    RECORD

    reducer输出

    SequenceFile输出使用的压缩类型:NONEBLOCK

     

    开启Map输出阶段压缩

    开启map输出阶段压缩可以减少job中map和Reduce task间数据传输量。具体配置如下:

    案例实操:

    1)开启hive中间传输数据压缩功能

    hive (default)>set hive.exec.compress.intermediate=true;

    2)开启mapreduce中map输出压缩功能

    hive (default)>set mapreduce.map.output.compress=true;

    3)设置mapreduce中map输出数据的压缩方式

    hive (default)>set mapreduce.map.output.compress.codec= org.apache.hadoop.io.compress.SnappyCodec;

    4)执行查询语句

    select count(1) from score;

     

    开启Reduce输出阶段压缩

    当Hive将输出写入到表中时,输出内容同样可以进行压缩。属性hive.exec.compress.output控制着这个功能。用户可能需要保持默认设置文件中的默认值false,这样默认的输出就是非压缩的纯文本文件了。用户可以通过在查询语句或执行脚本中设置这个值为true,来开启输出结果压缩功能。

    案例实操:

    1)开启hive最终输出数据压缩功能

    hive (default)>set hive.exec.compress.output=true;

    2)开启mapreduce最终输出数据压缩

    hive (default)>set mapreduce.output.fileoutputformat.compress=true;

    3)设置mapreduce最终数据输出压缩方式

    hive (default)> set mapreduce.output.fileoutputformat.compress.codec = org.apache.hadoop.io.compress.SnappyCodec;

    4)设置mapreduce最终数据输出压缩为块压缩

    hive(default)>set mapreduce.output.fileoutputformat.compress.type=BLOCK;

    5)测试一下输出结果是否是压缩文件

    insert overwrite local directory '/export/servers/snappy' select * from score distribute by s_id sort by s_id desc;

     

    二、hive的数据存储格式

    Hive支持的存储数据的格式主要有:TEXTFILE(行式存储) SEQUENCEFILE(行式存储)ORC(列式存储)、PARQUET(列式存储)。

     

    列式存储和行式存储

    上图左边为逻辑表,右边第一个为行式存储,第二个为列式存储。

    行存储的特点: 查询满足条件的一整行数据的时候,行存储只需要找到其中一个值,其余的值都在相邻地方。列存储则需要去每个聚集的字段找到对应的每个列的值,所以此时行存储查询的速度更快。

    列存储的特点: 因为每个字段的数据聚集存储,在查询只需要少数几个字段的时候,能大大减少读取的数据量;每个字段的数据类型一定是相同的,列式存储可以针对性的设计更好的设计压缩算法。

    TEXTFILE和SEQUENCEFILE的存储格式都是基于行存储的;

    ORCPARQUET是基于列式存储的。

     

     TEXTFILE格式

    默认格式,数据不做压缩,磁盘开销大,数据解析开销大。可结合Gzip、Bzip2使用(系统自动检查,执行查询时自动解压),但使用这种方式,hive不会对数据进行切分,从而无法对数据进行并行操作。

     

    ORC格式

    Orc (Optimized Row Columnar)是hive 0.11版里引入的新的存储格式。

    可以看到每个Orc文件由1个或多个stripe组成,每个stripe250MB大小,这个Stripe实际相当于RowGroup概念,不过大小由4MB->250MB,这样能提升顺序读的吞吐率。每个Stripe里有三部分组成,分别是Index Data,Row Data,Stripe Footer:

    一个orc文件可以分为若干个Stripe

    一个stripe可以分为三个部分

    indexData:某些列的索引数据

    rowData :真正的数据存储

    StripFooter:stripe的元数据信息

       1)Index Data:一个轻量级的index,默认是每隔1W行做一个索引。这里做的索引只是记录某行的各字段在Row Data中的offset。

       2)Row Data:存的是具体的数据,先取部分行,然后对这些行按列进行存储。对每个列进行了编码,分成多个Stream来存储。

       3)Stripe Footer:存的是各个stripe的元数据信息

    每个文件有一个File Footer,这里面存的是每个Stripe的行数,每个Column的数据类型信息等;每个文件的尾部是一个PostScript,这里面记录了整个文件的压缩类型以及FileFooter的长度信息等。在读取文件时,会seek到文件尾部读PostScript,从里面解析到File Footer长度,再读FileFooter,从里面解析到各个Stripe信息,再读各个Stripe,即从后往前读。

     

    PARQUET格式

    Parquet是面向分析型业务的列式存储格式,由TwitterCloudera合作开发,20155月从Apache的孵化器里毕业成为Apache顶级项目。

    Parquet文件是以二进制方式存储的,所以是不可以直接读取的,文件中包括该文件的数据和元数据,因此Parquet格式文件是自解析的。

    通常情况下,在存储Parquet数据的时候会按照Block大小设置行组的大小,由于一般情况下每一个Mapper任务处理数据的最小单位是一个Block,这样可以把每一个行组由一个Mapper任务处理,增大任务执行并行度。Parquet文件的格式如下图所示。

    上图展示了一个Parquet文件的内容,一个文件中可以存储多个行组,文件的首位都是该文件的Magic Code,用于校验它是否是一个Parquet文件,Footer length记录了文件元数据的大小,通过该值和文件长度可以计算出元数据的偏移量,文件的元数据中包括每一个行组的元数据信息和该文件存储数据的Schema信息。除了文件中每一个行组的元数据,每一页的开始都会存储该页的元数据,在Parquet中,有三种类型的页:数据页、字典页和索引页。数据页用于存储当前行组中该列的值,字典页存储该列值的编码字典,每一个列块中最多包含一个字典页,索引页用来存储当前行组下该列的索引,目前Parquet中还不支持索引页。

     

    三、存储和压缩结合

    官网:https://cwiki.apache.org/confluence/display/Hive/LanguageManual+ORC

    ORC存储方式的压缩:

    Key

    Default

    Notes

    orc.compress

    ZLIB

    high level compression (one of NONE, ZLIB, SNAPPY)

    orc.compress.size

    262,144

    number of bytes in each compression chunk

    orc.stripe.size

    67,108,864

    number of bytes in each stripe

    orc.row.index.stride

    10,000

    number of rows between index entries (must be >= 1000)

    orc.create.index

    true

    whether to create row indexes

    orc.bloom.filter.columns

    ""

    comma separated list of column names for which bloom filter should be created

    orc.bloom.filter.fpp

    0.05

    false positive probability for bloom filter (must >0.0 and <1.0)

    1)创建一个非压缩的的ORC存储方式

    1)建表语句

    create table log_orc_none(

    track_time string,

    url string,

    session_id string,

    referer string,

    ip string,

    end_user_id string,

    city_id string

    )

    ROW FORMAT DELIMITED FIELDS TERMINATED BY '\t'

    STORED AS orc tblproperties ("orc.compress"="NONE");

           2)插入数据

    insert into table log_orc_none select * from log_text1 ;

           3)查看插入后数据

    dfs -du -h /user/hive/warehouse/myhive.db/log_orc_none;

    7.7 M  /user/hive/warehouse/log_orc_none/123456_0

    2)创建一个SNAPPY压缩的ORC存储方式

           1)建表语句

    create table log_orc_snappy(

    track_time string,

    url string,

    session_id string,

    referer string,

    ip string,

    end_user_id string,

    city_id string

    )

    ROW FORMAT DELIMITED FIELDS TERMINATED BY '\t'

    STORED AS orc tblproperties ("orc.compress"="SNAPPY");

           2)插入数据

    insert into table log_orc_snappy select * from log_text1 ;

           3)查看插入后数据

    dfs -du -h /user/hive/warehouse/myhive.db/log_orc_snappy ;

    3.8 M  /user/hive/warehouse/log_orc_snappy/123456_0

    3)上一节中默认创建的ORC存储方式,导入数据后的大小为

    2.8 M  /user/hive/warehouse/log_orc/123456_0

    Snappy压缩的还小。原因是orc存储文件默认采用ZLIB压缩。比snappy压缩的小。

    4)存储方式和压缩总结:

           在实际的项目开发当中,hive表的数据存储格式一般选择:orcparquet。压缩方式一般选择snappy

     

    展开全文
  • Hadoop 数据压缩

    千次阅读 2018-05-29 00:22:48
    在 Hadoop 下,尤其是数据规模很大和工作负载密集的情况下,使用数据压缩显得非常重要。在这种情况下, I/O 操作和网络数据传输要花大量的时间。还有, Shuffle与 Merge 过程同样也面临着巨大的 I/O 压力。 鉴于...

    1 概述

    压缩技术能够有效减少底层存储系统(HDFS) 读写字节数。压缩提高了网络带宽和磁盘空间的效率。在 Hadoop 下,尤其是数据规模很大和工作负载密集的情况下,使用数据压缩显得非常重要。在这种情况下, I/O 操作和网络数据传输要花大量的时间。还有, Shuffle与 Merge 过程同样也面临着巨大的 I/O 压力。

    鉴于磁盘 I/O 和网络带宽是 Hadoop 的宝贵资源,数据压缩对于节省资源、最小化磁盘I/O 和网络传输非常有帮助。不过, 尽管压缩与解压操作的 CPU 开销不高,其性能的提升和资源的节省并非没有代价。

    如果磁盘 I/O 和网络带宽影响了 MapReduce 作业性能,在任意 MapReduce 阶段启用压缩都可以改善端到端处理时间并减少 I/O 和网络流量。

    压缩 Mapreduce 的一种优化策略:通过压缩编码对 Mapper 或者 Reducer 的输出进行压缩,以减少磁盘 IO, 提高 MR 程序运行速度(但相应增加了 cpu 运算负担) 。

    注意: 压缩特性运用得当能提高性能,但运用不当也可能降低性能。
    基本原则:
    (1)运算密集型的 job,少用压缩
    (2) IO 密集型的 job,多用压缩

    2 MR 支持的压缩编码

    这里写图片描述
    为了支持多种压缩/解压缩算法, Hadoop 引入了编码/解码器,如下表所示
    这里写图片描述
    压缩性能的比较
    这里写图片描述
    http://google.github.io/snappy/
    On a single core of a Core i7 processor in 64-bit mode, Snappy compresses at about 250 MB/sec
    or more and decompresses at about 500 MB/sec or more.

    3 压缩方式选择

    1 Gzip 压缩
    优点:压缩率比较高,而且压缩/解压速度也比较快; hadoop 本身支持,在应用中处理gzip 格式的文件就和直接处理文本一样;大部分 linux 系统都自带 gzip 命令,使用方便。

    缺点:不支持 split。

    应用场景: 当每个文件压缩之后在 130M 以内的(1 个块大小内),都可以考虑用 gzip压缩格式。 例如说一天或者一个小时的日志压缩成一个 gzip 文件,运行 mapreduce 程序的时候通过多个 gzip 文件达到并发。 hive 程序, streaming 程序,和 java 写的 mapreduce 程序完全和文本处理一样,压缩之后原来的程序不需要做任何修改。

    2 Bzip2 压缩
    优点:支持 split;具有很高的压缩率,比 gzip 压缩率都高; hadoop 本身支持,但不支持 native;在 linux 系统下自带 bzip2 命令,使用方便。

    缺点:压缩/解压速度慢;不支持 native。

    应用场景: 适合对速度要求不高,但需要较高的压缩率的时候,可以作为 mapreduce 作业的输出格式; 或者输出之后的数据比较大,处理之后的数据需要压缩存档减少磁盘空间并且以后数据用得比较少的情况;或者对单个很大的文本文件想压缩减少存储空间,同时又需要支持 split,而且兼容之前的应用程序(即应用程序不需要修改)的情况。

    3 Lzo 压缩
    优点:压缩/解压速度也比较快,合理的压缩率;支持 split,是 hadoop 中最流行的压缩格式;可以在 linux 系统下安装 lzop 命令,使用方便。

    缺点:压缩率比 gzip 要低一些; hadoop 本身不支持,需要安装;在应用中对 lzo 格式的文件需要做一些特殊处理(为了支持 split 需要建索引,还需要指定 inputformat 为 lzo 格式)。

    应用场景: 一个很大的文本文件,压缩之后还大于 200M 以上的可以考虑,而且单个文件越大, lzo 优点越越明显。

    4 Snappy 压缩
    优点:高速压缩速度和合理的压缩率。

    缺点:不支持 split;压缩率比 gzip 要低; hadoop 本身不支持,需要安装;

    应用场景: 当 Mapreduce 作业的 Map 输出的数据比较大的时候,作为 Map 到 Reduce的中间数据的压缩格式;或者作为一个 Mapreduce 作业的输出和另外一个 Mapreduce 作业的输入。

    4 压缩位置选择

    压缩可以在 MapReduce 作用的任意阶段启用。
    这里写图片描述

    5 压缩配置参数

    要在 Hadoop 中启用压缩,可以配置如下参数:
    这里写图片描述

    展开全文
  • 文章目录一 __init__() 创建一个类文件对象二 append() 内存数据添加到zip对象三 appendfile() ...传统方法需要多次磁盘IO,性能很低,如果跳过文件存储,直接将内存的数据压缩保存,会大大减少磁盘IO,提升性能。 不

    工作中需要将大批的数据,压缩为zip存储。按照传统的处理办法需要将数据先存储到本地磁盘,再从磁盘读文件压缩成zip文件。
    传统方法需要多次磁盘IO,性能很低,如果跳过文件存储,直接将内存的数据压缩保存,会大大减少磁盘IO,提升性能。

    不需要看解析的,可以直接看最后完整的python代码

    创建一个类: InMemoryZIP(), 来处理所有的程序。

    class InMemoryZIP(object):
    

    init() 创建一个类文件对象

    	def __init__(self):
    		# create the in-memory file-like object
    		self.in_memory_zip = BytesIO()
    

    二 append() 内存数据添加到zip对象

    	def append(self, filename_in_zip, file_contents):
    		""" Appends a file with name filename_in_zip \
            and contents of file_contents to the in-memory zip.
            """
    
            # create a handle to the in-memory zip in append mode\
    		if not isinstance(file_contents, bytes):
    			file_contens = bytes(str(file_contens), encoding='utf-8')
    
    		# write the file to the in-memory zip
    		zf = zipfile.ZipFile(self.in_memory_zip, 'a', zipfile.ZIP_DEFLATED, False)
    
    		zf.writestr(filename_in_zip, file_contents)
    
    		# mark the files as having been created on Windows
            # so that Unix permissions are not inferred as 0000
    		for zfiel in zf.filelist:
    			zfile.create_system = 0
    
    		return self
    
    

    三 appendfile() 文件添加到zip对象

    	def appendfile(self, file_path, file_name=None):
    		""" Read a file with path file_path \
            and append to in-memory zip with name file_name.
            """
    
            # file_path is abs path
    		if file_name is None:
    			file_name = os.path.split(file_path)[1]
    
    
    		with open(file_path, 'rb') as f:
    			file_contents = f.read()
    			self.append(file_name, file_contents)
    
    		return self
    

    四 read() 读取zip数据流

    	def read(self):
    		""" Returns a string with the contents of the in-memory zip.
            """
    
    		self.in_memory_zip.seek(0)
    		return self.in_memory_zip.read()
    

    五 writetofile() 内存zip流保存为zip文件

    def writetofile(self, zip_filename):
    	"""
            Write the in-memory zip to a file
        """
    
    	with open(zip_filename, 'wb') as f:
    		f.write(self.read())
    
    

    六 完整版python代码

    # !user/bin/env python3
    # -*-coding : utf-8 -*-
    
    import zipfile
    from io import BytesIO
    import os
    
    
    class InMemoryZIP(object):
        def __init__(self):
            # create the in-memory file-like object
            self.in_memory_zip = BytesIO()
    
        def append(self, filename_in_zip, file_contents):
            """ Appends a file with name filename_in_zip \
            and contents of file_contents to the in-memory zip.
            """
            # create a handle to the in-memory zip in append mode\
            if not isinstance(file_contents, bytes):
                file_contents = bytes(str(file_contents), encoding='utf-8')
    
            zf = zipfile.ZipFile(self.in_memory_zip, 'a',
                                 zipfile.ZIP_DEFLATED, False)
    
            # write the file to the in-memory zip
            zf.writestr(filename_in_zip, file_contents)
    
            # mark the files as having been created on Windows
            # so that Unix permissions are not inferred as 0000
            for zfile in zf.filelist:
                zfile.create_system = 0
            return self
    
        def appendfile(self, file_path, file_name=None):
            """ Read a file with path file_path \
            and append to in-memory zip with name file_name.
            """
            if file_name is None:
                file_name = os.path.split(file_path)[1]
    
            f = open(file_path, 'rb')
            file_contents = f.read()
            self.append(file_name, file_contents)
            f.close()
            return self
    
        def read(self):
            """ Returns a string with the contents of the in-memory zip.
            """
            self.in_memory_zip.seek(0)
            return self.in_memory_zip.read()
    
        def writetofile(self, filename):
            """
            Write the in-memory zip to a file
            """
            f = open(filename, 'wb')
            f.write(self.read())
            f.close()
    
    
    if __name__ == '__main__':
    
    	pass
    
    	# contens = 'xxxxxxxxx'  # 内存数据
        # imz = InMemoryZIP()
        # imz.append('test.txt', contens)
        # imz.writetofile('test.zip')
       
    
    
    展开全文
  • 深入解析数据压缩算法

    万次阅读 2018-05-06 10:30:45
    1、为什么要做数据压缩? 数据压缩的主要目的还是减少数据传输或者转移过程中的数据量。2、什么是数据压缩? 是指在不丢失信息的前提下,缩减数据量以减少存储空间,提高传输、存储和处理效率的一种技术方法。或者...

    1、为什么要做数据压缩?

           数据压缩的主要目的还是减少数据传输或者转移过程中的数据量。

    2、什么是数据压缩?

            是指在不丢失信息的前提下,缩减数据量以减少存储空间,提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间。

      3、常见的数据压缩算法

    (1).LZW压缩

            LZW压缩是一种无损压缩,应用于gif图片。适用于数据中存在大量重固子串的情况。

    原理:

           LZW算法中,首先建立一个字符串表,把每一个第一次出现的字符串放入串表中,并用一个数字来表示,这个数字与此字符串在串表中的位置有关,并将这个数字存入压缩文件中,如果这个字符串再次出现时,即可用表示它的数字来代替,并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串,如果在压缩时用266表示,只要再次出现,均用266表示,并将"print"字符串存入串表中,在图象解码时遇到数字266,即可从串表中查出266所代表的字符串"print",在解压缩时,串表可以根据压缩数据重新生成。

    编码过程:


         编码后输出:41 42 52 41 43 41 44 81 83 82 88 41 80。输入为17个7位ASC字符,总共119位,输出为13个8位编码,总共104位,压缩比为87%。

    解码过程:

         对输出的41 42 52 41 43 41 44 81 83 82 88 41 80进行解码,如下表所示:


    解码后输出:

    ABRACADABRABRABRA

    特殊标记:
           随着新的串(string)不断被发现,标号也会不断地增长,如果原数据过大,生成的标号集(string table)会越来越大,这时候操作这个集合就会产生效率问题。如何避免这个问题呢?Gif在采用lzw算法的做法是当标号集足够大的时候,就不能增大了,干脆从头开始再来,在这个位置要插入一个标号,就是清除标志CLEAR,表示从这里我重新开始构造字典,以前的所有标记作废,开始使用新的标记。
          这时候又有一个问题出现,足够大是多大?这个标号集的大小为比较合适呢?理论上是标号集大小越大,则压缩比率就越高,但开销也越高。 一般根据处理速度和内存空间连个因素来选定。GIF规范规定的是12位,超过12位的表达范围就推倒重来,并且GIF为了提高压缩率,采用的是变长的字长。比如说原始数据是8位,那么一开始,先加上一位再说,开始的字长就成了9位,然后开始加标号,当标号加到512时,也就是超过9为所能表达的最大数据时,也就意味着后面的标号要用10位字长才能表示了,那么从这里开始,后面的字长就是10位了。依此类推,到了2^12也就是4096时,在这里插一个清除标志,从后面开始,从9位再来。

          GIF规定的清除标志CLEAR的数值是原始数据字长表示的最大值加1,如果原始数据字长是8,那么清除标志就是256,如果原始数据字长为4那么就是16。另外GIF还规定了一个结束标志END,它的值是清除标志CLEAR再加1。由于GIF规定的位数有1位(单色图),4位(16色)和8位(256色),而1位的情况下如果只扩展1位,只能表示4种状态,那么加上一个清除标志和结束标志就用完了,所以1位的情况下就必须扩充到3位。其它两种情况初始的字长就为5位和9位。

    代码示例:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <map>
    #include <algorithm>
    #include <vector>
    using namespace std;
    long len=0;//原字符串的长度
    long loc=0;//去重之后字符串的长度
    map<string,long> dictionary;
    vector <long> result;
    #define MAX 100;
    void LZWcode(string a,string s)
    {
        //memset(&result,0,sizeof(int));
        string W,K;
        for(long i=0;i<loc;i++)
        {
            string s1;
            s1=s[i];//将单个字符转换为字符串
            dictionary[s1]=i+1;
        }
        W=a[0];
        loc+=1;
        for(int i=0;i<len-1;i++)
        {
            K=a[i+1];
            string firstT=W;
            string secontT=W;
            if(dictionary.count(firstT.append(K))!=0)//map的函数count(n),返回的是map容器中出现n的次数
                W=firstT;
            else
            {
                result.push_back(dictionary[W]);
                dictionary[secontT.append(K)]=loc++;
                W=K;
            }
        }
        if(!W.empty())
            result.push_back(dictionary[W]);
        for(int i=0;i<result.size();i++)
            cout<<result[i];
    }
    
    void LZWdecode(int *s,int n)
    {
        string nS;
        for(int i=0;i<n;i++)
            for(map<string,long>::iterator it=dictionary.begin(); it!=dictionary.end();it++)
                if(it->second==s[i])
                {
                    cout<<it->first<<" ";
                }
        for(map<string,long>::iterator it=dictionary.begin(); it!=dictionary.end();it++)//输出压缩编码的字典表
            cout<<it->first<<" "<<it->second<<endl;
    }
    int main(int argc, char const *argv[])
    {
        cout<<"本程序的解码是根据输入的编码字符进行的解码,并不是全256 的字符"<<endl;
        cout<<"选择序号:"<<endl;
        cout<<"1.压缩编码   2.解码"<<endl;
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            switch(n)
            {
                case 1:
                {
                    char s[100],a[100];
                    cout<<"输入一串字符:"<<endl;
                    cin>>s;
                    len=strlen(s);
                    for(int i=0;i<len;i++)
                        a[i]=s[i];
                    sort(s,s+len);//排序
                    loc=unique(s,s+len)-s;//去重
                    LZWcode(a,s);
                    break;
                }
                case 2:
                {
                    cout<<"输入解码数组的长度:"<<endl;
                    int changdu;
                    cin>>changdu;
                    cout<<"输入解码数串(每个数串以空格隔开):"<<endl;
                    int s[changdu];
                    for(int i=0;i<changdu;i++)
                        cin>>s[i];
                    LZWdecode(s, changdu);
                    break;
                }
                default:
                    cout<<"你的输入不正确,请从重新开始"<<endl;
            }
            if(n==2)
            {
                auto iter=result.begin();   // 每次正确输入结束后对结果进行清零
                while(iter!=result.end())
                    result.erase(iter++);
            }
        }
        return 0;
    }
    

    (2).霍夫曼压缩

          哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示,而不常见的符号需要很多位来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而,它并不处理符号的顺序和重复或序号的序列。

    原理:

         利用数据出现的次数构造Huffman二叉树,并且出现次数较多的数据在树的上层,出现次数较少的数据在树的下层。于是,我们就可以从根节点到每个数据的路径来进行编码并实现压缩。

    编码过程:

    假设有一个包含100000个字符的数据文件要压缩存储。各字符在该文件中的出现频度如下所示:

           在此,我会给出常规编码的方法和Huffman编码两种方法,这便于我们比较。

           常规编码方法:我们为每个字符赋予一个三位的编码,于是有:


           此时,100000个字符进行编码需要100000 * 3 = 300000位。


           Huffman编码:利用字符出现的频度构造二叉树,构造二叉树的过程也就是编码的过程。

    这种情况下,对100000个字符编码需要:(45 * 1 + (16 + 13 + 12 + 9)*3 + (9 + 5)*4) * 1000 = 224000

     

    孰好孰坏,例子说明了一切!好了,老规矩,下面我还是用上面的例子详细说明一下Huffman编码的过程。

           首先,我们需要统计出各个字符出现的次数,如下:

           接下来,我根据各个字符出现的次数对它们进行排序,如下:

           好了,一切准备工作就绪。

           在上文我提到,huffman编码的过程其实就是构造一颗二叉树的过程,那么我将各个字符看成树中将要构造的各个节点,将字符出现的频度看成权值。Ok,有了这个思想,here we go!

           构造huffman编码二叉树规则:

    从小到大,

    从底向上,

    依次排开,

    逐步构造。

           首先,根据构造规则,我将各个字符看成构造树的节点,即有节点a、b、c、d、e、f。那么,我先将节点f和节点e合并,如下图:

    于是就有:

    经过排序处理得:

     

            接下来,将节点b和节点c也合并,则有:

           于是有:

           经过排序处理得:

           第三步,将节点d和节点fe合并,得:

           于是有:

           继续,这次将节点fed和节点bc合并,得:

           于是有:

           最后,将节点a和节点bcfed合并,有:

           以上步骤就是huffman二叉树的构造过程,完整的树如下:

           二叉树成了,最后就剩下编码了,编码的规则为:01

           于是根据编码规则得到我们最终想要的结果:

           从上图中我们得到各个字符编码后的编码位:


    代码示例:

    哈夫曼树结构:

    struct element
    {
        int weight;        // 权值域
        int lchild, rchild, parent;  // 该结点的左、右、双亲结点在数组中的下标
    };

    weight保存结点权值;lchild保存该节点的左孩子在数组中的下标;rchild保存该节点的右孩子在数组中的下标;parent保存该节点的双亲孩子在数组中的下标。

    哈夫曼算法的C++实现:

    #include<iostream>
    #include <iomanip>
    
    using namespace std;
    // 哈夫曼树的结点结构
    struct element
    {
        int weight;        // 权值域
        int lchild, rchild, parent;  // 该结点的左、右、双亲结点在数组中的下标
    };
    // 选取权值最小的两个结点
    void selectMin(element a[],int n, int &s1, int &s2)
    {
        for (int i = 0; i < n; i++)
        {
            if (a[i].parent == -1)// 初始化s1,s1的双亲为-1
            {
                s1 = i;
                break;
            }
        }
        for (int i = 0; i < n; i++)// s1为权值最小的下标
        {
            if (a[i].parent == -1 && a[s1].weight > a[i].weight)
                s1 = i;
        }
        for (int j = 0; j < n; j++)
        {
            if (a[j].parent == -1&&j!=s1)// 初始化s2,s2的双亲为-1
            {
                s2 = j;
                break;
            }
        }
        for (int j = 0; j < n; j++)// s2为另一个权值最小的结点
        {
            if (a[j].parent == -1 && a[s2].weight > a[j].weight&&j != s1)
                s2 = j;
        }
    }
    // 哈夫曼算法
    // n个叶子结点的权值保存在数组w中
    void HuffmanTree(element huftree[], int w[], int n)
    {
        for (int i = 0; i < 2*n-1; i++)    // 初始化,所有结点均没有双亲和孩子
        {
            huftree[i].parent = -1;
            huftree[i].lchild = -1;
            huftree[i].rchild = -1;
        }
        for (int i = 0; i < n; i++)    // 构造只有根节点的n棵二叉树
        {
            huftree[i].weight = w[i];
        }
        for (int k = n; k < 2 * n - 1; k++) // n-1次合并
        {
            int i1, i2; 
            selectMin(huftree, k, i1, i2); // 查找权值最小的俩个根节点,下标为i1,i2
            // 将i1,i2合并,且i1和i2的双亲为k
            huftree[i1].parent = k;
            huftree[i2].parent = k;
            huftree[k].lchild = i1;
            huftree[k].rchild = i2;
            huftree[k].weight = huftree[i1].weight + huftree[i2].weight;
        }
        
    }
      // 打印哈夫曼树
    void print(element hT[],int n)
    {
        cout << "index weight parent lChild rChild" << endl;
        cout << left;    // 左对齐输出 
        for (int i = 0; i < n; ++i) 
        {
            cout << setw(5) << i << " ";
            cout << setw(6) << hT[i].weight << " ";
            cout << setw(6) << hT[i].parent << " ";
            cout << setw(6) << hT[i].lchild << " ";
            cout << setw(6) << hT[i].rchild << endl;
        }
    }
    int main()
    {
        int x[] = { 5,29,7,8,14,23,3,11 };        // 权值集合
        element *hufftree=new element[2*8-1];    // 动态创建数组
        HuffmanTree(hufftree, x, 8);
        print(hufftree,15);
        system("pause");
        return 0;
    }

    说明:

          parent域值是判断结点是否写入哈夫曼树的唯一条件,parent的初始值为-1,当某结点加入时,parent域的值就设置为双亲结点在数组的下标。构造哈夫曼树时,首先将n个权值的叶子结点存放到数组haftree的前n个分量中,然后不断将两棵子树合并为一棵子树,并将新子树的根节点顺序存放到数组haftree的前n个分量的后面。

    (3).游程编码(RLC)

               游程编码又称“运行长度编码”或“行程编码”,是一种无损压缩编码,JPEG图片压缩就用此方法,很多栅格数据压缩也是采用这种方法。

               栅格数据如图3-1所示:

                                                       

                                                                         3-1 栅格数据

      原理:

             用一个符号值或串长代替具有相同值的连续符号(连续符号构成了一段连续的“行程”。行程编码因此而得名),使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时,一次记录该代码及相同代码重复的个数,从而实现数据的压缩。

            常见的游程编码格式包括TGA,Packbits,PCX以及ILBM。
    例如:5555557777733322221111111
    行程编码为:(5,6)(7,5)(3,3)(2,4)(1,7)。可见,行程编码的位数远远少于原始字符串的位数。
    并不是所有的行程编码都远远少于原始字符串的位数,但行程编码也成为了一种压缩工具。
    例如:555555 是6个字符 而(5,6)是5个字符,这也存在压缩量的问题,自然也会出现其他方式的压缩工具。
    在对图像数据进行编码时,沿一定方向排列的具有相同灰度值的像素可看成是连续符号,用字串代替这些连续符号,可大幅度减少数据量。

            游程编码记录方式有两种:①逐行记录每个游程的终点列号:②逐行记录每个游程的长度(像元数)

    第一种方式:

            

          上面的栅格图形可以记为:A,3  B,5  A,1  C,4  A,5

          第二种就记作:A,3  B,2  A,1  C,3   A,1

         行程编码是连续精确的编码,在传输过程中,如果其中一位符号发生错误,即可影响整个编码序列,使行程编码无法还原回原始数据。

    代码示例:

           根据输入的字符串,得到大小写不敏感压缩后的结果(即所有小写字母均视为相应的大写字母)。输入一个字符串,长度大于0,且不超过1000,全部由大写或小写字母组成。输出输出为一行,表示压缩结果,形式为:
    (A,3)(B,4)(C,1)(B,2)

          即每对括号内部分别为字符(都为大写)及重复出现的次数,不含任何空格。

    样例输入:aAABBbBCCCaaaaa

    样例输出:(A,3)(B,4)(C,3)(A,5)

    #include<stdio.h>
    #include<string.h>
    char a[1001];
    int main()
    {
        char t;
        int i;
    gets(a);
    int g=1;
    int k=strlen(a);
    if(a[0]>='a'&&a[0]<='z')
        a[0]-=32;
      t=a[0];
    for(i=1;i<=k;i++)
    {
      if(a[i]>='a'&&a[i]<='z')
      a[i]-=32;
      if(a[i]==t)
          g++;
    if(a[i]!=t)
      {
        printf("(%c,%d)",t,g);
         g=1;
           t=a[i];
      }
    }return 0;
    }

    应用场景:

    (1).区域单色影像图

    (2).红外识别图形

    (3).同色区块的彩色图形

    参阅资料:

    https://blog.csdn.net/u012455213/article/details/45502573

    https://www.cnblogs.com/smile233/p/8184492.html

        说明:部分图源来自网络,感谢作者的分享。

    展开全文
  • Influxdb数据压缩

    千次阅读 2017-04-23 15:06:00
    数据压缩可以参考: https://docs.influxdata.com/influxdb/v1.1/concepts/storage_engine/#compression   influxdb根据不同的数据类型会采用不同的压缩算法。 int  首先使用ZigZag算...
  • hdfs的数据压缩

    千次阅读 2018-09-05 13:49:51
    数据压缩 Hadoop 作为一个较通用的海量数据处理平台,每次运算都会需要处理大量数据,我们会在 hadoop 系统中对数据进行压缩处理来优化磁盘使用率,提高数据在磁盘和网络中的传输速度,从而提高系统处理数据的效率...
  • 数据压缩之不可压缩性

    千次阅读 2016-09-13 08:32:26
    数据压缩算法一直朝着更高的压缩率方向突破,同时也在压缩率和压缩时间上做出权衡。 美剧《硅谷》中的初创公司魔笛手就是一个以数据压缩为核心的公司,在第三季里面杜撰的数据压缩算法可以将数据压缩到几乎不占空间...
  • 一、客户端-服务端数据压缩解压流程 客户端生成request,设置header允许使用压缩("Accept-Encoding","gzip"),即是告诉服务器,客户端支持压缩,但凡可以压缩的服务器,尽管来吧!服务器收到这个header,如果它支持...
  • Hadoop之Hadoop数据压缩

    千次阅读 2019-06-10 21:04:37
    Hadoop之Hadoop数据压缩 目录 概述 MR支持的压缩编码 Gzip压缩 Bzip2压缩 Lzo压缩 Snappy压缩 压缩位置选择 压缩参数配置 1. 概述 压缩技术能够有效减少底层存储系统(HDFS)读写字节数。压缩提高了网络带宽和...
  • SQL SERVER 数据压缩

    千次阅读 2016-11-26 20:29:07
    从SQL SERVER 2008开始,SQL SERVER 提供了对数据进行压缩的功能,启用数据压缩无须修改应用程序。 数据压缩可有效减少数据的占用空间,读取和写入相同数据花费的IO也响应减少,从而可以有效缓解IO压力,但由于...
  • Hive --数据压缩

    千次阅读 2019-12-03 20:39:12
    hive的数据压缩 在实际工作当中,hive当中处理的数据,一般都需要经过压缩,节省我们的MR处理的网络带宽 mr支持的压缩编码 压缩格式 工具 算法 文件扩展名 ...
  • 矢量数据压缩

    千次阅读 2013-11-28 19:45:59
    1矢量数据压缩的几种常用算法 目前,矢量曲线数据压缩算法主要有:垂距限制法、角度限制法141、道格拉斯一普克法、基于自然规律的宏 观综合法,以及黄培之1995年...
  • Zlib内存数据压缩和解压缩

    千次阅读 2016-04-11 00:26:41
    前言现在要将抓图数据传到另外一台计算机,首先要解决的是将BMP数据压缩. BMP的压缩率是很大的, 如果不压缩,没办法往下做了. 当前Zlib版本是2013年出的1.2.8, 先做个静态库, 将.h和.cpp包进去,封成静态库使用. ...
  • 开启Map输出阶段压缩 ...1)开启hive中间传输数据压缩功能 hive (default)>set hive.exec.compress.intermediate=true; 2)开启mapreduce中map输出压缩功能 hive (default)>set mapredu...
  • 数据压缩算法实现

    千次阅读 2017-06-10 16:57:57
    利用香农-费诺编码、霍夫曼编码、LZ编码、算术编码实现数据压缩
  • 数据压缩算法,文本压缩算法 几种压缩算法原理介绍- https://blog.csdn.net/clevercode/article/details/46691645 文本压缩算法的对比和选择- https://blog.csdn.net/horkychen/article/details/75174035 数据压缩...
  • 浅析数据压缩算法

    千次阅读 2017-05-17 15:51:17
    数据压缩是减少信息传输量最经济直接的办法,所以这篇文章将讲解一些经典的数据压缩算法。 一 热身:基因组 对于生物学的基因研究中,A、C、T、G是是用来表示生物DNA的四种碱基,对基因序列的处理实际上是对这四种...
  • 数据压缩算法

    千次阅读 2013-12-02 16:41:59
    一 引言 随着互联网的飞快发展,整个互联网产生原来越多的数据,这个世界充满了数据,人们的生活离不开数据,然而能够有效表达数据的算法在现代的计算机基础架构...因为大多数数据有很大的冗余,所以数据压缩算法能够节
  • Hadoop数据压缩

    千次阅读 2020-08-27 16:58:07
    2、 MR支持的压缩编码 3、 压缩方式选择 3.1 Gzip压缩 3.2 Bzip2压缩 3.3 Lzo压缩 3.4 Snappy压缩 4、 压缩位置选择 5、 压缩参数配置 1、 概述 压缩策略与原则 2、 MR支持的压缩编码 压缩格式 ...
  • HADOOP与HDFS数据压缩格式

    千次阅读 2018-10-17 18:20:11
    HADOOP与HDFS数据压缩格式 1、cloudera 数据压缩的一般准则 一般准则 是否压缩数据以及使用何种压缩格式对性能具有重要的影响。在数据压缩上,需要考虑的最重要的两个方面是 MapReduce 作业和存储在 HBase 中的...
  • Zstd-数据压缩组件

    千次阅读 2019-01-03 17:38:27
    Zstandard 简称Zstd,是一款快速实时的开源数据压缩程序,由Facebook开发,源码是用C语言编写的。相比业内其他压缩算法(如Gzip、Snappy、Zlib)它的特点是:当需要时,它可以将压缩速度交换为更高的压缩比率(压缩...
  • 数据压缩学习(一)

    千次阅读 2020-03-08 11:50:29
    数据压缩之数据去重简介 什么是Data deduplication 数据去重,简单地说就是重复数据删除。从某种意义上说也是一种数据压缩技术。 数据去重的优势 节约磁盘空间:对于村出在同一个磁盘上的同一个文件或者是不同的...
  • Hadoop:数据压缩、Yarn、企业优化

    万次阅读 2020-06-03 20:41:20
    Hadoop数据压缩、Yarn架构以及工作流程、Hadoop企业优化方案
  • 前后端数据之间的交互,在数据量比较大的时候经常会有带宽占用高,数据传输慢,并且文件越大传输时间就越长,为了减少传输时间和优化网站提高用户体验;这时候我们就考虑一些压缩的方案了
  • java实现第三届蓝桥杯数据压缩

    万次阅读 多人点赞 2019-07-29 20:24:10
    数据压缩 某工业监控设备不断发回采样数据。每个数据是一个整数(0到1000之间)。各个数据间用空白字符(空格,TAB或回车换行)分隔。这些数据以文本形式被存储在文件中。 因为大多数时候,相邻的采样间隔数据是...
  • 数据压缩这是mapreduce的一种优化策略:通过压缩编码对mapper或者reducer的输出进行压缩,以减少磁盘IO,提高MR程序运行速度(但相应增加了cpu运算负担) Mapreduce支持将map输出的结果或者reduce输出的结果进行...
  • Hive数据压缩笔记

    万次阅读 2013-06-26 21:49:14
    Hive数据压缩 本文介绍Hadoop系统中Hive数据压缩方案的比较结果及具体压缩方法。 一、压缩方案比较 关于Hadoop HDFS文件的压缩格式选择,我们通过多个真实的Track数据做测试,得出结论如下: 1. 系统的默认压缩...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,527
精华内容 22,610
关键字:

数据压缩