Mengenal algoritma kompresi Zstandard

Zstandard, atau lebih dikenal dengan nama implementasinya: zstd, adalah algoritma kompresi lossless yang sangat cepat dan fleksibel. Algoritma kompresi ini sudah disupport di banyak software, sampai sudah masuk di kernel Linux. Salah satu keunikan kompresi dengan zstandard adalah adanya fitur custom dictionary dan waktu kompresi dan dekompresi yang cepat. Kita bisa membuat custom dictionary untuk aplikasi kita sendiri. Bagian dictionary ini yang akan saya bahas lebih dalam pemanfaatnya di tulisan ini.

Lengkapnya bisa dilihat di: https://facebook.github.io/zstd/

Kompresi Lossless dan Lossy

Banyak praktisi IT yang masih bingung antara kompresi lossless dan lossy, dan ketika saya beritahu bahwa zstd adalah lossless compression malah bertanya apakah bisa mengkompress film dengan baik.

Algoritma kompresi yang lossless digunakan untuk mengkompres data dan hasil dekompresinya akan kembali sama persis 100% seperti semula. Ada batasan maksimum kompresinya. Tidak mungkin sebuah file dikompress lagi terus menerus sampai jadi 1 byte. Algoritma lossless ini yang dipakai untuk kompresi database, file text, dsb.

Algoritma kompresi lossy akan mengkompres data dengan membuang informasi yang dianggap tidak penting bagi manusia. Contohnya: suara yang tidak terdengar manusia bisa dihapus dari audio, detail gambar bisa dihapus dari gambar. Algoritma ini cocok untuk foto, suara, dan video. Contoh yang sering dilihat sehari-hari adalah file JPG, dan file MP4 (yang saat artikel ini ditulis biasanya memakai kompresi lossy H264/H265).

Jadi jangan membandingkan kompresi lossless dengan kompresi lossy, karena tidak masuk akal. Jika punya file video yang belum dikompres sama sekali, pasti akan lebih kecil jika dikompress dengan kompresi lossy.

Format file arsip dan Algoritma Kompresi

Perlu dibedakan antara format file arsip dan algorima kompresi. Contoh format file arsip adalah ZIP dan 7Z. Keduanya bisa digunakan untuk menyimpan banyak file, dan masing-masing filenya bisa dikompresi ataupun dibiarkan saja tidak dikompres.

Jika sebuah file dikompres dalam file arsip, ada banyak algoritma kompresi yang bisa dipilih. Defaultnya file ZIP memakai algoritma deflate, dan 7Z memakai algoritma LZMA. Tapi file ZIP juga mendukung banyak algoritma lain (termasuk juga lzma, dan juga zstandard).

Format file tar juga merupakan format arsip, tapi tidak mendukung kompresi untuk file-file di dalamnya. Jadi yang biasa dilakuan adalah: membuat file tar yang berisi banyak file, lalu file tarnya dikompres seluruhnya.

Masih banyak format file arsip lain dengan kelebihan dan kekurangan masing-masing. Contohnya ada zpaq yang memiliki fitur deduplikasi, artinya bisa pintar menyimpan data yang duplikat tidak akan memakan banyak space. Misalnya kita punya 30 file yang mirip (contoh: backup harian database SQL), maka arsip zpaq bisa lebih kecil dari 7z (untuk 1 file biasanya 7z akan lebih efisien).

Pendekatan Kompresi

Saat ini ada beberapa pendekatan kompresi yang umum. Yang pertama adalah dictionary based, yaitu melihat ke belakang dan merujuk ke data sebelumnya. Sederhananya begini, jika kita punya kalimat dengan repetisi seperti ini:

Laki-laki tinggi besar itu berbicara pada gadis kecil bertopi biru. Laki-laki tingi besar itu lalu mengajak gadis kecil bertopi biru untuk melihat keramaian kota.

Kita bisa membuat referensi ke data sebelumnya

Laki-laki tinggi besar (Andi) itu berbicara pada gadis kecil bertopi biru (Amy). Andi itu lalu mengajak Amy untuk melihat keramaian kota.

Pendekatan dictionary ini dipakai pada algoritma berbasis Lempel-Ziv. Ada banyak variasi dari algoritma ini dengan ide yang serupa.

Pendekatan kedua adalah menggunakan simbol yang lebih pendek. Misalnya kita bisa menuliskan semua daftar kata yang dipakai di kalimat, lalu diurutkan kata yang paling banyak dipakai mana. Kata teratas mendapatkan urutan 1, berikutnya urutan 2, dst. Setelah memiliki daftar angkanya, kita bisa mengganti tiap kata dengan angka.

