Naive Kompression
Verwenden des Codes für die vorangestellte Länge
Wir werden eine Komprimierung von Text (Zeichenfolge, Array / Liste von Zeichen / Bytes) implementieren, indem wir jedes Zeichen durch einen Binärcode ersetzen, basierend auf der Häufigkeit dieses Zeichens im Text. Die Zeichen, die häufiger vorkommen, werden durch kürzere Codes ersetzt. Das resultierende Bit-Array wird auf Chunks mit der Länge 8 aufgeteilt.
Der Code
Code mit vorangestellter Länge mit der Länge 3 ist ein Code, der aus einem Präfix - 3 Bits, die die Länge des folgenden Felds angeben, und einem Feld besteht. 3 Bits reichen für 8 (2 ^ 3) verschiedene Präfixe aus. Jedes Präfix nbeschreibt wiederum 2 ^ n verschiedene Felder, die von 0 bis 2 ^ n-1 aufgezählt sind.
n = 0;; 1 Eintrag (2 ^ 0)
000 – field with length 0;
n = 1;; 2 Einträge (2 ^ 1)
001|0 (`|` is put for clarity)
001|1
n = 2;; 4 Einträge (2 ^ 2)
010|00
010|01
010|10
010|11
…
n = 7;; 128 Einträge (2 ^ 7)
111 | 0000000 111 | 0000001 111 | 0000010 … 111 | 1111111
Hier ist eine Tabelle aller Codes, die von 0 bis 254 aufgelistet sind
┌──┬────────┬─────────┬─────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ │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│ │
└──┴────────┴─────────┴─────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
Der Prozess
Zuerst müssen wir alle eindeutigen Zeichen im Text in absteigender Reihenfolge nach ihrer Häufigkeit sortieren. Dann weisen wir jedem Zeichen einen Code zu - der häufigste wird erhalten 000, der nächste - 0010und so weiter. Jetzt ist es Zeit, den Text zu durchlaufen und jedes Zeichen durch den entsprechenden Code zu ersetzen. Am Ende teilen wir die resultierende Binärliste in 8-Bit-Chinks auf und konvertieren sie in dezimale (oder hexadezimale) Ganzzahlen. Der letzte Block kann kürzer als 8 Bit sein, daher sollte er mit 8 Bit gefüllt werden. Die Füllung ist unwichtig, daher können Sie beliebige Werte verwenden - alle 0, alle 1 oder eine beliebige Kombination aus 1 und 0. Damit die komprimierten Daten dekomprimierbar sind, müssen wir die Länge der ursprünglichen Nachricht verfolgen. sowie die sortierte Liste der Zeichen.
Die Aufgabe
Schreiben Sie zwei Funktionen (oder vollständige Programme):
Komprimieren, das eine Zeichenfolge als Eingabe verwendet und die komprimierten Daten zurückgibt. Die komprimierten Daten sollten die komprimierte Liste / das komprimierte Array von Dezimal- oder Hexadezimalzahlen, die Länge der ursprünglichen Eingabe und die sortierte Liste von Zeichen enthalten. Die drei können in einer beliebigen Reihenfolge vorliegen und als Liste, Array, Tupel oder jede andere für Sie geeignete Struktur gespeichert werden. Zum Beispiel gibt mein Testcode in J ein Array von 3 Boxwerten zurück:
compress 'Hello World' ┌──┬────────┬────────────────┐ │11│loredWH │90 0 38 20 70 18│ └──┴────────┴────────────────┘
** Hinweis: Wenn Sie die Länge des ursprünglichen Eingangs für Ihren Dekompressor nicht benötigen, müssen Sie ihn nicht in Ihrem Kompressor speichern / drucken.
- Dekomprimieren, das komprimierte Daten verwendet und die Zeichenfolge nach der Dekomprimierung zurückgibt.
Bewertungs- und Gewinnkriterien
Ihre Punktzahl ist die Summe der Längen Ihrer beiden Funktionen in Bytes. Die niedrigste Punktzahl in jeder Sprache gewinnt.
Testfälle
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
Hinweis
Die komprimierten Daten können sich zwischen den Sprachen unterscheiden, da die Sortierung nach Zeichen mit gleicher Häufigkeit funktioniert. Dies ist kein Problem, vorausgesetzt, Ihr Dekomprimierungscode funktioniert ordnungsgemäß.
Antworten
05AB1E , 94 89 71 64 63 61 (29 + 32) Bytes
-25,5 Bytes dank @ovs .
-2 Bytes dank @Neil .
Kompressor:
ÙΣ¢}R=āεb¦Dgb₄+¦ì}‡¤_9׫8ô¨C,
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Dekompressor:
b₁b+€¦J¤Ü[D3£C3+ôć3.$1ìC<Isè?J¤F
Die erste Eingabe ist eine Ganzzahlliste. Die zweite Eingabe ist die Zeichenfolge.
Stoppt das Programm mit einem Fehler, nachdem es das richtige Ergebnis ausgegeben hat, das gemäß dem Meta zulässig ist .
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Weder mein Kompressor noch mein Dekompressor verwenden die Länge.
Wenn die Länge der resultierenden Binärzeichenfolge im Kompressor durch 8 teilbar ist, wird der Ausgabeliste eine nachfolgende No-Op-Ganzzahl hinzugefügt. (Der Dekomprimierer verarbeitet offensichtlich immer noch sowohl dies als auch Binärzeichenfolgen, die nicht durch 8 teilbar sind, korrekt.)
Erläuterung:
Kompressor:
Ù # 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
Dekompressor:
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
k4 , 69 + 90 = 159 Bytes
compress:{|(0b/:'8#'0N 8#,/(,/,/:'[c 3;c:7{,/x,/:\:01b}\,()])e?x;e:>#:'=x;#x)}
c:7{,/x,/:\:01b}\,()erstellt eine Liste der gültigen Suffixen, durch ihre Länge gruppiert (zB(,();(,0b;,1b);(00b;01b;10b;11b);...))- Die Präfixe (
c 3) werden den Suffixen mit vorangestellt,/:'[c 3;c:...] e:>#:'=xGibt die Zeichen inx(stabil) sortiert nach ihrer Häufigkeit absteigend zurück- Die Bitmuster werden durch indiziert
e?x, dh die Indizesefür jedes Zeichen inx 0N 8#,/konvertiert die komprimierte Eingabe in eine Liste von Bytes, wobei8#'sichergestellt wird , dass jeder Block (einschließlich des letzten) volle 8 Bits enthält0b/:'konvertiert jeden Block von 8 Bits in eine hexadezimale Bytedarstellung (dh eine Liste von Bytes, die die dritte Ausgabe ist)
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}
- Konvertieren Sie die Eingabe (eine Liste von Bytes) mit in eine Liste von Bits / Booleschen Werten
z:,/0b\:'z - Ziehen Sie für jedes Zeichen in der unkomprimierten Eingabe (dessen Gesamtzahl als übergeben wird
x) die ersten 3 Bits ab und bestimmen Sie, mit wie vielen zusätzlichen Bits ein Teil davon enthalten ist(d:+/3,4 2 1*3#z) - Suchen Sie den komprimierten Bitcode in der Tabelle der Bitcodes, um seinen Index abzurufen (z. B.
000b => 0, 0010b => 1, ...). Verwenden Sie dieses Ergebnis, um in die sortierte Liste der Zeichen zu indizieren (y) - Hängen Sie das unkomprimierte Zeichen an die Ausgabe an
ound löschen Sie das komprimierte Zeichen aus der Eingabe (z), um die nächstedoIteration vorzubereiten
Holzkohle , 71 64 + 32 = 96 Bytes
Kompressor, 64 Bytes:
≔Ｅθ⟦№θιι⟧ηＷ⁻ηυ⊞υ⌈ιＵＭυ⊟ι⭆¹⟦Ｌθ⪫υωＥ⪪⭆Ｅθ⍘⊕⌕υλ !⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ⁸⍘◨λ⁸ !
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:
≔Ｅθ⟦№θιι⟧η
Koppeln Sie alle eingegebenen Zeichen mit ihrer Häufigkeit.
Ｗ⁻ηυ
Wiederholen Sie diesen Vorgang, bis alle Paare sortiert und dedupliziert wurden.
⊞υ⌈ι
Schieben Sie das höchste (dh das häufigste) verbleibende Paar in die vordefinierte leere Liste.
ＵＭυ⊟ι
Löschen Sie die Frequenzen aus der sortierten, deduplizierten Liste.
⭆¹⟦
Stringifizieren Sie die Liste der ...
Ｌθ
... die Länge der Eingabe, ...
⪫υω
... die Verkettung der Zeichen in absteigender Reihenfolge der Häufigkeit und:
Ｅθ⍘⊕⌕υλ !
Suchen Sie für jedes Zeichen in der Eingabezeichenfolge den Beliebtheitsindex (1-indiziert, daher muss ich ihn erhöhen) und konvertieren Sie ihn mit benutzerdefinierten Ziffern in Basis 2.
⭆...⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ
Fügen Sie für jedes konvertierte Zeichen 7 zu seiner Länge hinzu, konvertieren Sie diese mit benutzerdefinierten Ziffern in Basis 2 und erstellen Sie eine Liste dieses und der konvertierten Zeichenfolge. Enthauptet alle Fäden und verkettet die Körper.
Ｅ⪪...⁸⍘◨λ⁸ !
Zerhacken Sie die Zeichenfolge in Teilzeichenfolgen der Länge 8, füllen Sie die letzte Teilzeichenfolge mit der rechten Maustaste auf und dekodieren Sie jede Teilzeichenfolge mit den benutzerdefinierten Basiszeichen als Basis 2 (insbesondere verwendet die rechte Teilzeichenfolge Leerzeichen, daher muss dies das benutzerdefinierte Basiszeichen für 0 sein). .
Beachten Sie, dass diese Version des Kompressors Bindungen löst, indem das Zeichen mit der höchsten Ordnungszahl anstelle des Zeichens mit dem ersten Erscheinungsbild verwendet wird, das in der vorherigen Version ausgewählt wurde. Ich habe die Eingabe für den Dekomprimierungslink entsprechend aktualisiert.
Dekomprimierer, 32 Bytes:
Ｆ⮌ζＦ⁸⊞υ﹪÷ιＸ²κ²⭆θ§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes.
Ｆ⮌ζ
Schleife über die Bytes in umgekehrter Reihenfolge.
Ｆ⁸
Schleife über jedes Bit in umgekehrter Reihenfolge.
⊞υ﹪÷ιＸ²κ²
Schieben Sie das Bit in die vordefinierte leere Liste.
⭆θ
Ordnen Sie jeden Index zu, verbinden Sie ihn und drucken Sie ihn implizit aus:
§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²
Pop 3 Bits aus der Liste, dekodieren als Basis 2, Pop so viele Bits aus der Liste, Präfix 1, dekodieren als Basis 2, Index in die Zeichenfolge (0-indiziert, also muss ich dekrementieren). (I verwendet haben könnte BaseStringund StringMapzweimal.)
JavaScript (Node.js) , 223 + 126 = 349 Byte
Kompressor, 223 Bytes
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))]
Probieren Sie es online aus!
Wie?
Generieren der sortierten Liste a[]eindeutiger Zeichen:
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()
Generieren des Byte-Streams als einzelnes 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()
Aufteilen des BigInt in eine Liste von Bytes:
(... << 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
Dekomprimierer, 126 Bytes
19 Bytes von @Neil gespeichert!
(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``)
Probieren Sie es online aus!
Wie?
Den Byte-Stream in eine Binärzeichenfolge umwandeln:
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
Ausgabe generieren:
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
Python 3 , 190 + 128 = 318 Bytes
Gespeicherte 28 41 55 57 82 Bytes (und unter 400!) Dank ovs !!!
10 Bytes dank Neil gespart !!!
Kompressor
Python 3 , 190 Bytes
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
Probieren Sie es online aus!
Dekompressor
Python 3 , 128 Bytes
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
Probieren Sie es online aus!
Bei der Dekomprimierung wird die Länge der ursprünglichen Zeichenfolge verwendet.
Schale , 119 103 95 (55 + 40) Bytes
Edit: -8 Bytes dank Neil
Kompressor (55 Byte):
,₁¹B256ḋS+ö`R0%8_Lṁ!ṁλm+tḋ+8¹(motḋ→½ŀ`^2→))ŀ8m€₁¹
↔Ö#¹u
Probieren Sie es online aus!
Dekomprimierer (40 Byte):
mö!²ḋ:1↓3↑I¡λ§,↓↑+3ḋ↑3¹)Ṡ+ö`R0%8_LḋB256⁰
Probieren Sie es online aus!
Wie funktioniert es?
Kompressor:
- Buchstaben nach Häufigkeit sortieren (Hilfsfunktion
₁):
↔Ö#¹u
- Ersetzen Sie Buchstaben durch ihren Rang nach Häufigkeit:
m€₁
- Genrate Präfix-Längen-Code:
ṁ ŀ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
- Suchen Sie jeden Präfix-Längencode aus jedem Buchstabenrang:
ṁ!
- Pad-Ende mit Ziffern auf Vielfaches von 8:
S+ö`R0%8_L
- Konvertieren Sie von binär zu base-256:
B256ḋ
- Und schließlich mit Buchstaben sortiert nach Häufigkeit sortiert:
,₁¹
Dekompressor:
- Konvertieren Sie das erste Argument von Base-256 in Binärziffern:
ḋB256⁰
- Pad beginnen mit Ziffern bis zu einem Vielfachen von 8:
Ṡ+ö`R0%8_L
- Abrufen von Präfixlängencodes:
¡λ ) # 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
- In jedes Element in eine Zahl konvertieren:
↓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
- Schlagen Sie den Brief vom zweiten Argument nach:
mö!²
J , 70 + 95 = 165 Bytes
Der Encoder kehrt length;table;byteswie in der Beschreibung zurück. Die Füllung für den letzten Block ist das zuletzt erzeugte Bit.
#;[(];[:#.@($~8,~#>.@%8:)@;(~.(128#3+i.8)<@$"0 1#:i.4^5){~i.~)~.\:#/.
Decoder mit genau demselben Format für die Eingabe:
>@{.$>@{~&1({~(~.(128#3+i.8)<@$"0 1#:i.4^5)i.l<@{.])"1[:(}.~l=:3+3#.@{.])^:(<_)128,@}.@#:@,>@{:
Probieren Sie es online aus!
Wie es ungefähr funktioniert
Codetabelle, die in beiden verwendet wird:
#:i.4^50… 1024 in binär.128#3+i.8Wiederholen Sie jede Zahl in 3… 11 128 Mal<@$"0für 0… 127 nehmen Sie die ersten 3 Ziffern, für 128… 255 nehmen Sie die ersten 4 Ziffern,…~.Nehmen Sie die einzigartigen Elemente des Ergebnisses.
Encoder:
~.\:#/.Sortieren Sie die eindeutigen Zeichen in der Eingabe nach Vorkommen. Das ist die Zeichentabelle.(table){~i.~Ordnen Sie die Eingabe den Positionen der Zeichentabelle zu und erhalten Sie den entsprechenden Code.($~8,~#>.@%8:)@;Verketten Sie alle Codes miteinander und teilen Sie sie in 8er-Blöcke auf.#;…];#.@Konvertieren Sie zurück in Ganzzahlen und stellen Sie die Zeichentabelle und die Länge voran.
Decoder:
128,@}.@#:@,>@{Nehmen Sie Bytes und konvertieren Sie sie zurück in Bits. Sie müssen 128 vorübergehend voranstellen, um die Ergebnisse auf 8 Bit aufzufüllen.[:(}.~l=:3+3#.@{.])^:(<_)Analysieren Sie die ersten 3 Bitsnund entfernen Sie sie und die nächstennBits aus dem Bit-Array. Tun Sie dies, bis das Bit-Array leer ist. Geben Sie alle Zwischenergebnisse zurück (also Startpositionen für die Codes).(table)i.l<@{.]Analysieren Sie erneut die Startbits und schlagen Sie sie in der Codetabelle nach.>@{~&1({~und suchen Sie den Index in der Zeichentabelle.>@{.$Trimmen Sie die Ausgabe auf die Länge der Zeichenfolge.
Perl 5 , 354 Bytes
@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]}
Probieren Sie es online aus!
Führen Sie dies aus, um mit der Funktion c () zu komprimieren und mit d () zu dekomprimieren.
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";
Ausgabe:
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|
Julia , 331 Bytes
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
Probieren Sie es online aus!
Ich möchte Komprimierung und Dekomprimierung nicht trennen, da ich die Funktionen pund sfür beide verwende.
c dient zur Komprimierung, gibt die sortierten Buchstaben und die komprimierte Zeichenfolge zurück (fehlende Bits werden mit 1s gefüllt)
ddient zur Dekomprimierung und benötigt nicht die Länge der ursprünglichen Zeichenfolge (das letzte ungültige Zeichen wird verworfen)