技术

轨迹压缩算法(Polyline encoding algorithm)探究

GIS, Google, 算法, 轨迹

前言

文中的代码表达采用Java，如果不想看原理，可以直接跳到博客末尾，有我写的一个Java版的demo
一般来说，轨迹是由若干个轨迹点组成的数组来表达的，每个轨迹点可以表达为 $p = (x, y, t, A)$。其中 $x, y$ 是其空间坐标（一般来说，空间坐标用经纬度表示，即$x$一般对应经度(longitude)，$y$一般对应纬度(latitude)），$t$是记录这个轨迹点的时间戳(Timestamp), $A$则是这个轨迹点的属性。如果只想保留一个轨迹点最基本的信息，则只需要保留其空间信息和时间信息，即可以将一个轨迹点表示为 $p = (x, y, t)$。在写代码时，一个轨迹点的类型可以定义如下：

1
2
3
4
5
class PointTs {
    double lng;
    double lat;
    long timestamp;
}

而这样保存一个轨迹点，$x$和$y$一般使用double类型，$t$一般使用long类型，再加上至少3个字符的分隔符（分隔x,y,t和每个轨迹点），一个轨迹点就要占 Double.SIZE * 2 + Long.SIZE + Character.SIZE * 3 == 27 * Byte.SIZE, 也就是说保存一个轨迹点至少需要占27个字节。在如今轨迹数量越来越大的情况下，有必要使用轨迹压缩的算法来解决轨迹数据量过大的问题。在查阅了资料后，我在Google地图开发平台中看到了Google采用的轨迹数据压缩算法，名为Polyline encoding algorithm（需要科学上网），可以将若干个轨迹点编码成一串字符串，并且实现轨迹的压缩。这是一个有损的压缩算法，并且可以压缩有符号的数字。
接下来我将从编码和解码两个方面解析这个算法，并给出示例代码。

编码

Polyline encoding算法的核心思想是对一个浮点数进行压缩，比如说，有一个经度为：
-179.9832104

对于这样的浮点型数字，首先需要做的是想办法去掉其小数点。所以，可以预设一个10的整数倍的值来与这个浮点数相乘，并取得整数。

  1. 在这里，我预设这个值为$10^5$，将这个经度乘以$10^5$，得到：
    -17998321

  2. 将上一步得到的整数转换成二进制，由于我们的值是负数，得到的是17998321的补码：
    11111110 11101101 01011110 00001111

  3. 将二进制数左移一位：
    11111101 11011010 10111100 00011110

  4. 如果原来的数是负数，则取反码：
    00000010 00100101 01000011 11100001
    3、4两步的目的是为了区分正负数，这样做后，负数的最后一位都是1，正数的最后一位都是0

  5. 从右到左，每5位分为一组（一组称为一个chunk）：
    00001 00010 01010 10000 11111 00001
    这样可以舍弃高位的0，节约空间。

  6. 将这些分组顺序反转（reverse order）：
    00001 11111 10000 01010 00010 00001
    这样做的目的是在写代码时可以每次从低位取数据，更适合代码实现。因为一般而言，写代码读二进制时，读高位比较复杂，而读低位较简单（例如，读最后五位只需要 &0x1F），读到最后几位后可以直接append到结果中，不用插入到结果的前端，效率更高。

  7. 除了最后一个chunk，其他chunk和0x20进行或操作：
    100001 111111 110000 101010 100010 000001
    这一步的目的是保证只有最后一个chunk是小于0x20的。起到了分隔的作用。

  8. 分别将每个二进制的chunk转化为十进制的数字：
    33 63 48 42 34 1

  9. 对每个数字都加上63：
    96 126 111 105 97 64
    由于ASCII码前63位中有很多不可显示的控制符（比如NULL、换行符之类的），并且第127个是删除符，所以这一步将数字范围控制在了64~126之间。

  10. 将数字转化成ASCII表中对应的字符：

1
`~oia@

综上，一个浮点数被编码成了一串字符串，并且自带分隔符。对于时间戳这样的长整型来说，不进行第1步也可以编码为一串字符串，那么，将经度、纬度和时间戳的编码拼接起来就能够组成一个轨迹点的编码，还不用额外的分隔符。
其实如果单独对一个数字来说，这个方法的压缩率并不高，有时候还会得不偿失。比如上述的数字-179.9832104，使用这种方法压缩后成为5个字符，占5个字节。如果将直接乘以$10^5$，可以直接用有符号的整型表示，还只占4个字节呢！所以，这个算法还有一个思想就是：后一个值用其与前一个值的差值表示，由于差值比较小，所以在上述的第5步时可以将高位的零舍弃掉，节省空间。下面是Google地图开发平台中给出的例子（这个例子中没有带时间戳）：

图1 Example of polyline encoding

可以看到，这个例子中除了第一个轨迹点存储时全量信息（完整的经纬度数据）之外，后面的轨迹点都是存储的相对于前一个轨迹点偏移量。

解码

解码其实就比较简单了，相当于把编码步骤倒过来执行一遍。编码中的步骤4可以使得我们在解码时知道这个数字是正数还是负数，步骤7可以让我们知道数字的边界在哪，所以还是比较方便解码的，我在此就不再赘述解码过程了。

Talk is cheap, show me the code

原理知道了之后，代码就比较简单了，贴一个我写的代码：
SimpleTrajectoryCompressor

分享到