将大整数压缩为尽可能小的字符串

Question

我在 URL 中传递了一堆 10 位整数。像这样的东西： “4294965286”，“2292964213”。它们将始终为正数并且始终为 10 位数。

我想将这些整数压缩成仍然可以在 URL 中使用的最小形式（又名字母和数字完全没问题），然后稍后解压缩它们。我看过使用 gzipstream 但它会创建更大的字符串，而不是更短的字符串。

我目前使用的是 asp.net，因此 vb.net 或 c# 解决方案是最好的。

谢谢

Answer 1

是的。 GZIP 是一种压缩算法，它既需要可压缩数据，又具有开销（帧和字典等）。应改用编码算法。

“简单”方法是使用base-64编码。

也就是说，将数字（在字符串中表示为基数 10）转换为表示该数字的实际字节序列（5 个字节将覆盖 10 位十进制数字），然后将结果转换为基数 64。每个 Base-64 字符存储 6 位信息（精确到小数~3.3 位/字符），因此将导致大小大约刚刚超过一半（在这种情况下，需要 6* Base-64 输出字符）。

此外，由于输入/输出长度可从数据本身获得，因此“123”可能最初（在进行 Base-64 编码之前）转换为 1 字节，“30000”转换为 2 字节等。如果不是全部，这将是有利的这些数字的长度大致相同。

快乐编码。

---

* 使用 base-64 需要 6 个输出字符。

编辑：我最初错了，我说十进制为“2.3 位/字符”，并建议需要少于一半的字符。我已经更新了上面的答案，并在此处显示了（应该是正确的）数学，其中 lg(n) 是以 2 为底的对数。

表示输入数字所需的输入位数为 位/字符 * 字符 -> lg(10) * 10 （或只是 lg(9999999999)） -> ~33.2 位。使用jball的操作先对数字进行移位，需要的位数为lg(8999999999) -> ~33.06 位。然而，在这种特殊情况下，这种转换无法提高效率（需要将输入位数减少到 30 或以下才能产生影响）。

因此，我们尝试找到一个 x（base-64 编码中的字符数），使得：

lg(64) * x = 33.2 -> 6 * x = 33.2 -> x ~ 5.53。当然，五个半字符是没有意义的，因此我们选择 6 作为在 Base-64 编码中编码高达 999999999 的值所需的最大字符数。这比原来 10 个字符的一半多一点。

但是，应该注意的是，要在 Base-64 输出中仅获取 6 个字符，需要非标准的 Base-64 编码器或进行一些操作（大多数 Base-64 编码器仅适用于整个字节）。这是可行的，因为在最初的 5 个“所需字节”中，仅使用了 40 位中的 34 位（前 6 位始终为 0）。需要 7 个 base-64 字符来编码所有 40 位。

这是 Guffa 在他的答案中发布的代码的修改（如果你喜欢它，请给他投票），只需要 6 个 base-64 字符。请参阅 Guffa 的回答和 Base64 for URL applications 中的其他注释，因为下面的方法不使用URL友好的映射。

byte[] data = BitConverter.GetBytes(value);
// make data big-endian if needed
if (BitConverter.IsLittleEndian) {
   Array.Reverse(data);
}
// first 5 base-64 character always "A" (as first 30 bits always zero)
// only need to keep the 6 characters (36 bits) at the end 
string base64 = Convert.ToBase64String(data, 0, 8).Substring(5,6);

byte[] data2 = new byte[8];
// add back in all the characters removed during encoding
Convert.FromBase64String("AAAAA" + base64 + "=").CopyTo(data2, 0);
// reverse again from big to little-endian
if (BitConverter.IsLittleEndian) {
   Array.Reverse(data2);
}
long decoded = BitConverter.ToInt64(data2, 0);

---

使其“更漂亮”

由于 base-64 已确定使用 6 个字符，因此任何仍将输入位编码为 6 个字符的编码变体都将创建同样小的输出。使用 base-32 编码 不会完全成功，如 base-32 编码 6字符只能存储 30 位信息 (lg(32) * 6)。

