Naprawdę prosta kompresja krótkich ciągów znaków

Question

Czy istnieje naprawdę prosta technika kompresji dla ciągów o długości do około 255 znaków (tak, kompresuję URLs)?

Nie jestem zainteresowany siłą kompresji - szukam czegoś, co działa bardzo dobrze i jest szybkie do wdrożenia. Chciałbym czegoś prostszego niż SharpZipLib: coś, co można zaimplementować za pomocą kilku krótkich metod.

Answer 1

Myślę, że kluczową kwestią jest tutaj „Dlaczego chcesz skompresować adresy URL?”

Próbując skrócić długie adresy URL do paska adresu?

Lepsze przechowywanie oryginalnego adresu URL gdzieś (baza danych, plik tekstowy ...) wraz z hashcode części bez domeny (MD5 jest w porządku). Możesz wtedy mieć prostą stronę (lub jakiś moduł HTTP, jeśli czujesz się krzykliwie), aby odczytać MD5 i wyszukać prawdziwy adres URL. Oto jak działa TinyURL i inni.

Na przykład:

http://mydomain.com/folder1/folder2/page1.aspx 

Może być zwarte do:

http://mydomain.com/2d4f1c8a 

Korzystanie z biblioteki kompresji to nie będzie działać. Ciąg zostanie skompresowany do krótszej reprezentacji binarnej, ale konwersja z powrotem na ciąg znaków, który musi być ważny jako część adresu URL (na przykład Base64), zaneguje jakąkolwiek korzyść uzyskaną z kompresji.

Przechowywanie partii adresów URL w pamięci lub na dysku?

Użyj wbudowanej biblioteki kompresji w System.IO.Compression lub bibliotece ZLib, która jest prosta i niewiarygodnie dobra. Ponieważ będziesz przechowywać dane binarne, skompresowane dane wyjściowe będą w porządku, tak jak jest.Musisz ją zdekompresować, aby użyć go jako adresu URL.

Answer 2

Jaki jest twój cel?

• Krótszy adres URL? Spróbuj skracać adresy URL, np. http://tinyurl.com/ lub http://is.gd/
• Miejsce do przechowywania? Sprawdź System.IO.Compression. (Lub SharpZipLib)

Answer 3

Zacznę od wypróbowania jednej z istniejących (wolnych lub otwartych źródeł) bibliotek zip, np. http://www.icsharpcode.net/OpenSource/SharpZipLib/

pocztowy powinien działać dobrze dla ciągów tekstowych, a nie jestem pewien, czy warto realizacji algorytmu kompresji yourserlf ....

Answer 4

bym Proponuję patrząc w System.IO.Compression Namespace. Jest an article on CodeProject, które mogą pomóc.

Answer 5

Czy próbowałeś już użyć gzip?

Nie mam pojęcia, czy działałby skutecznie z tak krótkimi łańcuchami, ale powiedziałbym, że to prawdopodobnie najlepszy zakład. Biblioteka

Answer 6

open source SharpZipLib jest łatwy w użyciu i dostarczy Ci narzędzi kompresji

Answer 7

Zgodnie z sugestią podaną w artykule the accepted answer, użycie kompresji danych nie działa na rzecz skracania ścieżek adresów URL, które są już dość krótkie.

DotNetZip ma klasę DeflateStream, która udostępnia metodę statyczną (Udostępnione w VB): CompressString. Jest to jednoliniowy sposób kompresji ciągu znaków przy użyciu DEFLATE (RFC 1951). Implementacja DEFLATE jest w pełni kompatybilna z System.IO.Compression.DeflateStream, ale DotNetZip kompresuje lepiej. Oto w jaki sposób można go używać:

string[] orig = { 
    "folder1/folder2/page1.aspx", 
    "folderBB/folderAA/page2.aspx", 
}; 
public void Run() 
{ 
    foreach (string s in orig) 
    { 
     System.Console.WriteLine("original : {0}", s); 
     byte[] compressed = DeflateStream.CompressString(s); 
     System.Console.WriteLine("compressed : {0}", ByteArrayToHexString(compressed)); 
     string uncompressed = DeflateStream.UncompressString(compressed); 
     System.Console.WriteLine("uncompressed: {0}\n", uncompressed); 
    } 
} 

Używając tego kodu, oto wyniki moich badań:

original : folder1/folder2/page1.aspx 
compressed : 4bcbcf49492d32d44f03d346fa0589e9a9867a89c5051500 
uncompressed: folder1/folder2/page1.aspx 

original : folderBB/folderAA/page2.aspx 
compressed : 4bcbcf49492d7272d24f03331c1df50b12d3538df4128b0b2a00 
uncompressed: folderBB/folderAA/page2.aspx 

Więc można zobaczyć „skompresowany” tablicę bajtów, gdy reprezentowana w hex, jest dłuższy niż oryginał, około 2 razy dłuższy. Powód jest taki, że bajt szesnastkowy to właściwie 2 znaki ASCII.

Można to w pewnym stopniu skompensować, używając base-62, zamiast base-16 (hex) do przedstawienia liczby. W takim przypadku a-z i A-Z są również cyframi, co daje 0-9 (10) + a-z (+26) + A-Z (+26) = 62 całkowite cyfry. To znacznie skróciłoby produkcję. Nie próbowałem tego. jeszcze.

---

EDIT
Ok testowane baza-62 kodera. Skraca łańcuch szesnastkowy o około połowę. Pomyślałem, że zmniejszy to do 25% (62/16 = ~ 4), ale myślę, że tracę coś z dyskretyzacją. W moich testach wynikowy łańcuch zakodowany w bazie 62 jest mniej więcej tej samej długości co pierwotny URL. Zatem nie, używanie kompresji, a następnie kodowania base-62 nadal nie jest dobrym podejściem. naprawdę potrzebujesz wartości hash.

Answer 8

Można użyć korekta algorytmu bezpośrednio, bez żadnych nagłówków sum kontrolnych lub stopek, jak opisano w tej kwestii: Python: Inflate and Deflate implementations

To skraca URL 4100 znaków do 1270 znaków base64, moim teście, pozwalając, aby zmieścić Limit IE 2000.

Oto przykład 4000-character URL, którego nie można rozwiązać za pomocą hashtable, ponieważ aplet może istnieć na dowolnym serwerze.