商家入驻网站建设,小程序制作费用一览表,公众号推广合作平台,学校网站建设情况说明书作者如何选择和设计编码方案#xff0c;以实现高效的解压缩和高压缩比#xff1f;BtrBlocks是否适用于所有类型的数据#xff1f;
选择和设计编码方案#xff1a;
结合多种高效编码方案#xff1a;BtrBlocks 通过选择一组针对不同数据分布的高效编码方案#xff0c;实现…作者如何选择和设计编码方案以实现高效的解压缩和高压缩比BtrBlocks是否适用于所有类型的数据
选择和设计编码方案
结合多种高效编码方案BtrBlocks 通过选择一组针对不同数据分布的高效编码方案实现高压缩比和快速高效的解压缩。基于采样的方案选择BtrBlocks 对每个编码方案在样本上进行测试并选择表现最佳的方案。采样算法在保持相邻元组的局部性和准确表示整个数据范围方面取得了平衡。级联应用方案BtrBlocks 的递归应用方法将一个方案应用于另一个方案的输出直至达到最大递归深度。
BtrBlocks 适用于所有类型的数据
支持各种数据类型BtrBlocks 用于处理有符号整数、双精度浮点数和可变长度字符串等类型的数据。针对浮点数的伪十进制编码BtrBlocks 引入了针对二进制浮点数的伪十进制编码以提高浮点数数据的压缩效果。
总之作者通过结合多种高效编码方案、使用基于采样的方案选择和递归应用方法实现了高效的解压缩和高压缩比。BtrBlocks 适用于各种数据类型包括有符号整数、双精度浮点数和可变长度字符串。
级联
级联是指将多个设备或系统按照一定的顺序连接起来形成一个整体使得每个设备或系统的输出作为下一个设备或系统的输入实现功能的递进和互补。
举个例子我们可以考虑一个音响系统的级联。假设有一个音乐播放器和一个音箱我们可以将它们级联起来。首先将音乐播放器的音频输出连接到音箱的音频输入接口上。这样在播放音乐时音乐播放器会将音频信号发送到音箱进行放大和输出从而可以听到更大声音的音乐。在这个例子中音乐播放器是级联系统中的第一个设备音箱是第二个设备它们通过级联连接起来实现了音频信号的输出和放大。
当我们连接多个电视机或显示器来同时播放相同的内容时就可以将它们级联。其中一个电视机或显示器作为主机其他的电视机或显示器作为从机它们通过HDMI或VGA线连接在一起主机的信号输出被发送到从机实现内容的同时播放。
在计算机网络中我们也可以将多个路由器级联起来。每个路由器连接着不同的局域网并且将数据包根据目标地址进行路由转发最终将数据包发送到正确的目标设备。
电子商务中的供应链管理也可以看作是级联的一个例子。产品从供应商到制造商再到批发商最后到零售商形成一个供应链网络每个环节都在前一环节的基础上进行加工、组装、配送等最终将产品送到消费者手中。
这些例子中级联的设备或系统能够实现信息、信号或物流的流动从而达到更高的功能或效果。
编码方案
RLE One Value。Run-length Encoding (RLE)是一种普遍的技术它对相等值的连续序列进行压缩。例如连续的序列{42, 42, 42}存储为(42, 3)。One Value是针对只有一个唯一值的列进行特殊优化。
Dictionary。字典编码是另一种简单但有效的方案它使用较短的编码替换输入中的不同值。一个查找结构即字典将每个编码映射到原始的不同值。用于实现字典的数据结构由编码类型确定字典通常是压缩字符串的唯一方式。
Frequency。在真实世界的数据集中通常会有一些多次出现的值形成了偏斜分布。DB2 BLU提出了一种基于数据频率的频率编码使用多个代码长度。例如一个一位编码可以表示两个最频繁的值一个三位代码可以表示接下来的八个最频繁的值依此类推。通常一列只有一个主导的频繁值其次频繁的值出现的频率呈指数下降。本文针对这种情况进行了优化只存储1最频繁的值2标记哪些值是最频繁值的位图3不是最顶部值的异常值。
FOR Bit-packing。对于整数参考框架Frame of ReferenceFOR将每个值编码为相对于选定基值的增量。例如序列{105, 101, 113}我们可以选择基值为100然后存储{5, 1, 13}。这在与Bit-packing结合使用时很有用后者截断不必要的前导位可以使用4位而不是8位对每个值进行Bit-packing。但是基本的FOR方案在处理离群值时效果不佳。例如向示例序列添加118这种情况下每一个值都需要5位来表示。因此Patched FOR (PFOR)将这些离群值存储为异常并保留其余值的较小位宽。SIMD-FastPFOR和SIMD-FastBP128构建在这个想法上并专门为SIMD单指令多数据优化了算法和布局。在BtrBlocks中使用这些现有的高性能实现。
FSST。Fast Static Symbol Table (FSST)是一种用于字符串的轻量级压缩方案因为真实世界中大部分的数据都以字符串形式存储。FSST通过将长度最多为8个字节的频繁出现的子字符串替换为1个字节的编码来实现压缩。这些编码在一个固定大小的255条目字典符号表中进行跟踪。符号表是不可变的并且用于整个字符串块。解压缩是简单且快速的但是压缩时需要找到一个合适的符号表所以较为复杂。
NULL Storage Using Roaring Bitmaps。BtrBlocks使用Roaring Bitmap存储每列的NULL值。Roaring 的背后思想是根据位的局部密度使用不同的数据结构这使得它对于许多数据分布非常高效。BtrBlocks使用一个针对现代硬件进行了优化的开源C库来实现Roaring Bitmaps。除了追踪NULL值之外BtrBlocks还使用Roaring Bitmaps来追踪内部编码方案例如频率编码的异常情况。
三. 方案选择和压缩
方案选择算法。针对不同数据类型本文提供了不同的编码方案以适合各种不同的数据分布。但存在一些挑战一种更好的编码方案选择是使用抽样。为了更好的压缩样本必须捕获与压缩相关的数据集特征。例如随机抽样可能不能很好地检测RLE是否有效。另一方面简单地取第一个k个元组就可能会得到一个有偏差的样本。方案选择算法的另一个挑战是要考虑级联即它必须决定是否对已经编码的数据进行二次编码。编码后的数据作为新的输入然后尝试是否可以继续编码
解决方案。在BtrBlocks中将在每一个样本中测试每种编码方案并且选择性能最好的方案。给定一个要压缩的数据块每个递归级别都执行以下步骤
1收集有关该块的简单统计信息。
2基于这些统计数据过滤不可行的编码方案。
3对于每个可行的方案使用数据中的一个样本来估计压缩比。
4选择观测压缩比最高的方案并以此压缩整个块。
5如果压缩的输出为可压缩格式则重复步骤1。
3.1 样本压缩率评估
为了让每个数据块选择最佳方案样本必须代表数据的特征。主要是需要保留空间局部性以及捕捉到唯一值的分布而且开销尽可能要低。如图1所示文章从数据的非重叠部分的随机位置选择多个小runs。对于64,000个值的块大小文章使用每个包含64个值的10个runs从而得到1%数据的样本大小。 图1 从一个列块中选择一个随机的样本
估计压缩比。BtrBlocks首先通过一次遍历收集诸如、、唯一计数和平均运行长度等统计数据。基于这些统计数据然后应用启发式方法来排除不可行的方案。然后BtrBlocks使用每个可行的编码方案对样本进行压缩以估计每个方案的压缩比。
3.2 级联
递归应用方案。在选择了一个压缩算法之后压缩后的数据或其中的一部分可能会使用不同的方案进行压缩。如图所示递归点表示额外的可能压缩步骤。用于额外步骤的方案再次使用我们的压缩比估算算法进行选择。递归的最大次数默认为3。一旦达到这个递归深度BtrBlocks 将不再进行压缩。 图2 递归应用的编码方案决策树
编码方案池。结果是一个通用的、可扩展的级联压缩框架它从任意编码方案的池中进行选择。方案池显著影响BtrBlocks的整体效果有了更多的方案压缩速度变慢因为需要评估更多的样本但压缩比增加。添加更多的重型方案可能也会提高压缩比但减慢解压缩速度。
意思就是说D,S,I等三种类型是可以继续压缩的在递归中会遇到不可压缩的为递归终点以及递归深度超过3时自动终止
四. 伪十进制编码
过去对关系型数据库中浮点压缩的研究非常少。这有一个历史原因关系系统通常将实数表示为小数或数值可以物理地存储为整数。然而随着数据湖的转移以及随后与非关系系统的集成这种情况正在改变例如Tableau的内部分析DBMS将所有实数编码为浮点数而机器学习系统几乎完全依赖浮点数。
文章设计了一种专门为二进制浮点数设计的压缩方案即伪十进制编码Pseudodecimal Encoding。
4.1 压缩浮点数
挑战1物理上的IEEE 754表示导致许多压缩方法不适合2一些十进制数不能用二进制精确表示如0.99实际存储的值是0.98999...。
浮点数表示为整数元组。伪十进制编码使用十进制表示法对双精度浮点数进行编码。它使用两个整数进行表示带符号的有效数字和指数。例如3.25变为(325, 2)就像325 × 10^(-2)一样对于0.99只需要存99, 2而不用存98999...17。
算法细节。伪十进制编码算法通过测试所有10的幂并检查它们是否正确地将双精度浮点数乘以一个整数值来确定紧凑的十进制表示。首先在一个静态表中存储10的幂的倒数以避免为每个数字重新计算它们。其次为解决-0、lnf和NaN问题算法将其作为补丁存储。同时将数字和指数的位数限制为32和5。这些属性确保编码比特位相同。
4.2 BtrBlocks中的伪十进制编码
级联到整数编码方案。伪十进制编码将一个浮点数列转换为两个整数列和一个小的异常列。BtrBlocks可能会再次使用级联压缩对这些列进行编码
图3 伪十进制编码示例
图中所示的级联压缩选择只是示例而不是固定的BtrBlocks使用其先前描述的采样算法来选择方案。
何时使用伪十进制编码。有些数据不适合使用伪十进制编码比如包含许多异常值的列伪十进制编码略微提高了压缩比但由于存在许多异常值解压缩速度较慢。因此BtrBlocks对那些具有超过50%不可编码异常值的列禁用该方案。同样具有很少唯一值的列通常使用字典几乎可以实现同样好的压缩效果而字典具有更高的解压缩速度。因此在BtrBlocks的上下文中选择在具有少于10%唯一值的列中排除伪十进制编码。
RLE代码
import java.util.*;public class Main {private static ListMap.EntryInteger, Integer RLE(int[] nums) {if (nums null || nums.length 0) {return new ArrayList();}ListMap.EntryInteger, Integer result new ArrayList();int count 1;for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1]) {count;} else {result.add(new AbstractMap.SimpleEntry(nums[i - 1], count));count 1;}}result.add(new AbstractMap.SimpleEntry(nums[nums.length - 1], count));return result;}public static void main(String[] args) {int[] nums {11, 11, 10, 999, 999, 999};ListMap.EntryInteger, Integer encoding RLE(nums);for (Map.EntryInteger, Integer entry : encoding) {System.out.println(( entry.getKey() , entry.getValue() ));}}
}
