Elias Gamma & Delta Coding

Kompresi sangat bermanfaat karena kecepatan prosesor dalam melakukan encode dan decode jauh di atas kecapatan baca dan tulis dari disk ke memory. Apalagi jika kita menggunakan Single-Pass In Memory Indexing (SPIMI) dimana kita dapat melakukan kompresi pada Terms dan Postings. Berbagai metode dapat kita gunakan untuk melakukan kompresi pada Terms, sementara untuk Postings dapat kita lakukan dengan dua cara yaitu:

Storing successive docIDs, dengan kata lain menggunakan offset. Misal dari pada kita menulis <1001,1010,1052,…> kita dapat menuliskannya dengan <1001,9,42,…> dimana menghasilkan angka yang jauh lebih kecil.
Menggunakan variable size dari prefix code. Caranya adalah dengan melihat nilai maksimum dari sebaran angka, akibatnya terhindar dari pemborosan kapasitas byte tiap Posting. Nah, akan kita bahas penggunakaan variable size ini dengan kode Elias gama dan delta.

Elias Gamma Coding

Metode ini dikembangkan oleh Peter Elias. Dengan teknik pengkodean:

Tulis dalam biner
Jumlah bit pada proses no.1 dikurang satu untuk menentukan jumlah nol (zeros) yang harus ditambahkan di muka angka tersebut.

Contoh kita punya bilangan 11 langkah pertama adalah konversi 11 menjadi biner, yakni 1011. Langkah dua menghasilkan tiga yang berasal dari 4 bit dikurang satu. Hasilnya adalah 0001011. Deretan angka 11, 15, dan 27 dengan elias gamma code menjadi 00010110001111000011011.

Bagaimana dengan docede-nya? Caranya gampang, hitung jumah nol (zero) sebelum ditemukan bilangan 1, misalnya kita akan mendekode 0001011. Karena ada 3 zero maka (3+1) setelah zero itu adalah bilanganya, yaitu 1011, yang jika dikonversi ke desimal menjadi 11. Apa fungsi Elias Gamma Coding tersebut? Tentu saja manfaatnya adalah kita dapat mengirim tiga angka berjajar sekaligus, sebab jika kita hanya meng-concatenate tiga bilangan tersebut akan tidak bermakna, misalnya tiga bilangan tersebut di atas jika dikirim 1011111111011 ada berjuta2 variasi kombinasi biner tersebut yang setara dengan desimalnya.

Elias Delta Coding

Seperti Elias Gamma, kode ini ditemukan oleh Peter Elias. Kode ini menerapkan juga metode pada gamma coding, terutama di bagian kepala. Tekniknya adalah sebagai berikut:

Cari pangkat tertinggi binernya, misalnya desimal 11 jika dibinerkan menjadi 1011 dimana pangkat tertingginya adalah 3. Jadi N’=3.
Gunakan Gamma Coding untuk mengkodekan bilangan N dimana N=N’+1. Jadi untuk kasus desimal 11 maka kita harus membuat Gamma Coding dari 4 yaitu 00100.
Tambahkan sisa N’ binary pada hasil no.2. Jadi diperoleh jawaban 00100011.

Berikutnya adalah medekode Elias Delta Coding, prinsipnya adalah kebalikan dari langkah satu sampai tiga di atas. Misalnya kita akan mendekode 00100011.

Temukan jumlah zero sebelum ditemukan angka satu, yaitu 00, berjumlah dua. Berarti ada (2+1) angka yang harus diperhatikan setelah dua angka nol ini yaitu 100 yang dalam desimalnya berarti 4, jadi kita mendapatkan N’ dengan N-1 = 4-1 = 3.
Jika N’ telah diketahui, yaitu 3 maka ada tiga bit tersisa yang menjadi bagian bilangan itu yakni 011. Jadi diperoleh jawaban 1011 yang artinya 11.

Jika kita diberikan rentetan biner sebagai berikut: 00110000110011110010100111110000 merupakan deretan angka 35, 101, dan 112. (Perhatikan warna biner di atas untuk memudahkan).