Introducere în arborii Huffman

  • 7 minute de citit
  • 4 exemple de cod în Python

Disponibil și în English

Pe această pagină

Salut tuturor! 👋

Acest articol este despre arborii Huffman. Am făcut acest proiect la facultate și, după vreo zece ani, am vrut să-l reiau ca să-mi consolidez înțelegerea și să exersez codificarea manuală.

Introducere

Arborele de codificare Huffman este o structură de date fundamentală în informatică și este folosit pentru compresia fără pierderi a datelor și pentru codificarea entropică. Arborii de codificare Huffman sunt deja folosiți în ZIP, Mp3, Png pentru compresie, adesea nu singuri, ci împreună cu alți algoritmi de compresie a datelor.

Entropia reprezintă aleatorietatea datelor.

Să luăm roooar: are 6 caractere și 3 caractere unice, iar entropia este scăzută din cauza caracterelor care se repetă, ceea ce implică mai puțină incertitudine. Pentru 123456, sunt 6 caractere și 6 caractere unice, entropia este ridicată pentru că datele arată ca fiind „aleatorii”, există mai multă incertitudine.

Codificarea entropică urmărește să codifice datele cu entropie scăzută astfel încât să poată fi comprimate mai eficient. Pentru roooar ai nevoie de 6 octeți de date, dar atribuind coduri poți folosi mai puțini octeți. De exemplu, poți atribui următorii biți literelor:

Caracter Biți
r 100
o 0
a 101

Rezultatul va fi ceva de genul: 100,0,0,0,101,100, care reprezintă cuvântul roar folosind doar 12 biți, ceea ce înseamnă că ai comprimat cuvântul roooar de la 6 octeți la 2 octeți. Va trebui să completezi cei 12 biți până ajungi la 16 biți, adică doi octeți.

Dacă vrei să implementezi singur arborii Huffman, derulează până la secțiunea Referințe și consultă linkurile. În continuare îți voi arăta și discuta implementarea mea în Python.

Implementarea unui instrument de compresie

Să parcurgem un instrument în Python care comprimă datele folosind arborii de codificare Huffman. Implementarea completă poate fi găsită în conturile mele de Github și de GitLab self-hosted.

Harta frecvențelor

Primul pas este crearea unei hărți a frecvențelor: trebuie să numeri caracterele din fișierul sursă ca să determini caracterele și octeții care apar cel mai des.

În Python, poți crea o hartă a frecvențelor parcurgând octeții fișierului și numărând de câte ori apare fiecare octet.

    def _build_frequency_map(self, content: bytes) -> dict[int, int]:        """            Construiește harta frecvențelor numărând de câte ori apare fiecare octet în conținut.        :param content: Octeții conținutului sursă.        :return: Un dicționar reprezentând harta frecvențelor.        """        with utils.Timer(name="Build frequency map", logger=self._logger):            frequency_map = defaultdict(lambda: 0)            for byte in content:                frequency_map[byte] += 1            return frequency_map

Cred că această parte este destul de simplu de înțeles. Următorul pas este să folosim harta frecvențelor pentru a construi arborele.

Construirea arborelui

Arborele Huffman are două tipuri de noduri: noduri interne și noduri frunză. Pe noi ne interesează deocamdată doar nodurile frunză, iar nodurile interne le folosim ca să parcurgem arborele și să obținem codificarea finală.

Strategia este să creăm un nod frunză pentru fiecare octet și să-i atribuim o pondere egală cu frecvența sa. Apoi luăm două elemente (noduri frunză sau interne) cu ponderea cea mai mică și construim un nod intern, căruia îi atribuim ca pondere suma celor două noduri luate.

Ca să facem asta eficient, putem folosi un min heap sau o coadă de priorități minimă. Dacă vrei să rămâi simplu, poți pune toate nodurile frunză într-un array și să creezi o funcție care returnează și elimină elementul cu ponderea minimă. Folosești această funcție recursiv ca să iei câte două elemente deodată, construiești un nod intern și pui înapoi nodul intern în array. Repetând asta de multe ori, vei ajunge cu un singur element în array, care este nodul rădăcină.

