使用非 2 的幂的基数的基数编码效率

Question

Base64 将三个 8 位字符编码为四个 (base-64) 6 位“字符”。 Base64 之所以高效，是因为它使用的底数 (64) 和指数 (4) 恰好与 2 (24) 的以 10 为底的指数完美匹配：3x8=4x6=24 和 2²⁴=64⁴=16777216。

似乎没有基/指数组合产生与 2 的以 10 为底的指数完全匹配的值（特别是 2ⁿ 对于任何 0<n<256), except for base32, base64 and base128 (along with base4, base8, base16, base256, base512, etc which are more difficult to make practical use of). 请参阅最后一个代码块以获取匹配的完整列表）指数！

以base92为例，92²=8464，2的最接近的以10为底的指数是2¹³=8192。8464-8192=272个在base92侧可用的索引（如果我理解正确的话）是不可能利用的。 （2¹⁹=524288 < 91³=753571 < 2²⁰=1048576，但 2²⁰-91³=295005。272 是明显的赢家。）

今天下午早些时候，在思考这些损失问题时，我想到了一个有趣的问题。如果我一次查看 14 位输入，并且遇到像

00100000 11111111

这样的输入序列，我可以将其解释为

10000011111111

或 8447，并将其编码在 8193<n<8464 that is otherwise inaccessible! However, once I reach

10000100010001

区域内， 8465，我需要重新使用 7 位编码。这使得该方法对输入敏感，并且实际上仅对起始字节为 10000100（132，ASCII 'Z'）的两字节序列有用。我宁愿我的编码器不输入敏感。

我有两个问题：

1. 我对base-n编码的理解似乎总体上是正确的吗？除了维基百科页面，我还能去哪里了解它？

2. 我可以使用任何技巧或技术来提高除base32/64/128之外的任意基数的base-n压缩效率吗？

 

---

参考文献

这一点以下的所有内容都不需要阅读来回答我的问题。

这个小型 PHP 脚本计算每个可能的底^指数（对于 0n （对于 0<n<256). It then subtracts the results of the two calculations, and lists the results in ascending order.

它是为 Linux 编写的，但如果您注释掉

fprintf()

调用（其中包含一些转义序列），则应该可以在 Windows 上正常运行。

请注意，该程序将生成 30,145 行输出:)

<?php

$c = 0;
$op = 0;

for ($i = 3; $i < 513; $i++) {
    for ($j = 2; $j < 257; $j++) {
        $p = ($c * 100) / 33835;
        if ($p > $op + 5 || $p == 100) {
            fprintf(STDERR, "\rgen:  %2.1f%%", $p);
            $op = $p;
        }
        if ($i >= 2 ** 32 || $j >= 2 ** 32 || $i ** $j >= 2 ** 32) continue;
        for ($k = 1; $k < 33; $k++) {
            $x = $i ** $j - 2 ** $k;
            if ($x < 0) continue;
            if (!isset($a[$x])) $a[$x] = [];
            $a[$x][] = [ $i, $j, $k, $i ** $j, 2 ** $k, (float)sprintf("%2.1f", ((2 ** $k) / ($i ** $j)) * 100) ];
            $c++;
        }
    }
}

foreach ($a as $i => $_) {
    if ($i < 0) {
        print "\r64-bit machine required\n";
        die;
    }
}

$q = $op = $c = 0;
foreach ($a as $i => $_) {
    $p = ($c * 100) / 28013;
    if ($p > $op + 5 || $p == 100) {
        fprintf(STDERR, "\rsort: %2.1f%%", $p);
        $op = $p;
    }
    $c++;
    uasort($a[$i], function($a, $b) {
        return $a[0] < $b[0];
    });
}

fprintf(STDERR, "\rsort root\e[K");
uksort($a, function($a, $b) {
    return $a > $b;
});

fprintf(STDERR, "\r\e[K");
$l = 0;
foreach ($a as $i => $z) {
    foreach ($z as $x) {
        print
            sprintf("%5d %5.1f%%", $l++, $x[5])
            .' ('.$x[0].'^'.$x[1].'='.sprintf("%.0f", $x[0] ** $x[1]).')'
            .'-(2^'.$x[2].'='.(2 ** $x[2]).')'
            .'='.$i
            ."\n";

    }
}

