Kompresja liczbę duże (lub ciąg) do małej wartości

Question

Moja strona ASP.NET ma następujące parametru ciąg kwerendy:

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

Tutaj IDs parametr zawsze będą miały numery oddzielone przez coś, w tym przypadku ,. Obecnie są 4 liczby, ale normalnie byłyby pomiędzy 3 i 7.

Teraz szukam metody konwersji każdej dużej liczby z góry na najmniejszą możliwą wartość; specjalnie kompresująca wartość parametru ciągu zapytania IDs. Zarówno kompresowanie każdego algorytmu liczbowego, jak i kompresowanie wartości całkowitej parametru IDs są mile widziane.

1. Kodowanie lub dekodowanie nie stanowi problemu; po prostu kompresja wartości parametru ciągu zapytania o wartości IDs.
2. Utworzenie unikatowej małej wartości dla IDs, a następnie pobranie jej wartości z jakiegoś źródła danych jest poza zakresem.

Czy istnieje algorytm do kompresowania tak dużych liczb do małych wartości lub do kompresowania wartości parametru ciągu zapytania IDs razem?

Answer 1

Po prostu potrzebujesz tyle miejsca na liczby, ponieważ używasz podstawy 10 do ich reprezentowania. Poprawą byłoby użycie bazy 16 (hex). Na przykład możesz podać 255 (3 cyfry) jako ff (2 cyfry).

Można przyjąć, że pojęcie dalej za pomocą znacznie większej liczby bazę ... zbiór wszystkich znaków, które są ważne parametry ciągu zapytania: „”

AZ, az, 0-9, „- ',' ~ ',' _ ',' + '

To daje podstawę 67 znaków do pracy (patrz Wikipedia on QueryString).

Spójrz na this SO post dla metod konwersji podstawy 10 na dowolne liczby bazowe.

EDIT:

w połączonej SO wątku, spójrz na tej części:

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'}); 

To prawie to, czego potrzebujesz. Wystarczy go rozwinąć dodając kilka znaków go brakuje:

yz.- ~ _ +

tym stanowisku brakuje sposób, aby wrócić do bazy 10. Nie zamierzam ją napisać :-) ale procedura jest taka:

Zdefiniuj licznik Będę wywoływać TOTAL.

Spójrz na prawą większość postaci i znajdź jej pozycję w tablicy.
TOTAL = (pozycja znaku w tablicy) Przykład: Wejście to BA1. TOTAL jest teraz 1 (ponieważ "1" znajduje się na pozycji 1 w tablicy)

Teraz spójrz na następny znak po lewej i znajdź jego pozycję w tablicy. TOTAL + = 47 * (pozycja znaku w tablicy) Przykład: Wejście to BA1. TOTAL jest teraz (47 * 11) + 1 = 518

Teraz spójrz na następny znak po lewej stronie poprzedniego i znajdź jego pozycję w tablicy. TOTAL + = 47 * 47 * (pozycja znaku w tablicy) Przykład: Wejście to BA1. Razem jest teraz (47 * 47 * 10) + (47 * 11) + 1 = 243508

I tak dalej.

Proponuję napisać test jednostkowy, który przekształci kilka bazowych 10 liczb w bazę 47, a następnie z powrotem, aby upewnić się, że kod konwersji działa poprawnie.

Uwaga, w jaki sposób reprezentuje 6-cyfrowy numer podstawa 10 w zaledwie 3 cyfry podstawy 47 :-)

Answer 2

Jeśli jedynym problemem jest długość adresu URL, można przekonwertować numery , a następnie konwertować je do numerów po stronie serwera

Answer 3

Jaki jest zakres numerów? Zakładając, że zmieści się w 16-bitowej liczby całkowitej, byłbym:

• przechowywać wszystkie swoje numery jak 16-bit integers (2 bajtów na liczby, zakres -32768 do 32767)
• Zbuduj bytestream 16-bitowych liczb całkowitych (XDR może być dobrym rozwiązaniem tutaj; co najmniej, upewnij się, aby obsłużyć endianness poprawnie)
• Base64 zakodować bytestream, stosując zmodyfikowaną kodowanie base64 dla URL (netto wynosi około 3 znaków na liczby)

Jak an dodany bonus nie wymaga już znaków przecinków, ponieważ wiesz, że każda liczba to 2 bajty.

Alternatywnie, jeśli to nie wystarczy, użyłbym zlib do skompresowania strumienia liczb całkowitych, a następnie base64 do strumienia skompresowanego zlib. Możesz również przełączyć się na 32-bitowe liczby całkowite, jeśli 16-bitowy nie jest wystarczająco duży (tzn. Jeśli naprawdę potrzebujesz liczb w zakresie 1 000 000 000).

Edit:

Może zbyt późno, ale tutaj jest implementacja, że ​​może zrobić to, czego potrzebujesz:

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

