Naiwna kompresja

Question

przy użyciu kodu długości z przedrostkiem

Zamierzamy zaimplementować kompresję tekstu (napis, tablica / lista znaków / bajtów) poprzez proste podstawienie każdego znaku kodem binarnym, w oparciu o częstotliwość tego znaku w tekście. Częściej występujące znaki zostaną zastąpione krótszymi kodami. Wynikowa tablica bitów zostanie podzielona na fragmenty o długości 8.

Kod

Kod długości z prefiksem o długości 3 to kod składający się z przedrostka - 3 bitów określających długość następującego pola oraz pola. 3 bity wystarczają na 8 (2 ^ 3) różnych prefiksów. Każdy prefiks nz kolei opisuje 2 ^ n różnych pól, wyliczonych od 0 do 2 ^ n-1.

n = 0; 1 wpis (2 ^ 0)

000 – field with length 0;

n = 1; 2 wpisy (2 ^ 1)

001|0      (`|` is put for clarity)
001|1    

n = 2; 4 wpisy (2 ^ 2)

010|00
010|01
010|10
010|11

…

n = 7; 128 wpisów (2 ^ 7)

111 | 0000000
111 | 0000001
111 | 0000010
…
111 | 1111111

Oto tabela wszystkich kodów, wyliczonych od 0 do 254

┌──┬────────┬─────────┬─────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│  │0       │32       │64       │96        │128       │160       │192       │224       │
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│0 │000     │10100001 │110000001│110100001 │1110000001│1110100001│1111000001│1111100001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│1 │0010    │10100010 │110000010│110100010 │1110000010│1110100010│1111000010│1111100010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│2 │0011    │10100011 │110000011│110100011 │1110000011│1110100011│1111000011│1111100011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│3 │01000   │10100100 │110000100│110100100 │1110000100│1110100100│1111000100│1111100100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│4 │01001   │10100101 │110000101│110100101 │1110000101│1110100101│1111000101│1111100101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│5 │01010   │10100110 │110000110│110100110 │1110000110│1110100110│1111000110│1111100110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│6 │01011   │10100111 │110000111│110100111 │1110000111│1110100111│1111000111│1111100111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│7 │011000  │10101000 │110001000│110101000 │1110001000│1110101000│1111001000│1111101000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│8 │011001  │10101001 │110001001│110101001 │1110001001│1110101001│1111001001│1111101001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│9 │011010  │10101010 │110001010│110101010 │1110001010│1110101010│1111001010│1111101010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│10│011011  │10101011 │110001011│110101011 │1110001011│1110101011│1111001011│1111101011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│11│011100  │10101100 │110001100│110101100 │1110001100│1110101100│1111001100│1111101100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│12│011101  │10101101 │110001101│110101101 │1110001101│1110101101│1111001101│1111101101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│13│011110  │10101110 │110001110│110101110 │1110001110│1110101110│1111001110│1111101110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│14│011111  │10101111 │110001111│110101111 │1110001111│1110101111│1111001111│1111101111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│15│1000000 │10110000 │110010000│110110000 │1110010000│1110110000│1111010000│1111110000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│16│1000001 │10110001 │110010001│110110001 │1110010001│1110110001│1111010001│1111110001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│17│1000010 │10110010 │110010010│110110010 │1110010010│1110110010│1111010010│1111110010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│18│1000011 │10110011 │110010011│110110011 │1110010011│1110110011│1111010011│1111110011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│19│1000100 │10110100 │110010100│110110100 │1110010100│1110110100│1111010100│1111110100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│20│1000101 │10110101 │110010101│110110101 │1110010101│1110110101│1111010101│1111110101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│21│1000110 │10110110 │110010110│110110110 │1110010110│1110110110│1111010110│1111110110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│22│1000111 │10110111 │110010111│110110111 │1110010111│1110110111│1111010111│1111110111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│23│1001000 │10111000 │110011000│110111000 │1110011000│1110111000│1111011000│1111111000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│24│1001001 │10111001 │110011001│110111001 │1110011001│1110111001│1111011001│1111111001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│25│1001010 │10111010 │110011010│110111010 │1110011010│1110111010│1111011010│1111111010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│26│1001011 │10111011 │110011011│110111011 │1110011011│1110111011│1111011011│1111111011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│27│1001100 │10111100 │110011100│110111100 │1110011100│1110111100│1111011100│1111111100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│28│1001101 │10111101 │110011101│110111101 │1110011101│1110111101│1111011101│1111111101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│29│1001110 │10111110 │110011110│110111110 │1110011110│1110111110│1111011110│1111111110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│30│1001111 │10111111 │110011111│110111111 │1110011111│1110111111│1111011111│1111111111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│31│10100000│110000000│110100000│1110000000│1110100000│1111000000│1111100000│          │
└──┴────────┴─────────┴─────────┴──────────┴──────────┴──────────┴──────────┴──────────┘

