Implementando a Codificação Huffman para Compactação de Dados usando Rust

Foto de Markus Spiske no Unsplash

No vasto cenário da programação, um dos desafios mais empolgantes que os desenvolvedores encontram é trabalhar com algoritmos de compressão de dados. Esses algoritmos servem a um propósito inestimável: eles nos permitem armazenar e transmitir dados de forma mais eficiente, uma necessidade em nosso mundo cada vez mais orientado por dados. Dentre a miríade de algoritmos de compressão de dados, o algoritmo de Huffman tem se mostrado um método eficaz e amplamente utilizado. Esse algoritmo, baseado no conceito de usar representações de código mais curtas para entradas que ocorrem com frequência, tem sido a base de muitos sistemas de compactação de arquivos.

Neste post, vamos nos aprofundar nos detalhes da implementação do Algoritmo de Compressão Huffman, mas com uma reviravolta intrigante – usaremos Rust, uma linguagem de programação que vem ganhando força por sua ênfase em desempenho, segurança de memória e simultaneidade.

Rust, com suas impressionantes garantias de velocidade e segurança, se presta perfeitamente às rigorosas exigências de implementar um algoritmo de compressão como o de Huffman. Se você é um Rustacean experiente ou um programador curioso procurando expandir seus horizontes, este post promete ser uma jornada informativa. Vamos detalhar as complexidades do algoritmo de Huffman, explicar as nuances de implementá-lo em Rust e oferecer orientação passo a passo para garantir que você possa acompanhar.

Então aperte o cinto, pois nos propusemos a explorar a implementação do Algoritmo de Compressão de Huffman usando Rust. Ao final deste post, você terá adquirido uma compreensão mais profunda das técnicas de compressão de dados e dos recursos robustos do Rust e, com sorte, estará equipado para enfrentar desafios de programação semelhantes em seus empreendimentos futuros.

Codificação Huffman

Esse algoritmo opera atribuindo códigos mais curtos a bytes que ocorrem com frequência e códigos mais longos àqueles que aparecem com menos frequência. A noção de codificação não é nova. Para garantir uma compreensão robusta dos benefícios derivados do algoritmo Huffman, falaremos sobre dois modos de codificação:

Codificação de largura fixa

Esse é um tipo de codificação em que o código atribuído a bytes de um fluxo de entrada tem uma largura fixa. Digamos que precisamos codificar a string abbcdeef . Há 6 caracteres nela, então precisaríamos de uma largura de código de pelo menos 3 bits para codificar essa string por caractere, já que a representação de bits de 6 é 110.

Podemos atribuir arbitrariamente códigos para esses caracteres com a largura em mente, conforme abaixo:
a — 000, b — 001, c — 010, d — 011, e — 100, f — 101
Usando a tabela de código acima, agora podemos compactar essa cadeia de caracteres e ela ficará assim:

000001001010011100100101

Bem, isso é decepcionantemente mais longo do que a nossa string original, não é? Então por que alguém acha que isso é uma "compressão" por qualquer métrica? Bem, em primeiro lugar, essa nova string é composta de apenas 1's e 0's, o que significa que podemos representar essa string como um grupo de bits, então trate essa saída como um número binário e não uma string. Isso significaria que precisamos de 24 bits para armazenar os dados codificados acima. Comparando isso com a string não codificada anterior àquela (abbcdeef) que armazena cada caractere usando um byte (8 bits), precisaríamos de 64 bits para armazenar os dados não codificados, já que havia mapeamento de código para caractere.

Codificação de largura variável

Esse é um tipo de codificação em que o código atribuído aos bytes de um fluxo de entrada não tem uma largura fixa. Essa codificação é boa porque ajuda a reduzir a quantidade de bits que precisam ser usados para armazenar dados codificados no final. No entanto, tem suas desvantagens. Ele introduz complexidade no processo de codificação porque temos que evitar choques entre códigos de bytes diferentes e evitar prefixos enganosos. Vamos a um exemplo.

a — 0, b — 1, c — 10, d — 11, e — 100, f — 101

Com a seguinte tabela de código acima, vamos codificar o fluxo fa. Isso retornaria 1010. Então, vamos tentar decodificar isso de volta para a string original:
Não deve demorar muito para notar que a saída decodificada é ambígua, porque podemos obter várias saídas diferentes da mesma entrada:

