Zawsze nie dawałem odpowiedzi na wyzwania związane ze złożonością łańcucha Kołmogorowa, które wymagają kompresji łańcuchów, a głównym powodem jest to, że nie wiem, jak używać narzędzi do kompresji łańcuchów tak skutecznie, jak powinienem .

Z tego powodu opublikowałem to pytanie. W przeciwieństwie do moich innych pytań ze wskazówkami, nie jest to specyficzne dla języka, co oznacza, że ​​jeśli możesz wymyślić jakieś wskazówki w swoim własnym języku, możesz je opublikować (pod warunkiem, że określisz język). Doceniane są również ogólne wskazówki.

Jak więc korzystać z narzędzi do kompresji ciągów, aby uzyskać maksymalną skuteczność?

Konwersja bazy (CJam)

Prostym sposobem kodowania ciągów ASCII, które nie zaczynają się od bajtu zerowego, jest konwersja z bazy 128 na liczbę całkowitą, a następnie do bazy 256:

128b256b:c              e# Prints encoded string.
128b256b:c`"256b128b:c" e# Prints encoded string with decoder.

Używa 7 bitów do kodowania każdego znaku ASCII.

Jeśli oryginalny ciąg składa się tylko z np. Małych liter i nie zaczyna się od litery a , możemy zacząć od odwzorowania "a...z"na [0 ... 25], a następnie postępować jak wyżej:

'afm26b256b:c               e# Prints encoded string.
'afm26b256b:c`"256b26b'af+" e# Prints encoded string with decoder.

Wreszcie, jeśli oryginalny ciąg ma tylko kilka unikalnych znaków (typowych w sztuce ASCII), zwykle lepiej jest wyraźnie podać alfabet.

Na przykład:

" +-/\|"f#6b256b:c                       e# Prints encoded string.
" +-/\|"f#6b256b:c`"256b6b"" +-/\|"`"f=" e# Prints encoded string with decoder.

Zasadniczo chcesz, aby pierwszym znakiem oryginalnego łańcucha był drugi znak alfabetu, następnym wyraźnym znakiem oryginalnego łańcucha był pierwszy znak alfabetu, kolejnym wyraźnym znakiem oryginalnego łańcucha być trzecim znakiem alfabetu, następnym wyraźnym znakiem oryginalnego ciągu będącym czwartym znakiem alfabetu itp.

Koder z ostatniego przykładu działa w następujący sposób:

" +-/\|"f# e# Replace each character by its index in that string.
6b256b     e# Convert from base 6 (length of the alphabet) to base 256.
:c         e# Cast each digit to character.

Dekoder ostatniego przykładu działa w następujący sposób:

256b6b     e# Convert from base 256 to base 6.
" +-/\|"f= e# Replace each digit by the corresponding character of the alphabet.

Większe pytania o złożoność Kołmogorowa o pewnej strukturze, ale bez prostej formuły (np. Tekstów piosenek) zazwyczaj korzystają z podejścia opartego na gramatyce. W zasadzie wyodrębniasz powtarzające się podciągi i jakoś je kodujesz. To właśnie robi Lempel-Ziv, używając dość ograniczonej klasy gramatyk; jeśli używasz gramatyki ogólnej, musisz dowiedzieć się, jak zakodować reguły. Np. Jednym podejściem jest tutaj „kodowanie offsetowe”, w którym każdy bajt źródłowy jest przesuwany o liczbę reguł ( n), przypisuje się bajty 1do nreguł, używa 0bajtu do oddzielania reguł i wielokrotnie zastępuje bajt iregułą ewaluowaną i. Na koniec cofnij przesunięcie, odejmując nod każdego bajtu.

Napisałem program Java, który implementuje różne podejścia:

Większość podejść opiera się na dwufazowym procesie. W pierwszej fazie łańcuch jest przekształcany w gramatykę, która go generuje; w drugiej fazie gramatyka jest konwertowana na program GolfScript. Wdrożenia w pierwszej fazie są w dużej mierze oparte na Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai i Shelat (2005) Najmniejszy problem gramatyczny , Teoria informacji, Transakcje IEEE, 51 (7), 2554-2576.

Obejmuje także podejście Lempel-Ziv, podstawowe kodowanie i podejście kodujące długość oraz identyfikuje ten, który daje najkrótszy program.

Stax

W języku golfowym z kodem Stax znajduje się pomocne małe narzędzie zwane kompresorem dosłownym do ciągów znaków . Nie wiem, jak to działa, dokładnie, ale nie ma innego gdzie ja nie wiem, jak to działa. Konwertuje ciągi na liczby, a następnie na Bazę 256. To CP437 , z 0x00 i 0xFF konwertowanymi do kopiowania. To PackedStax. Możesz przekonwertować swoje ciągi za pomocą kompresora dosłownego na ciąg, a następnie spakować, aby uzyskać dobrą kompresję.

Korzystając z tego procesu, ciąg „Ten ciąg ma trzydzieści dwa bajty” można przekonwertować na v * „A] - | W4]} 3”% (skompresowany ciąg jest zwykle otoczony za pomocą wstecznych znaków, aby odróżnić normalny ciąg w Stax ) i wreszcie üvìë! [┴╩qJu ← ▓α dla kompresji / redukcji o 18 bajtów, czyli więcej niż o połowę.