Kompresi dalam Big Data: Jenis dan Teknik

\

Pendahuluan

Artikel ini akan membahas kompresi dalam konteks Big Data, mencakup jenis dan metode kompresi. Saya juga akan menyoroti mengapa dan kapan setiap jenis dan metode harus digunakan.

\

Apa itu kompresi?

Menurut definisi umum bahasa Inggris tentang kompresi, ini mengacu pada mengurangi sesuatu agar menempati ruang yang lebih kecil. Dalam Ilmu Komputer, kompresi adalah proses mengurangi data ke ukuran yang lebih kecil. Data, dalam hal ini, dapat direpresentasikan dalam teks, audio, file video, dll. Anggap saja sebagai apa pun yang Anda simpan di hard drive komputer Anda, sebagai data yang direpresentasikan dalam berbagai format. Untuk memberikan definisi yang lebih teknis, kompresi adalah proses pengkodean data untuk menggunakan lebih sedikit bit.

\ Ada beberapa alasan untuk mengompresi data. Alasan paling umum dan intuitif adalah untuk menghemat ruang penyimpanan. Alasan lain adalah hasil dari data yang lebih kecil. Manfaat bekerja dengan data yang lebih kecil meliputi:

1. Waktu Transmisi Data Lebih Cepat: Data terkompresi berukuran lebih kecil dan membutuhkan waktu lebih sedikit untuk ditransmisikan dari sumber ke tujuan.
2. Konsumsi bandwidth berkurang: Alasan ini sangat terkait dengan keuntungan transmisi data yang lebih cepat. Data terkompresi menggunakan lebih sedikit bandwidth jaringan, sehingga meningkatkan throughput dan mengurangi latensi.
3. Peningkatan kinerja untuk sistem digital yang sangat bergantung pada data: Ini terlihat jelas dalam sistem yang bergantung pada pemrosesan data. Sistem tersebut memanfaatkan kompresi untuk meningkatkan kinerja sistem dengan mengurangi volume data yang perlu diproses. Harap dicatat bahwa ini mungkin spesifik untuk sistem tertentu dan akan bergantung pada penggunaan teknik kompresi yang sesuai. Teknik kompresi akan dibahas nanti dalam artikel ini.
4. Efisiensi Biaya: Layanan cloud mengenakan biaya untuk penyimpanan data. Dengan menggunakan lebih sedikit penyimpanan, penghematan biaya diperkenalkan, terutama dalam sistem Big Data.

\ Alasan lain untuk kompresi tergantung pada teknik dan format kompresi yang berbeda. Beberapa algoritma enkripsi dapat digunakan sebagai metode kompresi. Dengan melakukan itu, ini mencakup lapisan keamanan untuk alasan yang dibahas sebelumnya untuk mengompresi data. Selain itu, menggunakan format kompresi umum membawa kompatibilitas dan ruang untuk ekstensibilitas ke sistem eksternal untuk tujuan integrasi.

\ Perlu dicatat bahwa alasan untuk kompresi juga terdengar seperti manfaat. Namun, kompresi tidak tanpa kompromi. Salah satu kompromi umum untuk kompresi adalah kebutuhan untuk dekompresi, yang mungkin menjadi perhatian untuk sistem dengan sumber daya terbatas. Kompromi lain tergantung pada teknik kompresi dan jenis data yang digunakan.

\

Jenis Kompresi

Untuk membahas berbagai teknik yang digunakan untuk mengompresi data, saya akan terlebih dahulu mengkategorikan kompresi menjadi 2 kategori utama. Artikel ini kemudian akan membahas teknik yang relevan untuk setiap kategori. Kompresi dapat dikelompokkan secara luas menjadi kompresi Lossy dan Lossless.