Proces

Najpierw musimy posortować wszystkie unikalne znaki w tekście w kolejności malejącej według ich częstotliwości. Następnie każdemu znakowi przypiszemy kod - najczęściej otrzymywany 000, następny - 0010i tak dalej. Nadszedł czas, aby przejść przez tekst i zastąpić każdy znak odpowiednim kodem. Na koniec rozdzielamy wynikową listę binarną na 8-bitowe szczeliny i konwertujemy je na dziesiętne (lub szesnastkowe) liczby całkowite. Ostatni fragment może być krótszy niż 8 bitów, więc powinien być wypełniony do 8 bitów. Wypełnienie nie jest ważne, więc możesz użyć dowolnych wartości - wszystkie 0, wszystkie 1 lub dowolna kombinacja 1 i 0. Aby skompresowane dane można było zdekompresować, musimy śledzić długość oryginalnej wiadomości, a także posortowaną listę znaków.

Zadanie

Napisz dwie funkcje (lub kompletne programy):

• Compress, który pobiera ciąg znaków jako dane wejściowe i zwraca skompresowane dane. Skompresowane dane powinny zawierać skompresowaną listę / tablicę liczb całkowitych dziesiętnych lub szesnastkowych, długość oryginalnego wejścia i posortowaną listę znaków. Te trzy elementy mogą być w dowolnej kolejności i mogą być przechowywane jako lista, tablica, krotka lub dowolna inna wygodna dla Ciebie struktura. Na przykład mój kod testowy w języku J zwraca tablicę 3 wartości w pudełkach:

     compress 'Hello World'
  ┌──┬────────┬────────────────┐
  │11│loredWH │90 0 38 20 70 18│
  └──┴────────┴────────────────┘
  

** Uwaga: jeśli nie potrzebujesz długości oryginalnego wejścia dla swojego dekompresora, nie musisz go zapisywać / drukować w kompresorze.

• Decompress, który pobiera skompresowane dane i zwraca ciąg znaków po dekompresji.

Punktacja i kryteria zwycięstwa

Twój wynik to suma długości dwóch funkcji w bajtach. Najniższy wynik w każdym języku wygrywa.

Przypadki testowe

   compress 'Hello World'
┌──┬────────┬────────────────┐
│11│loredWH │90 0 38 20 70 18│
└──┴────────┴────────────────┘
   decompress 11;'loredWH ';90 0 38 20 70 18
Hello World

   compress 'Code Golf Stack Exchange is a site for recreational programming competitions'
┌──┬───────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│76│ oieatrncsmgplfxkhdSGEC│142 80 208 34 147 207 136 138 75 48 68 104 12 194 75 14 32 27 65 33 163 82 3 228 176 180 50 180 37 70 76 37 224 234 201 197 165 182 205 135 3 36 219 168 81 168 201 134 128│
└──┴───────────────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
   decompress 76;' oieatrncsmgplfxkhdSGEC'; 142 80 208 34 147 207 136 138 75 48 68 104 12 194 75 14 32 27 65 33 163 82 3 228 176 180 50 180 37 70 76 37 224 234 201 197 165 182 205 135 3 36 219 168 81 168 201 134 128
Code Golf Stack Exchange is a site for recreational programming competitions

   compress 'GFFEEEDDDDCCCCCBBBBBBAAAAAAA'
┌──┬───────┬────────────────────────────────────────────────┐
│28│ABCDEFG│90 148 148 165 8 66 12 204 204 136 136 136 0 0 0│
└──┴───────┴────────────────────────────────────────────────┘
   decompress 28;'ABCDEFG';90 148 148 165 8 66 12 204 204 136 136 136 0 0 0
GFFEEEDDDDCCCCCBBBBBBAAAAAAA

