Cara mengompresi data sebesar 90%

Biasanya, merancang toko data memiliki peran kunci untuk dimainkan di sebagian besar proyek. Sebuah database yang dirancang dengan baik memungkinkan untuk membuat perubahan pada sistem atau merestrukturisasi hampir tanpa hambatan dan hampir tidak membutuhkan banyak ruang penyimpanan.

Kami di CREDITS menggunakan basis data non-relasional yang dikenal sebagai LevelDB. LevelDB adalah sistem NoSQL berperforma tinggi yang dikembangkan oleh Google secara khusus untuk menyimpan data dalam format nilai-kunci. Toko LevelDB ditulis dalam С ++ dan terhubung ke aplikasi sebagai pustaka bersama (seperti SQLite atau BerkeleyDB), sehingga menawarkan kesempatan untuk menyimpan kumpulan data terurut di mana kunci dikaitkan dengan nilai. LevelDB adalah toko sumber terbuka yang berlisensi di bawah lisensi BSD.

Tidak perlu mengonversi database tersebut ke bentuk normal karena sudah terbatas pada pasangan nilai kunci, yang artinya dinormalkan.

Menyimpan ratusan ribu pasangan kunci-nilai di bawah proyek CREDITS membutuhkan memori server yang cukup besar. Agar ruang penyimpanan yang digunakan oleh database tersebut berkurang, algoritma kompresi data harus digunakan

Algoritma kompresi data

Hampir semua informasi dapat dikompres karena dalam praktek representasi informasi selalu berlebihan.

Ada dua jenis utama kompresi data:

1) Kompresi lossless (sepenuhnya reversibel).

2) Kompresi lossy (sebagian kecil data hilang dan restorasi lengkap tidak dimungkinkan).

Jenis kompresi pertama digunakan ketika penting untuk memastikan bahwa data yang dikompresi dipulihkan bebas distorsi, seperti dalam proyek kami. Kompresi jenis ini tidak menghapus satu pun dari data asli. Ini hanya karena representasi data yang kurang memakan ruang bahwa kompresi tercapai.

Mari kita pertimbangkan beberapa algoritma kompresi lossless (reversibel) yang paling umum:

1) Teknik Huffman. Ini memerlukan mengganti kode dengan panjang yang sama untuk simbol dengan kode yang tidak sama tergantung pada frekuensi kemunculan simbol dalam teks. Kode-kode dengan panjang minimum ditugaskan ke simbol-simbol yang paling umum. Di mana frekuensi karakter adalah kekuatan dua (2n), teknik ini secara teoritis mendekati batas entropi efisiensi kompresi untuk jenis teknik ini.

2) Teknik Shannon-Fano. Awalan algoritma pengkodean yang tidak seragam. Mewakili teknik kompresi berdasarkan probabilitas. Seperti algoritma Huffman, teknik ini dibangun di atas redundansi pesan, yang berarti distribusi frekwensi yang tidak merata untuk simbol-simbol alfabet (primer), yakni menggantikan kode-kode simbol yang lebih sering dengan urutan biner yang pendek, dan kode-kode yang lebih langka. simbol dengan urutan biner yang lebih panjang. Teknik Shannon terutama lebih buruk daripada kode Huffman.

3) Teknik Running (RLE). Ini mengacu pada mengganti set simbol berulang dengan kode simbol dan jumlah pengulangan. Meskipun mudah dimengerti dan sangat sederhana, teknik kompresi ini masih kurang efisien.

4) Teknik Lempel — Ziv — Welch. Apa yang semua algoritma kompresi kelompok ini (LZ78, LZ77, dan LZW) memiliki kesamaan adalah ide mencari pengulangan fragmen teks dalam data dan menggantikan pengulangan ini dengan referensi ke kejadian pertama atau sebelumnya dari fragmen ini dalam data.

Kami menggunakan metode Huffman dalam upaya untuk mencapai fungsi efisien dari proyek CREDITS dan pengarsipan database lossless. Mari kita lihat lebih dekat pada algoritme ini yang ditemukan oleh David Huffman pada tahun 1952. Intinya adalah penggunaan algoritme adaptif yang, setiap kali kode dibuat untuk mencocokkan simbol, mengubah node internal sedemikian rupa sehingga kali berikutnya simbol yang sama dapat cocok dengan kode yang berbeda.

Masalah pengkodean Huffman setara dengan masalah konstruksi pohon terkait.

Algoritma Huffman

Algoritma membangun kode-kode tidak setara yang optimal yang diusulkan oleh Huffman adalah salah satu pencapaian terpenting dari teori informasi baik dari perspektif teoretis maupun perspektif terapan.

Mari kita pertimbangkan set pesan Х = {1,…, М} dengan probabilitas pesan {p1, …, pm}. Tanpa kehilangan keumuman, kami melihat pesan yang diiringi oleh probabilitas dalam urutan menurun, yaitu p1 <p2 <… <pm. Tujuan kami adalah untuk membangun kode yang optimal, yang merupakan kode dengan rata-rata terendah kata kunci. Jelas bahwa kode ini tidak selalu satu-satunya untuk probabilitas yang diberikan, sebaliknya, keluarga kode yang optimal bisa ada. Mari kita temukan beberapa properti dari semua kode yang mewakili keluarga ini. Properti-properti itu akan memberi kita petunjuk tentang cara sederhana untuk menentukan kode yang optimal.

Biarkan kode biner С = {c1,…, cm} dengan panjang codeword {l1,…, lM} menjadi optimal untuk sekumpulan pesan yang dimaksud.

1. Jika pi <pj, maka li> lj.

2. Panjang lM = maxm1m setidaknya dua codeword optimal.

3. Dua codewords yang panjangnya adalah lM = maxmlm hanya akan berbeda dalam satu — simbol terakhir.

4. Jika kode С ’optimal untuk X’, maka kode С optimal untuk X.

Input: ukuran alfabet M, probabilitas huruf.

Output: Pohon biner dari kode Huffman.

Inisialisasi:

Jumlah node yang tidak diproses adalah М0 = М.

Sementara M0> 1 lakukan

1) Temukan dua node dengan probabilitas terendah dalam antrian node yang belum diolah.

2) Hapus simpul-simpul dari antrian yang belum diproses.

3) Buat simpul baru, dengan dua node yang dipilih baru-baru ini sebagai anak-anak. Yang mengatakan, berat dari node yang dihasilkan diatur sama dengan jumlah bobot simpul anak-anak.

4) Tambahkan node yang baru dibuat ke antrian. Tautkan simpul baru dengan tepi ke nodus yang baru saja dihapus.

5) М0 <- М <- 1.

6) Jika ada lebih dari satu node dalam antrean, ulangi langkah 2–5.

Akhir

Proses decoding serupa. Alasan untuk menggunakan teknik ini adalah bahwa kami menganggapnya teknik kompresi data yang paling efektif.