如何压缩数字：一种基于对有效位做base64的比数字字符串更短的人类可读字符串表达 #24
Comments
|
粗略看了一下，这有点类似我很久以前依赖大进制数字的进制位空余空间进行数据压缩的想法。 简单讲下，大概是这样的：
可以明显看到，整个数据直接少了一位数字（相对于这个大进制而言）。 如果有别的手段压缩或者记录目标进制，确实可以做到压缩数据。但这其实只是一个数学上的小把戏，因为本质上我只是先假定这些数据占据有多大的进制空间，然后将它们收缩起来而已，实际上数据的熵还是不变的。 别误会，这只是我初中那会儿想出来的东西，放到现在肯定有很多不完善的地方。我当初确实是希望它能作为一个新的数据压缩方法来使用的，但后来发现它可能还是更适合拿来重新排列数据、然后再交给字典压缩算法进行压缩罢了。 有很多思路可以优化这个方法，从而进一步提升压缩数据的可能性，例如目标进制记录时不再直接记录具体进制的数字，而是记录这个目标进制与起始进制的差（例如 不多说了，我也只是提个思路。 最后，您真要讨论，不抵回群里，一群人念叨你都没处念叨……隐退不是这么个隐退法子，很多都是你一手创办的东西，是跟你个人绑定的，你不可能完全丢掉它们。 |
在这里就已经去除了原输入中每组数最左侧的无意义的leading zeros
然而额外记录
您已经找出了最大值是多少，自然可以将原先
各种编码转换也是保证信息熵不变的，因为他们都是双射函数（而有损压缩那样的就不是）
然而输出
之前我跟杨博文阁下讨论protobuf的varint时提到过把一个unix timestamp减去固定值（如 然而做减法对于本文的这个编码而言没用，因为根据上文中的下表
可见除非您的输入大到减去固定值后比输入小
https://en.wikipedia.org/wiki/Hamming_code 指出：
|
|
https://github.com/qntm/base65536
https://github.com/qntm/hexagram-encode ：
alphabet：
https://github.com/qntm/braille-encode ：
alphabet：
疑似BCD8421 https://en.wikipedia.org/wiki/Binary-coded_decimal |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
是这样的，所以我强调了这只是一个数学上的小把戏，现在只能当作一种玩具算法来用，而且相比较于其它的数据重排算法来说，这个算法要的算力明显不占优势——别的算法大多可以并行计算，这个不好并行 |
关于端序
那么，为什么对于负数部分要换成 native endian 而不是 little endian ？如果您的目标是减少因数值的绝对值常常比整数类型能容纳的范围来得小而造成的冗余的话，那这里理应总是 little endian 而不是 native endian 。因为只有 little endian 的情况下，冗余的高位才出现在 pack 结果的右边部分。这对不论非负数（的高位 0 ）还是（采用 Two's complement 编码的）负数（的高位 1 ）来说都是这么回事。不但如此，这里采取 native endian 实际上还会破坏可移植性——在 little endian 的平台和 big endian 的平台之间无法保持相同的表达。 什么情况可以压缩无损压缩算法不能凭空减少数据长度，只能减少本来就信息冗余的部分。不论采取何种设计，实际能达到的效果是取决于输入数据的分布情况的。具体来说，您的这个压缩因为省去的是高位多出的 0 或者 1 ，所以适用于 绝对值比较小的数值更频繁出现 的情况。
它所适用的情况（只对于那样的情况能起到压缩的作用）就不一样：它适用于被压缩的数据（比起均匀分布而言）更可能在每个 起始进制分组 全都有一些高位 0 的情况。如果这样的输入并不比其它输入更频繁地出现的话，这个算法就毫无作用。 数字字符串和人类可读字符串表达压缩的结果需要人类可读，或者需要由人类可读的字符组成，这样的要求同样是取决于具体场景的。而且数字字符串除了满足 人类可读 以外，其实还满足了 人类可算 。 对 pack 结果的压缩——如何做得更好？有符号数
比起通过额外的元数据来记录是否负数而言，我的建议是您仿照有符号数的 Sign extension 的过程，采用截断高位后的数值的最高位作为这个符号标记。即，截断时保证对正数保留至少一个高位 0 位，而对负数保留至少一个高位 1 位。解码时根据最高位是 0 还是 1 选择填充 0 还是填充 1 。 高位截断从您的例子当中也许您也会注意到一件事：二进制数据中连续的 00 被 Base64 为连续的 A ，而二进制数据中连续的 FF 被 Base64 为连续的 / 。这当然不是巧合，而是因为 64 是 2 幂，而 A 和 / 刚好分别是 Base64 编码表的 0 和 63 。 整数和字节Base64 是将字节串编码为 Base64 字符串，而 pack 的步骤则将输入的整数填充为字节串。 Base64 的 = 填充正是由于它要把 8bit 一组的输入编码成 6bit 一组的输出而造成的，与此同时从上面说的可以看出，对 8bit 组（也就是字节）作高位截断其实并没有发挥充分的效果。所以如果考虑 Base64 的内部设计的话，就会发现这里实际上是迂回的——输入的整数先被 8bit 分组，然后 Base64 的原理又要重新将它看作整数。这个迂回也造成了 = 填充的问题。 总之……综合上面说的，如果希望编码成的是 Base64 这样的以 6bit 为单位的编码表的话，建议的做法是这样：
对应的解码过程就是：
如何实现？Base64 只接受（ 8bit 为单位的）字节流输入，解码时也只输出字节流。不满整字节边界的位流似乎不能被 Base64 解码出来，换言之即便不填充，由 Base64 编码表字符组成的排列组合，也有一些是不可能的 Base64 编码。对于压缩整数这个场景而言这是造成冗余的。所以我一下子想不出简单的办法来复用 Base64 编码解码函数。那么如果不复用的话，对于上面的方案，我试着用我比较熟悉的 C++ 来写一下。以 int64 范围为例，且假定 char 为有符号 8 位。 constexpr std::size_t length_max = ((64 - 1) / 6) + 1;
constexpr std::size_t bits_remaining = 64 % 6;
char arr_table_encode[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
std::uint8_t arr_table_decode[256];
void generate_table_decode() {
for (unsigned int i = 0; i < 256; ++i) arr_table_decode[i] = 64;
for (std::uint8_t i = 0; i < 64; ++i) arr_table_decode[static_cast<unsigned char>(arr_table_encode[i])] = i;
}
std::string encode_int64(std::int64_t value) {
std::uint8_t arr_digit[length_max];
for (std::size_t i = 0; i < length_max; ++i) {
arr_digit[i] = value & 63;
// signed bitwise-shift is arithmetic shift
// do arithmetic shift, so that the highest remaining bits are sign-extended
value >>= 6;
}
std::size_t length = length_max;
if (arr_digit[length - 1] == 0) {
while (length >= 2 && arr_digit[length - 1] == 0 && arr_digit[length - 2] < 32) --length;
// length == 1 || arr_digit[length - 1] != 0 || arr_digit[length - 2] >= 32
// remove the following line to avoid empty string output
if (length == 1 && arr_digit[0] == 0) --length;
} else if (arr_digit[length - 1] == 63) {
while (length >= 2 && arr_digit[length - 1] == 63 && arr_digit[length - 2] >= 32) --length;
// length == 1 || arr_digit[length - 1] != 63 || arr_digit[length - 2] < 32
}
std::string str;
for (std::size_t i = 0; i < length; ++i) str.push_back(arr_table_encode[arr_digit[i]]);
return str;
}
std::int64_t decode_int64(std::string str) {
std::uint8_t arr_digit[length_max];
assert(str.size() <= length_max);// may not exceed max length
if (str.empty()) return 0;// empty string either decodes to 0 or is invalid
{
std::size_t i = 0;
for (; i < str.size(); ++i) {
assert(arr_table_decode[str[i]] < 64);// there's invalid character
arr_digit[i] = arr_table_decode[str[i]];
}
// if the highest bit is 0, extend 0
// otherwise, extend 63
std::uint8_t digit_extend = ~((arr_digit[str.size() - 1] >> 5) - 1) & 63;
for (; i < length_max; ++i) arr_digit[i] = digit_extend;
}
assert(arr_digit[length_max - 1] < (1 << (bits_remaining - 1)) || arr_digit[length_max - 1] >= -(1 << (bits_remaining - 1)));// may not exceed the range of int64_t
std::uint64_t unsigned_value = 0;
for (int i = length_max - 1; i >= 0; --i) {
unsigned_value <<= 6;
unsigned_value |= static_cast<std::uint64_t>(arr_digit[i]);
}
return unsigned_value;
} |
这是php人从perl人抄来的 更何况我后来又发现连指定
所以后文中都是说的
现在消费级常见cpu arch中也就基于RISC的arm还是大端了（实际上现在是可变端序： https://developer.arm.com/documentation/ddi0406/cb/Appendixes/ARMv4-and-ARMv5-Differences/Application-level-memory-support/Endian-support ）建议致电在树莓派上跑php的 @BANKA2017 和薅oracle arm服务器羊毛的hostloc主机佬来试试php的arm构建结果运行时到底用的小还是大端序
您前几个月在tg上跟我私聊时探讨protobuf所使用的varint实现时已经说过这些了
一串md5 sha那样的hash（输出均匀分布）或是某种鉴权token那毫无规律可言也没人会专门去缩短他们的长度（除了币圈助记符），而且真压缩了反而可能有很难利用的旁信道攻击如timing attack，因为如果随机输出中真的由于巧合或是输入而出现了规律那mitm也会发现您利用规律压缩后传输的输出有所不同
我只看懂了伊欧神举的那个例子本身是如何计算的，但我根本不知道为什么要这样做，也不知道什么特征的输入会输出更短，什么会更长
所以1楼
我的需求场景就是url safe，因为cursor pagination的cursor值应该放在GET method的url里而不是经典POST的request body（还真有人想把url缩短就改成POST的结果f5一下浏览器就弹窗是否重复提交表单），不然就无法分享当前页面的canonical url给别人看，那cursor paging比起offset paging所带来的防止page shifting/drift优势就毫无用武之地了
准确地说是最常见的十进制阿拉伯数字，给您看一大坨hex或是大写汉字数字您也不好脑中做四则运算吧
baseXX本就是XX进制的含义，只不过还额外修改了alphabet（用于表达这个encoding的可用字符集）
base32被btc用来做为钱包地址的编码，后来其他币也都是直接抄的
我写了一遍： https://3v4l.org/PiE5u <?php
// https://stackoverflow.com/questions/35536141/converting-binary-data-to-ascii-with-php-any-possibility/35536281#35536281
function bin2ascii($input) {
$output = '';
for($i=0; $i<strlen($input); $i+=8) {
$output .= chr(intval(substr($input, $i, 8), 2));
}
return $output;
}
https://stackoverflow.com/questions/6382738/convert-string-to-binary-then-back-again-using-php/6382880#6382880
function ascii2bin($input) {
return array_reduce(str_split($input), fn ($acc, $i) => $acc .= decbin(ord($i)));
//return array_reduce(str_split($input), fn ($acc, $i) => $acc .= str_pad(decbin(ord($i)), 8, '0', STR_PAD_LEFT));
}
$i = -114514;
var_dump( decbin($i));
var_dump( ltrim(decbin($i), $i < 0 ? '1' : '0'));
var_dump( ($i < 0 ? '1' : '0') . ltrim(decbin($i), $i < 0 ? '1' : '0'));
var_dump( bin2ascii(($i < 0 ? '1' : '0') . ltrim(decbin($i), $i < 0 ? '1' : '0')));
$o = rtrim(base64_encode(bin2ascii(($i < 0 ? '1' : '0') . ltrim(decbin($i), $i < 0 ? '1' : '0'))), '=');
var_dump($o);
$d = base64_decode($o);
var_dump($d);
$bits = ascii2bin($d);
$signBit = decbin(ord($d))[0];
$paddedBits = str_pad($bits, (strlen($bits) + (strlen($bits) % 8)) / 8, $signBit, STR_PAD_LEFT);
var_dump($bits);
var_dump($signBit);
var_dump($paddedBits);
var_dump(intval($paddedBits, 2));string(64) "1111111111111111111111111111111111111111111111100100000010101110"
string(17) "00100000010101110"
string(18) "100100000010101110"
string(3) "�+�"
string(4) "kCsC"
string(3) "�+�"
string(16) "1001000010101110"
string(1) "1"
string(16) "1001000010101110"
int(37038)如果您将输入的 然后在解码时我们把base64decode结果 10010000 00101011 00000010 base64encode后的位
10010000 101011 10 ascii2bin()后的位可见少了8位的 array_reduce(str_split($input), fn ($acc, $i) => $acc .= decbin(ord($i)));而decbin的输出本就是ltrim掉所有 那么我们把 array_reduce(str_split($input), fn ($acc, $i) => $acc .= str_pad(decbin(ord($i)), 8, '0', STR_PAD_LEFT));您会发现他的输出的确变成了base64decode的输出： string(24) "100100000010101100000010"
string(1) "1"
string(24) "100100000010101100000010"
int(9448194)但更关键的问题是我们要的根本不是24位长的 // https://stackoverflow.com/questions/35536141/converting-binary-data-to-ascii-with-php-any-possibility/35536281#35536281
function bin2ascii($input) {
$output = '';
for($i=0; $i<strlen($input); $i+=8) {
$output .= chr(intval(substr($input, $i, 8), 2));
}
return $output;
}在这里是逐8个位去转换为对应的ascii码（ 100100000010101110 每8位拆开便乘了：
10010000 00101011 10 最后一个10不足8位于是被`intval(..., 2)`自动在高位填充了0b0那1楼中的 base64_encode(rtrim(pack('P', $i), "\x00"))为什么不会遇到这问题呢？ 所以我们需要手动完成正确的padding： https://3v4l.org/5Xj4i <?php
// https://stackoverflow.com/questions/35536141/converting-binary-data-to-ascii-with-php-any-possibility/35536281#35536281
function bin2ascii($input) {
$output = '';
for($i=0; $i<strlen($input); $i+=8) {
$output .= chr(intval(substr($input, $i, 8), 2));
}
return $output;
}
https://stackoverflow.com/questions/6382738/convert-string-to-binary-then-back-again-using-php/6382880#6382880
function ascii2bin($input) {
//return array_reduce(str_split($input), fn ($acc, $i) => $acc .= decbin(ord($i)));
return array_reduce(str_split($input), fn ($acc, $i) => $acc .= str_pad(decbin(ord($i)), 8, '0', STR_PAD_LEFT));
}
// https://stackoverflow.com/questions/11946696/php-signed-binary-strings/11946971#11946971
function bindec2($bin)
{
if (strlen($bin) == 64 && $bin[0] == '1') {
for ($i = 0; $i < 64; $i++) {
$bin[$i] = $bin[$i] == '1' ? '0' : '1';
}
return (bindec($bin) + 1) * -1;
}
return bindec($bin);
}
$i = -114514;
var_dump(decbin($i));
$trimmedPadding = ltrim(decbin($i), $i < 0 ? '1' : '0');
var_dump($trimmedPadding);
$signBitsPading = $i < 0
? str_repeat('1', 8 - strlen($trimmedPadding) % 8)
: str_repeat('0', 8 - strlen($trimmedPadding) % 8);
var_dump($signBitsPading . $trimmedPadding);
var_dump(bin2hex(bin2ascii($signBitsPading . $trimmedPadding)));
$o = rtrim(base64_encode(bin2ascii($signBitsPading . $trimmedPadding)), '=');
var_dump($o);
$d = base64_decode($o);
var_dump(bin2hex($d));
$bits = ascii2bin($d);
$signBit = $bits[0];
$paddedBits = str_pad($bits, 64, $signBit, STR_PAD_LEFT);
$restBits = substr($bits, 1);
var_dump($bits);
var_dump($signBit);
var_dump($restBits);
var_dump($paddedBits);
var_dump(bindec($paddedBits));
var_dump(intval($paddedBits, 2));
var_dump(bindec2($paddedBits));
$paddedHexs = str_pad($d, 8, $signBit === '0' ? "\x00" : "\xFF", STR_PAD_LEFT); // 保持decbin()输出的大端序octet
var_dump(bin2hex($paddedHexs));
var_dump(unpack('q', $paddedHexs)); // signed long long (always 64 bit, machine byte order)
var_dump(unpack('Q', $paddedHexs)); // unsigned long long (always 64 bit, machine byte order)
var_dump(unpack('J', $paddedHexs)); // unsigned long long (always 64 bit, big endian byte order)
var_dump(unpack('P', $paddedHexs)); // unsigned long long (always 64 bit, little endian byte order)
$paddedHexs = str_pad(strrev($d), 8, $signBit === '0' ? "\x00" : "\xFF", STR_PAD_RIGHT); // 大端序转小端序octet
var_dump(bin2hex($paddedHexs));
var_dump(unpack('q', $paddedHexs)); // signed long long (always 64 bit, machine byte order)
var_dump(unpack('Q', $paddedHexs)); // unsigned long long (always 64 bit, machine byte order)
var_dump(unpack('J', $paddedHexs)); // unsigned long long (always 64 bit, big endian byte order)
var_dump(unpack('P', $paddedHexs)); // unsigned long long (always 64 bit, little endian byte order)string(64) "1111111111111111111111111111111111111111111111100100000010101110"
string(17) "00100000010101110"
string(24) "111111100100000010101110"
string(6) "fe40ae"
string(4) "/kCu"
string(6) "fe40ae"
string(24) "111111100100000010101110"
string(1) "1"
string(23) "11111100100000010101110"
string(64) "1111111111111111111111111111111111111111111111100100000010101110"
float(1.8446744073709437E+19)
int(9223372036854775807)
int(-114514)
string(16) "fffffffffffe40ae"
array(1) {
[1]=>
int(-5890427937135525889)
}
array(1) {
[1]=>
int(-5890427937135525889)
}
array(1) {
[1]=>
int(-114514)
}
array(1) {
[1]=>
int(-5890427937135525889)
}
string(16) "ae40feffffffffff"
array(1) {
[1]=>
int(-114514)
}
array(1) {
[1]=>
int(-114514)
}
array(1) {
[1]=>
int(-5890427937135525889)
}
array(1) {
[1]=>
int(-114514)
}现在编码过程时输入给base64encoded的就已经是对齐好了的24位byte[]，所以输出也是正确的
TL;DR：我们无法通过砍掉所有leadding 0/1后又只保留一个位就能保存符号信息，而是需要保留1~8个位 另外当用来保存为符号信息的位达到6位时就正好是base64 alphabet的最后一个字符
|
如果我们同时trim（不论ltrim还是rtrim还是双方向都trim）了
您解释了为什么在输入<10时输出没有长度优势：
我也不知道为什么以base64为代表的各种baseXX编码内部都是使用sextet6位组而不是octet8位组，盲猜这是为了以前ascii环境下的7bit clean
我的需求并不是编码内部的6位组，而是这个编码的alphabet排列组合出的输出能urlsafe就行
什么叫
主要是因为这类编码都是将输入变得更长，如base64使用每4个bytes（32位）的输出对应3个bytes（24位）的输入
我完完全全看不懂现代cpp代码，建议立即致电新创无际cpp老人ISO/IEC 14882 spec语法律师HKUST高材生新创刘予顺神 @DWVoid |
确实小端更为常见，包括 ARM 平台也常常是以小端运行的。但对程序来说不要假定平台只能是小端比较好吧。
是。因为您这里这个 压缩 其实也是一种 varint 。
不，不是追加一个
这其实就是我说的
为了记住符号，只需要一个位，但 Base64 要求输入被 padding 到 8 个位，再被 padding 到 6 个位。即便如此仍旧是有办法的，就是不止保留一个 0 或 1 位，而是保留到填满 padding 后的字节那么多的位。
trim 的方向理应是对应输入数值的高位的方向，对于小端序来说就是右边。除非您有理由认为您的输入数据频繁地出现有很多低 0 位的数，比方说 48 、192 等，那种情况下 trim 低位才有帮助，但不在我前面说的的讨论范围内。
使用 sextet 当然是因为 2 的 6 次方是 64 。每个 sextet （范围 0~63 ）刚好对应 Base64 的一个编码字符。
这两件事是密切相关的，因为能 URL safe 的字符是有限的。之所以 Base64 为了达到 7bit clean 的目标要选择 64 而不是更大，显然是因为 ASCII 当中人类可读字符的数量介于 64 和 128 之间（ ASCII 总共就 128 个，其中包含很多不可读字符），而采用 2 幂使得这个编码转换只需要用到位运算，不需要对于低端平台而言昂贵得多的乘除法。（除法非常昂贵，而乘法在现代 x86 上只比加减法慢一点点，而除数固定的整数除法可以优化成乘法。但对更低端或更古老的平台而言乘法可能昂贵得多）
我打了 tlide 符表示范围，但不幸的是它被 GitHub 识别为 strikethrough 了。而且我没发现。
我已经尽力避免现代cpp代码来照顾不擅长cpp的人的理解了，所以那个其实基本上就是 C ，只用了比较少的cpp特性。您应该可以试着当作 C 来阅读。 |
我不知道有哪些android rom可以在arm保持大端序模式的情况下正常引导启动linux并进入launcher
那么我写的又不是要兼容几十年前各种cpu arch百花齐放时代的c程序，为什么不能假定只有小端序？ 实际上假定 事实核查：截止2023年1月，以
我只不过是砍掉了最初的int二进制表达中无用的leading zeros来压缩长度又保留相同的信息熵，我不觉得这能跟那些完全为了缩短长度而设计的varint算法类比：
utf8编码的设计也是很巧妙的，他像baseXX使用sextet一样用更长的输出来彻底解决了以往的EASCII编码中把双字节序列截断成两部分字节就无法解析或正好解析成其他有效ASCII的问题
从结果上来看
是一样的，而很明显第一种兜圈子的实现路径反而更容易写，如果在乎性能那自然是手写第二种trim的行为
1楼中解码时
base64编码算法内部把octet便乘sextet是他自己的实现，我们是没法改变他的
如您之前所说这也的确造成他的压缩效率更低
所以我们需要学习
我当时类比他的问题相当于音乐播放器中常用的伪随机算法（即故意避免播放随机下一首时随机到之前已经播放过的歌）
默认trim的都是高位，所以我才要强调如果要trim两个方向那就必须得携带额外元数据来注明另一个方向trim掉了几个0或1
我之前也已经试出来不能只追加一个0或1（或者说trim到只剩下一个高位符号位的0或1）
我记得现在那3大email协议还是只支持7bit ascii，unicode人以前也发明过utf7试图取代base64在email协议中的地位但失败了
我们同样可以把url safe和ascii人类可读char的概念推广到unicode charset中
https://github.com/qntm/base65536
https://qntm.org/safe 进一步指出：
那么反过来想，在这个场景中并不在乎性能（我甚至为了直观直接把bit[]变成10字符串来操作而不是用位运算了），在允许使用各种平台可用的数学运算的条件下能否发明更压缩的表达？建议学习
您可以加个\转义如
反转了我主要是看不懂套娃位运算，所以才会有 |
实际上大部分代码根本不依赖也不应该依赖平台原生端序。当且仅当某个二进制数据（用 C++ 的话说叫 对象表示 ）要同时被当作 多字节原生整数类型 和 字节数组 访问时，原生端序才产生影响。这对很多高级语言来说都是本就不存在的操作。而且从用途上讲也只有在序列化/反序列化之类的情况，而且要求性能的时候才用得上——假设您的数据是从 JSON 之类的格式转换来的，那么这个开销很容易就超过 将二进制字节流当作原生整数访问而不是手动排列每个字节 的节省了。
您只不过是砍掉了最初的int二进制表达中无用的leading zeros来压缩长度又保留相同的信息熵，而这跟那些完全为了缩短长度而设计的varint算法的基本原理是完全一致的。只不过后者多出了如何高效地同时存放长度信息，而不是依赖于外部的元数据来知道长度。
原文 unary 应该译作 一进制 —— UTF-8 正是在前导字节中使用一进制编码需要多少个后续字节。
先 trim 光再 padding 跟 trim 到剩下一个确实是一样的，但这里的关键在于到底要 trim 多少的判断。假如您看懂了我的 C++ 代码的话就会看明白那个判断条件的问题。而不论1还是2都是一样面临这个问题的。
同样的，关键在于到底填充 \x00 还是 \xFF ，可以直接根据填充前的最高位。
我不知道，但
这个问题的答案仍旧取决于您的输入数据的分布情况。越是有复杂但显著（远离均匀）的分布规律，就越有机会使用更昂贵的运算发明更压缩的表达。但我怀疑整数数据可能没那么多可以压缩的空间，尤其是您要对单个整数进行压缩，而不是许多个相关联的数。另外，既然您的整数本来也没那么大，那么本来占据的空间也不大了。
是的，主要是我之前没意识到这里有这个问题。
原来是这样。那我试着解释一下某些位运算套娃吧。 constexpr std::size_t length_max = ((64 - 1) / 6) + 1;
constexpr std::size_t bits_remaining = 64 % 6;这里 char arr_table_encode[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
std::uint8_t arr_table_decode[256];
void generate_table_decode() {
for (unsigned int i = 0; i < 256; ++i) arr_table_decode[i] = 64;
for (std::uint8_t i = 0; i < 64; ++i) arr_table_decode[static_cast<unsigned char>(arr_table_encode[i])] = i;
}
std::string encode_int64(std::int64_t value) {
std::uint8_t arr_digit[length_max];
for (std::size_t i = 0; i < length_max; ++i) {
arr_digit[i] = value & 63;
// signed bitwise-shift is arithmetic shift
// do arithmetic shift, so that the highest remaining bits are sign-extended
value >>= 6;
}
std::size_t length = length_max;
if (arr_digit[length - 1] == 0) {
while (length >= 2 && arr_digit[length - 1] == 0 && arr_digit[length - 2] < 32) --length;
// length == 1 || arr_digit[length - 1] != 0 || arr_digit[length - 2] >= 32
// remove the following line to avoid empty string output
if (length == 1 && arr_digit[0] == 0) --length;
} else if (arr_digit[length - 1] == 63) {
while (length >= 2 && arr_digit[length - 1] == 63 && arr_digit[length - 2] >= 32) --length;
// length == 1 || arr_digit[length - 1] != 63 || arr_digit[length - 2] < 32
}根据最高 sextet 判断正负。也可能最高 sextet 位于 1~7 或者 56~62 ，这种情况下根本不能压缩，必须保留所有 sextet ，这两个
就可以继续
std::string str;
for (std::size_t i = 0; i < length; ++i) str.push_back(arr_table_encode[arr_digit[i]]);
return str;
}这个部分无非就是依次根据 sextet 的值在编码表中索引然后追加进字符串并返回。 std::int64_t decode_int64(std::string str) {
std::uint8_t arr_digit[length_max];
assert(str.size() <= length_max);// may not exceed max length
if (str.empty()) return 0;// empty string either decodes to 0 or is invalid同样地， {
std::size_t i = 0;
for (; i < str.size(); ++i) {
assert(arr_table_decode[str[i]] < 64);// there's invalid character
arr_digit[i] = arr_table_decode[str[i]];
}依次从字符串中取出字符，反向查找得到对应的 sextet 值。先前初始化反向查找表的时候其它的全都会被初始化为 64 ，所以这里可以这样判断非法字符。 // if the highest bit is 0, extend 0
// otherwise, extend 63
std::uint8_t digit_extend = ~((arr_digit[str.size() - 1] >> 5) - 1) & 63;
for (; i < length_max; ++i) arr_digit[i] = digit_extend;
}这里包含可能是整个程序最难懂的一个位运算。
assert(arr_digit[length_max - 1] < (1 << (bits_remaining - 1)) || arr_digit[length_max - 1] >= -(1 << (bits_remaining - 1)));// may not exceed the range of int64_t如同前面说的，最高的 sextet 只用到 4bit 所以只能是 0~7 或者 56~63 。这里判断超出范围的非法情况。 std::uint64_t unsigned_value = 0;
for (int i = length_max - 1; i >= 0; --i) {
unsigned_value <<= 6;
unsigned_value |= static_cast<std::uint64_t>(arr_digit[i]);
}
return unsigned_value;
}最后这部分就是依次左移位然后按位或，来将填充完的各个 sextet 重新拼成 uint64 。先拼成无符号 uint64 再在返回时转换成有符号是为了避免这里有符号移位产生意想不到的结果。
事实上正是为了避免太多现代cpp语法，所以才假定 char 是有符号 8bit 并且只写 int64 的例子的。否则完全可以用模板之类的方式写得更通用但更难懂。而且那个反查表也可以不用运行时生成，而是编译时生成。话说回来，“有符号右移位是算术移位”严格来说反而是现代特性，因为以前为了照顾负数不是 Two's complement 的平台，这个甚至是 implementation-defined 的。（虽说并没有听说过哪个实现真的不是这样的） |
我觉得对于浮点数来说这种从一侧或两侧去除重复的 0 的方案恐怕很大程度上根本就不适用。与整数不同，浮点数固有的不精确性意味着它就是被设计成对较小的值和较大的值保留相近的精度（有效位数）的。如果您确实有必要区分 1000000 和 1000000.5 ，却认为 1 和 1.00006103515625 的差异是可以忽略的，那也许从一开始就不适合选择浮点数作为表示方式。再者，您也注意到很多十进制表示很简短的小数，由于在二进制中是循环小数所以有很长的既非全 0 也非全 1 的 mantissa 。 之所以说只匹配不大的分母可能更好，是因为注意到随着分母的提高，循环节长度也增长得很快，不久就不比 53bit 小太多了（意味着消除它的重复不一定划算了）。 |
之所以要这样优化，是因为条件分支在性能上通常是比顺序的运算要差的。我不知道这里如果写 bool cond;
if (cond)
return -1;
else
return 0;确实会被优化掉这个条件分支，变成减 1 再取非，或者什么。 |
https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_applications 早已道明：
|
|
如果仅需要考虑小规模数据的不碰撞而无需保证长期的唯一性，可以考虑使用 nanoid |
不推荐这种 每次随机产生 的原理。为了省去额外占用的数据库字段，也为了避免碰撞的可能性（“发生碰撞的概率”遵循 生日问题 ，例如 64 位真随机只能提供 32 位的抗碰撞），建议从（可预测的、顺序的）唯一序号/主键 决定性地 产生这个 ID 。 这种情况下所需要的实际上就是一个秘密的 伪随机排列 ——在 序列ID 跟 混淆ID 之间的一个 双射 。该双射函数需要有合适的/可自定义的输入/输出宽度，以满足您希望的 ID 空间大小的要求。同时该双射函数需要是伪随机的。 但考虑到您可能不希望一个这么长的 ID ，您所需要的实际上就是一个 FPE算法 ——指定一个密钥以及自定义的取值空间，它可以产生密码学上安全的伪随机排列，而且可以高效地正向和反向计算（当然，在知道密钥的前提下）。 |
你说得对，所以这种库其实仅仅是用在诸如前端界面（不一定是 Web）的组件树的临时标记——只需要确保几万条以内不会发生重复就足以应对了（P.S. 如果你的应用场景可能会有几十万甚至百万个节点同时出现在一个屏幕上，你应该先认真考虑一下是不是你写的有问题，而不是去改这里的随机序列算法） |
界面组件的话确实没有这个 碰撞 的问题——真要是那么不巧的话检测到了就重新随机也很简单。我考虑的使用场景是网站用户、视频之类的的 ID ，就像B站的 BV 号那种。这种情况下不仅数量可以多到碰撞的概率不容忽略，而且编号是长期储存的，因此我认为 另外，对一个 单调递增值 做 块密钥加密（例如 AES-CTR ）相当于将该 块密钥 转化为了一个 流密钥 ，而 流密钥 的输出流确实可以直接用作随机数序列，而且事实上也经常被如此使用。 |
这个是关于编码到字符串吧。编码到字符串显然是 trivial 的，怎么都行。 |
我没号呀。 |
建议立即大脑升级自托管zulip实例迁出zulip cloud free plan实例，，， 建议直接下载我昨天做的懒人整合 https://n0099-my.sharepoint.cn/:f:/g/personal/n_n0099_partner_onmschina_cn/IgBum3ZatgoMR5nNq4wCczuwAV3xgWM-4RdX1dUx9JS5jFw |
|
https://en.wikipedia.org/wiki/Octal#By_Europeans
|
https://news.ycombinator.com/item?id=27085952 |
|
其实讲道理我不是很明白有什么比直接十进制数字更容易记忆和读写的ID表达方式。硬要说的话你可以选择往里面encode一本英语字典然后用随机可读短语来表达编号，或许会更好记忆。压缩成不可简单拼读的字符串除了在跨设备抄写URL时可以少几个按键之外我认为完全是属于无用功。可能极少的更好记的极端情况就是如下这样？但是大多数时候大小写数字字符混合是一个非常难记忆和正确抄写的组合 另外，如果单纯为了避免手打ID抄错而访问错页面的情况可以考虑引入校验位 |
|
-------- Original Message --------
请问新创lys神还有23年初的四叶GTNH服存档吗？ |
|
https://codegolf.stackexchange.com/questions/274322/braille-based-base64 |
对于$0\ to\ 2^{64}-1, \text{inclusive}$ 的输入：
uint64范围对于$-2^{63}\ to \ -1, \text{inclusive}$ 的输入：
int64范围中负数部分您可以判断输入
$i >= 0来选择使用哪个版本如果您的输入上下限超出了$\{-2^{63}, ..., 2^{64}-1\}$ ，您可以将
uint64（正）和int64（负）的范围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
P和q，pack()的结果是相同的实际上对于有无符号的不同版本int的pack format，只在
unpack()反向转换时有不同效果但我测试过对于
"\xfe\xff\xff\xff\xff\xff\xff\xff"，unpack('P或q')都给出了正确的-2，这可能是特定于平台的： https://3v4l.org/V5une#veolhttps://3v4l.org/Ve5F0#veol
php的
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格式：
{"输入": "输出位数 输入位数"}{ "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" }更快的命令式思维
0xFF版本用以计算[-100000000,0]输入范围：{ "-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", "0 ": "11 1" }其中
-1的输出是0长度是因为上文提到的空字节序列，而0的输出是11字符长的AAAAAAAAAAA是因为只删除了0xFF而没有删除0x00交互式图表： https://jsfiddle.net/x6wp2kno/
代码备份
点击图例隐藏系列
原始输入后不省略正号的正数（+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://en.wikipedia.org/wiki/Variable-length_quantity
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并没有位数优势：
{ ... "77": "4 2", "80": "3 2", "81": "4 2", "84": "3 2", "85": "4 2", "88": "3 2", "89": "4 2", "92": "3 2", "93": "4 2", "96": "3 2", "97": "4 2", "100": "3 3", "101": "4 3", "104": "3 3", "105": "4 3", "108": "3 3", "109": "4 3", "112": "3 3", "113": "4 3", "116": "3 3", "117": "4 3", "120": "3 3", "121": "4 3", "124": "3 3", "125": "4 3", "128": "3 3", "129": "4 3", "136": "3 3", "137": "4 3", "144": "3 3", "145": "4 3", "152": "3 3", "153": "4 3", "160": "3 3", "161": "4 3", "168": "3 3", "169": "4 3", "176": "3 3", "177": "4 3", "184": "3 3", "185": "4 3", "192": "3 3" ... }因为对于整数人类通常会只保留其有效位数，对于整数是省略无意义的
.0小数部分而IEEE 754则是基于2幂的组合公式来迫近输入值（见上图和下文），所以对于整数输入总会比输出短
这跟整数输入时
省略正号的正数是类似的：部分输入是小数时：
{ ... "72.0": "3 4", "72.5": "4 4", "76.0": "3 4", "76.5": "4 4", "80.0": "3 4", "80.5": "4 4", "84.0": "3 4", "84.5": "4 4", "88.0": "3 4", "88.5": "4 4", "92.0": "3 4", "92.5": "4 4", "96.0": "3 4", "96.5": "4 4", "100.0": "3 5", "100.5": "4 5", "104.0": "3 5", "104.5": "4 5", "108.0": "3 5", "108.5": "4 5", "112.0": "3 5", "112.5": "4 5", "116.0": "3 5", "116.5": "4 5", "120.0": "3 5", "120.5": "4 5", "124.0": "3 5", "124.5": "4 5", "128.0": "3 5", "128.5": "4 5", "136.0": "3 5", "136.5": "4 5", "144.0": "3 5", "144.5": "4 5", "152.0": "3 5", "152.5": "4 5", "160.0": "3 5", "160.5": "4 5", "168.0": "3 5", "168.5": "4 5", "176.0": "3 5", "176.5": "4 5", ... }{ "0.0": "0 3", "0.1": "11 3", "0.5": "3 3", "0.6": "11 3", "4.5": "3 3", "4.6": "11 3", "10.0": "11 4", "19.0": "3 4", "19.1": "11 4", "31.8": "10 4", "31.9": "11 4", "44.6": "10 4", "44.7": "11 4", "100.0": "11 5", "152.3": "10 5", "152.4": "11 5", "177.9": "10 5", "178.0": "11 5", "203.5": "10 5", "203.6": "11 5", "229.1": "10 5", "229.2": "11 5", "254.7": "10 5", "254.8": "11 5", "531.9": "10 5", "532.0": "11 5", "557.5": "10 5", "557.6": "11 5", "583.1": "10 5", "583.2": "11 5", "608.7": "10 5", "608.8": "11 5", "634.3": "10 5", "634.4": "11 5", "659.9": "10 5", "660.0": "11 5", "685.5": "10 5", "685.6": "11 5", "711.1": "10 5", "711.2": "11 5", "736.7": "10 5", "736.8": "11 5", "762.3": "10 5", "762.4": "11 5", "787.9": "10 5", "788.0": "11 5", "813.5": "10 5", "813.6": "11 5", "839.1": "10 5", "839.2": "11 5", "864.7": "10 5", "864.8": "11 5", "890.3": "10 5", "890.4": "11 5", "915.9": "10 5", "916.0": "11 5", "941.5": "10 5", "941.6": "11 5", "967.1": "10 5", "967.2": "11 5", "992.7": "10 5", "992.8": "11 5" }请注意输出长度是如何由于浮点精度丢失而退化到定长的10/11字符长的
例如32和64位IEEE 754的2幂公式都不可能准确表达十进制小数
1.2：https://www.exploringbinary.com/floating-point-converter/
所以需要对IEEE 754的2幂公式的结果做舍入才能迫近原来的
1.2： https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules而这就导致其base64输出是11字符长的
P/MzMzMzMzM： https://3v4l.org/QdLQBhttps://cryptii.com/pipes/base64-to-hex
也就是
https://www.exploringbinary.com/floating-point-converter/
再例如对于32位IEEE 754，
2147483647会迫近到2147483648https://www.h-schmidt.net/FloatConverter/IEEE754.html
因为
2147483648=1 * 2^31https://www.exploringbinary.com/floating-point-converter/
而换成64位IEEE 754表达就可以通过
1.999999999068677425384521484375 * 2^30（十进制）来迫近输入2147483647https://www.binaryconvert.com/result_double.html?decimal=050049052055052056051054052055
十进制的
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中的在 44be32e 中从传统的偏移分页（offset pagination）切换为游标分页（cursor pagination）的帖子查询接口所产生的至多6个游标值：
44be32e...673b7c3
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/pagination
cc @Starry-OvO @Juicpt @BANKA2017 @kokoro-aya @ControlNet @FeiBam @langyo
The text was updated successfully, but these errors were encountered: