从原神抽卡记录谈起，将数据压缩成字符串

2022-02-22coding

好久没写过新东西了，然而并不是没东西可写。 而是行动力太弱了，大多数行动力已经扔在了工作这个深坑里，行尸走肉般的躯体便只能沉溺于游戏与快消娱乐上了。
(题外话：这篇文章其实在 21 年 10 月就开始动笔了，但一直到现在才完成)

今天我们就从原神抽卡记录说起，讲一下将抽卡记录数据压缩为字符串。(这部分代码其实已经在 N 个月前完成了)

引言

动机很简单，因为有一个原神抽卡记录分析工具，这个工具是纯前端的静态网页，通过解析包含抽卡记录数据的 excel 文件， 从而实现抽卡记录数据的可视化，并允许生成一些可视化结果的图片，链接见下：

原神抽卡记录分析工具
上传原神游戏抽卡记录文件，进行一些可视化分析

在这个基础上，我是希望能够把抽卡记录数据压缩到 url 里，从而实现以 url 的形式把抽卡数据分享出去。

最终实现的结果示例展示，点击前往：

抽卡记录示例
共包含 8009 抽抽卡记录

实现

抽卡记录数据格式

抽卡记录数据是通过抽卡记录导出工具导出的，这种工具一般是通过抓取游戏日志里的带有 authkey 的链接来获取 authkey 信息， 然后通过此信息向游戏内部获取抽卡记录数据的链接发起请求，从而获取到抽卡记录数据。并对数据做一些处理最终导出至 excel 文件。

一般的数据结构是如下的格式：

原神抽卡记录数据示例

从上图我们可以知道，需要压缩的数据其实只有 时间、角色、顺序。

  • 时间：需要完整记录。
  • 角色：只需记录 id，具体名称，类型，星级都可以从数据中解析出来，并不需要存储。
  • 顺序：通过保持不同祈愿的顺序，我们可以计算出总次数，保底内等数据。

接下来便介绍一下具体压缩算法。

时间数据的压缩

首先我们可以知道原神的抽卡分为 单抽 和 十连，即一次抽取 1 个与一次抽取 10 个。在一次抽取 10 个时，在一般情况下，这 10 抽时间是相同的 (存在时间不同的情况，在某好心人分享的 8000 抽数据里存在一例 10 连里的最后一抽和前九抽差了 1 s 的情况，在此忽视这种情况)

因此时间数据条目数是比抽卡数据总数少挺多的。

比如一条时间数据 2020-09-28 10:25:28 ，转换为数字格式则为 1601259928。

以 8 条时间数据为例，我们将其转换为数字

['2020-09-28 10:41:55', '2020-09-28 10:42:10', '2020-09-28 10:42:20', '2020-09-28 10:42:27', '2020-09-28 10:44:42', '2020-09-28 10:44:50', '2020-09-28 10:44:59', '2020-09-28 10:45:06']
[1601260915, 1601260930, 1601260940, 1601260947, 1601261082, 1601261090, 1601261099, 1601261106]

接着我们可以逐个获取日期间的差值，而最开始的差值，我们可以设定为原神的开服时间 2020-09-15 06:00:00。按照这种方法，数据可以转换为：

[1140115, 15, 10, 7, 135, 8, 9, 7]

问题转变为了对一串数字进行压缩。

一般而言，在这种情况下，就没有必要再对数据进行额外处理了，直接用一些字符串压缩的库处理即可，如lz-string。

但我出于某种尝试，继续将这部分数据进行了压缩，在费了很大功夫的前提下，也最终只压缩了不到 20% 的大小，因此也不建议大家对这些数据再进行压缩。

下面是进一步的数据压缩过程：

众所周知，二进制数据是数据的最终形态，因此将数据转换为二进制应该是可以对数据起到一定压缩效果的。如 0123456789 组成的一串字符，如果将其按照huffman编码，易知每一个字符都需要三位或四位数字来表示，以一种huffman编码为例，结果为 1100110111101111000001010011100101，共计 34 位。而如果将其按照数字来看待，最小值为0123456789，对应二进制为111010110111100110100010101，位数为 27; 最大值为9876543210，对应二进制为 1001001100101100000001011011101010，位数为 34。易知以数字形式直接转换为字符串压缩效果更高，同时，在编码已经给定的情况下，如按照上述huffman编码压缩 15，则需要 6 ~ 8 位数字，直接转换为数字则只需要 4 位，在面对小数字的情况下直接将数字转换为二进制编码能够取得不错的压缩效率。

