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

2022-02-22coding

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

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

引言

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

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

最终实现的结果示例展示,点击前往:

实现

抽卡记录数据格式

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

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

原神抽卡记录数据示例
/* @jsxRuntime classic */ /* @jsx mdx */ const layoutProps = { }; const MDXLayout = "wrapper" export default function MDXContent({ components, ...props }) { return

{`[object Object]`}

; } ; MDXContent.isMDXComponent = true;

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

  • 时间:需要完整记录。
  • 角色:只需记录 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。如何划分层次关系则会影响到编码长度,这里的话我用到了下面的代码仓库(感谢作者~)

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

{
  "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%。

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

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

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

角色数据的压缩

角色数据的话,只需要保存一个 id 就可以了,因为在压缩和解析时,都能根据这个 id 来获取实际角色的名称,类型。但是我们需要保证每一个角色都有一个唯一的 id,在后续出新角色新武器时都不会影响之前的解析结果。

像如动态 huffman 编码,以及各种神奇的自适应编码,应该都能比较棒地实现此效果。

待补充,联系网站底部邮箱催更 (×

顺序数据的压缩

点赞 0