但是，使用自定义的 base-48（或 52/62）编码可以实现相同的输出大小。 （基数 48-62 的优点是它们只需要字母数字字符的子集，不需要符号；可选地，可以避免变体中的“不明确”符号，例如 1 和“I”）。使用 base-48 系统，6 个字符可以编码约 33.5 位 (lg(48) * 6) 的信息，该信息略高于约 33.2（或约33.06）位 (lg( 10) * 10) 必需。

这是一个概念验证：

// This does not "pad" values
string Encode(long inp, IEnumerable<char> map) {
    Debug.Assert(inp >= 0, "not implemented for negative numbers");

    var b = map.Count();
    // value -> character
    var toChar = map.Select((v, i) => new {Value = v, Index = i}).ToDictionary(i => i.Index, i => i.Value);
    var res = "";
    if (inp == 0) {
      return "" + toChar[0];
    }
    while (inp > 0) {
      // encoded least-to-most significant
      var val = (int)(inp % b);
      inp = inp / b;
      res += toChar[val];
    }
    return res;
}

long Decode(string encoded, IEnumerable<char> map) {
    var b = map.Count();
    // character -> value
    var toVal = map.Select((v, i) => new {Value = v, Index = i}).ToDictionary(i => i.Value, i => i.Index);      
    long res = 0;
    // go in reverse to mirror encoding
    for (var i = encoded.Length - 1; i >= 0; i--) {
      var ch = encoded[i];
      var val = toVal[ch];
      res = (res * b) + val;
    }
    return res;
}

void Main()
{
    // for a 48-bit base, omits l/L, 1, i/I, o/O, 0
    var map = new char [] {
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K',
        'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
        'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g',
        'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't',
        'u', 'v', 'x', 'y', 'z', '2', '3', '4',
    };
    var test = new long[] {0, 1, 9999999999, 4294965286, 2292964213, 1000000000};
    foreach (var t in test) {
        var encoded = Encode(t, map);
        var decoded = Decode(encoded, map);
        Console.WriteLine(string.Format("value: {0} encoded: {1}", t, encoded));
        if (t != decoded) {
            throw new Exception("failed for " + t);
        }
    }
}

结果是：

value: 0 encoded: A
value: 1 encoded: B
value: 9999999999 encoded: SrYsNt
value: 4294965286 encoded: ZNGEvT
value: 2292964213 encoded: rHd24J
value: 1000000000 encoded: TrNVzD

---

上面考虑了数字“随机且不透明”的情况；也就是说，对于数字的内部结构没有任何可以确定的信息。然而，如果存在已定义的结构（例如，第 7、8 和 9 位始终为零，第 2 和 15 位始终相同），那么——当且仅当可以消除 4 位或更多位信息 /em> 来自输入——仅需要 5 个 base-64 字符。增加的复杂性和对结构的依赖很可能超过任何边际收益​​。

Answer 2

您可以使用 base64 编码将数据减少为七个字符。您需要五个字节来表示数字，并且可以使用 base64 将它们编码为八个字符，但最后一个字符始终是填充符 =，因此可以将其删除：

long value = 4294965286;

// get the value as an eight byte array (where the last three are zero)
byte[] data = BitConverter.GetBytes(value);
// encode the first five bytes
string base64 = Convert.ToBase64String(data, 0, 5).Substring(0, 7);
Console.WriteLine(base64);

输出：

Jvj//wA

要解码文本，再次添加 =，对其进行解码，并将其读取为数字：

// create an eight byte array
byte[] data = new byte[8];
// decode the text info five bytes and put in the array
Convert.FromBase64String(base64 + "=").CopyTo(data, 0);
// get the value from the array
long value = BitConverter.ToInt64(data, 0);

Console.WriteLine(value);

输出：

4294965286

base64 使用的两个字符不适合在 URL 中使用，因此您可以将它们替换为其他字符，然后将它们放回原处。例如，+ 和 / 字符可以替换为 - 和 _。

Answer 3

我认为您正在寻找的是哈希 ID： http://hashids.org/

它们有多种语言的实现，虽然看起来 C# 并不是其中之一。

我用 JavaScript 为您做了一个示例： http://codepen.io/codycraven/pen/MbWwQm

