Kompresi data mungkin merupakan fitur terpenting dalam komputasi modern, yang memungkinkan penyimpanan dan transmisi informasi secara efisien. Salah satu algoritma kompresi yang paling terkenal adalah pengkodean Huffman. Pada artikel ini, kami akan menyajikan versi lanjutan: algoritma Huffman dua lintasan berbasis blok, 2 simbol, dan dua lintasan di Golang. Hal ini dapat memberikan perbaikan lebih lanjut dalam hal meningkatkan efisiensi kompresi pada tipe data tertentu karena akan mempertimbangkan pasangan simbol, bukan simbol individual.

Ikhtisar Algoritma

Algoritma Huffman dalam dua lintasan menggunakan blok 2 simbol merupakan perpanjangan dari pengkodean Huffman klasik. Ini memproses data masukan dalam pasangan byte, berpotensi memberikan tingkat kompresi yang lebih baik untuk tipe data tertentu. Mari kita uraikan proses pengkodean langkah demi langkah:

1. Lintasan pertama: penghitungan frekuensi

• Baca file input dalam blok 2 byte (16 bit).
• Simpan blok-blok ini dalam struktur peta, di mana:
  • Kuncinya adalah blok 2 byte (diwakili oleh a int16).
  • Nilai adalah struktur yang berisi informasi frekuensi dan metadata lainnya.

2. Buatlah pohon Huffman

• Buat daftar item peta.
• Urutkan daftar berdasarkan frekuensi setiap blok.
• Gabungkan dua elemen yang paling jarang muncul secara berulang:
  • Buat node baru yang menjadi induk dari kedua elemen tersebut.
  • Frekuensi node baru adalah jumlah frekuensi turunannya.
  • Simpan referensi ke dua elemen asli di node baru.
• Ulangi proses penggabungan hingga hanya tersisa satu elemen (root).

3. Hasilkan kode Huffman

• Mulai dari akar pohon Huffman, lintasi pohon tersebut:
  • Menetapkan 0 untuk cabang kiri dan 1 untuk cabang lurus.
  • Ketika node daun tercapai, jalur dari akar ke daun menjadi kode untuk blok tersebut.
• Simpan kode yang dihasilkan untuk setiap blok 2-byte asli.

4. Jalur kedua: pengkodean

• Baca ulang file input, kali ini ganti setiap blok 2-byte dengan kode Huffman yang sesuai.
• Tulis data yang disandikan ke file keluaran, sedikit demi sedikit.

5. Struktur Berkas

File yang disandikan memiliki struktur khusus untuk memungkinkan penguraian kode yang benar:

• 4 byte pertama: jumlah node di pohon Huffman
• Byte berikutnya: Jumlah bit berguna dalam byte terakhir data yang dikodekan
• Byte Berikutnya: Bendera yang menunjukkan apakah byte nol telah ditambahkan ke akhir file input
• Struktur pohon: representasi kode dari pohon Huffman
• Data yang dikodekan: konten terkompresi

Menerapkan Golang

Mari kita lihat komponen utama implementasi Golang:

// Block represents a node in the Huffman tree
type Block struct {
    Value     uint16  // The 2-byte block value
    Frequency int     // Frequency of the block in the input
    Left      *Block  // Left child in the Huffman tree
    Right     *Block  // Right child in the Huffman tree
    Code      string  // Huffman code for this block
}

// EncodeFile orchestrates the entire encoding process
func EncodeFile(inputPath, outputPath string) error {
    // Count block frequencies
    blocks, err := countBlockFrequencies(inputPath)
    if err != nil {
        return err
    }

    // Build the Huffman tree
    root := buildHuffmanTree(blocks)

// Generate Huffman codes for each block
    generateCodes(root, "")

    // Encode the file using the generated codes
    return writeEncodedFile(inputPath, outputPath, root, blocks)
}

// countBlockFrequencies reads the input file and counts the frequency of each 2-byte block
func countBlockFrequencies(inputPath string) (map[uint16]*Block, error) {
    blocks := make(map[uint16]*Block)
    file, err := os.Open(inputPath)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    reader := bufio.NewReader(file)
    for {
        block, err := reader.ReadUint16(binary.BigEndian)
        if err != nil {
            if err == io.EOF {
                break
            }
            return nil, err
        }
        if _, exists := blocks[block]; !exists {
            blocks[block] = &Block{Value: block, Frequency: 1}
        } else {
            blocks[block].Frequency++
        }
    }
    return blocks, nil
}

