Wydajny algorytm kompresji krótkich ciągów tekstowych [zamknięty]

Szukam algorytmu do kompresji małych ciągów tekstowych: 50-1000 bajtów (czyli adresów URL). Który algorytm najlepiej się do tego nadaje?

Sprawdź Smaz :

Smaz to prosta biblioteka kompresji odpowiednia do kompresji bardzo krótkich ciągów.

Huffman ma koszt statyczny, stół Huffmana, więc nie zgadzam się, że to dobry wybór.

Istnieją wersje adaptacyjne, które to eliminują, ale współczynnik kompresji może ucierpieć. Właściwie pytanie, które powinieneś zadać, brzmi: „jaki algorytm kompresuje ciągi tekstowe o tych cechach”. Na przykład, jeśli oczekuje się długich powtórzeń, wystarczy proste kodowanie Run-Lengh. Jeśli możesz zagwarantować, że będą obecne tylko angielskie słowa, spacje, znaki interpunkcyjne i sporadyczne cyfry, to Huffman z predefiniowaną tabelą Huffmana może dać dobre wyniki.

Generalnie algorytmy z rodziny Lempel-Ziv charakteryzują się bardzo dobrą kompresją i wydajnością, a ich biblioteki są bogate. Poszedłbym z tym.

Z informacją, że kompresowane są adresy URL, sugerowałbym, aby przed kompresją (za pomocą dowolnego łatwo dostępnego algorytmu) CODYFIKOWAĆ je. Adresy URL są zgodne z dobrze zdefiniowanymi wzorcami, a niektóre z nich są wysoce przewidywalne. Korzystając z tej wiedzy, możesz na początek skodyfikować adresy URL w coś mniejszego, a pomysły związane z kodowaniem Huffmana mogą Ci w tym pomóc.

Na przykład, tłumacząc adres URL na strumień bitów, możesz zamienić „http” na bit 1, a cokolwiek innego na bit „0”, po którym następuje rzeczywisty procotol (lub użyć tabeli, aby uzyskać inne popularne protokoły, takie jak https, ftp, plik). „: //” można całkowicie usunąć, o ile można zaznaczyć koniec protokołu. Itd. Przeczytaj o formacie adresów URL i zastanów się, jak można je zakodować, aby zajmowały mniej miejsca.

Nie mam pod ręką kodu, ale zawsze podobało mi się podejście do budowania tabeli wyszukiwania 2D o rozmiarze 256 * 256 znaków ( RFC 1978 , PPP Predictor Compression Protocol ). Aby skompresować ciąg, należy zapętlić każdy znak i użyć tabeli przeglądowej, aby uzyskać „przewidywany” następny znak, używając bieżącego i poprzedniego znaku jako indeksów tabeli. Jeśli jest dopasowanie, napiszesz pojedynczy 1 bit, w przeciwnym razie napisz 0, znak i zaktualizuj tablicę przeglądową o bieżący znak. To podejście zasadniczo utrzymuje dynamiczną (i surową) tabelę wyszukiwania najbardziej prawdopodobnego następnego znaku w strumieniu danych.

Możesz zacząć od zerowanej tabeli przeglądowej, ale oczywiście działa ona najlepiej w przypadku bardzo krótkich łańcuchów, jeśli jest zainicjowana najbardziej prawdopodobnym znakiem dla każdej pary znaków, na przykład dla języka angielskiego. Dopóki początkowa tablica wyszukiwania jest taka sama dla kompresji i dekompresji, nie musisz emitować jej do skompresowanych danych.

Algorytm ten nie zapewnia doskonałego współczynnika kompresji, ale jest niesamowicie oszczędny, jeśli chodzi o zasoby pamięci i procesora, a także może pracować na ciągłym strumieniu danych - dekompresor zachowuje własną kopię tabeli przeglądowej podczas dekompresji, a tym samym tablicę przeglądową dostosowuje się do rodzaju kompresowanych danych.

Dowolny algorytm / biblioteka obsługująca predefiniowany słownik, np . Zlib .

W ten sposób możesz zalać kompresor tym samym rodzajem tekstu, który prawdopodobnie pojawi się na wejściu. Jeśli pliki są w jakiś sposób podobne (np. Wszystkie adresy URL, wszystkie programy C, wszystkie posty StackOverflow, wszystkie rysunki ASCII-art), to określone podciągi pojawią się w większości lub we wszystkich plikach wejściowych.

Każdy algorytm kompresji pozwoli zaoszczędzić miejsce, jeśli ten sam podciąg zostanie powtórzony wiele razy w jednym pliku wejściowym (np. „The” w tekście angielskim lub „int” w kodzie C).

Jednak w przypadku adresów URL niektóre ciągi (np. „ Http: // www .”, „.Com”, „.html”, „.aspx”) pojawiają się zwykle raz w każdym pliku wejściowym. Dlatego musisz udostępniać je między plikami w jakiś sposób zamiast jednego skompresowanego wystąpienia na plik. Umieszczenie ich w predefiniowanym słowniku pozwoli to osiągnąć.

Kodowanie Huffmana generalnie działa w tym przypadku dobrze.

Jeśli mówisz o faktycznej kompresji tekstu, a nie tylko skracaniu, a następnie Deflate / gzip (wrapper wokół gzip), zip działa dobrze w przypadku mniejszych plików i tekstu. Inne algorytmy są bardzo wydajne w przypadku większych plików, takich jak bzip2 itp.

Wikipedia zawiera listę czasów kompresji. (poszukaj porównania wydajności)

Name       | Text         | Binaries      | Raw images
-----------+--------------+---------------+-------------
7-zip      | 19% in 18.8s | 27% in  59.6s | 50% in 36.4s
bzip2      | 20% in  4.7s | 37% in  32.8s | 51% in 20.0s
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s
advzip     | 24% in 21.1s | 37% in  70.6s | 57& in 41.6s
gzip       | 25% in  4.2s | 39% in  23.1s | 60% in  5.4s
zip        | 25% in  4.3s | 39% in  23.3s | 60% in  5.7s

Możesz rzucić okiem na Standardowy schemat kompresji dla Unicode .

SQL Server 2008 R2 używa go wewnętrznie i może osiągnąć do 50% kompresji.