\ Seperti namanya yang sudah menjelaskan artinya, kompresi Lossy adalah teknik yang tidak mempertahankan fidelitas penuh dari data. Sederhananya, beberapa data dibuang, tetapi tidak cukup untuk membuat apa yang direpresentasikan data menjadi tidak dapat dikenali. Oleh karena itu, kompresi lossy dapat menawarkan tingkat kompresi yang sangat tinggi dibandingkan dengan kompresi lossless, yang akan diperkenalkan sebentar lagi.

\ Karakteristik kompresi lossy adalah bahwa itu tidak dapat dibalik, yaitu, ketika disajikan dengan file terkompresi, seseorang tidak dapat mengembalikan data mentah dengan fidelitas aslinya. File dan format file tertentu cocok untuk kompresi lossy. Ini biasanya digunakan untuk gambar, audio, dan video. Misalnya, gambar berformat JPEG cocok untuk kompresi, dan dengan mengompresi gambar JPEG, pembuat atau editor dapat memilih berapa banyak kehilangan yang akan diperkenalkan.

\ Di sisi lain, kompresi lossless dapat dibalik, yang berarti bahwa ketika dikompresi, semua data dipertahankan dan dipulihkan sepenuhnya selama dekompresi. Ini menyiratkan bahwa kompresi lossless cocok untuk file seperti teks, dan dalam dunia data warehouse dan lakehouse, ini akan menjadi satu-satunya jenis yang relevan untuk digunakan. Beberapa format file audio (FLAC dan ALAC) dan gambar (GIF, PNG, dll.) bekerja dengan baik dengan jenis kompresi ini.

Memilih metode

Tidak ada metode kompresi terbaik secara umum. Berbagai faktor terlibat dalam memilih metode apa yang cocok berdasarkan kasus per kasus. Untuk menguatkan ini dengan contoh, seorang data engineer di industri keuangan yang bekerja pada data tabular yang disimpan akan cenderung menggunakan kompresi lossless karena dampak data yang hilang dalam membuat pelaporan yang akurat. Sebagai alternatif, kompresi lossy bisa menjadi cara untuk mengoptimalkan halaman web dengan banyak gambar dengan mengompresi gambar dan mengurangi item beban dengan membuat situs web lebih ringan. Oleh karena itu, sangat penting untuk melakukan penilaian untuk menentukan metode kompresi yang paling tepat yang selaras dengan persyaratan bisnis.

Teknik Kompresi

Bagian ini hanya akan mencakup teknik kompresi umum untuk kompresi lossy dan lossless. Harap dicatat bahwa ini tidak lengkap dengan cara apa pun. Selanjutnya, teknik yang dibahas mungkin memiliki variasi kecil untuk meningkatkan kinerjanya, sebagaimana didukung oleh berbagai penelitian.

Teknik kompresi lossless

Tiga teknik lossless umum adalah Run-Length Encoding (RLE), Huffman Coding, dan teknik Lempel-Ziv-Welch.

\ Run-Length Encoding: RLE didasarkan pada pengkodean data, sehingga menggantikan urutan data yang berulang dengan satu bagian data dan jumlah bagian data tersebut. Ini efektif untuk urutan panjang data yang berulang. Juga, dataset yang memiliki dimensi (bidang) yang diurutkan dari tingkat kardinalitas rendah ke tinggi mendapat manfaat dari RLE.

\ Misalnya, ambil string sederhana seperti AAAAABBCDDD. RLE mengompresi data menjadi A(5)B(2)C(1)D(3). Untuk lebih praktis, ambil tabel pada gambar di bawah ini.

\ Gambar 1 - sebelum RLE. Penting untuk mengamati bahwa tingkat kardinalitas meningkat pada bidang dari kiri ke kanan

Gambar 2 - Setelah RLE

Karena RLE bergantung pada urutan bidang yang berulang, dan dalam contoh kedua, kardinalitas dan urutan pengurutan data, catatan Mouse pada kolom item tidak dapat dikompresi menjadi hanya Mouse (3) karena kolom sebelumnya membagi semua nilai menjadi IT, Mouse dan HR, Mouse. Format file tertentu kompatibel dengan RLE, seperti format file bitmap seperti TIFF, BMP, dll. File Parquet juga mendukung RLE, membuatnya sangat berguna di data lakehouse modern yang menggunakan object storage seperti S3 atau GCS.

