Konversi basis (CJam)
Cara mudah untuk menyandikan string ASCII yang tidak dimulai dengan byte nol adalah mengkonversi dari basis 128 ke integer, kemudian ke basis 256:
128b256b:c e# Prints encoded string.
128b256b:c`"256b128b:c" e# Prints encoded string with decoder.
Ini menggunakan 7 bit untuk mengkodekan setiap karakter ASCII.
Jika string asli hanya terdiri dari, misalnya, huruf kecil, dan tidak dimulai dengan huruf a , kita bisa mulai dengan memetakan "a...z"
ke [0 ... 25]
, kemudian melanjutkan seperti di atas:
'afm26b256b:c e# Prints encoded string.
'afm26b256b:c`"256b26b'af+" e# Prints encoded string with decoder.
Akhirnya, jika string asli hanya memiliki beberapa karakter unik (umum dalam seni ASCII), biasanya lebih baik untuk menentukan alfabet secara eksplisit.
Sebagai contoh:
" +-/\|"f#6b256b:c e# Prints encoded string.
" +-/\|"f#6b256b:c`"256b6b"" +-/\|"`"f=" e# Prints encoded string with decoder.
Sebagai aturan praktis, Anda ingin karakter pertama dari string asli menjadi karakter kedua dari alfabet, karakter berbeda berikutnya dari string asli menjadi karakter pertama dari alfabet, karakter berbeda berikutnya dari string asli menjadi menjadi karakter ketiga alfabet, karakter berbeda berikutnya dari string asli menjadi karakter keempat alfabet, dll.
Encoder dari contoh terakhir berfungsi sebagai berikut:
" +-/\|"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 contoh terakhir berfungsi sebagai berikut:
256b6b e# Convert from base 256 to base 6.
" +-/\|"f= e# Replace each digit by the corresponding character of the alphabet.
Pertanyaan kompleksitas Kolmogorov yang lebih besar dengan beberapa struktur tetapi tanpa formula sederhana (misalnya lirik lagu) biasanya akan mendapat manfaat dari pendekatan berbasis tata bahasa. Intinya, Anda mengekstrak substring berulang dan menyandikannya entah bagaimana. Inilah yang dilakukan Lempel-Ziv, menggunakan kelas tata bahasa yang cukup terbatas; jika Anda menggunakan tata bahasa yang lebih umum maka Anda harus mencari cara untuk menyandikan aturan. Misalnya satu pendekatan di sini adalah "offset encoding", di mana Anda mengimbangi setiap byte sumber dengan jumlah aturan (
n
), menetapkan byte1
ken
aturan, gunakan0
byte untuk memisahkan aturan, dan berulang kali mengganti bytei
dengan aturan yang dievaluasii
. Akhirnya Anda membatalkan offset dengan mengurangin
dari setiap byte.Saya sebenarnya telah menulis program Java yang mengimplementasikan berbagai pendekatan:
Ini juga mencakup pendekatan Lempel-Ziv, pendekatan pengkodean basis, dan pendekatan pengkodean runlength, dan mengidentifikasi pendekatan yang memberikan program terpendek.
sumber
Stax
Dalam bahasa golf kode Stax , ada alat kecil yang membantu yang disebut kompresor literal string . Saya tidak tahu cara kerjanya, tepatnya, tapi ada lain di mana saya tidak tahu cara kerjanya. Ini mengubah string menjadi angka, kemudian ke Basis 256. Ini CP437 , dengan 0x00 dan 0xFF dikonversi untuk disalin. Itu PackedStax. Anda dapat mengubah string Anda dengan kompresor literal string kemudian Kemas, untuk kompresi yang baik.
Menggunakan proses ini string "String ini adalah tiga puluh dua byte" dapat dikonversi ke v * "A] - | W4]} 3"% (string terkompresi biasanya dikelilingi oleh backticks untuk membedakan antara string normal di Stax ) dan akhirnya ke !vìë! [┴╩qJu ← ▓α untuk kompresi / pengurangan 18 byte, lebih dari setengahnya.
sumber