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

Question

我有一堆10位数的整数,我在URL中传递.类似于:"4294965286","2292964213".它们总是积极的,总是10位数.

我想将这些整数压缩成可以在URL中使用的最小可能形式(也就是字母和数字完全正常),然后在以后解压缩它们.我已经看过使用gzipstream,但它创建了更大的字符串,而不是更短.

我目前正在使用asp.net,所以vb.net或c#解决方案是最好的.

谢谢

Answer 1

是.GZIP是一种压缩算法,它既需要可压缩数据,又需要开销(框架和字典等).一个编码算法应被代替使用.

"简单"方法是使用base-64编码.

也就是说,将数字(在字符串中表示为基数10)转换为表示数字的实际字节系列(5个字节将覆盖10位十进制数),然后将结果转换为base-64.每个base-64字符存储6位信息(小数~3.3位/字符),因此将导致大约一半以上的大小(在这种情况下,需要6*base-64输出字符).

另外,由于输入/输出长度可以从数据本身获得,"123"可能最初(在进行base-64编码之前)转换为1字节,"30000"转换为2字节等.如果不是全部,这将是有利的.数字大致相同.

快乐的编码.

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

编辑:我最初错误的地方,我说十进制的"2.3位/字符",并提出不到一半的字符是必需的.我已经更新了上面的答案,并在这里显示(应该是正确的)数学,其中lg(n)是登录到基数2.

表示输入数字所需的输入位数是bits/char * chars- > lg(10) * 10(或仅lg(9999999999)) - > ~33.2 bits.使用jball的操作来首先移动数字,所需的位数是lg(8999999999)- > ~33.06 bits.然而,在这种特定情况下,这种转换不能提高效率(输入比特的数量需要减少到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的答案中的其他说明和URL应用程序的Base64,因为下面的方法不使用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位或更多位信息时- - 只需要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 中使用，因此您可以将它们替换为其他字符，然后将它们替换回来。例如，+and/字符可以替换为-and _。

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

请注意，HashIDs库可保护您的哈希表不包含肮脏的语言。