\ Huffman Coding: Ini didasarkan pada pemodelan statistik yang menetapkan kode panjang variabel ke nilai dalam data mentah berdasarkan frekuensi di mana mereka terjadi dalam data mentah. Representasi pemodelan ini dapat disebut sebagai pohon Huffman, yang mirip dengan pohon biner. Pohon ini kemudian digunakan untuk membuat kode Huffman untuk setiap nilai dalam data mentah. Algoritma memprioritaskan pengkodean nilai yang paling sering dalam bit sesedikit mungkin.

\ Mari kita ambil data yang sama yang digunakan dalam contoh RLE AAAAABBCDDD. Pohon Huffman yang sesuai terlihat seperti ini.

\ Pohon Huffman

Dari pohon, kita dapat melihat bahwa huruf A direpresentasikan oleh 0 demikian juga D direpresentasikan oleh 10. Dibandingkan dengan huruf B: 111 dan C:110, kita mengamati bahwa A dan D direpresentasikan oleh lebih sedikit bit. Ini karena mereka memiliki frekuensi yang lebih tinggi; oleh karena itu, algoritma Huffman merepresentasikan mereka dengan lebih sedikit bit berdasarkan desain. Data terkompresi yang dihasilkan menjadi 00000111111110101010.

\ Huffman Coding menggunakan aturan awalan, yang menyatakan bahwa kode yang mewakili karakter tidak boleh ada dalam awalan kode lain. Misalnya, kode Huffman yang valid tidak dapat memiliki huruf c dan d yang direpresentasikan menggunakan C: 00 dan D: 000 karena representasi C adalah awalan dari D.

\ Untuk melihat ini dalam aksi, Panduan Bidang Ilmu Komputer memiliki Generator Pohon Huffman yang bisa Anda mainkan.

\ Lempel–Ziv–Welch Coding: Ini dibuat oleh Abraham Lempel, Jacob Ziv, dan Terry Welch pada tahun 1984 dan dinamai sesuai pembuatnya, tentu saja 😅. Mirip dengan RLE dan Huffman Coding, LZW bekerja dengan baik dengan data yang mengandung banyak data yang berulang. Algoritma LZW berbasis kamus dan membuat kamus yang berisi pasangan kunci-nilai dari pola yang umum terlihat dalam data mentah. Kamus seperti itu juga dapat disebut sebagai tabel kode. Menggunakan ilustrasi untuk menjelaskan bagaimana teknik ini bekerja, mari kita ambil data mentah kita untuk direpresentasikan oleh ABBABABABA. Ketika dilewatkan melalui algoritma menggunakan konfigurasi A-Z sebagai nilai yang mungkin, tabel kode yang dihasilkan terlihat seperti:

\ Tabel Kode LZW

Dari tabel kode di atas, ada pasangan kunci-nilai untuk semua huruf A-Z dan pasangan kunci-nilai untuk pola seperti AB, BB, BA, dan ABA. Dengan memiliki representasi yang lebih pendek dari pola ini, algoritma LZW dapat mengompresi data mentah dengan mengkodekannya menjadi lebih sedikit bit. Oleh karena itu, menggunakan tabel kode yang dihasilkan dari input tersebut, versi terkompresi adalah 0 1 1 26 29 28. Penting untuk memperhatikan spasi dalam data terkompresi. Seseorang dapat menganggapnya sebagai akhir dari karakter, sehingga decoder tidak akan menginterpretasikan 1,0 sebagai 10 karena mereka berarti hal yang berbeda.

\ LZW biasanya untuk tujuan umum dan banyak digunakan saat ini. Ini terintegrasi ke dalam banyak sistem operasi berbasis Unix/Linux di belakang perintah shell compress. Juga, format file umum yang kompatibel dengan LZW adalah GIF, TIFF, dan PDF. Aplikasi lain dari Kompresi LZW dapat dilihat di bidang Pemrosesan Bahasa Alami, seperti yang dibahas dalam makalah ini tentang tokenisasi dalam NLP.

