작은 값과 큰 숫자 (또는 문자열)을 압축

Question

내 ASP.NET 페이지 쿼리 문자열 매개 변수는 다음과 같습니다

여기

…?IDs=1000000012,1000000021,1000000013,1000000022&... 

IDs 매개 변수는 항상이 경우 ,에 뭔가로 분리 된 숫자를해야합니다. 현재 4 개의 숫자가 있지만 보통 3과 7 사이에 있습니다.

이제 큰 숫자를 가능한 가장 작은 값으로 변환하는 방법을 찾고 있습니다. 쿼리 문자열 매개 변수 IDs의 값을 구체적으로 압축합니다. 둘 다, 각 숫자 알고리즘을 압축하거나 IDs 쿼리 문자열 매개 변수의 전체 값을 압축하는 것은 환영합니다.

1. 인코딩 또는 디코딩은 문제가되지 않습니다. 그냥 값 IDs 쿼리 문자열 매개 변수를 압축.
2. IDs에 대해 고유 한 작은 값을 만든 다음 일부 데이터 원본에서 해당 값을 검색하는 것이 범위를 벗어납니다.

큰 숫자를 작은 값으로 압축하거나 IDs 쿼리 문자열 매개 변수의 값을 모두 함께 압축하는 알고리즘이 있습니까?

Answer 1

기본적으로 10을 사용하여 숫자를 표현하기 때문에 기본적으로 많은 공간이 필요합니다. 기본 16 (16 진수)을 사용하는 것이 좋습니다. 예를 들어, 255 (3 자리)를 ff (2 자리)로 나타낼 수 있습니다. '.':

당신은 훨씬 더 많은 수의 기지 ... 유효한 쿼리 문자열 매개 변수 모든 문자 집합을 사용하여 그 개념이 더 걸릴 수 있습니다

AZ, AZ, 0-9, '을 - ','~ ','_ ','+ '

이렇게하면 작업 할 67 자의 기본 문자를 얻을 수 있습니다 (Wikipedia on QueryString 참조).

기본 10을 임의의 수 기준으로 변환하는 방법은 this SO post을 참조하십시오.

편집 : 링크 된 SO 게시물에

,이 부분을보고 :

당신이 필요로하는 거의 무엇

string xx = IntToString(42, 
      new char[] { '0','1','2','3','4','5','6','7','8','9', 
      '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'}); 

. 그냥 몇 문자가없는 추가하여 확장 :

yz.-을 ~ _ + 게시물 :-) 다시 기본 내가 작성하지 않을거야 (10)에 갈 수있는 방법을 누락되었음을

절차는 다음과 같습니다.

TOTAL을 호출합니다.

오른쪽 문자를보고 배열의 위치를 ​​찾으십시오.
TOTAL = (배열의 문자 위치) 예 : 입력은 BA1입니다. TOTAL은 이제 1입니다 ("1"은 배열의 1 번 위치에 있기 때문에)

이제 첫 번째 문자의 왼쪽 문자를보고 배열의 위치를 ​​찾습니다. TOTAL + = 47 * (배열의 문자 위치) 예 : 입력은 BA1입니다. TOTAL은 (47 * 11) + 1 = 518

입니다. 이제 이전 문자의 왼쪽 문자를보고 배열의 위치를 ​​찾으십시오. TOTAL + = 47 * 47 * (배열의 문자 위치) 예 : 입력은 BA1입니다. 합계는 (47 * 47 * 10) + (47 * 11) + 1 = 243508

등입니다.

기본 10 진수를 47 진수로 변환 한 다음 다시 변환 코드가 제대로 작동하는지 확인하는 단위 테스트를 작성하는 것이 좋습니다. 유일한 문제는 URL의 길이, 당신은 다음, 에 숫자를 변환 번호로 다시 변환 할 수있는 경우는 기본 47 :-)

Answer 2

단지 3 자리에서 6 자리 기준 10 수를 표현하는 방법을

주 서버 측에서

Answer 3

숫자 범위는 무엇입니까? 그들은 내가, 16 비트 정수에 딱 맞는 수 있습니다 가정 :