În implementarea mea am folosit un min heap ca să găsesc eficient elementul minim și să construiesc arborele.

În fragmentul următor am inclus întregul cod sursă al arborelui:

import abcimport heapqimport typingfrom functools import total_orderingclass BaseTreeNode(abc.ABC):    """    Clasă abstractă de bază care modelează un arbore Huffman.    """    def __init__(self, weight: int, is_leaf: bool = False):        self._weight: int = weight        self._is_leaf: bool = is_leaf    def weight(self) -> int:        return self._weight    def is_leaf(self) -> bool:        return self._is_leaf@total_orderingclass LeafNode(BaseTreeNode):    def __init__(self, byte_element: int, weight: int):        super().__init__(weight, is_leaf=True)        self._element: int = byte_element    def value(self) -> int:        return self._element    def __lt__(self, other):        if not issubclass(other.__class__, BaseTreeNode):            return NotImplemented        return self.weight() < other.weight()class InternalNode(BaseTreeNode):    def __init__(self, left: BaseTreeNode, right: BaseTreeNode):        weight = left.weight() + right.weight()        super().__init__(weight, is_leaf=False)        self._weight = weight        self._left = left        self._right = right    def left(self):        return self._left    def right(self):        return self._right    def __lt__(self, other):        if not issubclass(other.__class__, BaseTreeNode):            return NotImplemented        return self.weight() < other.weight()    @staticmethod    def from_frequency_map(        frequency_map: dict[int, int],    ) -> typing.Optional["InternalNode"]:        """            Construiește arborele Huffman dintr-o hartă a frecvențelor dată.        :param frequency_map: Harta frecvențelor.        :return: Un nod intern reprezentând rădăcina arborelui.        """        if not frequency_map:            return None        # Creează un heap        binary_heap = []        for item in frequency_map.items():            # adaugă elementul în heap după frecvență și caracter            heapq.heappush(binary_heap, LeafNode(byte_element=item[0], weight=item[1]))        # Construiește arborele Huffman        while len(binary_heap) > 1:            left = heapq.heappop(binary_heap)            right = heapq.heappop(binary_heap)            #  nod intern după frecvență, pentru a putea fi parcurs            heapq.heappush(binary_heap, InternalNode(left, right))        return binary_heap[0]

Crearea codificărilor

Trebuie să parcurgi arborele ca să construiești tabelul de codificare sau ca să obții codificarea pentru un singur caracter. Ca să evit munca duplicată, am decis să parcurg arborele o singură dată și să construiesc tabelul de codificare dintr-o dată.

Pentru a parcurge arborele poți folosi algoritmul DFS (Depth First Search, parcurgere în adâncime). Funcționează mergând în adâncime până la fiecare nod frunză. Odată ajuns la un nod frunză, salvezi valoarea într-o hartă, împreună cu drumul parcurs ca să ajungi acolo: dacă ai mers la stânga, de obicei pui un 0, iar dacă ai mers la dreapta, poți pune un 1.

    def _build_encoding_table(self):        """        Construiește tabelul de codificare pentru Huffman folosind un algoritm DFS pe arbore.        """        with utils.Timer(name="Build encoding table", logger=self._logger):            stack = []            root = self._huffman_tree_root            stack.append([root, []])            while len(stack) > 0:                element, encoding = stack.pop()                if element.is_leaf():                    self._encoding_table[element.value()] = "".join(encoding)                else:                    if (left := element.left()) is not None:                        stack.append([left, [*encoding, "0"]])                    if (right := element.right()) is not None:                        stack.append([right, [*encoding, "1"]])

Scrierea în fișier