Uwaga

Skompresowane dane mogą się różnić w zależności od języka ze względu na sposób, w jaki działa sortowanie na znakach o równej częstotliwości. To nie jest problem, pod warunkiem, że twój kod dekompresyjny działa poprawnie.

Answer 1

05AB1E , 94 89 71 64 63 61 (29 + 32) bajtów

-25,5 bajtów dzięki @ovs .
-2 bajty dzięki @Neil .

Kompresor:

ÙΣ¢}R=āεb¦Dgb₄+¦ì}‡¤_9׫8ô¨C,

Wypróbuj online lub zweryfikuj wszystkie przypadki testowe .

Dekompresor:

b₁b+€¦J¤Ü[D3£C3+ôć3.$1ìC<Isè?J¤F

Pierwsze wejście to integer-list; drugie wejście to ciąg.
Zatrzymuje program z błędem po tym, jak wyprowadzi poprawny wynik, co jest dozwolone zgodnie z meta .

Wypróbuj online lub zweryfikuj wszystkie przypadki testowe .

Żaden z moich kompresorów ani dekompresorów nie używa długości.

Jeśli długość wynikowego łańcucha binarnego w kompresorze jest podzielna przez 8, dodaje on końcową liczbę całkowitą braku operacji do listy wyjściowej. (Oczywiście dekompresor nadal obsługuje zarówno to, jak i ciągi binarne, które nie są podzielne przez 8, poprawnie.)

Wyjaśnienie:

Kompresor:

Ù           # Uniquify the characters of the (implicit) input-string
 Σ          # Sort these characters by:
  ¢         #  Their count in the (implicit) input-string
 }R         # After the sort: reverse it so the order is from most to least frequent
   =        # Output this string with trailing newline (without popping the string)
ā           # Push a list in the range [1,string-length] (without popping the string)
 ε          # Map each integer to:
  b         #  Convert it to a binary-string
   ¦        #  Remove its first digit
  Dg        #  Create a copy, and pop and push its length
    b       #  Convert this length to binary
            #  Pad it to length 3 with leading 0s by:
     ₄+     #   Adding 1000
       ¦    #   And then removing the first digit
        ì   #  Prepend this in front of the binary-string we've duplicated
}‡          # After the map: transliterate all sorted unique characters with these
            # strings in the (implicit) input-string
¤           # Push its last digit (without popping the string)
 _          # Invert the boolean (1 becomes 0; 0 becomes 1)
  9×        # Repeat that 9 times as string
    «       # And append it to the big string
     8ô     # Then split it into parts of size 8
       ¨    # Remove the trailing part
        C   # Convert each part from binary to an integer
         ,  # And pop and output it as well

Dekompresor:

b           # Convert each integer in the (implicit) input-list to a binary-string
            # Pad each to length 8 with leading 0s by:
 ₁b         #  Pushing 256, and converting it to binary as well: 100000000
   +        #  Adding it to each binary string
    €¦      #  And then removing the first digit of each string
      J     # Join all binary-strings together to a single string
       ¤    # Push its last digit (without popping the string)
        Ü   # And right-strip all those trailing digits