16 비트 정수의 바이트 스트림을 구축 16-bit integers (번호 당 2 바이트 범위 -32,768 32,767)로

• 스토어의 모든 숫자 (적어도, (그물 번호 당 약 3 자)

그대로 URL에 대한 수정 된 base64 인코딩을 사용하여) 올바르게 바이트 스트림을

Base64 인코딩을 endianness을 처리해야합니다; XDR 여기에 좋은 옵션이 될 수 있습니다 ~ 추가 된 보너스는 각 숫자가 2 바이트라는 것을 알고 있기 때문에 쉼표 문자가 더 이상 필요하지 않습니다.

또는 그다지 좋지 않은 경우 zlib을 사용하여 정수 스트림을 압축 한 다음 zlib 압축 스트림을 base64 할 수 있습니다. 16 비트가 충분히 큰 범위가 아닌 경우 (즉, 1,000,000,000 개의 범위에 실제로 숫자가 필요한 경우) 32 비트 정수로 전환 할 수도 있습니다.

편집 :

어쩌면 너무 늦게, 그러나 여기에서 할 수있는 구현이 당신이 필요로하는 무엇을 :

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Scratch { 
    class Program { 
     static void Main(string[] args) { 
      //var ids = new[] { 1000000012, 1000000021, 1000000013, 1000000022 }; 
      var rand = new Random(); 
      var ids = new int[rand.Next(20)]; 
      for(var i = 0; i < ids.Length; i++) { 
       ids[i] = rand.Next(); 
      } 

      WriteIds(ids); 
      var s = IdsToString(ids); 
      Console.WriteLine("\nResult string is: {0}", s); 
      var newIds = StringToIds(s); 
      WriteIds(newIds); 
      Console.ReadLine(); 
     } 

     public static void WriteIds(ICollection<Int32> ids) { 
      Console.Write("\nIDs: "); 
      bool comma = false; 
      foreach(var id in ids) { 
       if(comma) { 
        Console.Write(","); 
       } else { 
        comma = true; 
       } 
       Console.Write(id); 
      } 
      Console.WriteLine(); 
     } 

     public static string IdsToString(ICollection<Int32> ids) { 
      var allbytes = new List<byte>(); 
      foreach(var id in ids) { 
       var bytes = BitConverter.GetBytes(id); 
       allbytes.AddRange(bytes);     
      } 
      var str = Convert.ToBase64String(allbytes.ToArray(), Base64FormattingOptions.None); 
      return str.Replace('+', '-').Replace('/', '_').Replace('=', '.'); 
     } 

     public static ICollection<Int32> StringToIds(string idstring) { 
      var result = new List<Int32>(); 
      var str = idstring.Replace('-', '+').Replace('_', '/').Replace('.', '='); 
      var bytes = Convert.FromBase64String(str); 
      for(var i = 0; i < bytes.Length; i += 4) { 
       var id = BitConverter.ToInt32(bytes, i); 
       result.Add(id); 
      } 
      return result; 
     } 
    } 
} 

Answer 4

방법 무늬 ID를 사용하면 을 받고있다? 숫자로 한 자릿수, ID가 무작위 인 경우 내가 제안하려고하는 방법은 그리 효율적이지 않습니다. 예를 들어 ID로받은 유형을 대표한다면 다음과 같이 작동 할 수 있습니까?

나는이 아이디어를 예제로 동기 부여합니다.

예를 들어, 압축하려는 ID는 1000000012입니다. [{1}, {0,7}, {12}]로 저장하지 않으시겠습니까? 이것은 첫 번째 숫자가 1이고 그 뒤에 7이 0이고 12가 오는 것을 의미합니다. 따라서 x의 한 인스턴스를 나타내는 표기법 {x}을 사용하는 반면 {x, y}를 사용하면 x y 번 연속으로 발생합니다.

패턴 일치 및/또는 함수 피팅을 사용하여이 값을 확장 할 수 있습니다.

예를 들어, 패턴 일치 : 1000100032는 [{1000,2} {32}]입니다.