按照二进制编码的情况下，我们可以把上面的数据转换为

['100010110010110010011', '1111', '1010', '111', '10000111', '1000', '1001', '111']

如果直接把这些数据合并成一条字符串，那肯定是行不通的，是解析不了的。因此需要配置一下分隔符，在这里，我选择的分隔符为 通过 huffman 编码的包含每一条数据长度的编码。

比如我们把每一条信息的长度分为 2，4，8 等层级，分别用 0，10，11 来表示。 那么 0xx10xxxx11xxxxxxxx 就是我们最终编码得到的数据，其中 x 表示其中包含的二进制信息。在解码时读取到 0，则表明数据位为 2 位，向后读取 2 位数据，再按照 huffman 编码继续向下解析即可。

当然信息的长度层级不一定是 2，4，8，也可能是 5，6，7。如何划分层次关系则会影响到编码长度，这里的话我用到了下面的代码仓库(感谢作者~)

OneBST/GI_gacha_dataset
汇总收集了一些原神抽卡记录导出文件

通过这个仓库我获取到了两条抽卡记录之间的时间转换到二进制的数字长度，见下：

{
  "1": 20,
  "2": 2236,
  "3": 12062,
  "4": 14292,
  "5": 3862,
  "6": 2702,
  "7": 1518,
  "8": 913,
  "9": 633,
  "10": 726,
  "11": 837,
  "12": 856,
  "13": 886,
  "14": 1013,
  "15": 1275,
  "16": 2501,
  "17": 3727,
  "18": 2612,
  "19": 2309,
  "20": 1253,
  "21": 997,
  "22": 319,
  "23": 149,
  "24": 95,
  "25": 1,
  "26": 0,
  "27": 0,
  "28": 0,
  "29": 0,
  "30": 0,
  "31": 0,
  "32": 0
}

通过上面描述的方法进行压缩时，需要给定一个数据最大长度，在这里我选择了 32，大概最大时间间隔代表着 136 年。

直接使用上面的数据生成 huffman 编码明显是不合理的，我们需要合并一些区间，减少整体需要的编码数量。在这里，我最终选定的方案是依次将每一个值合并到上一个值，并分别计算合并后的编码总长度，选择编码总长度最短的合成方案重复以上进行的操作，直到所有合并的编码总长度都大于合并前的编码总长度，不再进行区间合并，返回结果。

该方案不一定是最优方案，最终计算的结果如下：

{
  "4": "0",
  "6": "101",
  "8": "1000",
  "9": "110001",
  "13": "1001",
  "17": "111",
  "19": "1101",
  "21": "11001",
  "22": "1100001",
  "23": "11000001",
  "24": "110000001",
  "25": "1100000001",
  "32": "1100000000"
}

通过以上描述的方法我们可以对时间信息进行压缩。可以把之前提到的数据通过上面描述的方法得到最终的压缩结果

11001100010110010110010011011110101000111100010000111010000100100111

该压缩数据是完全可以可以解压出原有数据的，以上压缩与解压缩算法见：https://github.com/voderl/genshin-gacha-analyzer/blob/main/src/utils/v1/compressDateNumbers.ts

通过此算法，以一个共计 8009 抽的抽卡记录为例，得到的有效抽卡时间为 890 个，最终时间相关数据压缩后二进制编码长度为 7010。

而如果直接用 lz-string 提供的方法(见下)，那么使用起来非常简洁易懂，而且一个 base64 字符，对应 6 位二进制数据，其二级制编码长度为 8640。

LzString.compressToBase64(dDates.join(",")); // length: 1440

那么以这个抽卡记录为例，相比直接使用 lz-string 方法，压缩率大概为 81%。

lz-string
lz-string: JavaScript compression, fast! - pieroxy.net

与得到的压缩率相比，此压缩方法已经付出了太多的局限性，只支持一定范围内的正整数，而且整数的长度还需要具有一定特征。而通用的文本压缩算法，则对几乎任何文本都能得到有效的压缩。

而在拥有这部分局限性的数据里，我相信也一定存在着针对这些数据的更好的压缩算法。

综上所述，不要拿自己的业余想法挑战各种成熟压缩算法的专业性。当然，兴趣除外

角色数据的压缩

角色数据的话，只需要保存一个 id 就可以了，因为在压缩和解析时，都能根据这个 id 来获取实际角色的名称，类型。