Di dalam kompresi kita akan berurusan level bit, bukan kata. Contoh algoritma yang paling sederhana yang memakai pendekatan ini adalah Huffman coding yang memakai jumlah bit yang bulat. Pendekatan lain yang lebih efisien (misalnya arithmetic coding) tidak perlu memakai jumlah bit yang bulat (misalnya bisa memakai 1,5 bit untuk satu simbol).

Secara teori arithmetic coding ini paling efisien, tapi paling lambat, sehingga ada beberapa variasi untuk mempercepat ini. Saat ini yang paling efisien adalah Asymmetric numeral systems (ANS), dan variannya yang berbasis table: tANS.

Pendekatan ketiga adalah dengan mengubah data menjadi program. Contohnya: kita bisa menggantikan file bergiga byte berisi 1 juta digit PI dengan program yang menghasilkan bilangan tersebut yang hanya ratusan byte (tapi akan lama menghasilkan digitnya). Saat ini tidak ada cara untuk mengubah sembarang data menjadi program yang efisien dan selalu lebih kecil dari datanya.

Data kadang bisa dikompres lebih baik jika diproses lebih dahulu. Contoh salah satu algoritma transformasi adalah Burrows-Wheeler Transform yang dipakai dipakai di BZIP2. Format kompresi RAR memiliki bytecode yang bisa dieksekusi dengan RarVM. Secara sederhana: file RAR bisa memiliki program di dalamnya yang bisa mengubah data supaya lebih efisien ketika dikompres.

Zstandard

Zstandard adalah algoritma kompresi yang memakai teknik dictionary (Lempel-Ziv) dan tANS. Secara umum yang membuat zstandard ini bagus adalah karena detail formatnya dioptimasi untuk dunia modern, misalnya: dirancang untuk bisa diparalelkan, memakai dictionary yang ukurannya fleksibel, dsb. Detail implementasinya bisa dibaca di posting zstandard dari Meta.

Implementasi de facto zstandard ini adalah library dan command line yang bernama zstd. Default extensionnya adalah zst. Jadi secara sederhana, memakai zstd adalah memakai implementasi algoritma dan format zstandard.

Di berbagai distribusi Linux, zstd ini sudah default, jadi kita bisa mengkompres satu file dengan:

zstd namafile

dan dekompresi dengan:

zstd -d namafile.zst

Bagaimana jika ingin mengkompres banyak file menjadi satu? ada beberapa opsi tapi biasanya memakai tar (yang akan sekedar menggabungkan file), lalu memakai zstd. Jika Anda terbiasa memakai tar.gz yang dibuat seperti ini:

tar -zcf namafile.tar.gz namadirektori

maka parameter z bisa diganti menjadi --zstd

tar --zstd -cf namafile.tar.zst namadirektori

Dibandingkan algoritma kompresi lain: zstd ini sangat cepat (bisa puluhan kali lebih cepat). Ada 22 level kompresi, jika ingin kompresinya lebih baik (hasilnya lebih kecil) atau ingin kompresinya lebih cepat (hasilnya lebih besar), maka ini bisa diset.

Kecepatan kompresi kadang lebih penting dari ukuran. Contoh: saya memiliki file text 1GB, dengan zstd (setting standard) ini bisa dikompres dalam 1.5 detik (saya memakai NVME jadi akses disk cepat) menjadi 57 MB, dan 7z bisa mengkompres menjadi 38MB (jauh lebih kecil) tapi butuh 45 detik. Jika saya ingin mentransfer file di LAN, maka waktu untuk kompresi dengan plus waktu transfer + waktu dekompres, maka akan lebih cepat jika saya memakai zstd walau ukuran filenya lebih besar.

Hampir semua program kompresi akan memakai CPU yang tinggi, dan sering kali lebih diinginkan agar proses kompresi bisa cepat selesai, sehingga CPU bisa dipakai proses lain. Salah satu keunikan lain zstd adalah: meskipun kita set kompresinya sangat tinggi (misalnya dengan --ultra) dan waktu kompresinya menjadi lama, tapi waktu dekompresnya akan tetap cepat.

zstd dengan custom dictionary

Sekarang saya ingin membahas bagian fitur zstd yang tidak dimiliki kompressor populer lain saat ini: custom dictionary. Pertama untuk contoh, saya membuat 1000 file json dengan menggunakan library Python yang bernama faker. Saya memakai seed di contoh kecil ini, sehingga hasilnya bisa direproduksi.

from faker import Faker
import json

fake = Faker('id_ID')
Faker.seed(4321)
for i in range(0, 10000):
    data = {}
    data['nama'] = fake.name()
    data['alamat'] = fake.address()
    data['bio'] = fake.text()
    data['email'] = fake.email()
    data['birthdate'] = fake.date()
    data['company'] = fake.company()
    with open("person-{}.json".format(i), "w") as f:
        json.dump(data, fp=f, indent=True)

