Tulis encoder GIF

9

Ya, GIF tua yang bagus. Dicintai karena keserbagunaannya, dibenci karena patennya dan sebagian sudah usang karena keterbatasannya (dan patennya), GIF pada intinya terdiri dari palet warna dan gambar yang diindeks palet yang dikompres menggunakan algoritma LZW.

Tugas Anda adalah menulis program yang membaca gambar dalam format ASCII PPM ("nomor ajaib") dari input standar, dan menulis gambar yang sama (pixel-by-pixel identik) dalam format GIF ke output standar. Outputnya bisa dalam bentuk biner, atau teks ASCII dengan setiap byte diwakili oleh angka antara 0 dan 255 (inklusif), dipisahkan oleh spasi putih.

Gambar input dijamin tidak memiliki lebih dari 256 warna berbeda.

Mencetak:

Program Anda akan diuji pada 3 gambar sampel, dan skor Anda akan dihitung sebagai:
ukuran program + jumlah (ukuran output - ukuran referensi untuk setiap gambar sampel)
Skor terendah menang.

Persyaratan:

  • Program Anda harus bekerja dengan jenis gambar yang serupa dari berbagai ukuran, dan tidak terbatas pada gambar sampel. Anda dapat, misalnya, membatasi dimensi menjadi kelipatan 2 atau menganggap bahwa warna ppm max adalah 255, tetapi masih harus bekerja dengan berbagai macam gambar input.
  • Keluaran harus berupa file GIF yang valid yang dapat dimuat dengan program apa pun yang sesuai (setelah mengonversi kembali ke biner jika menggunakan opsi keluaran ASCII).
  • Anda tidak dapat menggunakan fungsi pemrosesan gambar apa pun (bawaan atau pihak ketiga), program Anda harus berisi semua kode yang relevan.
  • Program Anda harus dapat dijalankan di Linux menggunakan perangkat lunak yang tersedia secara bebas.
  • Kode sumber harus hanya menggunakan karakter ASCII.

Contoh gambar:

Berikut adalah 3 contoh gambar yang akan digunakan untuk penilaian. Anda dapat mengunduh arsip zip dengan file ppm (gunakan tombol unduh di bagian atas halaman itu). Atau Anda dapat mengonversinya dari gambar png di bawah ini, menggunakan ImageMagick dengan perintah berikut:

convert file.png -compress none file.ppm

Saya juga menyediakan checksum MD5 dari file ppm untuk konfirmasi.

1. kuning

amber.png

Ukuran referensi: 38055
MD5 checksum dari ppm: d1ad863cb556869332074717eb278080

2. mata biru

blueeyes.png

Ukuran referensi: 28638
MD5 checksum dari ppm: e9ad410057a5f6c25a22a534259dcf3a

3. paprika

paprika.png

Ukuran referensi: 53586
MD5 checksum dari ppm: 74112dbdbb8b7de5216f9e24c2e1a627

aditsu berhenti karena SE adalah JAHAT
sumber
1
Catatan Moderator: Komentar di luar topik / usang dihapus. Silakan lihat meta untuk diskusi tentang contoh gambar dalam pertanyaan ini.
Gagang pintu
Tampaknya gambar kedua diperlakukan dengan sesuatu seperti ini: optimasi situs web / kecepatan / tweak / loty yang akan menjelaskan rasio kompresi yang lebih baik dan sensitivitas terhadap tweak encoder LZW.
nutki
1
“Kode sumber harus hanya menggunakan karakter ASCII.” - jadi, dengan kata lain, kami tidak diizinkan melakukan tantangan ini di APL?
FUZxxl
@FUZxxl benar, tetapi Anda dapat menggunakan J. Anda juga tidak diizinkan menggunakan Aheui atau melakukan trik konversi dasar dalam GolfScript / CJam.
Aditsu berhenti karena SE adalah JAHAT

Jawaban:

4

Perl, 515 + -2922 + 0 + -2571 = -4978

Pendekatan lain. Kali ini saya mencoba untuk menyimpan gambar dalam ubin ukuran 64xH. Ini sesuai dengan spesifikasi, tetapi beberapa perangkat lunak hanya menampilkan ubin pertama atau animasi. Ubin mengkompres lebih baik karena lokalitas spasial yang lebih baik. Saya masih melakukan kompresi normal juga untuk gambar kedua dan memilih apa pun yang datang lebih pendek. Karena ini memampatkan gambar dua kali, itu dua kali lebih lambat dibandingkan dengan solusi saya sebelumnya.

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@l=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
print+GIF89a,pack(vvCxxC768,@k,~8,@t);
sub v{($w,$h)=@_;for$k(0.."@k"/$w-1){
$k*=$w;$r='';@d=();@p=grep+($z++-$k)%"@k"<$w,@l;
$"=' ';$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
$h.=pack"Cv4n(C/a)*",44,$k,0,$w,$k[1],8,/.{0,255}/gs
}$b=$h if!$b||length$b>length$h}
"@k"%64||v 64;v"@k";print"$b;"

