按准对数标度压缩
Compression by quazi-logarithmic scale
我需要压缩一大组（无符号）整数值，而目标是保持它们的 相对 精度。简单来说，1,2,3差别很大，1001,1002,1003差别很小
所以，我需要一种有损转换。自然选择构建对数刻度，缺点是转换to/from需要浮点运算，log/exp计算等。
OTOH 我不需要真正的对数刻度，我只需要它在某种意义上类似于它。
我想到了以 浮点数 方式对数字进行编码的想法。也就是我给每一个压缩后的数分配N位，其中一些代表尾数，剩下的代表顺序。尾数大小和阶数的选择取决于所需的范围和精度。
我的问题是：这是个好主意吗？或者也许存在更好的编码方案w.r.t。计算复杂度与质量（与对数刻度相似）。
我具体实现了什么：
正如我所说，尾数位和顺序位。顺序位在前，因此编码数字越大 - 原始数字越大。
实际数字是通过在尾数上附加一个额外的前导位（又名隐式位）并按编码顺序左移来解码的。最小的解码数字将是 1 << M，其中 M 是尾数的大小。如果所需的范围应该从 0 开始（就像我的情况），那么可以减去这个数字。
数字编码也很简单。添加 1 << M，然后找到它的顺序，即它应该右移多少直到它适合我们的带有隐式前导位的尾数，然后编码就很简单了。查找顺序是通过中值搜索完成的，结果只需 if 秒。 （比如有4个阶位，最大阶为15，在4if秒内找到）。
我称之为 "quazi-logarithmic" 规模。数字越大，绝对精度越低。但与粒度连续增加的真正对数尺度不同，在我们的例子中，它在每个固定大小范围后跳跃 2 倍。
这种编码的优点：
- 快速编解码
- 没有浮点数，在处理它们、边界情况等时没有隐含的精度损失。
- 不依赖于标准库、复杂的数学函数等
- 编码和解码可以通过 C++ 模板实现，因此转换甚至可以在 编译时 实现。这对于以人类可读的方式定义一些编译时常量很方便。
在您的压缩算法中，压缩后产生相同输出的每组数字将被解压缩为该组中的最小数字。如果将其更改为中间的数字，则平均故障会减少。
例如对于 8 位尾数和 5 位指数，[0x1340, 0x1350) 范围内的数字将被 decompress(compress(x)) 转换为 0x1340。如果首先压缩整个范围然后再解压，则总差将为 120。如果输出为 0x1348，则总误差仅为 64，这将误差减少了 46.7%。所以简单地添加 2 << (exponent - 1) 到输出将显着减少压缩方案的错误。
除此之外，我认为此方案没有太大问题。请记住，您需要对 0 进行特定编码。可能会有其他编码，但在不知道任何关于输入的具体信息的情况下，这将是您可以获得的最佳编码。
编辑：
虽然可以将结果的校正从解压缩转移到压缩步骤，但这会增加将指数范围扩大一倍的费用。这是因为对于设置了 MSB 的数字，只有一半的数字会使用相应的指数（另一半将由设置了第二高有效位的数字填充）。设置了 MSB 的较高一半的数字将被放置在下一个更高的顺序中。
例如对于用 15 位尾数编码的 32 位数字，直到 0x8FFF FFFF 将具有阶数 15（尾数 = 0x1FFF 和指数 = 15）。所有更高的值将具有 16 阶（尾数 = 0x?FFF 和指数 = 16）。虽然指数增加 1 本身看起来并不多，但在本例中它已经为指数增加了额外的位。
此外，上述示例的解压步骤会产生整数溢出，这在某些情况下可能会出现问题（例如，如果在 checked 模式下完成解压，C# 将抛出异常） .这同样适用于压缩步骤：除非处理得当，否则将 2^(order(n) - 1) 添加到输入 n 将导致溢出，因此将数字排列为 0.
我建议将修正移动到解压缩步骤（如上所示）以消除潜在的整数溢出作为 problems/bugs 的来源，并保持需要编码的指数数量最少。
编辑2：
这种方法的另一个问题是，当对压缩进行校正时，一半的数字（不包括最低阶）最终会变成更大的 "group"，从而降低精度。
我需要压缩一大组（无符号）整数值，而目标是保持它们的 相对 精度。简单来说，1,2,3差别很大，1001,1002,1003差别很小
所以，我需要一种有损转换。自然选择构建对数刻度，缺点是转换to/from需要浮点运算，log/exp计算等。
OTOH 我不需要真正的对数刻度，我只需要它在某种意义上类似于它。
我想到了以 浮点数 方式对数字进行编码的想法。也就是我给每一个压缩后的数分配N位，其中一些代表尾数，剩下的代表顺序。尾数大小和阶数的选择取决于所需的范围和精度。
我的问题是：这是个好主意吗？或者也许存在更好的编码方案w.r.t。计算复杂度与质量（与对数刻度相似）。
我具体实现了什么：
正如我所说，尾数位和顺序位。顺序位在前，因此编码数字越大 - 原始数字越大。
实际数字是通过在尾数上附加一个额外的前导位（又名隐式位）并按编码顺序左移来解码的。最小的解码数字将是 1 << M，其中 M 是尾数的大小。如果所需的范围应该从 0 开始（就像我的情况），那么可以减去这个数字。
数字编码也很简单。添加 1 << M，然后找到它的顺序，即它应该右移多少直到它适合我们的带有隐式前导位的尾数，然后编码就很简单了。查找顺序是通过中值搜索完成的，结果只需 if 秒。 （比如有4个阶位，最大阶为15，在4if秒内找到）。
我称之为 "quazi-logarithmic" 规模。数字越大，绝对精度越低。但与粒度连续增加的真正对数尺度不同，在我们的例子中，它在每个固定大小范围后跳跃 2 倍。
这种编码的优点：
- 快速编解码
- 没有浮点数，在处理它们、边界情况等时没有隐含的精度损失。
- 不依赖于标准库、复杂的数学函数等
- 编码和解码可以通过 C++ 模板实现，因此转换甚至可以在 编译时 实现。这对于以人类可读的方式定义一些编译时常量很方便。
在您的压缩算法中，压缩后产生相同输出的每组数字将被解压缩为该组中的最小数字。如果将其更改为中间的数字，则平均故障会减少。
例如对于 8 位尾数和 5 位指数，[0x1340, 0x1350) 范围内的数字将被 decompress(compress(x)) 转换为 0x1340。如果首先压缩整个范围然后再解压，则总差将为 120。如果输出为 0x1348，则总误差仅为 64，这将误差减少了 46.7%。所以简单地添加 2 << (exponent - 1) 到输出将显着减少压缩方案的错误。
除此之外，我认为此方案没有太大问题。请记住，您需要对 0 进行特定编码。可能会有其他编码，但在不知道任何关于输入的具体信息的情况下，这将是您可以获得的最佳编码。
编辑：
虽然可以将结果的校正从解压缩转移到压缩步骤，但这会增加将指数范围扩大一倍的费用。这是因为对于设置了 MSB 的数字，只有一半的数字会使用相应的指数（另一半将由设置了第二高有效位的数字填充）。设置了 MSB 的较高一半的数字将被放置在下一个更高的顺序中。
例如对于用 15 位尾数编码的 32 位数字，直到 0x8FFF FFFF 将具有阶数 15（尾数 = 0x1FFF 和指数 = 15）。所有更高的值将具有 16 阶（尾数 = 0x?FFF 和指数 = 16）。虽然指数增加 1 本身看起来并不多，但在本例中它已经为指数增加了额外的位。
此外，上述示例的解压步骤会产生整数溢出，这在某些情况下可能会出现问题（例如，如果在 checked 模式下完成解压，C# 将抛出异常） .这同样适用于压缩步骤：除非处理得当，否则将 2^(order(n) - 1) 添加到输入 n 将导致溢出，因此将数字排列为 0.
我建议将修正移动到解压缩步骤（如上所示）以消除潜在的整数溢出作为 problems/bugs 的来源，并保持需要编码的指数数量最少。
编辑2：
这种方法的另一个问题是，当对压缩进行校正时，一半的数字（不包括最低阶）最终会变成更大的 "group"，从而降低精度。