큰 정수를 가능한 가장 작은 문자열로 압축

큰 정수를 가능한 가장 작은 문자열로 압축

URL에 전달하는 10자리 정수가 있습니다. "4294965286", "2292964213"과 같은 것입니다.항상 양수이고 항상 10자리입니다.

이러한 정수를 URL에서 사용할 수 있는 가장 작은 형식으로 압축한 다음 나중에 압축을 풀고 싶습니다.나는 gzipstream을 사용하는 것을 살펴보았지만 그것은 더 짧은 것이 아니라 더 큰 문자열을 합니다.

저는 현재 asp.net 을 사용하고 있으므로 vb.net 또는 c# 솔루션이 가장 좋습니다.

감사해요.

예. GZIP은 압축 가능한 데이터가 필요하고 오버헤드(프레임 및 사전 등)가 있는 압축 알고리즘입니다.대신 인코딩 알고리즘을 사용해야 합니다.

간단한 방법은 base-64 인코딩을 사용하는 것입니다.

즉, 숫자(문자열에서 기본 10으로 표시됨)를 숫자를 나타내는 실제 바이트 시리즈(5바이트가 10자리 10자리 숫자를 포함함)로 변환한 다음 결과를 기본 64로 변환합니다.각 base-64 문자는 6비트의 정보(소수점 ~3.3비트/문자)를 저장하므로 대략 절반 이상의 크기가 됩니다(이 경우 6* base-64 출력 문자가 필요함).

또한 입력/출력 길이는 데이터 자체에서 얻을 수 있기 때문에 "123"은 원래 (기본 64 인코딩 전) 1바이트, "30000"은 2바이트 등으로 변환될 수 있습니다.모든 숫자의 길이가 거의 동일하지 않은 경우 이 방법이 유용합니다.

해피 코딩.

---

base-64를 사용하려면 6개의 출력 문자가 필요합니다.

편집: 처음에 소수점에 대해 "2.3비트/char"라고 말한 것이 틀렸고 필요한 문자가 절반 미만이라고 제안했습니다.위의 답변을 업데이트하고 여기(정확해야 함) 수학을 보여줍니다.lg(n)기본 2에 로그합니다.

는 입력번나는데필입요력한비같다다습니음과수는트호입니다.bits/char * chars->lg(10) * 10 just (그냥)lg(9999999999)) ->~33.2 bits먼저 는 jball 의 조 사 용 하 여 숫 자 를 먼 이 다 니 같 습 과 다 음 수 는 비 트 필 한 요 작 면 하 을 동 저 ▁required ▁j ▁using ▁is 다 ▁of ▁bits 니 ▁the ▁the ▁number ball ▁shift , ▁first ▁j s ulation ball lg(8999999999)->~33.06 bits그러나 이러한 변환은 특정한 경우에 효율성을 증가시킬 수 없습니다(여기서 차이를 만들려면 입력 비트 수를 30 이하로 줄여야 합니다).

따라서 다음과 같은 x(base-64 인코딩의 문자 수)를 찾으려고 합니다.

lg(64) * x = 33.2->6 * x = 33.2->x ~ 5.53물론 5자 반은 무의미하므로 base-64 인코딩에서 최대 999999999까지의 값을 인코딩하는 데 필요한 최대 문자 수로 6자를 선택합니다.이것은 원래의 10자의 절반을 약간 넘는 것입니다.

그러나 base-64 출력에서 6자만 얻으려면 비표준 base-64 인코더 또는 약간의 조작이 필요합니다(대부분의 base-64 인코더는 전체 바이트에서만 작동함).이것은 원래의 5개의 "필수 바이트" 중 40비트 중 34비트만 사용되기 때문에 작동합니다(상위 6비트는 항상 0).40비트를 모두 인코딩하려면 7개의 기본 64자가 필요합니다.

구파가 답변에서 게시한 코드의 수정 사항입니다(마음에 들면, 가서 그에게 업 투표하세요). 6자만 필요합니다.아래 방법은 URL 친화적인 매핑을 사용하지 않기 때문에 URL 응용 프로그램에 대한 Guffa의 답변과 Base64의 다른 참고 사항을 참조하십시오.

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).

그러나 사용자 지정 기본 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);
        }
    }
}

결과는 다음과 같습니다.

값: 0 인코딩됨:a값: 1 인코딩됨:b값: 9999999999 인코딩:SrYsNt값: 4294965286 인코딩: ZNGEvT값: 2292964213 인코딩: rHd24j값: 1000000000 인코딩:TrNVzD

---

위에서는 숫자가 "무작위적이고 불투명한" 경우를 고려합니다. 즉, 숫자의 내부에 대해 결정할 수 있는 것은 아무것도 없습니다.그러나 정의된 구조가 있는 경우(예: 7번째, 8번째 및 9번째 비트는 항상 0이고 2번째 및 15번째 비트는 항상 동일) 입력에서 4비트 이상의 정보를 제거할 수 있는 경우에만 5개의 base-64 문자만 필요합니다.추가된 복잡성과 구조에 대한 의존성은 어떠한 한계 이득보다 훨씬 더 클 가능성이 높습니다.

base64 인코딩을 사용하여 데이터를 7자로 줄일 수 있습니다.숫자를 나타내려면 5바이트가 필요합니다. 그리고 그것들은 base64를 사용하여 8개의 문자로 인코딩될 수 있지만, 그 마지막 문자는 항상 채우기입니다.=제거할 수 있습니다.

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에서 사용하기에 적합하지 않으므로 다른 문자로 바꾼 다음 다시 바꿀 수 있습니다.그+그리고./를 들어 를 예들어문는자다대수체있될다습니로음으를있다수▁characters▁for▁could니로 대체할 수 있습니다.-그리고._.

제 생각에 당신이 찾고 있는 것은 해시 ID입니다: http://hashids.org/

C#이 그 중 하나가 아닌 것처럼 보이지만 여러 언어로 구현되어 있습니다.

자바스크립트로 예제를 만들었습니다: 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

해시에 유의하십시오.ID 라이브러리는 해시가 욕설을 포함하지 않도록 보호합니다.

인코딩의 기본을 변경하는 것 외에도(pst와 저는 비슷한 시기에 같은 생각을 했습니다), 모든 숫자가 10자리 숫자이기 때문에 인코딩하기 전에 각 숫자에서 가장 작은 10자리 숫자(10E9)를 뺀 다음 디코딩 후에 다시 추가할 수 있습니다.이렇게 하면 인코딩된 숫자가 0 - 8999999999 범위로 이동하여 기본 변경 후 더 작은 문자열을 사용할 수 있습니다.

큰 숫자를 공식으로 변환하면 어떨까요? 그래서 21312312312 대신 4^34를 사용할 수도 있습니다.링크

저는 @user166390 답변을 좋아했지만 가장 작은 형식을 선호했고 사전 사용이 인코딩에서 불필요하고 모든 디코딩에서 생성될 필요가 없기 때문에 코드를 개선할 수 있다고 생각했습니다.또한 음수 값이 지원되지 않기 때문에 예외를 추가하고 너무 오래 변경했습니다.

다른 사람이 성능 향상이 있으면 언제든지 글을 쓰십시오.String Builder보다 더 나은 대안이 있다면 어떨까요?

여기 제가 수정한 코드가 있습니다.

        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 &lt; &gt; 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);
    }

언급URL : https://stackoverflow.com/questions/5901153/compress-large-integers-into-smallest-possible-string