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

126

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?

Wasilij Korolew
źródło
1
Gdzie chcesz użyć tych skompresowanych ciągów?
Gumbo,
1
Czy to zmierza w kierunku, tinyurlsczy ma coś wspólnego z miejscem do przechowywania?
nik
6
Interesuje mnie algorytm kompresji adresów URL, najlepszy współczynnik kompresji jest ważniejszy niż koszt eksploatacji. Nie interesują mnie usługi online, takie jak tinyurls czy tr.im. Szukam algorytmu, a nie usługi. Nie myśl, że inne informacje mogą być przydatne ...
Wasilij Korolew
3
@Gumbo: „Algorytmy kompresji tekstu dla krótkich ciągów” wystarczą, aby znaleźć algorytmy, dlaczego tak bardzo chcesz wiedzieć, do czego one służą? Jestem pewien, że OP będzie w stanie znaleźć tego, który robi to, czego chce.
Dervin Thunk,
7
@ Vasily, mała wskazówka: za każdym razem, gdy zadajesz pytanie na temat SO w formie „Jaki jest najlepszy XYZ?”, Twoje pytanie prawie na pewno otrzyma głosy za zamknięcie, ponieważ proszenie o najlepsze może prowadzić do niepotrzebnego produktu porównania lub w najgorszym przypadku nawet wojny z ogniem. (Zwykle wystarczy niewielka zmiana, aby tego uniknąć: jeśli zadałeś to samo pytanie, na przykład „Zaproponuj XYZ.”, Nie dostaniesz tylu głosów zamykających, mimo że jest to w zasadzie to samo pytanie!)
stakx - nie publikujemy już

Odpowiedzi:

62

Sprawdź Smaz :

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

stvchu
źródło
17
Zobacz github.com/antirez/smaz/blob/master/smaz.c - jest to wariant kodowania, a nie kompresja jako taka (przynajmniej nie do końca). Używa statycznego słownika słów i liter.
Roy Tinker
7
Uwaga: to jest projekt antirez. Jest jednym z głównych autorów Redis i cieszy się bardzo dobrą opinią dzięki wydawaniu wysokiej jakości kodu produkcyjnego.
Homer6
7
Algorytm smaz jest zoptymalizowany dla tekstów w języku angielskim, dlatego nie działa dobrze w przypadku losowych ciągów znaków. Oto kilka próbek ( string:orig_size:compr_size:space_savings): This is the very end of it.:27:13:52%, Lorem ipsum dolor sit amet:26:19:27%, Llanfairpwllgwyngyll:20:17:15%, aaaaaaaaaaaaa:13:13:0%, 2BTWm6WcK9AqTU:14:20:-43%,XXX:3:5:-67%
mykhal
4
Spójrz także na niższą kompresję, ale szybki algorytm shoco ed-von-schleck.github.io/shoco
Dickey Singh.
Dodaj moją bibliotekę Unishox do listy github.com/siara-cc/unishox . Działa lepiej niż Smaz i Shoco i obsługuje kompresję ciągów UTF-8.
arun
28

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.

Daniel C. Sobral
źródło
4
Nie, jeśli tabela huffmana jest taka sama dla wszystkich plików, co miałoby sens, gdyby wszystkie pliki były do ​​siebie podobne.
finnw
1
Jeśli masz wiele podobnych, małych plików, wszystko robisz źle. Najpierw połącz je wszystkie (tak jak robi to tar), a następnie skompresuj to. Uzyskasz lepszą kompresję, a problem przestanie być „50-1000 bajtów”.
Daniel C. Sobral
8
@Daniel: zależy od tego, czy chcesz mieć swobodny dostęp do skompresowanych danych. Skompresowanie tego wszystkiego razem zapobiega temu w większości systemów kompresji.
Steve Jessop,
22

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.

redcalx
źródło
Ale jak zachowałby się predyktor z normalnym zdaniem angielskim? Podany przykład ma bardzo silną redundancję, a zysk jest minimalny.
Żeglarz naddunajski
Tablica przeglądowa 256 * 256 nie brzmi "niesamowicie oszczędnie z pamięcią" ...!
MikeW
@MikeW Cóż, to 65 kilobajtów.
redcalx
@redcalx Gdyby to było 65 bajtów, mógłbym się zgodzić!
MikeW
11

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ąć.

finnw
źródło
2
Wskazówki dotyczące korzystania ze słownika niestandardowego: stackoverflow.com/questions/2011653
Trenton,
4

Kodowanie Huffmana generalnie działa w tym przypadku dobrze.

Zifre
źródło
4
To nie jest odpowiedź zawierająca tylko łącze; bez linku to nadal ważna odpowiedź.
SL Barth - Przywróć Monikę
..i nadal nie jest dobrą odpowiedzią. (Wprowadzono za mało istotnych informacji.)
user2864740
4

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
Ryan Christensen
źródło
6
Chce kompresować tekst, a nie pliki.
Gumbo,
3
Za pomocą tych algorytmów można kompresować tekst i pliki binarne. W rzeczywistości używamy deflate w systemie cms, który działa w Pythonie.
Ryan Christensen,
Przykład w języku C # użycia gzip dla ciągów jest tutaj: csharphelp.com/archives4/archive689.html
Ryan Christensen,
Moduł zlib w Pythonie do kompresji łańcuchów: python.org/doc/2.5.2/lib/module-zlib.html
Ryan Christensen
3
gzip (i zlib) używa deflate i dodaje narzut wrapper / framing .. direct deflate / LZ77 (obciążenie słownika i wydajność nadal zależą od implementacji takich i ustawień) może zmniejszyć narzut na próg rentowności. Dotyczy to oczywiście „krótkich” ciągów składających się z dziesiątek do setek znaków (nadal powinno być trochę na wskazanie „czy to było skompresowane”? Aby uniknąć powiększania danych). Większe dodatkowe obciążenie nie ma znaczenia ... w miarę zwiększania się tekstu. Opublikowane tutaj liczby wydają się dotyczyć dużych plików tekstowych (wiele sekund do uruchomienia!), Podczas gdy OP prosi o 50-1000 czarterów - bardzo małe w porównaniu.
user2864740
2

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.

Le Hibou
źródło
SCSU „kompresuje” nieangielski Unicode w kodowaniu UTF-16 / MB. Jeśli oparty na języku angielskim Unicode / plain-old-ASCII, UTF-8 również „kompresuje” 50% UTF-16 ..
user2864740