[           # Loop indefinitely:
 D          #  Duplicate the binary-string
  3£        #  Pop the copy, and push its first 3 digits
    C       #  Convert that from binary to an integer
     3+     #  Add 3
       ô    #  Split the binary-string into parts of that size
  ć         #  Extract head; pop the remainder-list and first item separately
   3.$      #  Remove the first 3 digits of this first item
      1ì    #  Prepend a 1
        C   #  Convert it from binary to an integer as well
         <  #  And decrease it by 1
   I        #  Then push the second input-string
    s       #  Swap so the integer is at the top of the stack
     è      #  (0-based) index it into the input-string
      ?     #  Pop and output this character (without trailing newline)
   J        #  And join the remainder-list back to a string
    ¤       #  Push its first character (without popping the string),
            #  which will be either 0, 1, or an empty string
     F      #  Loop that many times, which will error for the empty string to exit the
            #  program

Answer 2

k4 , 69 + 90 = 159 bajtów

compress:{|(0b/:'8#'0N 8#,/(,/,/:'[c 3;c:7{,/x,/:\:01b}\,()])e?x;e:>#:'=x;#x)}

• c:7{,/x,/:\:01b}\,()buduje listę prawidłowych przyrostków, pogrupowanych według ich długości (np. (,();(,0b;,1b);(00b;01b;10b;11b);...))
• przedrostki ( c 3) są poprzedzane przyrostkami przez,/:'[c 3;c:...]
• e:>#:'=xzwraca znaki xposortowane (stabilnie) według częstotliwości, malejąco
• wzory bitowe są indeksowane przez e?x, tj. indeksy edla każdego znaku wx
• 0N 8#,/konwertuje skompresowane dane wejściowe na listę bajtów, 8#'zapewniając, że każdy fragment (w tym ostatni) zawiera pełne 8 bitów
• 0b/:' konwertuje każdy fragment 8 bitów na szesnastkową reprezentację bajtów (tj. listę bajtów, która jest trzecim wyjściem)

decompress:{z:,/0b\:'z;o:"";do[x;o,:y(,/,/:'[c 3;c:7{,/x,/:\:01b}\,()])?(d:+/3,4 2 1*3#z)#z;z:d_z];o}

• przekonwertuj dane wejściowe (listę bajtów) na listę bitów / wartości logicznych za pomocą z:,/0b\:'z
• dla każdego znaku w nieskompresowanym wejściu (którego całkowita liczba jest przekazywana jako x), odklej pierwsze 3 bity i określ, ile dodatkowych bitów jest jego częścią za pomocą(d:+/3,4 2 1*3#z)
• wyszukaj skompresowany kod bitowy w tabeli kodów bitowych, aby odzyskać jego indeks (np. 000b => 0, 0010b => 1, ...); użyj tego wyniku do indeksowania posortowanej listy znaków ( y)
• dołącz nieskompresowany znak do wyjścia o, a następnie upuść skompresowany znak z input ( z), aby przygotować się do następnej doiteracji

Answer 3

Węgiel , 71 64 + 32 = 96 bajtów

Kompresor, 64 bajty:

≔Ｅθ⟦№θιι⟧ηＷ⁻ηυ⊞υ⌈ιＵＭυ⊟ι⭆¹⟦Ｌθ⪫υωＥ⪪⭆Ｅθ⍘⊕⌕υλ !⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ⁸⍘◨λ⁸ !

Wypróbuj online! Link prowadzi do pełnej wersji kodu. Wyjaśnienie:

≔Ｅθ⟦№θιι⟧η

Sparuj wszystkie znaki wejściowe z ich częstotliwością.

Ｗ⁻ηυ

Powtarzaj, aż wszystkie pary zostaną posortowane i zdeduplikowane.

⊞υ⌈ι

Wypchnij najwyższą (tj. Najczęściej używaną) pozostałą parę na predefiniowaną pustą listę.

ＵＭυ⊟ι

Usuń częstotliwości z posortowanej, zdeduplikowanej listy.

⭆¹⟦

Uściślij listę ...

Ｌθ

... długość wejścia, ...

⪫υω

... konkatenacja znaków w malejącej kolejności częstotliwości oraz:

Ｅθ⍘⊕⌕υλ !

Dla każdego znaku w ciągu wejściowym znajdź jego (z indeksem 1, więc muszę zwiększyć) indeks popularności i przekonwertuj go na podstawę 2 za pomocą niestandardowych cyfr.

⭆...⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ

Dla każdego przekonwertowanego znaku dodaj 7 do jego długości, przekonwertuj go na podstawę 2 za pomocą niestandardowych cyfr i utwórz listę tego i przekonwertowanego ciągu. Odetnij wszystkie struny i połącz ciała.

Ｅ⪪...⁸⍘◨λ⁸ !

Potnij ciąg na podciągi o długości 8, ostatni dopełnij prawym klawiszem i zdekoduj każdy podciąg jako podstawę 2, używając niestandardowych znaków podstawowych (w szczególności dopełnienie prawe używa spacji, więc musi to być niestandardowy znak podstawowy dla 0) .

Zauważ, że ta wersja kompresora rozwiązuje problemy, przyjmując znak z najwyższą liczbą porządkową, a nie znak z pierwszym wyglądem, który wybrał poprzednia wersja. Zaktualizowałem odpowiednio wejście do łącza dekompresora.

Dekompresor, 32 bajty:

Ｆ⮌ζＦ⁸⊞υ﹪÷ιＸ²κ²⭆θ§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²

Wypróbuj online! Link prowadzi do pełnej wersji kodu.

Ｆ⮌ζ

Zapętlaj bajty w odwrotnej kolejności.

Ｆ⁸

Zapętlaj każdy bit w odwrotnej kolejności.

⊞υ﹪÷ιＸ²κ²

Wepchnij bit na predefiniowaną pustą listę.

⭆θ

Mapuj każdy indeks, dołącz i niejawnie wydrukuj:

§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²

Zdekoduj 3 bity z listy, zdekoduj jako podstawę 2, zdejmij tyle bitów z listy, prefiks 1, zdekoduj jako podstawę 2, indeks do ciągu (indeksowany 0, więc muszę zmniejszyć). (Mogłem użyć BaseStringi StringMapdwa razy.)

Answer 4

JavaScript (Node.js) , 223 + 126 = 349 bajtów

Kompresor, 223 bajty

s=>[s.length,a=[...new Set(s)].sort(g=(a,b)=>a?1/s.split(a).length-g(b):0),([...s].reduce((q,c)=>q<<3n+(x=(B=BigInt)(31-Math.clz32(i=a.indexOf(c)+1)))|x<<x|B(i)^1n<<x,1n)<<7n).toString(2).match(/\B.{8}/g).map(x=>+('0b'+x))]

Wypróbuj online!

W jaki sposób?

Generowanie posortowanej listy a[]unikatowych znaków:

a = [...new Set(s)]       // get the array of unique characters
.sort(g = (a, b) =>       // for each pair (a, b) of characters to be sorted:
  a ?                     //   if a is defined:
    1 / s.split(a).length //     compute 1 / (N + 1),
                          //     where N is the number of occurrences of a in s
    - g(b)                //     subtract the result of a recursive call
                          //     with a = b and b undefined
  :                       //   else:
    0                     //     stop the recursion
)                         // end of sort()

Generowanie strumienia bajtów jako pojedynczy BigInt:

[...s].reduce((q, c) =>      // for each character c in s, using q as the accumulator:
  q <<                       // left-shift q by:
    3n +                     //   3 + x positions,
    (x = (B = BigInt)(       //   where x is the number of bits required to write ...
      31 - Math.clz32(       //
        i = a.indexOf(c) + 1 //   ... the 1-indexed position i of c in a[]
      )                      //
    ))                       //
  |                          //   bitwise OR with:
  x << x                     //     x, left-shifted by x positions
  |                          //   bitwise OR with:
  B(i) ^ 1n << x,            //     i without the most significant bit
  1n                         //   start with q = 1 to preserve leading 0's
)                            // end of reduce()

Dzielenie BigInt na listę bajtów:

(... << 7n)            // left-shift the final result to add 7 trailing 0's
.toString(2)           // convert to binary
.match(/\B.{8}/g)      // split by groups of 8 binary digits, ignoring the 1st one
.map(x => +('0b' + x)) // convert each group back to decimal

Dekompresor, 126 bajtów

19 bajtów zapisanych przez @Neil!

(n,a,b)=>(g=s=>n--?a['0b1'+s[S](3,x=2-~('0b'+s[S](0,3)))-1]+g(s[S](x)):'')(b.map(v=>(256+v).toString(2)[S='slice'](1)).join``)

Wypróbuj online!

W jaki sposób?

Zamiana strumienia bajtów na ciąg binarny:

b.map(v =>         // for each byte v in b[]:
  (256 + v)        //  force a leading '1'
  .toString(2)     //  convert to binary
  [S = 'slice'](1) //  remove the leading '1'
).join``           // end of map(); join all strings together

Generowanie wyniku:

g = s =>                    // s = binary string
  n-- ?                     // decrement n; if it was not equal to 0:
    a[                      //   pick the next character from a[]:
      '0b1' +               //     the index of the character is 2 ** x + V - 1
      s[S](                 //     where V is defined
        3,                  //     as the x-bit value
        x = 2 -~(           //     whose length x (+3)
          '0b' + s[S](0, 3) //     is stored in the 3 leading bits
        )                   //
      ) - 1                 //
    ] +                     //   end of character lookup
    g(s[S](x))              //   recursive call with all processed bits removed
  :                         // else:
    ''                      //   stop the recursion

Answer 5

Python 3 , 190 + 128 = 318 bajtów

Zaoszczędzono aż 28 41 55 57 82 bajtów (i spadło poniżej 400!) Dzięki OVS !!!
Zapisano 10 bajtów dzięki Neilowi !!!

Kompresor

Python 3 , 190 bajtów

def c(r):j=''.join;s=j(sorted({*r},key=r.count))[::-1];i=s.index;g=j(f'{len(bin(i(c)+1)[3:]):03b}'+bin(i(c)+1)[3:]for c in r)+8*'0';return[int(g[a:a+8],2)for a in range(0,len(g),8)],len(r),s

Wypróbuj online!

Dekompresor

Python 3 , 128 bajtów

def d(a,l,s):
 d=''.join(f'{d:08b}'for d in a);r=''
 while len(r)<l:b=3+int(d[:3],2);r+=s[~-int('1'+d[3:b],2)];d=d[b:]
 return r

Wypróbuj online!

Dekompresja wykorzystuje oryginalną długość łańcucha.

Answer 6

Łuska , 119 103 95 (55 + 40) bajtów

Edycja: -8 bajtów dzięki Neilowi

Kompresor (55 bajtów):

,₁¹B256ḋS+ö`R0%8_Lṁ!ṁλm+tḋ+8¹(motḋ→½ŀ`^2→))ŀ8m€₁¹
↔Ö#¹u

Wypróbuj online!

Dekompresor (40 bajtów):

mö!²ḋ:1↓3↑I¡λ§,↓↑+3ḋ↑3¹)Ṡ+ö`R0%8_LḋB256⁰

Wypróbuj online!

Jak to działa?

Kompresor:

1. Sortuj litery według częstotliwości (funkcja pomocnicza ₁):

↔Ö#¹u

1. Zastąp litery według ich rangi według częstotliwości:

m€₁

1. Kod długości prefiksu-genrate:

ṁ                      ŀ8       # for each integer x from 0 to 7
 λm+                            # join 
    tḋ+8¹                       # zero-padded binary digits of x to
         (motḋ→½ŀ`^2→))         # zero-padded binary digits of 1..x