Scrierea în fișier este partea delicată, pentru că, după ce codifici fiecare element într-o secvență de biți, trebuie să completezi numărul final de biți astfel încât să fie divizibil cu 8, iar tu poți scrie doar 8 biți (un octet) la un moment dat. Nu poți scrie, de exemplu, 111; trebuie să scrii un octet întreg cu completare, adică 11100000. Am folosit pachetul Python bitstring ca să simplific acest proces, iar la final am adăugat completarea manual.

Pe lângă conținut, trebuie să scrii în fișier și tabelul de codificare. Acesta va fi folosit pentru decodificarea fișierului. Pentru a scrie tabelul de codificare am folosit pachetul din biblioteca standard Python pickle, dar poți folosi și o bibliotecă terță, cum ar fi msgpack, ca să convertești obiectul în formă binară. Îl poți scrie și ca un simplu șir de caractere.

Am scris tabelul de codificare la început, împreună cu lungimea sa, ca să știu că restul octeților reprezintă conținutul fișierului.

    def _get_encoded_file_contents(self, content: bytes) -> BitArray:        """            Având conținutul necodificat, îl codifică cu codurile Huffman.        :param content: Octeții conținutului brut.        :return: Octeții conținutului codificat.        """        with utils.Timer(name="Encode source file", logger=self._logger):            buffer = []            for byte in content:                buffer.append(self._encode_byte(byte))            bit_array = BitArray(bin="".join(buffer))            return bit_array    def _encode_byte(self, byte: int) -> str:        """        Codifică octetul dat folosind arborele Huffman.        """        if byte in self._encoding_table:            return self._encoding_table[byte]        raise Exception(            f"Can't encode byte {byte}. It is not found in the encoding table."        )    def encode(self, file_name: str, destination: str):        """            Codifică un fișier dat în octeți Huffman și îl scrie pe disc..        :param file_name: Calea către numele fișierului.        :param destination: Calea către numele fișierului de destinație.        """        with open(file_name, "rb") as fh:            content = fh.read()        frequency_map = self._build_frequency_map(content)        self._build_huffman_tree(frequency_map)        self._build_encoding_table()        bit_array = BitArray()        encoding_table = pickle.dumps(self._encoding_table)        # întreg fără semn de 2 octeți pentru lungimea tabelului de codificare        bit_array.append(pack("<H", len(encoding_table)))        # tabelul de codificare complet, serializat cu pickle        bit_array.append(encoding_table)        # conținutul fișierului codificat cu Huffman        encoded_content = self._get_encoded_file_contents(content)        if len(encoded_content) % 8 == 0:            encoded_content_padding_bits = 0        else:            encoded_content_padding_bits = 8 - (len(encoded_content) % 8)        bit_array.append(pack("<B", encoded_content_padding_bits))        bit_array.append(encoded_content)        self._write_to_destination_file(bit_array, destination)        self._logger.info(f"Done encoding {file_name}.")#...    def _write_to_destination_file(self, content: BitArray, destination: str):        """            Scrie octeții în fișierul de destinație.        :param content: Octeții conținutului.        :param destination: Numele fișierului de destinație.        """        with utils.Timer(name="Write to destination", logger=self._logger):            with open(destination, "wb") as fh:                content.tofile(fh)            self._logger.debug(                f"Wrote {content.len} bits to destination file: {destination}"            )

Decompresia

Decompresia fișierului este un pas simplu. Poți citi tabelul de codificare, îl poți inversa, construi o hartă și poți recupera elementele originale de acolo, apoi poți scrie octeții în fișierul de ieșire.

Concluzie

Proiectul Huffman este unul interesant: atinge algoritmi, manipulări de biți, fișiere, I/O și este folosit în multe aplicații reale, precum și în formate. Dacă încerci să comprimi un PNG cu el, nu va funcționa, pentru că comprimarea de două ori nu aduce rezultate mai bune.

Dacă vrei să-l implementezi singur, încearcă. Mai jos găsești implementarea mea în Python și câteva referințe pe care le-am folosit ca să o scriu.

Mulțumesc pentru lectură!

Referințe