baba,cba ,cc ,fa todos podem ser decodificados de 1010 usando essa tabela de códigos. Assim, o problema mais importante dessa forma de codificação é encontrar uma tabela de códigos que evite conflitos devido a prefixos, eliminando assim qualquer ambiguidade. Este é o propósito da codificação de Huffman. Ele faz esse trabalho excepcionalmente bem, fazendo duas coisas:
Construção de um byte para mapeamento de código de forma que não haja conflitos de prefixo entre quaisquer dois códigos, reduzindo a quantidade de bits necessários para representar os dados.
Atribuição de códigos mais curtos a bytes que ocorrem com mais frequência e códigos mais longos a bytes que ocorrem com menos frequência.

Vamos examinar o algoritmo da codificação huffman!

O algoritmo

A primeira coisa que queremos fazer é criar uma tabela de frequência para nossos dados para determinar quantas vezes cada byte exclusivo ocorre no fluxo. Isso nos ajudará a determinar quais bytes são mais frequentes do que outros.
Em seguida, usando essa tabela de frequência, criamos uma árvore binária na qual os bytes que ocorrem com mais frequência estão mais próximos da raiz e os bytes que ocorrem com menos frequência estão mais longe da raiz. Assim, em uma cadeia como aaaabbbccd a seria o mais próximo, enquanto d seria o mais distante em relação à raiz da árvore binária. Para alcançar este arranjo, nós:

Escolha as duas entidades menos frequentes.

Crie uma nova subárvore a partir desses nós onde a frequência do nó pai é a soma da frequência de seus filhos
Adicione essa nova subárvore à lista de entidades e remova as outras duas.
Vá para a etapa 1 e continue até que reste apenas uma entidade.
Ok, vamos analisar isso em termos de código. Sinta-se à vontade para clonar o código-fonte do [Github[(https://github.com/iambenkay/huffman) (recomendado) ou siga esta postagem no blog e copie os exemplos de código.
A estrutura de pastas tem esta aparência:

Eu defini essa estrutura para representar um nó de nossa árvore binária em huffman.rs:

#[derive(Debug)]
pub struct HuffmanNode {
    freq: usize,
    byte: Option<u8>,
    left: Option<Box<HuffmanNode>>,
    right: Option<Box<HuffmanNode>>,
}

Foram definidos os seguintes tipos para tratar erros de forma idiomática:

pub type Result<T> = std::result::Result<T, Error>;

#[derive(Debug)]
pub enum Error {
    HuffTreeErr,
    Message(String),
}

impl Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::HuffTreeErr => write!(f, "Falha ao criar a árvore de Huffman"),
            Self::Message(msg) => msg.fmt(f),
        }
    }
}

impl From<std::io::Error> for Error {
    fn from(value: std::io::Error) -> Self {
        Error::Message(value.to_string())
    }
}

impl From<bitmanip::Error> for Error {
    fn from(value: bitmanip::Error) -> Self {
        match value {
            bitmanip::Error::NotValid => Error::Message("String de bits inválida".into())
        }
    }
}

Eu defini essa função auxiliar para criar nós facilmente:

fn new_node(byte: Option<u8>, freq: usize) -> Box<HuffmanNode> {
    Box::new(
        HuffmanNode {
            byte,
            freq,
            left: None,
            right: None,
        }
    )

Em seguida, uma função para contar os bytes exclusivos, conforme discutido no algoritmo. Fazemos isso em um buffer para não usar muita memória:

fn count_unique_bytes(mut reader: impl Read + Seek) -> Result<HashMap<u8, usize>> {
    let mut freq_map: HashMap<u8, usize> = HashMap::new();

    let mut buffer: [u8; 65536] = [0; 65536];

    loop {
        let bytes_read = reader.read(&mut buffer)?;
        if bytes_read == 0 {
            break;
        }
        for byt in buffer.iter().take(bytes_read) {
            let count = freq_map.entry(*byt).or_insert(0);
            *count += 1;
        }
    }

    reader.seek(SeekFrom::Start(0))?;

    Ok(freq_map)
}

Em seguida, temos que criar uma árvore binária:

fn create_huffman_tree(mut reader: impl Read + Seek) -> Result<Box<HuffmanNode>> {
    let freq_map = count_unique_bytes(&mut reader)?;

    let mut nodes: Vec<Box<HuffmanNode>> = freq_map
        .iter()
        .map(|(ch, freq)| new_node(Some(*ch), *freq))
        .collect();

    while nodes.len() > 1 {
        nodes.sort_by(|a, b| b.freq.cmp(&a.freq));
        let a = nodes.pop().ok_or(Error::HuffTreeErr)?;
        let b = nodes.pop().ok_or(Error::HuffTreeErr)?;

        let mut node = new_node(None, a.freq + b.freq);
        node.left = Some(a);
        node.right = Some(b);
        nodes.push(node);
    }

    let root = nodes.pop().ok_or(Error::HuffTreeErr)?;

    Ok(root)
}

Esse código executa um loop que classifica os itens em frequência decrescente, de modo que os elementos mais frequentes venham primeiro e os elementos menos frequentes venham por último no array. Em seguida, ele remove os dois elementos menos frequentes e cria uma subárvore a partir deles. Em seguida, adiciona a subárvore de volta ao array. Isso continua até que haja apenas um elemento no array antes de encerrar o loop.

Em seguida, precisamos de outra função para criar a tabela de códigos de Huffman a partir da árvore binária:

fn assign_huffman_codes(node: Box<HuffmanNode>, h: &mut HashMap<u8, String>, s: String) {
    if let Some(ch) = node.byte {
        h.insert(ch, s);
    } else {
        if let Some(left) = node.left {
            assign_huffman_codes(left, h, s.clone() + "0");
        }
        if let Some(right) = node.right {
            assign_huffman_codes(right, h, s + "1");
        }
    }
}

Nessa função, estamos atribuindo 0 a todos os ramos da esquerda e 1 a todos os ramos da direita. Ao percorrer recursivamente a árvore a partir da raiz, chegaremos a uma cadeia de bits que representa cada caractere, na qual não há conflito de prefixos entre dois códigos.

Escrevi um pequeno módulo para manipulação de bits e o chamei simplesmente de bitmanip.rs. Usei esse módulo para converter uma string de bits (string que contém apenas 0s e 1s) em um array de bytes e vice-versa:

use std::cmp::min;

#[derive(Debug)]
pub enum Error {
    NotValid
}

pub type Result<T> = std::result::Result<T, Error>;

pub fn bytes_to_bit_str(bytes: Vec<u8>) -> String {
    let mut bits = String::new();


    for byte  in bytes {
        let bin_repr = format!("{:b}", byte);
        bits.push_str(&bin_repr.replace("0b", ""));
    }
    bits
}

pub fn bit_str_to_bytes(bits: &str) -> Result<Vec<u8>> {
    let mut bytes: Vec<u8> = Vec::new();

    let mut i = 0;

    while i < bits.len() {
        let bin_str = &bits[i..min(i + 8, bits.len())];
        let byte = u8::from_str_radix(bin_str, 2).map_err(|_| Error::NotValid)?;
        bytes.push(byte);
        i += 8;
    }

    Ok(bytes)
}

Em seguida, a função final que reúne tudo isso:

pub fn compress_data(mut reader: impl Read + Seek, mut writer: impl Write) -> Result<()> {
    let tree_root = create_huffman_tree(&mut reader)?;

    let mut huffman_code_table: HashMap<u8, String> = HashMap::new();

    assign_huffman_codes(tree_root, &mut huffman_code_table, "".to_string());

    let mut buffer: [u8; 65536] = [0; 65536];

    loop {
        let bytes_read = reader.read(&mut buffer)?;

        if bytes_read == 0 {
            break;
        }

        let mut compressed_segment = String::new();

        for byte in buffer {
            compressed_segment.push_str(&huffman_code_table[&byte]);
        }

        let compressed_bytes = bitmanip::bit_str_to_bytes(&compressed_segment)?;

        writer.write_all(&compressed_bytes)?;
    }

    Ok(())
}

E, por fim, uma função principal para executar nosso código:

use std::fs::{File};
use std::io::{BufReader, BufWriter};
use std::io;
use huffman::huffman;

fn main() {
    let mut reader = file_reader("data/S.csv").unwrap();
    let mut writer = file_writer("data/S.csv.huff").unwrap();

    huffman::compress_data(&mut reader, &mut writer).unwrap();
}

fn file_reader(filename: &str) -> io::Result<BufReader<File>> {
    let file = File::open(filename)?;
    let reader = BufReader::new(file);
    Ok(reader)
}

fn file_writer(filename: &str) -> io::Result<BufWriter<File>> {
    let file = File::create(filename)?;
    let writer = BufWriter::new(file);
    Ok(writer)
}

Este artigo foi escrito por Benjamin Chibuzor-Orie e traduzido para o português por Rafael Ojeda

Você pode ler o artigo original em inglês aqui