但是我们需要保证每一个角色都有一个唯一的 id，在后续出新角色新武器时都不会影响之前的解析结果。像如动态 huffman 编码，以及各种神奇的自适应编码，应该都能比较棒地实现此效果。

在这里的话，我的实现就相对简单一点。

首先是把武器和角色的类型给定一个前缀

const ItemTypeMap = {
  [ItemType.Weapon3]: "1",
  [ItemType.Weapon4]: "001",
  [ItemType.Weapon5]: "0000",
  [ItemType.Character4]: "01",
  [ItemType.Character5]: "0001",
};

然后在同一类型下的数据则直接按照给定的数据直接往下排序即可。

因为此项目维护了从开服到现在的所有祈愿，所以简单遍历就能获取到不同类型的道具，同时每次遍历都可以保持顺序一致。 大概原理就是同级 15 条数据，最后一条将数据长度延伸 4 位，接着再在同级维护 15 条数据，依次往下得到编码。

/**
 * 需保证添加新角色，不更改原有的编码
 */
function buildHuffmanTree(data: string[], bit = 4) {
  // 同级15个，最后一个向下延伸再15个，一直延伸
  let prefix = '';
  const map = {} as any;
  while (data.length !== 0) {
    const segs = data.splice(0, Math.pow(2, bit) - 1);
    segs.forEach((key, index) => (map[key] = prefix + padStart(index.toString(2), bit, '0')));
    prefix += '1'.repeat(bit);
  }
  return createHuffmanUtils(map);
}

顺序数据的压缩

顺序的话其实就更简单了，这里的话一般情况下是分了四个池子的，角色活动祈愿、武器活动祈愿、常驻祈愿、新手祈愿。 可以直接每个池子挨个进行数据的压缩即可，在这里的话我是用了换池子的操作符，设置了一系列的操作符。

/**
 * 控制字符包括 设定抽的池子，
 */
enum ControlAction {
  matchOne = '0', // 单抽 或者 十连
  matchTen = '1',
  changePool = '2', // 换池子
}

const ControlActionMap = {
  [ControlAction.matchOne]: '1',
  [ControlAction.matchTen]: '01',
  [ControlAction.changePool]: '001',
};

这个操作不一定能提高实际的压缩率，因为切换池子也是相对比较高频的操作，这个池子抽一下，那个池子抽一下也很常见，不过在处理这部分数据时也没想那么多。想得是把所有池子的时间数据放在一起的话，时间的差值就会变小，在时间压缩上会有一点提升。

但在完成后意识到，两种方案可能最终的压缩大小不会差很多。

const PoolTypeMap = {
  character: '11',
  weapon: '101',
  novice: '100',
  permanent: '0',
} as any;

其他处理

最终会把二进制字符串压缩到 url 安全的字符中，共计 64 个字符，每 6 位数字压缩成一个字符。

lz-string用到的字符如下

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=

我在这里用了微信和 QQ 测试，发现上面的一些字符可能会导致排版换行，所以实际使用的下面的

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789~=

不过事实证明这一点并没有用，在电脑上向微信和 QQ 发送消息时，如果抽卡数据过多，那么生成的 url 的字符变多，很有可能超过它们的限制而导致发不出去。

总结

实际在压缩过程中用到了以上的方法。

会先将所有池子的数据按照时间顺序放到一个数组里，然后先将其中的时间数据压缩成字符串，同时会压缩信息数据到另一个字符串。

后续补充：这一点对于数据还原来说可能不太好，比如说后半部分链接如果丢失了，那么全部数据都不能恢复。如果单个抽卡的时间和道具放在一起，是有机会从一个残缺的链接中恢复部分数据的。

在时间数据遇到 10 连抽时，时间会按照一个时间来处理，同时在信息数据的字符串里插入一个单抽或十连的控制字符。

题外话，我也是写到这里才注意到我这里每一个单抽和十连都加上了相关的控制字符，即每个单抽多了一个字符，每个十连多了两个字符，但这里完全没必要这么处理，在从单抽切换到十连或从十连切换到单抽时插入控制字符即可。 在这种情况下，像是上文提到的 8009 抽的抽卡数据，整体压缩数据应该还能再小 3.5% 左右

在切换池子抽卡后，会在数据信息字符串中插入一个切换池子的控制字符，后面跟一个池子信息的字符。

最终的结果就是