Perl, 354 + 12 + 0 + -1 = 365 418 9521 51168 56639

Entah ada beberapa bug dalam kode saya atau gambar kedua dioptimalkan untuk encoder tertentu karena perubahan yang tampaknya tidak signifikan mengurangi ukuran ke referensi dengan tepat. Memakan sekitar 30-an-60 per gambar.

Versi golf.

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

Satu-satunya keputusan yang dapat diambil oleh kompresor GIF adalah kapan harus mengatur ulang kamus LZW. Secara umum karena bagaimana gambar untuk tugas ini dipilih saat terbaik untuk melakukannya adalah setiap kode 4096 yang merupakan saat kamus akan meluap. Dengan batas seperti itu kamus tidak pernah meluap yang menyimpan beberapa byte dalam implementasi. Beginilah cara kerjanya secara detail:

#!perl -n0
# function to add one codeword to the output stream @r.
# the current codeword length is based on the dictionary size/
sub r{push@r,map"@_">>$_,0..log(@d|256)/log 2}
# get the dimensions into @k
@k=/(\d+) (\d+)/;
# get pixel indexes to @p and palette to @t
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
# convert index table into space separated string 
$_="@p ";$"='|';
# LZW encoder; while something to encode
while(/\S/){
# output reset code
r 256;
# reset code dictionary $d is the last code number,
# %d is the map of codes and @d list of codes
$d=257;%d=map{($_,$_-1)}@d=1..256;
# find codes using regexp, stop at dictionary overflow
while($d<4096&&s/^(@d) (\d*)/$2/){
unshift@d,$&;$d{$&}=++$d;r$d{$1}}}
# end LZW encoder; output end code
r 257;
# convert bit string @r to bytes $f
vec($f,$j++,1)=$_ for@r;
# output header up to the color table
print+GIF89a,pack(vvCvC768,@k,~8,0,@t),
# output rest of the header
pack(Cv4CC,44,0,0,@k,0,8),
# output the LZW compressed data $f slicing into sub-blocks
$f=~s/.{0,255}/chr(length$&).$&/egsr,';'

Perl, 394 + -8 + 0 + -12 = 374

Menambahkan heuristik untuk menebak titik reset meningkatkan kompresi sedikit tetapi tidak cukup untuk membenarkan kode tambahan:

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while
(@d<4001||(/((@d) ){11}/,$&=~y/ //>12))&@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'
nutki
sumber
Sangat bagus! Meskipun dibutuhkan lebih dari 30-an per gambar di sini. Saya cukup terkesan dengan -30 dari versi sebelumnya, saya ingin tahu apakah Anda dapat menggabungkan metode dan mendapatkan skor yang lebih rendah. Bisakah Anda menulis sedikit tentang apa yang dilakukan oleh program?
Aditsu berhenti karena SE adalah JAHAT
Membutuhkan lebar untuk kelipatan 64 tampaknya agak ekstrem ...
aditsu berhenti karena SE adalah EVIL
@aditsu, Tidak diperlukan, jika lebarnya tidak dari 64 metode ubin tidak dicoba dan kompresi biasa digunakan. Tentu saja dengan biaya lain ~ 100 karakter saya bisa membuat ukuran variabel ubin terakhir.
nutki
Sangat lambat, dan gambar ubin ditampilkan sebagai animasi, tapi .. bagus, cukup mengesankan untuk melihat Anda benar-benar dapat membuatnya lebih kecil.
Aditsu berhenti karena SE adalah JAHAT
2

CJam, skor 155 + 35306 + 44723 + 21518 = 101702

Hanya implementasi referensi bodoh. Ini lambat, tidak melakukan kompresi yang sebenarnya dan tidak golf.

"GIF89a":iS*SqN/S*S%1>:i3/:M0=2<256f{md\}S*:ZS247S0S0SM1>_|:PL*_,768\m0a*+S*S44S0S0S0S0SZS0S8SM1>Pf{\a#}254/256a*{512+2b1>W%}%:+8/{W%2b}%255/{_,S@S*S}/0S59
aditsu berhenti karena SE adalah JAHAT
sumber