1前言
1.1 背景
随着定位技术的发展和移动设备的普及，海量轨迹数据在源源不断产生。例如， 在 2019 博世智能出行大会上，滴滴旗下小桔车服车联网业务负责人黄智信表示，滴滴大概每天处理超过 106TB 的轨迹数据。此外现在人们的生活离不开智能手机，而手机产生的信令数据也可以视为人们的移动轨迹数据。面对这海量的数据，为了减少存储占用以及传输时间，我们选择将其进行压缩。
数据压缩算法分为有损压缩和无损压缩两种，前者会有一定的信息损失，是一个不可逆的过程；后者压缩后的数据可以完全恢复。但在数据库系统、热力图展现、人员追踪等应用中，不能够轻易地有信息的损失，这就需要做到无损压缩。
最简单的轨迹数据包含时间信息和空间信息两部分，接下来本文将介绍一些时间信息和空间信息的无损压缩算法。
1.2 时序数据特点
在轨迹数据中，一部分为时序数据。由于轨迹的 GPS 点采样率基本上是固定的，所以轨迹数据中的时间部分之间的间隔多数为定值。我们可以利用这个特点来进行轨迹压缩。但是也存在以下三种情况会影响我们的压缩：
① 噪声点。由于 GPS 设备的误差，可能会导致采样的时间发生变化，影响时间数据的计算。但是对于不同应用来说，噪声点的判断也是不同的。我们的目标是将数据进行无损压缩，所以我们不能简单地直接将可能的噪声点去除，也需要将其进行保留。增加了压缩算法设计的难度。
② 采样点缺失。我们收集到的 GPS 点可能会有部分缺失的情况。例如汽车在通过隧道路段时，由于 GPS 信号不佳，可能收集到的轨迹数据在隧道路段缺失 GPS 轨迹点。这就会导致这一段的轨迹点时间间隔较大，但是经过这一路段前后的采样率是相同的。这种波动也会影响我们的轨迹压缩。
③ 采样率变化。有些定位设备可能在不同情况下的采样率不太相同，例如汽车在停车的状态下，为了减少存储空间的占用，车辆上的定位设备会将采样率调整为较大间隔。这种采样率的改变也会影响压缩的效果。
1.3 空间信息特点
轨迹数据另外一部分重要的信息是空间数据，轨迹的空间数据由每个 GPS 点的经纬度信息构成。物体移动的速度有限，在采样率较小的情况下，空间变化也较少。我们需要尽可能地利用这个特征。但是相较于时间信息，空间信息的压缩更为困难，主要有以下几个方面：
①难以找到轨迹的经度和纬度的变化特点。由于每个轨迹的移动方向移动速度都难以准确地计算出，导致难以将二者有效地联系起来进行压缩。经度序列和纬度序列中相邻的 GPS 点变化也不确定。
②数据类型不易压缩。由于经纬度在存储时一般为高精度的 Double 类型数据，相比于整型数据更难处理。Double 类型数据在底层二进制表示时比较复杂，有着尾数、指数、符号位三部分，计算起来复杂，而且计算后也并不一定有着很好的压缩效果。因为上述原因，这部分相关的现有研究较少。
2 时间信息压缩
2.1 Delta 算法
我们可以发现，一条轨迹数据上 GPS 点的相邻时间信息相差不大。因此，我们考虑采用通过记录相邻 GPS 点时间信息的差值来代替时间信息。时间信息的差值为小整数，时间信息为大整数，以小整数编码代替大整数编码，从而实现对时间信息的压缩。
如表1所示，左列时间戳为GPS点的实际时间信息，右列delta为相邻两个时间戳信息的差值。存储时间戳的第一个时间信息以及其他时间戳所对应的delta，从而实现时间信息的压缩。解压时只需要依靠前一个时间戳就可以得到当前时间。
这种压缩算法简单易懂，其中每个delta的存储位数是以最大delta来确定的，是一种定长的存储，会造成不必要的空间浪费。因此可使用Protobuf [6]变长编码来进行存储，来进一步提高压缩效率。
2.2 Delta of Delta 算法
由于轨迹数据中GPS点的采样率基本恒定，所以相邻GPS点的时间间隔相似，即delta 数据的差值 delta of delta相差更小，而且多为0。因此，可以实现用更小整数编码的 delta of delta [1]代替原本小整数编码 delta。
如表２所示，第３列delta of delta 是相邻两个delta的差值。存储delta of delta时，由控制位和数据位两部分组成（除0以外，或者说存储0所用的1位比特数既是控制位也是数据位）。控制位决定了接下来存储实际数值时所需的比特位数，如表3所示，这样便实现了采用变长编码的方式进行存储，来进一步减少数据存储空间。
表２ Delta of Delta压缩示例
表3 控制位对应表
2.3 TED时间数据压缩算法
TED[2]算法为轨迹数据的有损压缩算法，其中时间信息的压缩是一种无损压缩的方法，压缩率并不高，但是采用的数据省略的方式为设计轨迹数据压缩算法提供了较好的思路。
基于采样率基本恒定，GPS 点的时间信息差值多为恒定的特点。TED 的时间信息压缩算法，只需要存储采样率发生变化的 GPS 点，对于采样率不变的中间 GPS 点进行省略，解压时通过计算得到。
如表4所示，可以看到第3，第4，第6个轨迹点时间信息的delta与前一个轨迹点的delta相同；因此，在存储时，可以省略这部分轨迹点时间信息的存储。其余点存储自己对应的下标以及完整的时间数据。现每次delta值发生改变时会额外存储较多的数据，导致压缩效果明显降低。
表4 TED时间数据压缩算法
3 空间信息压缩
我们可以直观地发现，正常情况下的轨迹数据相邻GPS点的经纬度变化不大。例如，理想状态下，车辆向正北方向行驶时的经度是保持不变的。而且由于速度的限制，两点经纬度的差值较小。
对相差不大的Double类型数据进行按位异或XOR[3-5]操作，可以发现结果中多数位为0，如表5所示。我们根据Double类型的这个特点对轨迹数据中的经纬度进行处理。
在存储时，若XOR值为０，则存储1bit 0。若XOR不为０，省略前导零和尾随零，主要存储有效位，如图1(a)所示。在XOR非零时，令控制位第一位为１，若当前XOR有效位在前一个XOR有效位范围内，令控制位第二位为１并存储当前XOR的非零数值（如图1(b)所示）；若当前XOR有效位不在前一个XOR有效位范围内，令控制位第二个bit为０，接下来存放6bits的尾随零比特个数、６bits有效位特比个数以及XOR非零数值（如图1(c)所示）。
参考文献：
[1] Pelkonen T, Franklin S, Teller J, et al. Gorilla: A fast, scalable, in-memory time series database[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1816-1827.
[2] Yang X, Wang B, Yang K, et al. A novel representation and compression for queries on trajectories in road networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 30(4): 613-629.
[3]Ratanaworabhan P, Ke J, Burtscher M. Fast lossless compression of scientific floating-point data[C]//Data Compression Conference (DCC'06). IEEE, 2006: 133-142.
[4]Lindstrom P, Isenburg M. Fast and efficient compression of floating-point data[J]. IEEE transactions on visualization and computer graphics, 2006, 12(5): 1245-1250.
[5]Ratanaworabhan P, Ke J, Burtscher M. Fast lossless compression of scientific floating-point data[C]//Data Compression Conference (DCC'06). IEEE, 2006: 133-142.