`${时间信息字符串}:${数据信息字符串}:${版本号}`;

具体压缩和解压缩代码见：https://github.com/voderl/genshin-gacha-analyzer/blob/main/src/utils/v1/index.ts#L47

一个数据的示例如下

https://genshin.voderl.cn/#=Nn76tHK~f4mENVDRCxCg6TXdXqdUc5sOOMtsENKCoQlio2YT6lUK2qJvH811r21Ja7GdCEGLUu52bkhPmJzKWbkLB6YI5rFzNWniO7xx7YpbuJRbjzcWpPJm31WtcVHbZOl8Xx7thl97KPgrlZuKDorp5GSVZ6jxDoSc6FyILedBa2fiNTlQmnyI5S~WSEk7a3xpZd8DrZvO889y08Qnk4HOkplTEGUYpCSUg428JfPKOWtzJV1ROKsnHp1VfISKErUpjm1qZH8QbkIurg7Fn7bMqkg7TEKP0KN9oS4yldQUeopH0lmDYvUwatZUr7W5yy~cNX3TIOc7VJdtNcNO~7OnIic6bxs0bjAteOUoiDrNju5YW4UD6q33UZZDm1TYsUZx8u=ZSmMysHKWf0kQZyG8eO~~nxJ6z1bC9VUaPSyNPKjF4bDGJ56pTWp9R=TJMUpPNZ=1xg6USkdhqXQiyf3WIT1LBHky56oHn2PhfKKEyCesKHlDJLyU=g7l8xwwkJ1DWRWa7Wilh0Mk2OklbRJ~niP6OaVuMkpq=JRYpCTDqkl1JFLi4A1D61NsXXkFG1RdCnGbVQFEkbtVCg=j6erOZNoSLoMtSIkqhJUqpKmW=2ti8xr2oyiObdSFtBjQmoNq26TquiknhDylHt2fqgv2=Zc2LalmNqrJWxGTFJPZ=zD89MttqXh5QJeC6pq6~RrqicxzIPWK3UjoqljVebfHecZjVY5kGqZi~bzcqhJPFdt9Ep3zYw2RvrMZeiG=dLDnFsCE:MaZ1Wmcr4mWuMTMduqS3iMrRLnrFjZuXMcxrTQ5u~4QhbN8Mu~Me~8epFlvWc4rRXDoB3CmYHj580517780xVL4hvcZZmncSlOELQmrQxPdc2IXa0rC1anoa662cW4jKl55ywhQze=ADM2oTJuFZVjBvorzUOctR0nad8CEOXTlpS1DcoJsnbW3CuIXalsxjPEo2vh1xhN88Y6dab918uM~es995nfrLTjTHju1zh4dlOUN43yRxinWkZblfTJXV4wgrrmvGe=eCT3yUqUhjdTLjjXHLnya2Z45q94p8lxvvrnvT106im2jOim64nfOuKfmXm2GeHfc533kWe2~3UxyffjHLimWveR8SoctBDMOVsWxo7nPLbpk~O8lsfN5G2MqQheGGJZ7nw53nzxxwywx56pz2PWJdnipdceVT4Fnnlxhltyfgr4c9Hb5o3eFKUyz5dmOZZhZ3Y~EqXhK8XVm9x1GNrymWnWfenm1q06zKMJ0s1SY3602LTDDDvab61080P51plcjGme2JaH6886md9u~NN99=LmOeM4WR9N=N~MMOLmWPG~eGWOVwubuB973O~O=eWO3V4nEaxtXR86XZUrE7jHNONd8nGEqK5y8hJ~Z88OdCnzPvzl1rULzPM~~uG3mhaY9Z5a0Os9vMtD5eV~vIizxmNbmaaozvSMBpWUly02nx27wyO3nLiteUpvutnGsdOC67O2vY1eW97zn3WLzO~GE3jnudzqLlbwzvfW0g05fMIa25EtcdtPOJc7qG5wvJPW20pR1SJGdNe9tMec7fE~fG~2=MTdVw3m2D4SfBtTdc3hF8Jb74Zba8y~GW2uGWWG5c7eHvgXPmuG9EF:1

链接数据点击前往：

抽卡记录示例 - 点击前往
共包含 835 抽抽卡记录

大概就是这样子，感谢大家看到这里。

大概拖了 4 个月才能完成这篇文章的我向大家道歉，抱歉呀 Tv

点赞 0