jak wzorzyste są identyfikatory otrzymujesz? jeśli cyfra po cyfrze, identyfikatory są losowe, to metoda, którą zamierzam zaproponować, nie będzie bardzo wydajna. ale jeśli identyfikatory, które podałeś jako przykład, są reprezentatywne dla typów, które otrzymujesz, być może poniższe mogą działać?

Ja motywuję ten pomysł przykładem.

masz na przykład 1000000012 jako ID, który chcesz skompresować. dlaczego nie przechowywać go jako [{1}, {0,7}, {12}]? Oznaczałoby to, że pierwsza cyfra to 1, po której następuje 7 zer, a następnie 12. Tak więc jeśli użyjemy oznaczenia {x}, które reprezentowałyby jedną instancję x, podczas gdy używamy {x, y}, co oznaczałoby, że x występuje y razy z rzędu.

można to rozszerzyć za pomocą dopasowania do wzoru i/lub dopasowania funkcji.

na przykład dopasowanie wzorca: 1000100032 będzie [{1000,2} {32}].

na przykład dopasowanie funkcji: , jeśli twoje ID mają 10 cyfr, następnie podziel identyfikator na dwie 5-cyfrowe liczby i przechowuj równanie linii przechodzącej przez oba punkty. jeśli ID = 1000000012, masz y1 = 10000 i y2 = 12. dlatego twoje nachylenie wynosi -9988, a twój przecinek to 10000 (zakładając, że x1 = 0, x2 = 1). W tym przypadku nie jest to poprawa, ale jeśli liczby były bardziej losowe, może tak być. Równoważnie, można przechowywać sekwencję identyfikatorów z liniowymi funkcjami liniowymi.

w każdym przypadku zależy to głównie od struktury identyfikatorów.

Answer 5

zakładam robisz to jako obejście ograniczeń długości URL żądania ...

Inne odpowiedzi sugerują kodujący dziesiętne numerów identyfikacyjnych w hex, base47 lub base64, ale można (teoretycznie) zrobić dużo lepiej niż przy użyciu LZW (lub podobnym) do kompresowania listy id. W zależności od tego, ile redundancji ma lista ID, można uzyskać znacznie więcej niż 40% redukcji, nawet po ponownym kodowaniu skompresowanych bajtów jako tekstu.

W skorupie orzechowej proponuję znaleźć bibliotekę kompresji tekstu gotowego, zaimplementowaną w Javascript i użyć jej po stronie klienta, aby skompresować listę identyfikatorów. Następnie zakoduj skompresowany test bytowy przy użyciu base47/base64 i podaj zakodowany ciąg jako parametr adresu URL. Po stronie serwera wykonaj odwrotną stronę; tj. dekodowanie, po którym następuje dekompresja.

EDYCJA: W ramach eksperymentu utworzyłem listę 36 różnych identyfikatorów, takich jak te, które zostały dostarczone i skompresowano je za pomocą programu gzip. Oryginalny plik ma 396 bajtów, skompresowany plik ma 101 bajtów, a skompresowany plik + base64 138 bajtów. Jest to ogólna redukcja o 65%. Współczynnik kompresji może poprawić się w przypadku większych plików. Jednak gdy próbowałem tego z małym zestawem wejściowym (na przykład tylko 4 oryginalne identyfikatory), nie miałem kompresji, a po kodowaniu rozmiar był większy niż oryginał.

Google "Biblioteka LZW javascript"

W teorii, nie może być prostsze rozwiązanie. Wyślij parametry jako "dane pocztowe" zamiast w adresie URL żądania i poproś przeglądarkę, aby zastosowała kompresję za pomocą jednego z kodowań, które rozumie. To da ci więcej oszczędności, ponieważ nie ma potrzeby kodowania skompresowanych danych do legalnych znaków URL.

Problem polega na tym, że przeglądarka skompresuje żądanie ... i robi to w niezależny sposób.

Answer 6

Oto kolejny naprawdę prosty schemat, który powinien zapewnić dobrą kompresję dla zestawu liczb w postaci N + delta, gdzie N jest dużą stałą.

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; 
} 

To powinno zmniejszyć zestaw {1000000012,1000000021,1000000013,1000000022} do listy [1000000012,1,9,1], które można następnie skompresować dalej reprezentujący cyfry w kodowaniu base47 jak opisano w innym odpowiedź.

Używając prostego kodowania dziesiętnego, liczba znaków wynosi od 44 do 16 znaków; tj. 63%. (A użycie base47 da jeszcze więcej kompresji).

Jeśli niedopuszczalne jest sortowanie identyfikatorów, nie uzyskuje się tak dobrej kompresji. W tym przykładzie {1000000012,1000000021,1000000013,1000000022} jest kompresowany do listy [1000000012,9,-8,9].To jest tylko jeden znak dłuższy dla tego przykładu.

Tak czy inaczej, jest to lepsze rozwiązanie niż ogólny algorytm kompresji lub schematy kodowania ... DLA TEGO RODZAJU WEJŚCIA.