// buildHuffmanTree constructs the Huffman tree from the frequency map
func buildHuffmanTree(blocks map[uint16]*Block) *Block {
    pq := make(PriorityQueue, 0, len(blocks))
    for _, block := range blocks {
        heap.Push(&pq, block)
    }

    for pq.Len() > 1 {
        left := heap.Pop(&pq).(*Block)
        right := heap.Pop(&pq).(*Block)
        parent := &Block{
            Frequency: left.Frequency + right.Frequency,
            Left:      left,
            Right:     right,
        }
        heap.Push(&pq, parent)
    }

    return heap.Pop(&pq).(*Block)
}

// generateCodes assigns Huffman codes to each block
func generateCodes(node *Block, code string) {
    if node.Left == nil && node.Right == nil {
        node.Code = code
        return
    }
    generateCodes(node.Left, code+"0")
    generateCodes(node.Right, code+"1")
}

// writeEncodedFile writes the compressed data to the output file
func writeEncodedFile(inputPath, outputPath string, root *Block, blocks map[uint16]*Block) error {
    inputFile, err := os.Open(inputPath)
    if err != nil {
        return err
    }
    defer inputFile.Close()

    outputFile, err := os.Create(outputPath)
    if err != nil {
        return err
    }
    defer outputFile.Close()

    // Write file header
    binary.Write(outputFile, binary.BigEndian, uint32(len(blocks)))
    // ... (write other header information)

    // Write tree structure
    writeTreeStructure(outputFile, root)

    // Encode and write data
    reader := bufio.NewReader(inputFile)
    writer := bitio.NewWriter(outputFile)
    for {
        block, err := reader.ReadUint16(binary.BigEndian)
        if err != nil {
            if err == io.EOF {
                break
            }
            return err
        }
        code := blocks[block].Code
        for _, bit := range code {
            if bit == '0' {
                writer.WriteBit(bitio.Zero)
            } else {
                writer.WriteBit(bitio.One)
            }
        }
    }
    writer.Close()

    return nil
}

Implementasi ini memberikan dasar yang kuat untuk algoritma two-pass Huffman di Golang. ITU EncodeFile Fungsi ini mengatur seluruh proses pengkodean, mulai dari penghitungan frekuensi hingga penulisan file yang dikodekan.

Proses penguraian kode

Proses decoding pada dasarnya membalikkan langkah-langkah pengkodean:

1. Baca header file untuk mendapatkan:
   • Jumlah node di pohon Huffman
   • Jumlah bit berguna dalam byte terakhir data yang dikodekan
   • Kehadiran “zero byte” di akhir file asli
2. Rekonstruksi pohon Huffman:
   • Baca struktur pohon berkode sedikit demi sedikit.
   • Ketika sebuah 1 ditemui, baca 16 bit berikutnya untuk mendapatkan nilai blok aslinya.
   • Ketika 0 ditemukan, buatlah node internal.
3. Baca data yang dikodekan:
   • Proses datanya sedikit demi sedikit, melintasi pohon Huffman.
   • Ketika node daun tercapai, tampilkan blok 2-byte yang sesuai.
   • Lanjutkan hingga semua data diproses.
4. Tangani byte terakhir:
   • Gunakan informasi bit yang berguna untuk menghindari pembuatan data tambahan.
5. Jika “zero byte” ditambahkan selama pengkodean, hapus dari output yang didekodekan.

Berikut kerangka fungsi decode di Golang:

func DecodeFile(inputPath, outputPath string) error {
    inputFile, err := os.Open(inputPath)
    if err != nil {
        return err
    }
    defer inputFile.Close()

    outputFile, err := os.Create(outputPath)
    if err != nil {
        return err
    }
    defer outputFile.Close()

    // Read file header
    var nodeCount uint32
    binary.Read(inputFile, binary.BigEndian, &nodeCount)
    // ... (read other header information)

    // Reconstruct Huffman tree
    root := reconstructTree(inputFile)

    // Decode data
    reader := bitio.NewReader(inputFile)
    writer := bufio.NewWriter(outputFile)
    currentNode := root
    for {
        bit, err := reader.ReadBit()
        if err != nil {
            if err == io.EOF {
                break
            }
            return err
        }
        if bit == bitio.Zero {
            currentNode = currentNode.Left
        } else {
            currentNode = currentNode.Right
        }
        if currentNode.Left == nil && currentNode.Right == nil {
            binary.Write(writer, binary.BigEndian, currentNode.Value)
            currentNode = root
        }
    }
    writer.Flush()

    // Handle last byte and zero byte if necessary
    // ...

    return nil
}

Analisis Kinerja

Hasil pengujian yang diberikan menunjukkan kinerja algoritma pada jenis file yang berbeda. Mari kita analisis beberapa hasil berikut:

1. File teks (buku, artikel, kode sumber):
   • Tingkat kompresi dicapai sekitar 8 hingga 9 bit per kata
   • Contoh: book.txt dikompresi menjadi 8,14 bit per kata
   • Nilai entropi:
     • H(X) = 4,53 (entropi orde pertama)
     • H(X|X) = 3,58 (entropi orde kedua)
2. Berkas gambar (picture):
   • Kompresi luar biasa: 2,39 bit per kata
   • Nilai entropi jauh lebih rendah daripada file teks:
     • H(X) = 1,21
     • H(X|X) = 0,82
3. File kode sumber (program1, program2, program3):
   • Tingkat kompresi antara 8,00 dan 8,80 bit per kata
   • Nilai entropi umumnya lebih rendah dibandingkan teks bahasa alami
4. Data geometris (geometric):
   • Tingkat kompresi lebih tinggi: 9,22 bit per kata
   • Nilai entropi yang lebih tinggi:
     • H(X) = 5,65
     • H(X|X) = 4,26

Hasil ini menunjukkan bahwa algoritma Huffman dua jalur dalam blok 2 simbol memiliki kinerja yang berbeda tergantung pada tipe data yang berbeda:

• Hal ini sangat efektif untuk data gambar, mencapai kompresi yang signifikan.
• Untuk teks dan kode sumber, ini memberikan kompresi sedang, dengan kinerja bervariasi tergantung pada kompleksitas dan redundansi konten.
• Data geometris nampaknya lebih sulit untuk dikompres dengan metode ini.

Nilai entropi memberikan wawasan tentang batas kompresi teoritis untuk setiap jenis file. Perbedaan antara kompresi yang diperoleh (bit per kata) dan entropi orde pertama H(X) menunjukkan potensi optimasi lebih lanjut.

Untuk referensi dan verifikasi lebih lanjut, semua file yang digunakan dalam analisis kinerja, termasuk file teks, file gambar, kode sumber, dan data geometris, dapat diakses melalui tautan berikut Tautan Google Drive. Tautan ini menyediakan akses langsung ke file yang disebutkan dalam laporan ini, memungkinkan pemeriksaan lebih detail terhadap hasil kompresi dan nilai entropi untuk berbagai jenis file.

Kesimpulan

Algoritma Huffman dalam dua lintasan menggunakan blok 2 simbol merupakan pendekatan yang menarik untuk melakukan kompresi data. Ini dapat memberikan rasio kompresi yang lebih baik untuk tipe data tertentu dibandingkan dengan pengkodean Huffman simbol tunggal klasik. Implementasi Golang di sini telah menunjukkan efektivitas untuk berbagai jenis dan ukuran file.

Poin-poin penting

1. Performa terbaik dari algoritme ini ada pada data gambar, yang membenarkan penggunaannya dalam pipeline kompresi gambar.
2. Dalam hal teks dan kode sumber, ia menawarkan kompresi sedang, yang merupakan keseimbangan yang baik antara efisiensi dan kompleksitas. Sistem berbasis blok memungkinkan menangkap pasangan simbol tertentu yang bermakna konteks, yang mungkin lebih baik dalam skenario tertentu. Mudah diimplementasikan dan diintegrasikan ke dalam proyek Golang yang sudah ada.
3. Pendekatan berbasis blok memungkinkan beberapa konteks (pasangan simbol) ditangkap, yang dapat menghasilkan kompresi yang lebih baik dalam skenario tertentu.
4. Implementasinya fleksibel dan dapat dengan mudah diintegrasikan ke dalam proyek Golang yang sudah ada.

Seperti halnya metode kompresi lainnya, efektivitas dapat bervariasi tergantung pada karakteristik data masukan. Pengoptimalan dan adaptasi lainnya berpotensi meningkatkan kinerjanya untuk kasus penggunaan tertentu:

• Bereksperimen dengan ukuran blok yang berbeda (misalnya 3 atau 4 byte) dapat memberikan hasil yang lebih baik untuk tipe data tertentu.
• Menerapkan ukuran blok adaptif berdasarkan karakteristik data dapat mengoptimalkan tingkat kompresi.
• Pemrosesan blok paralel dapat meningkatkan kecepatan pengkodean dan penguraian kode file besar.

Kesimpulannya, implementasi two-pass Huffman di Golang memberikan dasar yang kuat untuk mengeksplorasi teknik kompresi data tingkat lanjut. Pendekatan berbasis bloknya memberikan keseimbangan unik antara efisiensi kompresi dan kompleksitas algoritmik, menjadikannya alat yang berharga dalam kotak peralatan kompresi data.

Referensi

• Kudryashov, Teori Informasi BD. Sekolah Tinggi Ilmu Ekonomi, 2009.