字符串中包含的以 10 为基数的大数字的最佳压缩
Optimal compression for a large base 10 number contained in a string
我正在为包含 10 位数字的字符串编写压缩和解压缩函数。我认为，由于仅对 10 个字符进行操作，因此存在可以表示大字符串的小得多的字符串。压缩结果以 ISO-8859-7 编码，所以我可以在结果字符串中使用 256 个字符
例如，我想取一个表示1000位数字的字符串（this one, for example) and "compress it". Numbers of these lengths exceed the number type in the language that I am working in, JavaScript. As such, numeric manipulation/conversion is out of the question. The compression software I use (shoco）不压缩数字。完全没有。
我该怎么做？是否有某种算法可用于压缩数字？我不是在寻找执行速度，而是在寻找大多数数字的最佳压缩，而不仅仅是作为示例给出的数字。
如果您以三位数字为一组处理数字，则可以用 10 位表示每个三元组，而浪费很少。然后你 "just" 需要从你的 10 位三元组流创建一个 8 位八位字节流，这将需要一定量的位移，但并不十分复杂。
假定您的号码由 3 位数字的倍数组成（您可以用前导零填充它）或者您知道它包含多少位数字（在这种情况下您可以在末尾用尾随零填充它） .如果您将子序列编码为 50 位单元，您将有足够的代码空间来编码最多 15 位数字的数字序列，而不仅仅是 15 位数字，这将避免填充的需要。在一种使用 53 位浮点作为通用数字类型的语言中，您几乎无法摆脱它，但它可能值得也可能不值得额外的复杂化。
rici 的答案，每三位使用 10 位，这确实是我实际应用中会使用的。
但是，由于您要求 最佳 压缩并声明您不关心速度，因此将使用多精度算法生成十进制数的二进制表示。此代码已在 GMP library 中为您编写。该库经过高度优化且速度非常快，因此您不会看到巨大的速度影响，具体取决于您对数字进行的其他操作。
例如，您的 1000 位数字需要 418 个字节才能使用 334 组 10 位进行编码。当编码为单个大的二进制整数时，它将占用 416 个字节。在 2 GHz i7 上，使用 10 位组进行 1000 位数字转换需要 1.9 µs，而使用多精度算法生成大整数需要 55 µs。
更新：
我错过了 javascript 标签，直到有人在评论中指出它。您可以在 javascript.
中使用 Crunch 进行多精度运算
更新二：
正如 rici 所指出的，上面的比较假设输入的长度对于两种编码都是先验已知的。但是，如果比特流需要嵌入到更大的流中，并且先验地不知道位数，则必须提供一种方法来确定数字结束的位置。
三个数字的 10 位编码允许使用最终的 10 位代码作为该标记，因为 24 个可能的值未被使用。事实上，我们可以使用这 24 个中的 10 个来为数字提供多一位数字。 （我们甚至可以通过使用 0..19 的 20 个值来添加 "half" 数字，如果在该位置出现则允许前导 1。或者我们可以将其用于符号以允许负整数。但我离题了。）这个结果证明对于 1000 位数字的情况是完美的，它是三的倍数加一。然后 1000 位可以用 418 字节的结束标记进行编码，与之前不需要结束标记时相同。 （在比特流中，它实际上可以是 417.5 字节。）
对于二进制整数，我们可以在它前面加上一个以位为单位的长度，或者使用位填充来用一系列的位来标记流的结尾。无论哪种方式，开销都大致相同。我们将执行后者，以便轻松处理任意长度的整数。 1000 位整数将占用 3322 位，或 415 字节和两位。我们可以选择数据中一位最大运行为11长。当连续出现 11 个 1 时，向流中塞入一个 0 位。如果在一行中看到 12 个 1，那么您已经到达流的末尾（丢弃 12 个 1 和前面的 0。）使用 11 将在末尾添加 13 位，并允许最多填充一位填充最后一个字节（填充位的平均数为 0.81），使总字节数达到 417.
所以仍然有增益，准确地说是四位，虽然现在由于未使用的 10 位模式的优势而减少了。
我正在为包含 10 位数字的字符串编写压缩和解压缩函数。我认为，由于仅对 10 个字符进行操作，因此存在可以表示大字符串的小得多的字符串。压缩结果以 ISO-8859-7 编码，所以我可以在结果字符串中使用 256 个字符
例如，我想取一个表示1000位数字的字符串（this one, for example) and "compress it". Numbers of these lengths exceed the number type in the language that I am working in, JavaScript. As such, numeric manipulation/conversion is out of the question. The compression software I use (shoco）不压缩数字。完全没有。
我该怎么做？是否有某种算法可用于压缩数字？我不是在寻找执行速度，而是在寻找大多数数字的最佳压缩，而不仅仅是作为示例给出的数字。
如果您以三位数字为一组处理数字，则可以用 10 位表示每个三元组，而浪费很少。然后你 "just" 需要从你的 10 位三元组流创建一个 8 位八位字节流，这将需要一定量的位移，但并不十分复杂。
假定您的号码由 3 位数字的倍数组成（您可以用前导零填充它）或者您知道它包含多少位数字（在这种情况下您可以在末尾用尾随零填充它） .如果您将子序列编码为 50 位单元，您将有足够的代码空间来编码最多 15 位数字的数字序列，而不仅仅是 15 位数字，这将避免填充的需要。在一种使用 53 位浮点作为通用数字类型的语言中，您几乎无法摆脱它，但它可能值得也可能不值得额外的复杂化。
rici 的答案，每三位使用 10 位，这确实是我实际应用中会使用的。
但是，由于您要求 最佳 压缩并声明您不关心速度，因此将使用多精度算法生成十进制数的二进制表示。此代码已在 GMP library 中为您编写。该库经过高度优化且速度非常快，因此您不会看到巨大的速度影响，具体取决于您对数字进行的其他操作。
例如，您的 1000 位数字需要 418 个字节才能使用 334 组 10 位进行编码。当编码为单个大的二进制整数时，它将占用 416 个字节。在 2 GHz i7 上，使用 10 位组进行 1000 位数字转换需要 1.9 µs，而使用多精度算法生成大整数需要 55 µs。
更新：
我错过了 javascript 标签，直到有人在评论中指出它。您可以在 javascript.
中使用 Crunch 进行多精度运算更新二：
正如 rici 所指出的，上面的比较假设输入的长度对于两种编码都是先验已知的。但是，如果比特流需要嵌入到更大的流中，并且先验地不知道位数，则必须提供一种方法来确定数字结束的位置。
三个数字的 10 位编码允许使用最终的 10 位代码作为该标记，因为 24 个可能的值未被使用。事实上，我们可以使用这 24 个中的 10 个来为数字提供多一位数字。 （我们甚至可以通过使用 0..19 的 20 个值来添加 "half" 数字，如果在该位置出现则允许前导 1。或者我们可以将其用于符号以允许负整数。但我离题了。）这个结果证明对于 1000 位数字的情况是完美的，它是三的倍数加一。然后 1000 位可以用 418 字节的结束标记进行编码，与之前不需要结束标记时相同。 （在比特流中，它实际上可以是 417.5 字节。）
对于二进制整数，我们可以在它前面加上一个以位为单位的长度，或者使用位填充来用一系列的位来标记流的结尾。无论哪种方式，开销都大致相同。我们将执行后者，以便轻松处理任意长度的整数。 1000 位整数将占用 3322 位，或 415 字节和两位。我们可以选择数据中一位最大运行为11长。当连续出现 11 个 1 时，向流中塞入一个 0 位。如果在一行中看到 12 个 1，那么您已经到达流的末尾（丢弃 12 个 1 和前面的 0。）使用 11 将在末尾添加 13 位，并允许最多填充一位填充最后一个字节（填充位的平均数为 0.81），使总字节数达到 417.
所以仍然有增益，准确地说是四位，虽然现在由于未使用的 10 位模式的优势而减少了。