Wikiszótár

Huffman-kódolás

Magyar

Kiejtés

  • IPA: [ ˈhufmɒŋkoːdolaːʃ]

Főnév

Huffman-kódolás

  1. (matematika, algoritmusok)

A Huffman-kódolás egy veszteségmentes adatkompressziós technika, amelyet David A. Huffman fejlesztett ki. A módszer az egyes szimbólumok előfordulási gyakoriságán alapuló bináris kódokat rendel az adatokhoz, a gyakoribb szimbólumok rövidebb kódot kapnak, míg a ritkább szimbólumok hosszabbat.


Elméleti leírás

A Huffman-kódolás alapvető lépései: 1. Gyakoriság meghatározása: Határozzuk meg minden szimbólum gyakoriságát az adott adatfolyamban. 2. Prioritási sorrend: Készítsünk egy prioritási sort a szimbólumok gyakoriságának megfelelően (általában egy prioritási sor vagy verem formájában). 3. Faépítés: - Minden szimbólumot egy levélcsomópontként kezelünk. - A két legkisebb gyakoriságú csomópontot összevonjuk, és új belső csomópontot hozunk létre, amelynek a súlya az összevont csomópontok súlyainak összege. - Addig ismételjük az összevonást, amíg egyetlen gyökércsomópont nem marad. 4. Kód hozzárendelése: A létrejött fán keresztül minden szimbólumhoz hozzárendeljük a bináris kódját: - Balra haladva 0, jobbra haladva 1. 5. Kódolt adat előállítása: Az eredeti adatot az így generált bináris kódokkal helyettesítjük.


Példa

Tegyük fel, hogy a következő karaktereket szeretnénk kódolni a megadott gyakorisággal: - a: 5, b: 9, c: 12, d: 13, e: 16, f: 45

Faépítés lépései:

  1. Kezdeti sorrend:
    • a(5), b(9), c(12), d(13), e(16), f(45)
  2. Összevonjuk a(5) és b(9) csomópontokat: ab(14)
  3. Sorrend: c(12), d(13), ab(14), e(16), f(45)
  4. Összevonjuk c(12) és d(13): cd(25)
  5. Sorrend: ab(14), e(16), cd(25), f(45)
  6. Összevonjuk ab(14) és e(16): abe(30)
  7. Sorrend: cd(25), abe(30), f(45)
  8. Összevonjuk cd(25) és abe(30): cdeab(55)
  9. Összevonjuk cdeab(55) és f(45): gyökér(100)

Bináris kód hozzárendelése:

A fa bejárása után az alábbi kódokat kapjuk: - f: 0 - c: 100 - d: 101 - a: 1100 - b: 1101 - e: 111


Pszeudokód

függvény HuffmanKodolás(szimbólumok, gyakoriságok):
    Hozz létre egy prioritási sort, ahol minden szimbólum egy levélcsomópont a gyakoriságával.

    amíg egynél több csomópont van a prioritási sorban:
        Vedd ki a két legkisebb gyakoriságú csomópontot.
        Hozz létre egy új belső csomópontot ezekkel a csomópontokkal gyerekként,
        az új csomópont gyakorisága legyen a két csomópont gyakoriságának összege.
        Tedd be az új csomópontot a prioritási sorba.

    Az utolsó megmaradt csomópont lesz a Huffman-fa gyökere.
    Járd be a fát, hogy bináris kódokat rendelj minden szimbólumhoz.

Python implementáció

import heapq

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq


def huffman_coding(char_freq):
    heap = [Node(char, freq) for char, freq in char_freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    root = heap[0]
    codes = {}
    generate_codes(root, "", codes)
    return codes


def generate_codes(node, current_code, codes):
    if node is None:
        return
    if node.char is not None:
        codes[node.char] = current_code
        return
    generate_codes(node.left, current_code + "0", codes)
    generate_codes(node.right, current_code + "1", codes)


# Példa használat
char_freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
codes = huffman_coding(char_freq)
print("Huffman-kódok:", codes)

C++ implementáció

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

void generateCodes(Node* root, string code, unordered_map<char, string>& codes) {
    if (!root)
        return;

    if (root->ch != '\0')
        codes[root->ch] = code;

    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

unordered_map<char, string> huffmanCoding(const unordered_map<char, int>& charFreq) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    for (auto& pair : charFreq) {
        pq.push(new Node(pair.first, pair.second));
    }

    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();

        Node* merged = new Node('\0', left->freq + right->freq);
        merged->left = left;
        merged->right = right;

        pq.push(merged);
    }

    Node* root = pq.top();
    unordered_map<char, string> codes;
    generateCodes(root, "", codes);
    return codes;
}

int main() {
    unordered_map<char, int> charFreq = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};
    unordered_map<char, string> codes = huffmanCoding(charFreq);

    cout << "Huffman-kódok:" << endl;
    for (auto& pair : codes) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Összegzés

A Huffman-kódolás hatékony módszer az adatok tömörítésére, különösen szövegfájlok esetén, ahol egyes karakterek gyakrabban fordulnak elő, mint mások. Az algoritmus garantáltan optimális, ha az előfordulási gyakoriságok ismertek.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Huffman-kódolás&oldid=3479827”