共计 6941 个字符，预计需要花费 18 分钟才能阅读完成。
简介：目前，物联网、工业互联网、车联网等智能互联技术在各个行业场景下疾速遍及利用，导致联网传感器、智能设施数量急剧减少，随之而来的海量时序监控数据存储、解决问题，也为时序数据库高效压缩、存储数据能力提出了更高的要求。对于通量更加宏大的物联网时序大数据存储，只管规范压缩办法还能施展其价值，但某些场景对时序数据压缩解压技术效率、性能提出了新的需要。本文介绍了现有的时序数据压缩解压技术，分类介绍了不同算法的特点和优劣势。
作者 | 仁威
起源 | 阿里技术公众号
摘要：目前，物联网、工业互联网、车联网等智能互联技术在各个行业场景下疾速遍及利用，导致联网传感器、智能设施数量急剧减少，随之而来的海量时序监控数据存储、解决问题，也为时序数据库高效压缩、存储数据能力提出了更高的要求。对于通量更加宏大的物联网时序大数据存储，只管规范压缩办法还能施展其价值，但某些场景对时序数据压缩解压技术效率、性能提出了新的需要。本文介绍了现有的时序数据压缩解压技术，分类介绍了不同算法的特点和优劣势。
时序数据普遍存在于 IoT 物联网、工业互联网、车联网等相干场景，物联网设施已遍布各种行业场景利用，从可穿戴设施到工业生产设施，都会或将会产生大量数据。比方，新型波音 787 客机每次航行传感器产生的数据量都在 500GB 左右。在这些场景下，通常具备高并发写和高通量数据处理特点，抉择时序数据压缩算法须要全方位思考数据采集、存储、剖析的须要。特地须要留神的是业务利用对时序数据以后和历史数据分析的形式，抉择压缩算法不当将可能导致要害信息失落，从而影响剖析后果。对于业务来说，更间接应用时序数据压缩技术的利用就是时序数据库，对于时序数据库压缩解压是要害数据处理步骤，压缩算法性能间接影响时序数据库建设投入的 ROI。
一 时序数据压缩
对于数据压缩算法，业界存在更广泛的解释，通常是针对通用场景和业务相干场景，比方视频、音频、图像数据流压缩。本文重点介绍时序数据库中罕用的面向时序数据设计或可用于时序数据处理的通用压缩算法。咱们抉择剖析的算法具备对更广泛场景下继续产生时序数据压缩解决的能力，并对 IoT 物联网场景传感器数据压缩的以下特点做了非凡设计：
1、数据冗余（Redundancy）：一些特定模式的时序数据经常性反复呈现在一个或多个工夫序列。
2、函数估算（Approximability）：某些传感器产生的时序数据生成模式能够依据预约义函数估算。
3、趋势预测（Predictability）：某些时序数据将来趋势能够通过算法预测，例如利用回归、深度神经网络等技术。
图 时序数据压缩算法分类
本文重点总结了时序数据库和物联网 IoT 传感器治理罕用压缩算法，并依据技术办法（dictionary-based, functional approximation, autoencoders, sequential 等）和技术属性（adaptiveness, lossless reconstruction, symmetry, tuneability）对碎片化的压缩技术进行了分类，具体参考上图，并针对次要算法性能进行了比照剖析。
二 背景技术介绍
在介绍压缩算法之前，咱们先对时序数据、压缩和品质指数（quality indices）几个要害的概念进行定义。
1 时序数据（Time Series）
时序数据指数据元组依据工夫戳（ti）升序排列的数据汇合，能够被划分为：
- 单变量时序（Univariate Time Series，UTS）：每次采集的数据元组汇合为单个实数变量。
- 多变量时序（Multivariate Time Series，MTS）：每次采集的数据元组汇合由多个实数序列组成，每个组成部分对映时序一个特色。
比方，图 2 中股票价格在指定工夫窗口的稳定能够被定义为单变量时序数据，而每天交易信息（如：收盘、收盘价格，交易量等）则能够定义为多变量时序数据。
图 股票交易 UTS 时序数据样例
用数学范式表白时序能够被定义为：
2 数据压缩
数据压缩（又被称为源编码，source coding），依据 David Salmon 在《Data Compression: The Complete Reference》一书中的定义，能够简略形容为“将输出原始数据流转变为字符流（bit stream）或压缩流的体量更小的输入数据流的过程”。这个过程遵循 J. G.Wolff 提出的 Simplicity Power（SP）实践，旨在尽量保持数据信息的前提上来除数据冗余。
数据解压缩（又被称为源解码，source decoding），执行与压缩相同过程重构数据流以适应更高效数据应用层对数据表述、了解的须要。
现有压缩算法依据实现原理的差别，能够被划分为以下几类：
- 非适应 / 自适应（Non-adaptive/ adaptive）：非适应算法不须要针对非凡数据流进行训练以晋升效率，而适应算法则须要有训练过程。
- 涣散 / 非涣散（Lossy/Lossless）：涣散算法不保障对原始数据压缩后的后果惟一，而非涣散算法对同样原始数据的压缩后果惟一。
- 对称 / 非对称（Symmetric/Asymmetric）：对称算法对数据的压缩、解压缩应用雷同的算法实现，通过执行不同的代码门路切换压缩解压缩过程；非对称算法则在数据压缩、解压缩过程别离应用不同的算法。
- 对于具体的时序数据流压缩解压缩过程，一个压缩算法实例（encoder）输出 s 体量的时序数据流 TS，返回压缩后的体量 s′的时序数据流 TS′，且 s >s′蕴含一起压缩的工夫戳字段 E(TS) = TS′。解压缩算法实例（decoder）的执行过程则是从压缩数据流还源原始的时序数据流 D(TS′) = TS，若 TS = TSs 则压缩算法是非涣散的，否则就是涣散的。
3 品质指数（quality indices）
为了度量时序数据压缩算法的性能，通常须要思考三点个性：压缩率、压缩速度、精确度。
1、压缩率：掂量压缩算法对原始时序数据压缩比率，能够定义为：
ρ=s’s
其中，s′代表时序数据压缩后的体量，s 为时序数据压缩前的原始体量。ρ 的转置又被称为压缩因数，而品质指数（quality indices）则是被用来表述压缩收益的指标，其定义为：
cg=100loge1ρ
2、速度：度量压缩算法执行速度，通常用每字节压缩周期的均匀执行工夫（Cycles Per Byte，CPB）。
3、精确度：又被称为失真度量（Distortion Criteria，DC），掂量被压缩算法重构后的时序数据保留信息可信度。为适应不同场景度量须要，能够用多种度量指标来确定，罕用的指标有：
Mean Squared Error：
Root Mean Squared Error:
Signal to Noise Ratio:
Peak Signal to Noise Ratio:
三 压缩算法
目前罕用的时序数据压缩算法次要有以下几种：
1) Dictionary-Based (DB)
1.1. TRISTAN
1.2. CONRAD
1.3. A-LZSS
1.4. D-LZW
2) Functional Approximation (FA)
2.1. Piecewise Polynomial Approximation (PPA)
2.2. Chebyshev Polynomial Transform (CPT)
2.3. Discrete Wavelet Transform (DWT)
3) Autoencoders:
3.1. Recurrent Neural Network Autoencoder (RNNA)
4) Sequential Algorithms (SA)
4.1. Delta encoding, Run-length and Huffman (DRH)
4.2. Sprintz
4.3. Run-Length Binary Encoding (RLBE)
4.4. RAKE
5) Others:
5.1. Major Extrema Extractor (MEE)
5.2. Segment Merging (SM)
5.3. Continuous Hidden Markov Chain (CHMC)
1 Dictionary-Based (DB)
DB 算法实现理念是通过辨认时序数据都存在的雷同片段，并将片段定义为原子片段并以更精简的标识标记代替，造成字典供应用时以标识作为 Key 复原，这种形式可能在保障较高数据压缩比的同时，升高错误率。此技术实现的压缩可能是无损的，具体取决于实现状况。此架构的次要挑战是：
- 最大限度地进步搜寻速度，以便在字典中查找时间系列片段；
- 使存储在 dictionary 中的工夫串段尽可能个别，以最大限度地缩短压缩阶段的间隔。
TRISTAN 是基于 DB 策略实现的一种算法，TRISTAN 算法把压缩划分为两个阶段解决，第一阶段适应性学习，第二阶段数据压缩。在学习阶段，TRISTAN 字典表通过学习训练数据集来生成，或者联合专家教训定义特定模式的原子片段。有了字典表，在压缩阶段 TRISTAN 算法执行从以下公式中检索 w 的过程。
s=w·D w ∈ {0,1}k
其中，D 是字典表，s 为原子片段，K 是压缩后的时序表征数据长度。TRISTAN 解压过程则是通字典表 D 解释表征数据 w 失去原始时序数据的过程。
CORAD 算法在 TRISTAN 根底之上减少了主动数据关联信息，对两两时序数据片断进行基于 Pearson 相关系数的度量，以相邻矩阵 M 存储相关性，通过 M 与字典表 D 相结合的计算形式，进一步晋升压缩比和数据解压精确度。
Accelerometer LZSS（A-LZSS）算法是基于 LZSS 搜寻匹配算法的 DB 策略实现，A-LZSS 算法应用 Huffman 编码，以离线形式通过统计数据概率分布生成。
Differential LZW (D-LZW)算法核心思想是创立一个十分大的字典表，它会随着工夫的推移而增长。一旦字典表被创立，如果在字典表中发现缓冲区块，它就会被相应的索引替换，否则，新方块将插入字典作为新的条目。减少新的缓存区块是在保障非涣散压缩的准则下实现，并不限度减少的数量，但随之而来的问题就是字典表有可能有限收缩，这就导致 D -LZW 算法只实用于特定场景，比方输出时序数据流为无限词组或可枚举字符集组成。
Zstandard（zstd）是一种基于 Huffman 编码 Entropy coder 实现的疾速非涣散 DB 压缩算法，字典表作为一个可选选项撑持参数管制开启敞开。算法实现由 Facebook 开源，反对压缩速度与压缩比之间的按需调整，可能通过就义压缩速度来换取更高压缩比，反之亦然。相比同类算法，zstd 算法性能可参考下表数据。
表 zstd 算法性能比照
2 Function Approximation (FA)
函数近似类时序压缩算法 FA 的次要设计思维是假如工夫序列能够示意为工夫函数。因为难以避免呈现无奈解决的新值，找出可能精确形容整个工夫序列的函数是不可行的，因而咱们能够将工夫序列划分成多个片段，对每个段找到一个近似工夫函数来形容。
因为找到一个能残缺形容工夫序列的函数 f:T → X 是不可行的，因而实现上咱们须要思考找出一个函数簇，以及其对映的参数来形容分段时序数据绝对可行，但这也使得压缩算法为涣散的实现。
相比之下，FA 类算法长处是它不依赖于数据取值范畴，因而不须要有基于样本数据集的训练阶段，如果采纳回归算法，咱们只须要独自思考划分好的单个工夫片段。
Piecewise Polynomial Approximation (PPA)是 FA 类算法的罕用实现，此技术将工夫序列分为固定长度或可变长度的多个段，并尝试找到靠近细分的最佳多项式表述。只管压缩是有损的，但能够先于原始数据的最大偏差进行修复，以实现给定的重建精度。PPA 算法利用贪心的办法和三种不同的在线回归算法来近似恒定的函数、直线和多项式。
Chebyshev Polynomial Transform (CPT)实现原理与 PPA 算法相似，只是改良了反对应用不同类型多项式的能力。Discrete Wavelet Transform (DWT)应用 Wavelet 小波转换对时序数据进行转换。Wavelet 是形容起止值都为 0，两头值在此之间稳定的函数，
3 Autoencoders
Autoencoder 是一种非凡的神经网络，被训练生成用来解决时序数据。算法架构由对称的两局部组成：编码器 encoder 和解码器 decoder。在给定 n 维时序数据输出的前提下，Autoencoder 的编码器输入 m（m<n）维的输入。解码器 decoder 则能够将 m 维输入还原为 n 维输出。Recurrent Neural Network Autoencoder (RNNA)是 Autoencoder 的一种典型实现，通过 RNN 来实现对时序数据的压缩表述。
图 Autoencoder 算法实现构造
4 序列化算法 Sequential Algorithms（SA）
序列化算法 SA 实现原理是程序交融多种简略压缩技术实现对时序数据压缩，罕用技术有：
- Huffman coding：编码器创立一个字典，将每个符号关联到二进制示意，并以相应的示意替换原始数据的每个符号。
- Delta encoding：此技术对指标文件进行编码，以解决一个或多个参考文件。在工夫系列的特定状况下，每个元素在 t 被编码为∆（xt,xt=1）。
- Run-length encoding：在此技术中，每个运行（间断反复雷同值的序列）都与对（vt, o）进行子图，其中 vt 是工夫 t 值，o 是间断产生次数。
- Fibonacci binary encoding：此编码技术基于 Fibonacci 序列实现。
Delta encoding, Run-length and Huffman (DRH)算法是一种交融了 Delta encoding、Huffman coding、Run-length encoding 和 Huffman coding 四种技术的压缩算法，算法实现是非涣散的且计算复杂度绝对较小，适宜在边缘短实现对数据的压缩解压，也因而适宜利用在物联网、工业互联网、车联网等须要边缘短采集解决时序数据的场景。
Sprintz 就是一种专门针对物联网场景设计的 SA 算法，在算法设计中思考了对物联网场景中能源消耗、速度等时序指标稳定法则因素，为以下需要而特地优化了算法设计：
1）对较小片段数据的疾速解决
2）底计算复杂度的压缩、解压缩，以适应边缘端无限的计算资源
3）对实时采集时序数据的疾速压缩、解压缩
4）非涣散压缩
为了在解决 IoT 物联网环境时序数据上获得更好的压缩成果，Sprintz 算法通过预测数据生成趋势的形式来晋升算法对数据的压缩性能，其次要实现的算法过程包含以下几局部：
1）预测：基于 delta encoding 或 FIRE 算法通过统计历史时序数据，对新样本数据生成法则进行预测；
2）Bit packing：打包预测错误信息数据和包头形容用来解压数据的信息；
3）Run-length encoding：如果压缩过程中通过预测算法未发现任何错误信息，则略过 bit packing 过程的错误信息发送，并在下次产生谬误时在打包预测错误信息的包头中记录略过的数据长度；
4）Entropy coding：用 Huffman coding 对 big packing 生成的包文件进行编码。
Run-Length Binary Encoding (RLBE)算法 也是一种为 IoT 物联网场景下数据压缩解压，适应物联网边缘端无限计算、存储资源环境的罕用非涣散 SA 时序数据压缩算法，RLBE 算法交融了 delta encoding，run-length encoding 和 Fibonacci coding 三种技术，其执行过程如下图所示。
图 Run-Length Binary Encoding (RLBE)算法执行过程图示
RAKE 算法原理是通过检测时序数据稠密性来实现对数据的压缩。RAKE 为非涣散压缩，执行过程包涵预处理和压缩两个次要过程。预处理过程中，RAKE 算法设计由字典表来转换原始数据。压缩过程则对预处理的输入数据进行稠密性检测，压缩相邻的雷同数据。
5 其余类型算法
Major Extrema Extractor (MEE)算法通过统计指定时间段的时序数据最大、最小值来对数据进行压缩。Segment Merging (SM)算法则把时序数据抽象为工夫戳和值及偏差组成的片段，可用元组 (t,y,δ) 表述，其中 t 为开始工夫，y 是数值常量标识，δ 是数据片段偏差。Continuous Hidden Markov Chain (CHMC)算法则利用马尔可夫链概率模型来将时序数据定义为一系列无限状态节点汇合 S 及链接节点的状态迁徙概率边汇合 A。
四 总结
时序数据是物联网、工业互联网、车联网等场景下生成数据总量中占比最高的数据类型，无效的压缩算法岂但能够升高数据存储老本，同时能够在边缘到核心，核心到云的数据传输过程中节约网带宽资源，升高数据同步工夫。对于作为时序数据外围存储中枢的时序数据库，压缩算法性能更是至关重要。阿里云多模数据库 Lindorm 外围数据库引擎之一时序引擎 Lindorm TSDB 内置的自研、高效数据压缩算法针对物联网、工业互联网、车联网等智能、互联场景针对性优化，进一步晋升了时序数据存储的 ROI，新一代云原生智能互联零碎提供必要撑持。
原文链接
本文为阿里云原创内容，未经容许不得转载。
