??标题还说，一个关于压缩时间序列数据的经典重复数据删除的改进版本，可以随机访问压缩数据而不减少压缩；

期刊：IEEE INFOCOM 2020 A类

??目前，它不仅仅是为了存储而压缩，有时是为了应用程序的持续访问，所以设计方法是连续低成本随机访问压缩数据，避免压缩；特别是对于时间序列，大量压缩存储，大大提高了随机访问成本； ??可以看出，这种压缩后数据的随机访问技术应该相对较少，其中大部分是字符串；作者也很新颖，改变了场景，选择分析时间序列数据；

1. 由于可以实现支持随机访问的无损压缩，因此也必须实现有损压缩。此外，工业互联网上的数据也是可行的。本文根据相关性对偏差进行排序，因此如果我进行无损压缩，我也可以从这一块开始，考虑不同的方式或直接丢弃一些相关性差，以达到更高的压缩率；
2. 或提出无损压缩与有损压缩相结合的方法；
3. 这里的训练数据必须在一定程度上代表数据的结构，而实际的工业数据集不一定符合这样的条件；

• F表示没有压缩，F_c表示压缩；
• 文件是一系列二进制数字，可以使用 V=[v₀,v₁,…v_n-1]表示；V_a^b=[v_a,v_{a 1},…,v_b]；
• 数据块用z∈Z表示（Z它是所有可能块的集合)，使用转换函数φ(z)文件块z∈Z => （x,y）∈ X x Y；其中x是z的基base，而y是z的偏差deviation；

??当存储过程类似于经典的重复数据删除时Client上传一个文件时，会被分成几个块，转换函数不会立即存储块，而是对每个块应用变换函数，得到（基，偏差），Server删除基础应用的重复数据，确保每个基础只存储一次，偏差完全存储在基础上ID旁边，方便原块的恢复；

??如果所选的转换函数将几个类似的块转换为单个基础和不同的（小）偏差，则广义重复数据消除将获得压缩增益；最佳转换函数将取决于数据的结构，首先考虑一个简单的转换函数： ??相当于用z的前k位作为基础，剩下的n-k位将是偏差；即z∈F₂ⁿ，x∈F₂^k，y∈F₂^n-k；

??φ^-1(φ(z))=z，这是可逆的，适用于无损压缩；其次，为了增加匹配字符的数量，使用替换Permutation前面的方法n-k字符放在最后；

需要确定的参数包括：

• 每个数据块连接的样本数，即c ；
• 存储偏差位置的索引集合 Ι ；

??使用数据开始时的训练数据来完成，显然，训练数据必须在一定程度上代表数据的结构，假设第一个文件包含N作者的参数估计将使用一个样本。N1>10⁶作者将样本限制在这个数量上，以保持预处理阶段的计算易于处理。每个样本都是由n_s位组成。样本应该是一个时间序列数据文件的行数，也就是样本不超过10个⁶行；

??第一个关键参数是连接形成每个数据块的样本数，用c表示。连接的最佳样本数量将取决于相邻样本之间的相关性；每个样本的基础使用的比例较少，从而减少了相关费用。另一方面，连接过多的样本会降低匹配基的概率，因为它们需要在更多的位置相等，所以整体匹配可能会更少。

??此外，当每个块由更多的样本形成时，固定数量的样本会导致更小的块；块是固定多少样本块连接在一起，然后通过块应用转换函数获得基础和偏差。如果多个块的基础相同，删除重复的基础，只保留偏差；

??因此，正确的样本数量显然取决于数据集，应该从中推断出来。作者提出了这个参数C应该是什么算法1启发算法。这个过程是迭代的，越来越多的样本被连接起来，直到几乎所有的块都是唯一的；允许一小部分重复块，d=0.01；C确定后，每个块的长度为n=cn_s位； ??接下来，必须确定用于偏差的位数，即变换函数φ_k的k值，k是基础的大小，偏差是n-k。作者希望最大化匹配基的位数偏差包括与块的其他部分最不相关的位置 ，基数越大，偏差位数越小，因为两者之和是n；作者可以通过估计位集之间的相互信息来捕获这一点，并使用训练数据来找到皮尔逊之间的相关性（只捕获线性相关性）。估计相关矩阵后，块的位置按最大绝对相关性排序；