var hashids = new Hashids('my salt', 1, 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890');
var input = 4294965286;
var hex = input.toString(16); // 8 characters: fffff826
var hashid = hashids.encode(input); // 7 characters: 0LzaR1Y
var base64 = window.btoa(input).replace(/=+/, ''); // 14 characters: NDI5NDk2NTI4Ng

请注意，HashID 库可保护您的哈希值不包含粗俗语言。

Answer 4

除了更改编码的基础 (pst 我大约在同一时间有同样的想法），因为你所有的数字都是10位十进制数字，你可以从每个数字中减去最小的10位数字（10E9）在对其进行编码之前，然后在解码后将其添加回来。这会将您的编码数字转移到 0 - 8999999999 的范围内，从而在基数更改后允许更小的字符串。

Answer 5

将大数转换为公式怎么样：所以我可能会使用 4^34 而不是 21312312312。 链接

Answer 6

我喜欢@user166390的答案，但我更喜欢从大到小的格式，并认为代码可以改进，因为在编码中不需要使用字典，并且不需要在每次解码时生成。另外，我添加了一个例外并更改为 ulong，因为不支持负值。

如果有人有进一步的性能改进，请随意写。也许如果有更好的替代 StringBuilder

这是我修改的代码。

        public static string EncodeNumber(ulong input)
        {
            return EncodeNumber(input, Mapping85Bit);
        }

        // This does not "pad" values
        private static string EncodeNumber(ulong inp, char[] map)
        {
            // use ulong count instead of int since does not matter on x64 operating system.
            ulong cnt = (ulong)map.Length;
            // value -> character
            if (inp == 0)
            {
                return map[0].ToString();
            }
            var sb = new StringBuilder();
            while (inp > 0)
            {
                // encoded most-to-least significant
                ulong val = inp % cnt;
                inp = inp / cnt;
                sb.Insert(0, map[(int)val]);
            }
            return sb.ToString();
        }

        public static ulong DecodeNumber(string encoded)
        {
            return DecodeNumber(encoded, Mapping85Bit, Mapping85BitDict);
        }

        private static ulong DecodeNumber(string encoded, char[] map, Dictionary<char, ulong> charMapDict)
        {
            // use ulong count instead of int since does not matter on x64 operating system.
            ulong b = (ulong)map.Length;
            ulong res = 0;
            for (var i = 0; i < encoded.Length; i++)
            {
                char ch = encoded[i];
                if(!charMapDict.TryGetValue(ch, out ulong val))
                {
                    throw new ArgumentException($"Invalid encoded number: '{encoded}'. '{ch}' is not a valid character for this encoding.");
                }
                res = (res * b) + val;
            }
            return res;
        }



        // Windows file system reserved characters:     < > : " / \ | = * 

        /// <summary>
        /// Compatible with file system. Originates from ASCII table except starting like Base64Url and except windows path reserved chars. Skipped '/' and '\' to prevent path problems. Skipped ' for sql problems.
        /// https://www.ascii-code.com/
        /// Does not need to be encoded for json since it doesn't use \ and ". No encoding also needed for xml since < > are also not used. That is why it is also different to https://en.wikipedia.org/wiki/Ascii85
        /// </summary>
        public static readonly char[] Mapping85Bit = new char[] {
            'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
            'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
            'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd',
            'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
            'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
            'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7',
            '8', '9', '-', '_', ' ', '!', '#', '
, '%', '&',
            '(', ')', '+', ',', '.', ';', '?', '@', '[', ']',
            '^', '`', '{', '}', '~'
        };
        private static readonly Dictionary<char, ulong> Mapping85BitDict = Mapping85Bit.Select((v, i) => new { Value = v, Index = (ulong)i }).ToDictionary(i => i.Value, i => i.Index);

    [Test]
    public void EncodeTest()
    {
        // 85Bit Encoding:
        Assert.AreEqual(EncodeNumber(85), "BA");
        Assert.AreEqual(EncodeNumber(86), "BB");
        Assert.AreEqual(EncodeNumber(3), "D");
        Assert.AreEqual(EncodeNumber(84), "~");

        Assert.AreEqual(EncodeNumber(0), "A");

        Assert.AreEqual(DecodeNumber("BA"), 85);

        Assert.AreEqual(DecodeNumber("BA"), 85);
        Assert.AreEqual(DecodeNumber("`"), 81);
    }