1. Wyszukaj każdy kod długości prefiksu z każdego rzędu liter:

ṁ!

1. Koniec dopełniania cyframi do wielokrotności 8:

S+ö`R0%8_L

1. Konwersja z binarnego do base-256:

B256ḋ

1. I na koniec sparuj z literami posortowanymi według częstotliwości:

,₁¹

Dekompresor:

1. Konwertuj pierwszy argument z podstawy-256 na cyfry binarne:

ḋB256⁰

1. Zacznij od cyfr do wielokrotności 8:

Ṡ+ö`R0%8_L

1. Sekwencyjnie pobierz kody długości prefiksu:

  ¡λ          )                 # apply function repeatedly:
         3ḋ↑3¹                  # remove first 3 digits & convert to number
    §,↓↑+                       # split remaining list at this position
                                # (this keeps going forever, so the list ends-up
                                # with a lot of empty elements)
↑I                              # finally, just keep the truthy prefixes

1. Zamień każdy element na liczbę:

   ↓3                           # discard the first 3 digits
 :1                             # and add a '1' at the start
                                # (equivalent to converting the 3 digits
                                # to a value from binary and adding it: Thanks Neil! )
ḋ                               # and convert it all to a value from binary

1. Wyszukaj literę z drugiego argumentu:

mö!²