Program kecil tersebut akan membuat 10000 file json yang berisi informasi pribadi (rekaan saja) seorang user. Bayangkan ini dipakai di API oleh sebuah aplikasi mobile, tapi jangan bayangkan aplikasi mobilenya ingin langsung mengambil 1000 file, tapi hanya data yang diminta saja. Data ini bisa saja asalnya dari database atau sumber lain.

Jika saya kompresi satu file dengan berbagai kompressor yang ada, hasilnya seperti ini. File asli berukuran 239 byte, dan hasil kompresi standard semuanya lebih dari 200 bytes. Format seperti 7z akan lebih besar dibanding yang lain karena menyimpan nama file di dalam arsipnya.

239  person-0.json
201  person-0.json.gz
226  person-0.json.bz2
201  person-0.nodict.zst
327  person-0.json.7z

Jika kita punya banyak contoh file, kita bisa membuat dictionary sendiri:

zstd --train data/*json -o dict

Dalam kasus ini ukuran dictionary adalah 112640 bytes (dictionary ini bisa dikonfigurasi ukurannya, ini ukuran default). File ini perlu untuk kompresi dan dekompresi. Untuk aplikasi mobile, maka dictionary ini bisa dimasukkan ke dalam aplikasinya.

zstd -D dict data/person-0.json

Hasilnya adalah 85 bytes. Untuk mengkompres 1 file saja, maka ini sia-sia karena tetap butuh dictionary 100Kb. Tapi bayangkan jika ini dipakai di API call yang dipanggil jutaan kali dalam sehari, penghematan bandwidth bisa sangat besar.

Kita bisa menghasilkan data lain yang mirip (dengan mengganti limit loop agar menghasilkan data file baru), contohnya untuk file nomor 10000 (file ini tidak ada di data training):

348  person-10000.json
421  person-10000.json.7z
267  person-10000.json.gz
308  person-10000.json.bz2
125  person-10000.json.zst
275  person-10000.json.nodict.zst

Hasilnya: tetap cukup baik, ukurannya setengahnya gz. Dictionarynya dalam kasus ini membantu mengkompress “key” di JSON. Bagaimana jika ada data yang benar-benar baru di dalam JSON-ya, apakah data sembarang bisa dikompres dengan dictionary ini? jawabannya: ya sembarang data tetap bisa dikompres, hanya saja dictionarynya tidak akan membantu untuk kasus itu (kompresinya seperti kompresi biasa).

Saat ini sudah ada binding zstd untuk semua bahasa pemrograman yang populer. Jadi jika sudah memiliki dictionary yang dibuat dengan command line, ini bisa dipakai oleh program dalam hampir semua bahasa untuk mendekompres. Contohnya dalam Python seperti ini:

import zstandard
import pathlib

def decompress_zstandard_to_folder_with_dict(input_file, destination_dir, dict_file):
    input_file = pathlib.Path(input_file)
    with open(dict_file, 'rb') as data:
        dict_data = zstandard.ZstdCompressionDict(data.read())
        decomp = zstandard.ZstdDecompressor(dict_data=dict_data)
    with open(input_file, 'rb') as compressed:
        output_path = pathlib.Path(destination_dir) / input_file.stem
        with open(output_path, 'wb') as destination:
            decomp.copy_stream(compressed, destination)

decompress_zstandard_to_folder_with_dict('data/person-0.json.zst', 'output', 'dict')

Penutup

Dulu ketika baru punya komputer kali pertama, harddisk 1GB saya cepat penuh karena mencoba banyak software. Sejak itu saya penasaran dengan berbagai sistem kompresi yang ada karena belum punya uang untuk membeli harddisk baru (dulu di Windows 95 ada yang namanya DriveSpace untuk kompresi). Saya juga penasaran mengimplementasikan kompresi sendiri, yang paling sederhana yang saya coba adalah berbasis Huffman Coding. Sampai sekarang pun ilmu tentang kompresi ini masih terpakai di kehidupan sehari-hari. Minimal saya bisa menentukan program atau algoritma kompresi apa yang perlu dipakai untuk menyelesaikan masalah tertentu.

Perkenalan saya dengan zstandard adalah ketika dulu saya butuh implementasi kompresi untuk salah satu aplikasi internal perusahaan. Setelah itu saya mulai suka memakai zstd karena kecepatannya. Ternyata ketika saya sebutkan tentang kompresi ini di sebuah group, banyak yang belum pernah dengar sama sekali.

Zstd ini memang belum tentu cocok untuk semua kebutuhan, tapi menurut saya zstd ini sesuatu yang perlu diketahui baik oleh programmer ataupun administrator. Dalam kasus tertentu zstd ini bisa jadi game changer karena kecepatannya dan fitur custom dictionarynya.

One thought on “Mengenal algoritma kompresi Zstandard”

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *