O desafio da quarta edição do labs era fazer um algoritmo de compressão de Huffman que usasse operações de compartilhamento de memória para trafegar dados de um encoder para um decoder. Durante a semana de prazo para desenvolvimentos a solução criada envolveu a tradução do texto do infile.txt, codificação desse texto, compressão dele e depois descompressão e descodificação.
Principais aprendizados:
- Algoritmos de compressão
- Construção de árvore binária
- Codificação (compressão e descompressão) bit a bit
- Compartilhamento de memória entre programas
- Otimização de fluxo de código
A colaboração foi essencial nesse projeto e destaco principalmente os cadetes: ridalgo- acesar-l fnacarel etachott sguilher mameneze harndt revieira e rleite-s.
Para compilar é necessário rodar o makefile. Dois binários são gerados, encoder e decoder. Os dois devem ser sequencialmente executados.
O programa ./encoder vai pegar o conteúdo do arquivo chamado "infile.txt", gerar uma tabela de frequência (que é um array de 128 posições) e jogar essa tabela para uma função que ordena de forma crescente os elementos que apareceram na string.
Depois disso, a lista é transformada em uma árvore binária usando uma struct com ponteiros para left e right. A árvore serve para poder gerar um dicionário que dá um código único para cada caractere que aparece no texto a ser codificado. Os caracteres de maior ocorrência recebem uma sequência de zeros e uns menor e os caracteres de menor frequência recebem um código maior.
A árvore de Huffman foi criada para gerar uma codificação menor para os caracteres que têm mais ocorrência. Eles então ficam em níveis mais superiores da árvore, enquanto os caracteres de menor ocorrência ficam em níveis inferiores.
Uma outra função recebe esse código e compacta ele através da manipulação de bits, aglutinando a sequência de zeros e uns (que é o texto codificado) a cada 8 bits em um byte para poder reduzir o tamanho. O byte que é gerado muitas vezes é um símbolo aleatório (um char entre 0 e 255). Isso é o que de fato comprime a string, fazendo com que se usem menos bytes para poder escrever a mesma quantidade de informação. É importante lembrar que um dos grandes benefícios do algoritmo de Huffman é que ele foi pensado para não perder dados no processo de compactação.
A string então é enviada por memória compartilhada ao programa ./decoder. O decoder lê do segmento de memória reservado para o compartilhamento tanto a string codificada quanto o dicionário. Daí ela faz a descompressão e depois uma função itera sobre a string transformando-a de volta no texto original usando o dicionário para traduzir.
Depois de clonar o repositório, basta rodar os dois programas cada um em um terminal.
make- terminal 1
./encoder
- terminal 2
./decoder
Algoritmo de Huffman:
https://www.youtube.com/watch?v=o8UPZ_KDWdU&list=PLqJK4Oyr5WShtxF1Ch3Vq4b1Dzzb-WxbP
https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/
https://www.programiz.com/dsa/huffman-coding
https://www.youtube.com/watch?v=-TonlL3vcGk
Shared Memory Operations:
https://www.geeksforgeeks.org/ipc-shared-memory/
https://www.tutorialspoint.com/inter_process_communication/inter_process_communication_shared_memory.htm
https://www.youtube.com/watch?v=rPV6b8BUwxM
Árvore Binária:
https://www.ime.usp.br/~pf/algoritmos/aulas/bint.html
https://www.youtube.com/watch?v=z7XwVVYQRAA&list=PL8iN9FQ7_jt7LwqmdiyhVVu2J4jQQ9uRW&index=7
https://www.youtube.com/watch?v=UbhlOk7vjVY