??培训集的存储消耗如下：k是基的大小，K基数不同，N是块的个数； 所有块： 第一步:以整个块为基础，这样n=k；通过计算唯一基数来评估S_n； 第二步:删除相关性最小的位置，使基础长度为n-1；重新计算唯一基础的数量和存储费用S_n-1； 第三步:重复第二步直到 S_n-i-1>=S_n-i，说明此时消耗最低，基础长度为k=n-i，偏差长度为n-k=i； 第四步:最后，将之前删除的I个最不相关位置的索引形成集合 I={i₁，i₂，i₃…i_n-k}；如果他指定使用哪些位置作为偏差，实际上是集合 I 相应的位置作为偏差；(这样理解，比如块1和块2对应0号基，说明块1和块2是一样的 k 位，剩下的不一样n-k作为偏差存放在基旁边 => 0号基 偏差1 0号基 偏差2，因为每个块的I是一样的，因此，根据集合I可以拔最终n-k插入回去，恢复)

??若发生事件S_n<S_n?1，广义重复数据消除方法将被用作经典重复数据消除的特殊情况。也就是说，回到经典的重复数据删除，并使用它n=k，即c=1，n?k=以整个块为基础；

疑惑:如何找到块中位对之间的相关性？显然，块中只有一个序列，显然不可能检验单个二进制序列的相关性 相反，作者使用训练数据来找到皮尔逊之间的相关性。虽然这只捕获了线性和成对的相关性，但它捕获的信息与文献[25]基本相同。在估计相关矩阵后，块的位置根据最大绝对相关性进行排序？

??这一步涉及浏览所有文件来计算每个基础的使用次数。这使得作者可以通过计算每个基础的频率来估计基础的分布；这也可以用来定义基础ID熵编码方案，即对常用基进行少位编码，Huffman这可以进一步提高整体压缩能力，因为基础ID存储空间较少。

??然而，它会影响整体压缩速度和随机访问性能，因此只有当整体压缩速率比随机访问性能更重要时才应使用此步骤。一般来说，如果基础的使用分布远不均匀，这一步可以最大限度地提高压缩效果，因为大量使用的基础会很短ID，很少有碱基会得到很长的碱基ID。若分布均匀，则难以获得增益。为了解码，还需要将霍夫曼表以类似于解冻算法[27]的方式紧于解冻算法[27]的方式紧密存储；

??最后一步是实际执行文件的压缩，在算法2中详细说明了这些文件的压缩。每一始到结束，每个文件都以流动的方式处理，一次处理一个块。若文件不能分成整数块，则使用零填充形成最后一块。对于每个块，首先识别基础和偏差，然后找到特定的基础ID。如果基础不存在，首先将其添加到基字典D中，并分配下一个可用的整数。从0开始，它将被用作它ID。因此，第一个基得到整数0，第二个基得到1，以此类推。一旦确定了ID并更新字典，将处理下一个块。在处理了原始文件中的所有块后，作者决定需要多少位来表示基础id。基本id可以用?log₂Kⁱ?位表示； ??K⁽ⁱ⁾是将文件 i 将基数添加到字典后的基数中。最后，产生压缩输出。它首先有一个编码 l⁽ⁱ⁾ 需要解码的编码。然后它遵循交替结构，每个块匹配r_j⁽ⁱ⁾位的基ID旁边还有；

??此外，还必须存储字典D，它的储方式使得文件的前k位包含ID为0的基，下面的k位包含ID为1的基 => Base dictionary，以此类推。因此，存储在系统中的数据的压缩结构如图3所示；