---

正如本问题开头第二段末尾所指出的，这里是与 2ⁿ 完美匹配 0<n<256.

的指数组合的完整列表

格式为：行号； (2^n) / (基数^指数) 表示为百分比； (底^指数=结果)-(2^指数)=距离。

注意第 9 行的 base64。Base92 位于上述程序完整输出的第 200 行。

    0 100.0% (512^3=134217728)-(2^27=134217728)=0
    1 100.0% (512^2=262144)-(2^18=262144)=0
    2 100.0% (256^3=16777216)-(2^24=16777216)=0
    3 100.0% (256^2=65536)-(2^16=65536)=0
    4 100.0% (128^4=268435456)-(2^28=268435456)=0
    5 100.0% (128^3=2097152)-(2^21=2097152)=0
    6 100.0% (128^2=16384)-(2^14=16384)=0
    7 100.0% (64^3=262144)-(2^18=262144)=0
    8 100.0% (64^2=4096)-(2^12=4096)=0
    9 100.0% (64^4=16777216)-(2^24=16777216)=0
   10 100.0% (64^5=1073741824)-(2^30=1073741824)=0
   11 100.0% (32^6=1073741824)-(2^30=1073741824)=0
   12 100.0% (32^5=33554432)-(2^25=33554432)=0
   13 100.0% (32^4=1048576)-(2^20=1048576)=0
   14 100.0% (32^3=32768)-(2^15=32768)=0
   15 100.0% (32^2=1024)-(2^10=1024)=0
   16 100.0% (16^2=256)-(2^8=256)=0
   17 100.0% (16^7=268435456)-(2^28=268435456)=0
   18 100.0% (16^6=16777216)-(2^24=16777216)=0
   19 100.0% (16^5=1048576)-(2^20=1048576)=0
   20 100.0% (16^4=65536)-(2^16=65536)=0
   21 100.0% (16^3=4096)-(2^12=4096)=0
   22 100.0% (8^10=1073741824)-(2^30=1073741824)=0
   23 100.0% (8^8=16777216)-(2^24=16777216)=0
   24 100.0% (8^7=2097152)-(2^21=2097152)=0
   25 100.0% (8^6=262144)-(2^18=262144)=0
   26 100.0% (8^5=32768)-(2^15=32768)=0
   27 100.0% (8^4=4096)-(2^12=4096)=0
   28 100.0% (8^3=512)-(2^9=512)=0
   29 100.0% (8^2=64)-(2^6=64)=0
   30 100.0% (8^9=134217728)-(2^27=134217728)=0
   31 100.0% (4^3=64)-(2^6=64)=0
   32 100.0% (4^8=65536)-(2^16=65536)=0
   33 100.0% (4^4=256)-(2^8=256)=0
   34 100.0% (4^5=1024)-(2^10=1024)=0
   35 100.0% (4^6=4096)-(2^12=4096)=0
   36 100.0% (4^7=16384)-(2^14=16384)=0
   37 100.0% (4^13=67108864)-(2^26=67108864)=0
   38 100.0% (4^9=262144)-(2^18=262144)=0
   39 100.0% (4^10=1048576)-(2^20=1048576)=0
   40 100.0% (4^11=4194304)-(2^22=4194304)=0
   41 100.0% (4^12=16777216)-(2^24=16777216)=0
   42 100.0% (4^14=268435456)-(2^28=268435456)=0
   43 100.0% (4^15=1073741824)-(2^30=1073741824)=0
   44 100.0% (4^2=16)-(2^4=16)=0

Answer 1

base128 无效，因为您必须使用大于“128”的字符巫码。对于字符女巫代码> = 128 chrome，发送两个字节...（因此发送时该字符的1MB字符串女巫将更改为2MB字节...所以您失去了所有利润）。对于 Base64 字符串，这种现象不会出现（所以我们只丢失了约 33%）。更多详细信息在“更新”部分。