背景

兄弟们，之前我开发了支持联机对战的五子棋、斗地主、UNO。在大家的呼吁之下，我准备开发「象棋」啦！

😄 联机象棋马上就能跟大家见面了！

之前的进展：

• 《用SVG画一个象棋棋盘》。
• 《基于svg和ttf(字体文件)，我仅用6kb就画完了象棋所有棋子》。
• 《我用43个字符，就存下了象棋的棋盘状态》。
• 《JS实现象棋移动规则》。
• 《一种记录象棋历史记录的方案：平均每步仅占10bit位》。
• 《用JS实现平均每步仅占10bit位的象棋历史记录保存方案（encode篇）》。
• 《用JS实现平均每步仅占10bit位的象棋历史记录保存方案（decode篇）》。

今天的进展：优化了象棋历史记录encode和decode的逻辑，进一步减少了空间占用。

聊聊一些问题

现如今计算机存储已然不是瓶颈了，为什么我还执着于优化历史记录存储空间？

因为我要把所有的下棋记录序列化后存储在URL中，方便用户分享棋局。而URL长度是有限的，且为了方便分享，URL要尽可能短。

为什么不用短链服务？

因为短链服务本质上是有后端存储依赖的，当后端空间越来越大，服务器压力也会增大。且其实90%以上都是无用的数据。而开发者还不敢轻易清空。

根本原因是我不想为了保存记录而花时间和成本在服务器上。我认为利用URL把数据全部存储在客户端，记录都存在用户手里是成本最低、用户体验最好的（URL分享实在是太方便了）。

为什么还不发布象棋？

我发现了更多的压缩空间，我需要把整套存储空间压缩到我认为的极致，再发布。因为这种东西一旦发布就不能改了（如果要改，开发者必须兼容2个版本的历史记录解析器，这会是债务）。

所以我不采取逐步迭代方案，而是一步到位方案。优化到不能再优化，再发布。

为什么要用二进制表示17种可能性

在文章《一种记录象棋历史记录的方案：平均每步仅占10bit位》中我提到：车和炮有17个可移动范围，我需要用二进制来描述。

为什么是17种？象棋棋盘是9*10的，每行除了自己还剩8个位置，每列除了自己还剩9个位置。加起来是17。

17真是个不吉利的数字！

程序员最喜欢2、4、8、16。最讨厌2的n次方+1，因为我为了多存储这一种额外的可能性，不得不增加一位存储空间。

本来16种可能性，我可以用4位（2的4次方=16），但是表述17种可能性，我不得不用5位了。

今天，我发现了一种把数据量压缩到极致的方案！

如何用变长二进制数据表示17种可能性

注意，这里有个前提：变长二进制。

如果用长度固定的二进制表示，那这个题有唯一的公认最佳答案：把0-16（这是17个数字）直接转换为5位二进制即可。

方案一：经典方案，平均4.76位

这就是典型方案，除了第17个可能性用单独的1个1表示，其它的数字就是简单进制转换来的。

一共5*16+1=81位，平均每个可能性需要4.76位。

方案二：前缀可识别方案，平均4.35位

共4*8+5*8+2=74位，平均每种可能性74/17=4.35位。

可以看到，第17个可能性，是用2个1表示，剩下16个可能性，有8个用了4位二进制，有8个用了5位二进制。

最重要的是：该方案是「前缀可识别」的。（这是我自己起的名词，如果你了解编译原理，这相当于LR(0)文法）。也就是说，我们只需要从左往右遍历，就一定能获得该数据（而无需探测数据总长度）。

我写个decode该方案的伪代码你就知道了:

decoder 伪代码：

读取1个bit，称为a。
若a为0，再读取3个bit，返回这3个bit代表的值。
若a为1，再读取1个bit，称为b。
若b为0，再读取3个bit，返回这3个bit代表的值加上8。
若b为1，返回16（即第17个可能性）。

方案三：极致压缩方案，平均4.06位

共4*16+5=69位，平均每种可能性69/17=4.06位。

该方案不是「前缀可识别」的，看起来最节省空间，其实非常不实用。我们遇到0000后，是有二义性的，必须有办法知道这个二进制数据长度是4还是5，才能做判断。但是通常，二进制数据连续密铺，我们没法判断长度。

我什么我称之为「极致压缩方案」呢？

因为log2(17)约等于4.0875，已经是理论上最短的位数了。

如果你想知道x种可能性用变长二进制表示，平均最少需要多少位，那么log2(x)就是你的答案。

如果你想知道x种可能性用固定长度二进制表示，最少需要多少位，那么log2(x)向上取整就是你的答案。

例如log(2)16=4，说明用4位二进制可表示16个可能性。

方案四：另一个前缀可识别方案，平均4.12位

基于方案三改进而来，空间比方案二小，且满足LR(0)文法（前缀可识别）。

写在最后

我是HullQin，公众号线下聚会游戏的作者（欢迎关注公众号，联系我，交个朋友），转发本文前需获得作者HullQin授权。我独立开发了《联机桌游合集》，是个网页，可以很方便的跟朋友联机玩斗地主、五子棋等游戏，不收费无广告。还独立开发了《合成大西瓜重制版》。还开发了《Dice Crush》参加Game Jam 2022。喜欢可以关注我噢～我有空了会分享做游戏的相关技术，会在这2个专栏里分享：《教你做小游戏》、《极致用户体验》。