Grundkonvertierung (CJam)
Eine einfache Möglichkeit, ASCII-Zeichenfolgen zu codieren, die nicht mit einem Null-Byte beginnen, besteht darin, sie von der Basis 128 in eine Ganzzahl und dann in die Basis 256 zu konvertieren:
128b256b:c e# Prints encoded string.
128b256b:c`"256b128b:c" e# Prints encoded string with decoder.
Dies verwendet 7 Bits, um jedes ASCII-Zeichen zu codieren.
Wenn die ursprüngliche Zeichenfolge nur aus z. B. Kleinbuchstaben besteht und nicht mit einem a beginnt, können wir mit der Zuordnung "a...z"
zu beginnen. Gehen Sie [0 ... 25]
dann wie oben vor:
'afm26b256b:c e# Prints encoded string.
'afm26b256b:c`"256b26b'af+" e# Prints encoded string with decoder.
Wenn die ursprüngliche Zeichenfolge nur wenige eindeutige Zeichen enthält (wie in ASCII-Grafiken üblich), ist es in der Regel besser, das Alphabet explizit anzugeben.
Beispielsweise:
" +-/\|"f#6b256b:c e# Prints encoded string.
" +-/\|"f#6b256b:c`"256b6b"" +-/\|"`"f=" e# Prints encoded string with decoder.
Als Faustregel möchten Sie, dass das erste Zeichen der ursprünglichen Zeichenfolge das zweite Zeichen des Alphabets ist, das nächste eindeutige Zeichen der ursprünglichen Zeichenfolge das erste Zeichen des Alphabets und das nächste eindeutige Zeichen der ursprünglichen Zeichenfolge Das dritte Zeichen des Alphabets, das nächste eindeutige Zeichen der ursprünglichen Zeichenfolge das vierte Zeichen des Alphabets usw.
Der Encoder des letzten Beispiels funktioniert wie folgt:
" +-/\|"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.
Der Decoder des letzten Beispiels funktioniert wie folgt:
256b6b e# Convert from base 256 to base 6.
" +-/\|"f= e# Replace each digit by the corresponding character of the alphabet.
Größere Kolmogorov-Komplexitätsfragen mit einer gewissen Struktur, aber keiner einfachen Formel (z. B. Liedtexte) profitieren normalerweise von einem grammatikbasierten Ansatz. Im Wesentlichen extrahieren Sie wiederholte Teilzeichenfolgen und codieren sie irgendwie. Dies ist, was Lempel-Ziv mit einer ziemlich eingeschränkten Klasse von Grammatiken tut; Wenn Sie allgemeinere Grammatiken verwenden, müssen Sie herausfinden, wie die Regeln codiert werden. ZB ein hier Ansatz ist „Offset - Codierung“, wo Sie jede Quellbyte durch die Anzahl der Regeln Offset (
n
), assign Bytes1
zun
den Regeln, die verwenden0
Byte separate Regeln und wiederholt Byte ersetzeni
mit der ausgewerteten Regeli
. Zuletzt machen Sie den Versatz rückgängig, indem Sien
von jedem Byte abziehen .Ich habe tatsächlich ein Java-Programm geschrieben, das verschiedene Ansätze implementiert:
Es enthält auch einen Lempel-Ziv-Ansatz, einen Basiscodierungsansatz und einen Lauflängencodierungsansatz und identifiziert denjenigen, der das kürzeste Programm ergibt.
quelle
Stax
In der Stax- Code-Golfsprache gibt es ein hilfreiches kleines Tool, den String-Literal-Kompressor . Ich weiß nicht genau, wie es funktioniert, aber es gibt eine andere, bei der ich weiß , wie es funktioniert. Es konvertiert Strings in Zahlen und dann in Base 256. Es ist CP437 , wobei 0x00 und 0xFF zum Kopieren konvertiert werden. Es ist PackedStax. Sie können Ihre Zeichenfolgen mit dem String-Literal-Kompressor konvertieren und dann packen, um eine gute Komprimierung zu erzielen.
Mit diesem Verfahren kann die Zeichenfolge "Diese Zeichenfolge ist zweiunddreißig Bytes" in v * "A] - | W4]} 3"% konvertiert werden (die komprimierte Zeichenfolge wird normalerweise von Backticks umgeben, um den Unterschied zwischen einer normalen Zeichenfolge in Stax zu erkennen ) und schließlich zu üvìë! [┴╩qJu ← ▓α für eine Komprimierung / Reduzierung von 18 Bytes, mehr als die Hälfte.
quelle