langyo
commented
1 year ago 粗略看了一下，这有点类似我很久以前依赖大进制数字的进制位空余空间进行数据压缩的想法。
简单讲下，大概是这样的：
- 先确定一个起始进制，起始进制应当在可计算范围下足够的大，并且能够妥善分组容纳你需要压缩的数据。通常来讲，这应当是 2^8 的次幂进制，便于计算，例如 2^16（
0x1_0000_0000）进制。 - 将你所要压缩的数据分组存储到起始进制中。例如
0x0001FFFF, 0x0001FFFF, 0x00110000, 0x00FF_1111。 - 确定一个目标进制。在最优情况下，你应当指定刚刚分组数据中数字最大的一组再加一作为目标进制。在这个例子中，最大的一组是
0x00FF_1111，那么下面要用的目标进制最小就可以选择0x00FF_1112。 - 将原来的以
0x1_0000_0000进制的数据直接视为0x00FF_1112进制的数据，然后直接向0x1_0000_0000进制转换。0x1ffff * 0xff1112 ^ 3 + 0x1ffff * 0xff1112 ^ 2 + 0x110000 * 0xff1112 ^ 1 + 0xff1111 * 0xff1112 ^ 0，最终结果为0x01FA_699B, 0x2290_FF92, 0x25DF_0905。
可以明显看到，整个数据直接少了一位数字（相对于这个大进制而言）。
如果有别的手段压缩或者记录目标进制，确实可以做到压缩数据。但这其实只是一个数学上的小把戏，因为本质上我只是先假定这些数据占据有多大的进制空间，然后将它们收缩起来而已，实际上数据的熵还是不变的。
别误会，这只是我初中那会儿想出来的东西，放到现在肯定有很多不完善的地方。我当初确实是希望它能作为一个新的数据压缩方法来使用的，但后来发现它可能还是更适合拿来重新排列数据、然后再交给字典压缩算法进行压缩罢了。
有很多思路可以优化这个方法，从而进一步提升压缩数据的可能性，例如目标进制记录时不再直接记录具体进制的数字，而是记录这个目标进制与起始进制的差（例如0x1_0000_0000进制转换到0xAAFF_1234进制，取差后就变为0x5500_EDCC），或者丢失一部分精度的目标进制信息、再用汉明码来补充纠正信息差造成的目标进制歧义等等。
不多说了，我也只是提个思路。
最后，您真要讨论，不抵回群里，一群人念叨你都没处念叨……隐退不是这么个隐退法子，很多都是你一手创办的东西，是跟你个人绑定的，你不可能完全丢掉它们。
n0099
yangbowen
而
和HATETRIS（一个试图避免给您合适的下一个块总是给您S或Z-block的俄罗斯方块算法实现）作者发明的 
然而也存在着反例： 
可以参考这个正则看出有哪些alphabet中的字符无法作为一个4bytes组的中间2bytes，因为如果作为了就会解码失败
DWVoid
对于
uint64范围 $0\ to\ 2^{64}-1, \text{inclusive}$ 的输入：对于
int64范围中负数部分 $-2^{63}\ to \ -1, \text{inclusive}$ 的输入：您可以判断输入
$i >= 0来选择使用哪个版本如果您的输入上下限超出了
uint64（正）和int64（负）的范围 $\{-2^{63}, ..., 2^{64}-1\}$ ，您可以将pack()替换为通过gmp得出的其他bigint类型的字节表达输出编码步骤
其中
pack()是php从perl中借鉴的函数（perl的pack()文档： https://perldoc.perl.org/functions/pack https://perldoc.perl.org/perlpacktut ） 在这里的目的是将输入的int64转换为小端序的byte[]提供的P和q是pack format参数P意味着将输入作为uint64解释输出小端序的byte[]q意味着将输入作为uint64解释输出运行时平台环境的端序（对于x86也是小端序）的byte[]rtrim()的目的是将小端序byte[]中靠右（也就是高位）的所有0x00（当输入为正数时）或0xFF（当输入为负数时）删除，也就是只保留其有效位然后对这些有效位
byte[]做base64 encode 最后将base64字符串末尾所有用于padding=删除 而 https://stackoverflow.com/questions/4080988/why-does-base64-encoding-require-padding-if-the-input-length-is-not-divisible-by/26632221#26632221 早已道明：示例输入
行
strlen(out) - strlen(in)代表着输入比最终输出长了多少个字符请注意输入不同的format
https://3v4l.org/Ve5F0#veol
P和q，pack()的结果是相同的 实际上对于有无符号的不同版本int的pack format，只在unpack()反向转换时有不同效果 但我测试过对于"\xfe\xff\xff\xff\xff\xff\xff\xff"，unpack('P或q')都给出了正确的-2，这可能是特定于平台的： https://3v4l.org/V5une#veolphp的
pack()文档也指出了这一点：注意对于输入
-1和0的pack()结果做不同的rtrim(0x00或0xFF)，产生了相同的空字节序列，导致其base64结果也是相同的AA==实际上对于任何输入，都有着另一符号相反的输入，他们删除掉不同的0x00或0xFF后会产生相同的输出因此您需要额外标注您trim掉的是
0x00还是0xFF，这样才能在解码时正确padding对应的0x00或0xFF而如果不做rtrim()删除0x00或0xFF，最终输出将始终是对定长的64bit的base64字符串，其也是定长11（12当您没有删除=时）个字符反向解码
只需对最终输出反过来执行所有编码步骤便可得到原始输入：
str_pad()值（0x00或0xFF），您会得到符号反转并偏移了padding位的值，例如：位数趋势
示例输入表中的strlen(out) - strlen(in)行指出了对于某些输入，输出可能反而比输入更长，例如0的输出是AA，其比输入长了一个字符以下fp思维php代码片段可以求出
[0,1000000]输入范围的所有输出位数：json格式：
{"输入": "输出位数 输入位数"}更快的命令式思维
0xFF版本用以计算[-100000000,0]输入范围：其中
-1的输出是0长度是因为上文提到的空字节序列，而0的输出是11字符长的AAAAAAAAAAA是因为只删除了0xFF而没有删除0x00交互式图表： https://jsfiddle.net/x6wp2kno/
代码备份
```html ``` ```css #chart1, #chart2 { width: 100%; height: 80vh; } ``` ```js // https://github.com/n0099/TiebaMonitor/issues/24 const chart1Data = { "0": "0 1", "1": "2 1", "10": "2 2", "100": "2 3", "256": "3 3", "1000": "3 4", "10000": "3 5", "65536": "4 5", "100000": "4 6", "1000000": "4 7" }; const chart2Data = { "-100000000 ": "6 10", "-99999999 ": "6 9", "-16777216 ": "4 9", "-9999999 ": "4 8", "-999999 ": "4 7", "-99999 ": "4 6", "-65536 ": "3 6", "-9999 ": "3 5", "-999 ": "3 4", "-256 ": "2 4", "-99 ": "2 3", "-9 ": "2 2", "-1 ": "0 2" }; const baseOption = { tooltip: {trigger: 'axis'}, legend: {}, xAxis: { type: 'log', name: '输入数字', minorSplitLine: {show: true} }, yAxis: {name: '字符串长度'}, series: [ { type: 'line', step: 'end', name: '输出' }, { type: 'line', step: 'end', name: '原始输入' } ] }; const chart1 = echarts.init(document.getElementById('chart1')) chart1.setOption(baseOption); chart1.setOption({ title: {text: '正数输入'}, xAxis: {logBase: 2000000}, grid: {tooltip: {axisPointer: {label: {precision: 0}}}}, series: [ {data: _.map(chart1Data, (i, k) => [k, i.split(' ')[0]])}, {data: _.map(chart1Data, (i, k) => [k, i.split(' ')[1]])}, { type: 'line', step: 'end', name: '不省略正号的原始输入', data: _.map(chart1Data, (i, k) => [k, +i.split(' ')[1]+1]) } ] }); const chart2 = echarts.init(document.getElementById('chart2')); chart2.setOption(baseOption); chart2.setOption({ title: {text: '负数输入'}, xAxis: { logBase: 20000, axisLabel: {formatter: i => -i} }, grid: {tooltip: {axisPointer: {label: {formatter: p => '-'+p.value}}}}, series: [ {data: _.map(chart2Data, (i, k) => [Math.abs(k), i.split(' ')[0]])}, {data: _.map(chart2Data, (i, k) => [Math.abs(k), i.split(' ')[1]])} ] }); ```原始输入后不省略正号的正数（+1）跟必须带负号的负数（-1）的长度分布是完全相同的不难看出当 $-9\geq\text{输入}\leq10, \text{输入}\neq\{0, -1\}$ 时输出有着2个字符而输入有着1或2个字符 而往后输入每次达到 $2^{8n}$ 时输出的长度才会增加
使用以下php代码片段我们可以计算出 $n\in\{1,8\}$ 时 $2^{8n}$ 以及 $2^{8n}-1$ 的输出长度，并假定这就是对于任何 $\leq n$ 的输入的输出位数集合：
负数版本：
我们不难发现不可能存在长度为5或9个字符的输出，建议对此进行充实有力的数字论证
而这与以下两个OEIS数列相对应： https://oeis.org/A175824 可以存储在 n 个字节中的最大无符号整数
https://oeis.org/A133752
a(n) = 256^n其他算法
在 https://carlmastrangelo.com/blog/lets-make-a-varint 文中指出protobuf与utf8 encoding中都使用了两种不同的varint实现
他使用base32对protobuf版本varint的输出进行encode从而实现了一种可排序 分布密集的数字压缩算法：
并进一步指出也可以使用 https://en.wikipedia.org/wiki/Golomb_coding 或 https://en.wikipedia.org/wiki/Elias_gamma_coding 代替这两种varint实现然后再套base32
更多的选择：
https://en.wikipedia.org/wiki/LEB128
https://github.com/tsunaminoai/baseEmoji
小数输入
以上讨论都将输入限制为了整数，如果您的输入可能或必定是小数，您可以将其转换为32/64位IEEE 754的二进制再进行encode：
pack format
E表示转换为32或64位（根据运行时php是32还是64位构建）IEEE 754的大端序字节表达 请注意这里换成了大端序以便能够继续进行rtrim()，因为 https://stackoverflow.com/questions/5242589/would-float-point-format-be-affected-by-big-endian-and-little-endian/5242783#5242783 中指出小端序排列的IEEE 754相较sign, exponent, mantissa是倒过来的：如果您换成了小端序的
e那么需要改成[ltrim()]，并在解码时为str_pad()指定STR_PAD_LEFT：与整数版本的
相比您不再需要额外标记原输入是否为负数从而决定应该删除或添加
0x00或0xFF作为padding 因为IEEE 754本身就包含了符号位来表明其是否是负数： http://www.c-jump.com/bcc/common/Talk2/Cxx/IEEE_754_fp_standard/IEEE_754_fp_standard.html但如果您的输入大多数时候都是整数只有少数输入是小数那么将其转为IEEE 754并没有位数优势：
因为对于整数人类通常会只保留其有效位数，对于整数是省略无意义的
.0小数部分 而IEEE 754则是基于2幂的组合公式来迫近输入值（见上图和下文），所以对于整数输入总会比输出短 这跟整数输入时省略正号的正数是类似的：部分输入是小数时：
请注意输出长度是如何由于浮点精度丢失而退化到定长的10/11字符长的
例如32和64位IEEE 754的2幂公式都不可能准确表达十进制小数
https://www.exploringbinary.com/floating-point-converter/
所以需要对IEEE 754的2幂公式的结果做舍入才能迫近原来的
1.2：1.2： https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules而这就导致其base64输出是11字符长的
P/MzMzMzMzM： https://3v4l.org/QdLQB再例如对于32位IEEE 754，
https://www.h-schmidt.net/FloatConverter/IEEE754.html
2147483647会迫近到2147483648因为
https://www.exploringbinary.com/floating-point-converter/
2147483648=1 * 2^31而换成64位IEEE 754表达就可以通过
https://www.binaryconvert.com/result_double.html?decimal=050049052055052056051054052055
1.999999999068677425384521484375 * 2^30（十进制）来迫近输入2147483647十进制的
1.999999999068677425384521484375是mantissa的值（其二进制为1111111111111111111111111111110000000000000000000000），而30是exponent（二进制10000011101，十进制1053）的求值：1053-1023=301053这个magic num来自 https://en.wikipedia.org/wiki/Exponent_bias ：最后计算 $-1^{sign}1.\text{mantissa}2^{\text{exponent}-1023}$ （sign位为0表示输入是正数
-1^0=1，为1是负-1^1=-1）就是最接近原输入的整/小数值这也就是为什么
0.1 - 0.2 != 0.3： https://0.30000000000000004.com您也可以选择仍然将小数删除小数点转为整数输入，然后额外注明小数点位于整数的第几位，也就是使用定点数而不是浮点数： https://en.wikipedia.org/wiki/Fixed-point_arithmetic 而且定点数不会像浮点数那样对于超出范围的整/小数都丢失了精度
如果您的确不在乎精度丢失，您可以选择其他比IEEE 754精度更差但更短范围更大的浮点数表达： https://en.wikipedia.org/wiki/Minifloat 其相当于8位版本的IEEE 754
这个编码方式目前在tbm中用于表述会嵌入前端页面url querystring中的在 44be32e4a28027104bc028fb31bf7f575fac34a6 中从传统的偏移分页（offset pagination）切换为游标分页（cursor pagination）的帖子查询接口所产生的至多6个游标值： https://github.com/n0099/TiebaMonitor/compare/44be32e4a28027104bc028fb31bf7f575fac34a6...673b7c35f03d56d4fa1b04dad01e5059a2e597b4 https://github.com/n0099/TiebaMonitor/blob/673b7c35f03d56d4fa1b04dad01e5059a2e597b4/be/app/Http/PostsQuery/BaseQuery.php#L101 https://github.com/n0099/TiebaMonitor/blob/673b7c35f03d56d4fa1b04dad01e5059a2e597b4/be/app/Http/PostsQuery/BaseQuery.php#L156 有关为何
从传统的偏移分页（offset pagination）切换为游标分页（cursor pagination）可以查阅上海贵族信安底层壬上壬杨博文阁下@yangbowen 此前与我的私聊记录，其优缺点将在下一篇文章中介绍： https://medium.com/swlh/how-to-implement-cursor-pagination-like-a-pro-513140b65f32 https://slack.engineering/evolving-api-pagination-at-slack/ http://mysql.rjweb.org/doc.php/paginationcc @Starry-OvO @Juicpt @BANKA2017 @kokoro-aya @ControlNet @FeiBam @langyo