• N_i表示第i个文件的样本数
• K_i表示第i个文件基的个数；
• l⁽ⁱ⁾表示第i个文件基的ID的位数，采用Elias-gamma编码，占用γ(l⁽ⁱ⁾)位；
• y_j⁽ⁱ⁾表示第i个文件第j个块的n-k 位的偏差 ；
• r_j⁽ⁱ⁾表示第i个文件第j个块所匹配的基的ID；

  要以在线方式使用该方案，可以在接收数据时动态存储字典。有两种简单的方法来实现这一点，一是定期将流分解为文件，并单独处理；另一种方法是将ID的长度设置为全局参数，以便在识别ID时立即保存；

首先，恢复压缩的状态。然后，解码文件；

加载预处理阶段存储的参数n_s、c存储和 I。块长度n必须是c*n_s位；作者也可以立即推断出n−k=|I|，这意味着k=n−|I|。作为最后一步，作者准备好了字典D，因为基的组织是已知的，字典文件中的第j个k位块对应于ID为j−1的基。字典要么全部加载到内存中，或者所需的基在需要时从字典中检索；

  文件将被逐个解压缩。所有文件都以用于表示基ID的位数的编码 l(i) 开始。虽然这个编码有可变的长度，但它很容易通过首先计算连续零的数量m来解码。下面的m+1位是l(i)的二进制编码。一旦知道该值，解码器就知道压缩序列所包含基的l(i)位ID对和（n−k）位偏差。这就能够完美地重建原始文件。该过程详细说明了算法3；

  广义重复数据删除压缩方案允许低成本的随机访问数据，在本节中，作者将详细介绍访问数据的任意位置的过程及其成本。首先，必须在访问数据的第一部分中部分恢复压缩机状态，也就是说，在预处理阶段存储的参数ns、c和I将被加载。n和k是由这些方法计算出来的，因为它们对理解压缩表示是至关重要的。

  本节中所述的成本大多假设为最坏情况，即只对数据进行一次访问，后续访问的开销显然会更小，因为可以重用来自以前的访问的状态，状态只需恢复一次；

  给出访问任何特定块的过程，假设所需的块是z_j⁽ⁱ⁾，即文件F(i)的第j个块；第一步是加载l⁽ⁱ⁾，即用于表示压缩文件F_C⁽ⁱ⁾中基的ID的位数。该值的 Elias-gamma 编码位于F_C⁽ⁱ⁾的开头，并占用γ(l⁽ⁱ⁾)位，必须访问所有这些位才能解码该值，是有分隔符的，便于得到l⁽ⁱ⁾。然后，每个块都有一个使用精确的 l⁽ⁱ⁾+(n−k) 位的压缩表示，并且块以与原始文件相同的顺序出现。因此，块j的比特从这开始： 在这里结束： 因此总共需要访问：

  压缩格式还允许更细粒度的随机访问模式。可以从原始数据中访问任何特定的位。此访问的成本取决于该位是编码为块的基数还是偏差的一部分。现在将评估这两种情况：

  假设作者想知道第i个原始文件F⁽ⁱ⁾中的位a的值。与访问整个块一样，必须首先加载l⁽ⁱ⁾，即压缩文件F_C⁽ⁱ⁾中用于表示基id的位数。这仍然需要访问γ(l⁽ⁱ⁾)位，即该值的Elias-gamma编码。文件中每个块的压缩大小：l⁽ⁱ⁾+(n−k)位现在已知。在原始文件中，位a属于⌊a/n⌋ 个块z_⌊a/n⌋⁽ⁱ⁾，它必须位于压缩文件中，与前一节中发现的位置相同，从α(⌊a/n⌋)开始到 β(⌊a/n⌋)结束；

  不像前一节那样加载整个块，而是确定位a在这个块中的位置。在原始的块中，位a一定处于a mod n 这个块中；下一步取决于该位是作为压缩中偏差的一部分还是基的一部分；

  处于偏差中：如果 a mod n ∈ I，即该位存储在偏差中；I中元素的顺序揭示了位a的位置，如果a mod n是I中的第j个元素，同样该位同样可以作为压缩块中偏差的第j个元素找到；即位a的位置为α(⌊a/n⌋)+l⁽ⁱ⁾+j，能够立即索引； 在最坏的情况下，检索位必须访问的位总数为：   处于基中：要确定比特的值，第一步是访问块开头的l⁽ⁱ⁾位，以查找ID的值 r_⌊a/n⌋⁽ⁱ⁾；ID显示哪个基与该特定的块相关联，那么该基的位应该在此区间中：[kr_⌊a/n⌋⁽ⁱ⁾，kr_⌊a/n⌋⁽ⁱ⁾+k-1]；为了找到确切的位置，作者还不能直接访问一个特定的位，因为原始块中的一些位被移动到了最后。为了最终找到感兴趣的位置，作者确定有多少位置由于排列而移动，作者用一个指示器来判断：   1{·}表示指示器函数，如果语句为true，则取1，否则则取0；总共，检索位必须访问的位数为：   与访问位于偏差中的位相比，还有一个额外的l⁽ⁱ⁾位；

