Fannon_Hufman

Prévia do material em texto

<p>Apresentação: Codificação de Shannon-Fano e Huffman em Python</p><p>CONTEXTUALIZAÇÃO</p><p>Ao falarmos de compressão de dados, um dos conceitos mais importantes é a</p><p>codificação de fontes, onde o objetivo é reduzir a quantidade de dados necessários</p><p>para representar uma informação. Duas técnicas clássicas de codificação que</p><p>exemplificam essa abordagem são a Codificação de Shannon-Fano e a Codificação</p><p>de Huffman. Ambas tentam atribuir códigos mais curtos aos símbolos mais frequentes</p><p>e códigos mais longos aos menos frequentes, buscando assim uma compressão</p><p>eficiente. As condificações são explicadas abaixo:</p><p>Codificação de Shannon-Fano:</p><p>• Objetivo: Criar um código binário para cada símbolo, onde os símbolos mais</p><p>frequentes recebem códigos mais curtos.</p><p>• Método:</p><p>1. Os símbolos são ordenados com base em suas probabilidades.</p><p>2. A lista é dividida em dois subconjuntos cujas probabilidades somadas</p><p>sejam o mais próximo possível.</p><p>3. Um '0' é atribuído ao primeiro subconjunto e um '1' ao segundo.</p><p>4. O processo é repetido recursivamente para cada subconjunto até que</p><p>todos os símbolos sejam codificados.</p><p>Codificação de Huffman:</p><p>• Objetivo: Utilizar uma árvore binária para atribuir códigos de comprimento</p><p>variável a cada símbolo, garantindo que nenhum código seja prefixo de outro</p><p>(propriedade de prefixo).</p><p>• Método:</p><p>1. Cada símbolo começa como um nó folha em uma floresta de árvores.</p><p>2. Os dois nós de menor probabilidade são unidos para formar um novo nó</p><p>cuja probabilidade é a soma das duas.</p><p>3. Esse processo se repete até que reste apenas uma árvore, que será a</p><p>árvore de Huffman.</p><p>4. O caminho da raiz até cada folha define o código binário para cada</p><p>símbolo.</p><p>CODIFICAÇÃO</p><p>Foi escrito um código em python abordando ambas as funções. O usuário entra</p><p>com os símbolos separados por espaçamento simples e em seguida com as</p><p>probabilidade em espaçamento simples, e o programa dá a saída em ambos os</p><p>códigos. A quantidade de entrada de símbolos deve ser igual ao das probabilidades,</p><p>ou o programa retornará um erro.</p><p>================================================================</p><p>import heapq</p><p># Função de Shannon-Fano</p><p>def shannon_fano(symbols, probabilities):</p><p>def shannon_fano_recursive(symbols, probabilities):</p><p>if len(symbols) == 1:</p><p>return {symbols[0]: ""}</p><p>total = sum(probabilities)</p><p>cumulative = 0</p><p>split_point = 0</p><p>for i in range(len(probabilities)):</p><p>cumulative += probabilities[i]</p><p>if cumulative >= total / 2:</p><p>if abs(cumulative - total / 2) > abs((cumulative - probabilities[i]) - total / 2):</p><p>split_point = i - 1</p><p>else:</p><p>split_point = i</p><p>break</p><p>left_symbols = symbols[:split_point + 1]</p><p>right_symbols = symbols[split_point + 1:]</p><p>left_probs = probabilities[:split_point + 1]</p><p>right_probs = probabilities[split_point + 1:]</p><p>left_code = shannon_fano_recursive(left_symbols, left_probs)</p><p>right_code = shannon_fano_recursive(right_symbols, right_probs)</p><p>code = {}</p><p>for symbol in left_code:</p><p>code[symbol] = "0" + left_code[symbol]</p><p>for symbol in right_code:</p><p>code[symbol] = "1" + right_code[symbol]</p><p>return code</p><p># Ordenar os símbolos com base nas probabilidades</p><p>combined = sorted(zip(symbols, probabilities), key=lambda x: x[1], reverse=True)</p><p>symbols, probabilities = zip(*combined)</p><p>return shannon_fano_recursive(list(symbols), list(probabilities))</p><p># Função de Huffman</p><p>def huffman(symbols, probabilities):</p><p>heap = [[weight, [symbol, ""]] for symbol, weight in zip(symbols, probabilities)]</p><p>heapq.heapify(heap)</p><p>while len(heap) > 1:</p><p>lo = heapq.heappop(heap)</p><p>hi = heapq.heappop(heap)</p><p>for pair in lo[1:]:</p><p>pair[1] = '0' + pair[1]</p><p>for pair in hi[1:]:</p><p>pair[1] = '1' + pair[1]</p><p>heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])</p><p>huffman_code = sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))</p><p>return {symbol: code for symbol, code in huffman_code}</p><p># Entrada do usuário</p><p>symbols = input("Digite os símbolos separados por espaço: ").split()</p><p>probabilities = list(map(float, input("Digite as probabilidades correspondentes separadas por espaço:</p><p>").split()))</p><p># Verificar se o número de símbolos é igual ao número de probabilidades</p><p>if len(symbols) != len(probabilities):</p><p>print("Erro: o número de símbolos deve ser igual ao número de probabilidades.")</p><p>else:</p><p># Codificação Shannon-Fano</p><p>shannon_fano_code = shannon_fano(symbols, probabilities)</p><p>print("\nCodificação Shannon-Fano:")</p><p>for symbol in shannon_fano_code:</p><p>print(f"Símbolo: {symbol} - Código: {shannon_fano_code[symbol]}")</p><p># Codificação Huffman</p><p>huffman_code = huffman(symbols, probabilities)</p><p>print("\nCodificação Huffman:")</p><p>for symbol in huffman_code:</p><p>print(f"Símbolo: {symbol} - Código: {huffman_code[symbol]}")</p><p>Entrada de Dados:</p><p>• Símbolos e Probabilidades: O programa começa solicitando ao usuário uma lista de símbolos</p><p>e suas respectivas probabilidades.</p><p>Verificação:</p><p>• Verifica-se se o número de símbolos corresponde ao número de probabilidades.</p><p>Codificação Shannon-Fano:</p><p>• Recursividade: A função shannon_fano_recursive é chamada recursivamente para dividir os</p><p>símbolos e associar os códigos.</p><p>• Divisão por Probabilidade: A lista é dividida em dois subconjuntos com probabilidades totais</p><p>próximas, e códigos binários são atribuídos.</p><p>Codificação Huffman:</p><p>• Heap: A função huffman usa uma heap (fila de prioridades) para construir a árvore de Huffman.</p><p>• Construção da Árvore: Os símbolos são agrupados em nós com as menores probabilidades</p><p>e uma árvore binária é construída.</p><p>• Atribuição de Códigos: Códigos binários são atribuídos a partir do percurso da raiz da árvore</p><p>até os nós folhas.</p><p>Saída de Dados:</p><p>• As codificações de Shannon-Fano e Huffman para cada símbolo são exibidas ao usuário.</p><p>EXEMPLO DE ENTRADA E SAÍDA</p>