\ RLE, Huffman Coding, dan LZW Coding hanyalah contoh umum. Teknik kompresi lossless melampaui tiga (3) yang dijelaskan di atas. Teknik lain termasuk DEFLATE, yang menggunakan kombinasi Huffman dan LZW - khususnya LZ77 - Coding.

Teknik kompresi lossy

Di bagian ini, kita akan melihat dua jenis kompresi lossy. Ingat bahwa kompresi lossy memperkenalkan kehilangan pada data asli, yang berarti bahwa tidak semua data disimpan.

\ Discrete Cosine Transform (DCT): Metode kompresi ini digunakan terutama dalam file audio, gambar, dan video dan juga biasa disebut sebagai kompresi blok. Ini menggunakan fungsi matematika - fungsi kosinus, seperti yang tersirat dari namanya - untuk mengonversi blok data asli menjadi frekuensi. Blok data biasanya matriks 8x8, 4x4, dan seterusnya, dalam urutan besaran tersebut.

\ Kompresi datang ketika berurusan dengan frekuensi tinggi yang terjadi dalam data, setelah data mentah diterjemahkan ke dalam domain frekuensi menggunakan fungsi matematika. Proses keseluruhan menggunakan DCT untuk kompresi adalah:

• Memecah data mentah menjadi potongan. Misalnya, dalam kompresi gambar, ini bisa menjadi 8x8 piksel.
• Menerapkan fungsi matematika untuk mengonversi potongan data menjadi frekuensi. Ini akan menghasilkan beberapa frekuensi tinggi dan frekuensi rendah.
• Frekuensi tinggi kemudian dikurangi atau dihapus tergantung pada tingkat kehilangan yang dapat diterima yang bersedia diperkenalkan. Di sinilah ia benar-benar menjadi kompresi lossy.
• Untuk mengonversi kembali ke data yang dapat direpresentasikan, semua frekuensi yang tersisa dilewatkan melalui Inverse Discrete Cosine Transform - IDCT - untuk mengembalikan data dari frekuensi.

\ DCT banyak digunakan di berbagai bidang saat ini, tidak hanya dalam kompresi tetapi juga dalam pemrosesan sinyal. Format file umum yang kompatibel dengan DCT adalah JPEG (gambar), MP3 (audio), dan MPEG (video). Selain itu, DCT dapat mencapai rasio kompresi tinggi, membuatnya cocok untuk sistem digital dengan banyak gambar, seperti halaman web di Internet.

\ Fractal Compression: Fraktal adalah pola tak terbatas yang berulang sendiri yang berulang pada skala yang berbeda. Ketika dilihat dari titik mana pun pada skala, pola terlihat serupa. Karena pola serupa pada skala apa pun, kompresi fraktal mengurangi skala fraktal 'besar' untuk mengurangi ukuran data.

\ Contoh Fraktal

Fractal Compression diperkenalkan oleh Michael Barnsley pada tahun 1980-an. Ide umum menggunakan gambar adalah bahwa jika gambar berisi beberapa bagian yang terlihat mirip, mengapa menyimpannya dua kali? Untuk melakukan ini, kompresi fraktal melakukan hal berikut:

• Mempartisi gambar menjadi blok yang tidak tumpang tindih yang dikenal sebagai blok rentang. Ini bisa menjadi blok rentang 8x8, 16x16 piksel, dll.
• Ini memindai gambar untuk pola yang berulang sendiri (pola fraktal). Menggunakan blok rentang, algoritma menemukan bagian gambar yang lebih besar yang mirip dengan blok rentang ini. Bagian yang lebih besar ini disebut sebagai blok domain.
• Fungsi transformasi kemudian diterapkan pada blok domain untuk memperkirakan blok rentang. Fungsi transformasi ini adalah fungsi matematika seperti penskalaan, translasi, rotasi, dll. Mereka juga dapat disebut sebagai transformasi. Transformasi ini disebut kode fraktal dalam hal Kompresi Fraktal.
• Data kemudian dikodekan ke fungsi transformasi tersebut. Alih-alih menyimpan data piksel-piksel, transformasi disimpan. Transformasi ini adalah aturan yang menjelaskan cara merekonstruksi gambar dari blok domain.