• GZIP
• BZIP2
• 7-zip

将以下两点作为压缩质量进行对比：

• 压缩率CR：压缩后尺寸/压缩前
• 随机访问成本：

并没有将压缩速率作为指标；

来自不同领域的8个时间序列数据集；

  对于前6个数据集，作者的方法比GZIP的压缩比更小，但未达到Bzip2和7z；对于最后两个数据集，参数启发式式回到经典的重复数据删除，没有连接。这是作者的压缩方法在这些信号上的最佳配置，但通用方法都实现了更好的压缩；

  灰色的线分别代表c=1、c=2……c=8，启发式方法选择的方法是c=5，n−k=17，如红星所示。可以看出，所选的配置非常接近全局最小值，验证了启发式方法是合理的。其他数据集的性能相似，所实现的压缩接近全局最小值。

这是通用压缩方法的随机访问： [5] K. Tatwawadi, S. S. Bidokhti and T. Weissman, “On Universal Compression with Constant Random Access,” 2018 IEEE International Symposium on Information Theory (ISIT), 2018, pp. 891-895, doi: 10.1109/ISIT.2018.8437931.

验证了这种可随机访问的方案的可行性： [6] V. Chandar, D. Shah, and G. W. Wornell, “A locally encodable and decodable compressed data structure,” in Annual Allerton Conf. on Communication, Control, and Computing, 2009, pp. 613–619.

对基的序号进行编码的压缩方案 [28] P. Elias, “Universal codeword sets and representations of the integers,” IEEE Trans. Inf. Theory, vol. 21, no. 2, pp. 194–203, mar 1975.

重复数据消除综述 [7] W. Xia, H. Jiang, D. Feng et al., “A Comprehensive Study of the Past,Present, and Future of Data Deduplication,” Proc. IEEE, vol. 104, no. 9, pp. 1681–1710, 2016.

广义重复消除 [9] R. Vestergaard, Q. Zhang, and D. E. Lucani, “Generalized Deduplication: Bounds, Convergence, and Asymptotic Properties,” in IEEE GLOBECOM, dec 2019.

Vestergaard, Rasmus & Zhang, Qi & Lucani, Daniel. (2019). Lossless Compression of Time Series Data with Generalized Deduplication. 1-6. 10.1109/GLOBECOM38437.2019.9013957.

BZIP2 网址：sourceware.org/bzip2/

Gzip P. Deutsch, “GZIP File Format Specification Version 4.3,” United States,1996.

7-zip I. Pavlov, “7-zip.” [Online]. Available: 7-zip.org