Answer 7

J , 70 + 95 = 165 bajtów

Enkoder wraca length;table;bytestak jak w opisie. Wypełnienie dla ostatniej porcji to ostatni wygenerowany bit.

#;[(];[:#.@($~8,~#>.@%8:)@;(~.(128#3+i.8)<@$"0 1#:i.4^5){~i.~)~.\:#/.

Dekoder używający dokładnie tego samego formatu dla wejścia:

>@{.$>@{~&1({~(~.(128#3+i.8)<@$"0 1#:i.4^5)i.l<@{.])"1[:(}.~l=:3+3#.@{.])^:(<_)128,@}.@#:@,>@{:

Wypróbuj online!

Jak to z grubsza działa

Tabela kodów używana w obu:

• #:i.4^5 0… 1024 binarnie.
• 128#3+i.8 powtórz każdą liczbę w 3… 11 dla 128 razy
• <@$"0 dla 0… 127 weź pierwsze 3 cyfry, dla 128… 255 weź pierwsze 4 cyfry…
• ~. wziąć unikalne elementy wyniku.

Koder:

• ~.\:#/.posortować unikatowe znaki w danych wejściowych na podstawie wystąpień. To jest tabela postaci.
• (table){~i.~ odwzoruj dane wejściowe na pozycje tabeli znaków i uzyskaj odpowiedni kod.
• ($~8,~#>.@%8:)@; połącz wszystkie kody razem i podziel je na części po 8.
• #;…];#.@ przekonwertuj z powrotem na liczby całkowite i dołącz tabelę znaków i długość na początku.

Dekoder:

• 128,@}.@#:@,>@{weź bajty i zamień je z powrotem na bity. Muszę tymczasowo dodać 128, aby uzupełnić wyniki do 8 bitów.
• [:(}.~l=:3+3#.@{.])^:(<_)przeanalizuj pierwsze 3 bity ni usuń je oraz następne nbity z tablicy bitów. Rób to, aż tablica bitowa będzie pusta. Zwróć wszystkie wyniki pośrednie (czyli pozycje początkowe dla kodów).
• (table)i.l<@{.] ponownie przeanalizuj bity początkowe i wyszukaj je w tabeli kodów.
• >@{~&1({~ i poszukaj indeksu w tabeli znaków.
• >@{.$ przyciąć dane wyjściowe do długości łańcucha.

Answer 8

Perl 5 , 354 bajty

@c=map{$c=$_;map{sprintf"%0*b%0*b",$c?3:2,$c,$c,$_}0..2**$c-1}0..7; sub c{$_=pop;my%f;$f{$_}++for/./g;my%c;@c{@f=sort{$f{$b}<=>$f{$a}}keys%f}=@c;y///c,join('',@f),map oct(substr"0b$_".'0'x7,0,10),join('',@c{/./g})=~/.{1,8}/g} sub d{($l,$f,@i)=@_;@d{@c}=0..255;join'',map$f=~/^.{$d{$_}}(.)/,(join('',map sprintf('%08b',$_),@i)=~/@{[join'|',@c]}/g)[0..$l-1]}

Wypróbuj online!

Uruchom to, aby skompresować za pomocą funkcji c () i zdekompresować za pomocą d ().

my @c1 = c('Hello World');
my @c2 = c('Code Golf Stack Exchange is a site for recreational programming competitions');
print join('|',@c1)."\n";
print join('|',@c2)."\n";
print "Bytes in 1st compression: ".(@c1-2)."\n";
print "Bytes in 2nd compression: ".(@c2-2)."\n";
print d(@c1)."|\n";
print d(@c2)."|\n";

Wynik:

11|loredWH |90|0|38|20|70|18
76| oieatrncsmgplfxkhdSGEC|142|80|208|34|147|207|136|138|75|48|68|104|12|194|75|14|32|27|65|33|163|82|3|228|176|180|50|180|37|70|76|37|224|234|201|197|165|182|205|135|3|36|219|168|81|168|201|134|128
Bytes in 1st compression: 6
Bytes in 2nd compression: 49
Hello World|
Code Golf Stack Exchange is a site for recreational programming competitions|

Answer 9

Julia , 331 bajtów

p(s)=Meta.parse("0b"*s)
s(n,p)=last(bitstring(n),p)
b(i,n=0,B=2^n)=2B<=i ? b(i,n+1) : s(n,3)s(i-B,n)
c(s,u=sort(unique(s),by=x->count(==(x),s),rev=0<1))=join(u),p.(i.match for i=eachmatch(r".{8}",join(b.(findlast(==(i),u) for i=s))*'1'^7))
d(u,N,s=join(s.(N,8)),n=p(s[1:3]))=u[n<1||2^n+p(s[4:3+n])]*try d(u,0,s[4+n:end])catch;""end

Wypróbuj online!

Nie chcę oddzielać kompresji i dekompresji, ponieważ używam tych funkcji pi sdo obu.

c służy do kompresji, zwraca posortowane litery i skompresowany ciąg (brakujące bity są wypełniane 1s)

dsłuży do dekompresji, nie potrzebuje długości oryginalnego ciągu (odrzuca ostatni nieprawidłowy znak)