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

前语

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

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. 在这里，我预设这个值为10510^5105，将这个经度乘以10510^5105，得到： -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表中对应的字符：

`~oia@

综上，一个浮点数被编码成了一串字符串，而且自带分隔符。关于时刻戳这样的长整型来说，不进行第1步也能够编码为一串字符串，那么，将经度、纬度和时刻戳的编码拼接起来就能够组成一个轨道点的编码，还不必额外的分隔符。 其实假如独自对一个数字来说，这个方法的紧缩率并不高，有时候还会因小失大。比方上述的数字-179.9832104，运用这种方法紧缩后成为5个字符，占5个字节。假如将直接乘以10510^5105，能够直接用有符号的整型表明，还只占4个字节呢！所以，这个算法还有一个思维便是：后一个值用其与前一个值的差值表明，由于差值比较小，所以在上述的第5步时能够将高位的零放弃掉，节省空间。下面是Google地图开发渠道中给出的比如（这个比如中没有带时刻戳）：

能够看到，这个比如中除了第一个轨道点存储时全量信息（完整的经纬度数据）之外，后面的轨道点都是存储的相关于前一个轨道点偏移量。

解码

解码其实就比较简单了，相当于把编码过程倒过来履行一遍。编码中的过程4能够使得我们在解码时知道这个数字是正数仍是负数，过程7能够让我们知道数字的鸿沟在哪，所以仍是比较便利解码的，我在此就不再赘述解码过程了。

Talk is cheap, show me the code

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