예를 들어, ID가 10 자리인 경우 을 입력 한 다음 ID를 두 자리 5 자리 숫자로 분리하고 두 점을 통과하는 선의 등식을 저장하십시오. ID = 1000000012이면 y1 = 10000이고 y2 = 12이므로 기울기는 -9988이고 요격은 10000입니다 (x1 = 0, x2 = 1이라고 가정). 이 경우 개선되지는 않았지만 숫자가 더 무작위 인 경우 문제가 될 수 있습니다. 마찬가지로, 구분 된 선형 함수로 ID 시퀀스를 저장할 수 있습니다.

어떤 경우에도 이것은 주로 ID의 구조에 따라 다릅니다. 난 당신이 요청 URL 길이 제한을위한 해결 방법으로이 일을한다고 가정

Answer 5

...

다른 답변 진수, base47 또는 64 기수의 진수 ID 번호를 암호화하는 제안,하지만 당신은 (이론적으로)을 수행 할 수 있습니다 LZW (또는 유사)를 사용하여 id 목록을 압축하면 훨씬 더 좋습니다. ID 목록에 얼마나 많은 중복성이 있는지에 따라 압축 된 바이트를 텍스트로 다시 인코딩 한 후에도 40 % 이상 크게 줄일 수 있습니다.

너트 쉘에서 자바 스크립트로 구현 된 상용 텍스트 압축 라이브러리를 찾고 클라이언트 측에서 ID 목록을 압축하는 것이 좋습니다. 그런 다음 base47/base64를 사용하여 압축 된 bytestring을 인코딩하고 인코딩 된 문자열을 URL 매개 변수로 전달하십시오. 서버 측에서 그 반대로하십시오. 즉 디코딩 한 다음 압축을 풉니 다.

EDIT : 실험을 위해 gzip을 사용하여 제공하고 압축 한 것과 같은 36 개의 다른 식별자 목록을 만들었습니다. 원본 파일은 396 바이트, 압축 파일은 101 바이트, 압축 된 + base64 파일은 138 바이트입니다. 이는 전체적으로 65 % 감소한 것입니다. 그리고 압축률은 더 큰 파일의 경우 실제로 향상 될 수 있습니다. 그러나 작은 입력 집합 (예 : 4 개의 원래 식별자)으로이 작업을 시도해도 압축이 없으며 인코딩 후에 크기가 원본보다 큽니다.

은 이론적으로, 간단한 해결책이있을 수 있습니다

구글 "자바 스크립트 LZW 라이브러리". 매개 변수를 요청 URL이 아닌 "게시물 데이터"로 보내고 이해할 수있는 인코딩 중 하나를 사용하여 압축을 적용하도록 브라우저를 가져옵니다. 합법적 인 URL 문자로 압축 된 데이터를 인코딩 할 필요가 없기 때문에 그렇게하면 비용도 더 절약됩니다.

문제는 브라우저가 요청을 압축하여 브라우저 독립적 인 방식으로 처리하는 것입니다.

Answer 6

다음은 N이 큰 상수 인 N + delta 형태의 숫자 세트에 대해 좋은 압축을 제공해야하는 또 다른 간단한 구성표입니다.

public int[] compress(int[] input) { 
    int[] res = input.clone(); 
    Arrays.sort(res); 
    for (int i = 1; i < res.length; i++) { 
     res[i] = res[i] - res[i - 1]; 
    } 
    return res; 
} 

이것은 다음 다른 대답에 기재된 base47 인코딩 번호를 표시하여 상기 압축 할 [1000000012,1,9,1]리스트에 설정된 {1000000012,1000000021,1000000013,1000000022}을 감소한다.

간단한 십진수 인코딩을 사용하면 44 자에서 16 자로 변경됩니다. 즉 63 %이다. (그리고 base47을 사용하면 더 많은 압축률을 얻을 수 있습니다).

ID를 정렬하기가 용납 될 수 없다면, 꽤 좋은 압축을 얻지 못할 것입니다. 이 예의 경우 {1000000012,1000000021,1000000013,1000000022}은 [1000000012,9,-8,9] 목록으로 압축됩니다.이 예제에서는 한 문자 만 더 길어집니다.

어느 쪽이든이 방법은 일반적인 압축 알고리즘이나 인코딩 스키마보다 낫습니다.이 종류의 입력에는 적합합니다.