\ Dengan kode fraktal, gambar direkonstruksi menggunakan proses iteratif. Proses ini bisa secara komputasional mahal, tetapi kompresi fraktal dapat mencapai rasio kompresi tinggi dibandingkan dengan teknik kompresi lainnya. Karena ketergantungannya pada pola yang berulang sendiri, ini akan berkinerja lebih baik pada data yang sesuai dengan memiliki pola yang berulang sendiri seperti itu. Contohnya adalah foto lanskap (gambar alam) dan gambar DNA.

\ Ada teknik kompresi lossy lainnya, seperti Discrete Wavelet Transform, Quantization. Teknik ini biasanya digunakan dalam gambar, audio, dan file video dan cocok untuk jenis tertentu atau format file - JPEG, MP3 - untuk setiap jenis file.

\ Kompresi lossy umumnya memiliki rasio kompresi yang lebih tinggi daripada kompresi lossless dan kadang-kadang mengharapkan bahwa pengguna mengetahui jumlah kehilangan yang akan diperkenalkan sebelumnya. Penting untuk menekankan bahwa pilihan metode dan teknik kompresi tergantung pada beberapa faktor. Inti dari faktor-faktor ini adalah format data dan hasil yang diinginkan.

TL;DR

Secara keseluruhan, posting ini membahas kompresi di dunia data. Ini sangat bergantung pada badan pengetahuan yang ada dalam ilmu komputer dan teori informasi. Untuk mengompresi berarti mengurangi volume yang ditempati entitas, dan di bidang data, volume mengacu pada ruang penyimpanan. Kompresi dalam sistem digital memiliki banyak keuntungan ketika dilakukan dengan benar. Yang jelas adalah bahwa ini mengurangi ruang dan memberi ruang untuk menyimpan lebih banyak data. Keuntungan lain termasuk transmisi yang lebih cepat, penggunaan bandwidth yang lebih sedikit, dan peningkatan umum dalam efisiensi sistem tersebut. Ingat, ini ketika dilakukan dengan benar.

\ Untuk memanfaatkan keuntungan kompresi, penting untuk mengetahui jenis apa yang akan digunakan. Kompresi adalah lossy atau lossless. Kompresi lossy memperkenalkan kehilangan dalam data asli yang biasanya tidak dapat dibalik, sementara kompresi lossless mengompresi data dan mempertahankan semua informasi yang terkandung dalam data asli. Selanjutnya, ada diskusi tentang jenis kompresi hibrida, tetapi saya pikir kombinasi lossy dan lossless hanyalah lossy. Beri tahu saya apa yang Anda pikirkan di komentar.

\ Terakhir, berbagai teknik diperkenalkan untuk kompresi lossy dan lossless. Daftar teknik dan penjelasan teknik ini tidak lengkap atau komprehensif. Saya menganggapnya hanya awal yang baik dalam memberi Anda ide tentang bagaimana setiap teknik bekerja. Untuk menutup, saya telah menambahkan sumber daya tambahan untuk membantu Anda menyelidiki lebih lanjut dan membaca lebih dalam tentang kompresi dalam big data.

Sumber Daya Tambahan

Video: Data Lake fundamentals - RLE encoding with Parquet in practice

Makalah: A review of data compression techniques

Makalah: lossless compression techniques

A concise introduction to Data Compression by David Salomon

Makalah: A Study of Various Data Compression Techniques

Blog Post: Compression in open file formats

Artikel: Open file formats

Artikel: Compression in databases

Lossy Compression for Genomic data (RNA)

\