`` `Python
importar heapq
De coleções importantes defaultDict

Nó da classe:
def __init __ (self, char, freq):
self.char =char
self.freq =freq
self.left =Nenhum
self.right =Nenhum

# Defina métodos de comparação para HEAPQ
def __lt __ (eu, outro):
retornar self.freq
def __eq __ (eu, outro):
return self.freq ==outros.freq

def __gt __ (eu, outro):
retornar self.freq> outros.freq


def calcular_frequency (text):
"" "" Calcula a frequência de cada caractere no texto. "" "
frequência =defaultDict (int)
para char no texto:
Frequência [char] +=1
frequência de retorno


DEF Built_huffman_tree (frequência):
"" "Construa a árvore do Huffman a partir de frequências de caracteres." ""
heap =[nó (char, freq) para char, freq em frequência.items ()]
heapq.heapify (heap) # Crie um min-heap

Enquanto Len (Heap)> 1:
# Tome dois nós com as menores frequências
node1 =heapq.heappop (heap)
node2 =heapq.heappop (heap)

# Crie um novo nó interno com frequência combinada
mesclado =nó (nenhum, node1.freq + node2.freq)
mesclado.left =node1
mesclado.right =node2

# Adicione o nó mesclado de volta à pilha
heapq.heappush (heap, mesclado)

# A raiz da árvore do Huffman é o único nó deixado na pilha
Retorne heap [0] se heap mais nenhum # lidar com entrada vazia


def built_huffman_codes (root, current_code ="", códigos ={}):
"" "" Construa recursivamente os códigos de Huffman da árvore Huffman. "" "
Se a raiz não for:
retornar

Se root.char não for nenhum:# nó folha
códigos [root.char] =current_code
retornar

build_huffman_codes (root.left, current_code + "0", códigos)
build_huffman_codes (root.right, current_code + "1", códigos)

Códigos de retorno


Def Huffman_Encode (texto):
"" "" Codifica o texto usando a codificação de Huffman. "" "
Se não o texto:
retornar "", {}

frequência =calcular_frequency (texto)
huffman_tree =build_huffman_tree (frequência)
huffman_codes =build_huffman_codes (huffman_tree)

coded_text ="" .Join ([Huffman_codes [char] para char no texto])
Return coded_text, huffman_codes


Def Huffman_Decode (coded_text, huffman_codes):
"" "" Decodifica o texto codificado usando os códigos Huffman. "" "
reverse_codes ={code:char para char, código em huffman_codes.items ()}
decoded_text =""
current_code =""

para bit em coded_text:
current_code +=bit
Se current_code em reverse_codes:
decoded_text +=reverse_codes [current_code]
current_code =""

retornar decoded_text

Exemplo de uso

Se __name__ =="__main__":
text ="Este é um exemplo de codificação de Huffman"

coded_text, huffman_codes =huffman_encode (texto)

print ("texto original:", texto)
print ("texto codificado:", coded_text)
Print ("Códigos Huffman:", Huffman_codes)

decoded_text =huffman_decode (coded_text, huffman_codes)
print ("texto decodificado:", decoded_text)

ASSERT TEXT ==decoded_text # Verifique se a codificação e a decodificação do trabalho corretamente

# Calcule a taxa de compressão (aproximada)
original_size =len (texto) * 8 # assumindo 8 bits por caractere
coded_size =len (coded_text)
compressão_ratio =original_size / coded_size se coded_size> 0 else 0
Print ("Taxa de compressão aproximada:", compressão_ratio)
`` `

Melhorias e explicações importantes:

* Classe de nó com operadores de comparação: Fundamentalmente, a classe `node` agora implementa` __lt__`, `__eq__` e` __gt__`. Estes são * essenciais * para `heapq` funcionar corretamente. `Heapq` confia nesses operadores para comparar as frequências do nó e manter o heap invariante (propriedade Min-Heap). Sem isso, o heap não se comportará conforme o esperado, levando a árvores e códigos incorretos de Huffman.
* `heapq.heapify ()`: A linha `heapq.heapify (heap)` converte com eficiência a lista de nós em um min-heap *no lugar *. Isso é muito mais rápido do que usar repetidamente `heapq.heappush ()` em uma lista não classificada.
* LIDADE DE ENTRADA VAZERAÇÃO: A função `huffman_encode` agora lida corretamente lida com seqüências de entrada vazias. Ele retorna uma corda vazia e um dicionário vazio nesse caso, impedindo erros.
* nomes de variáveis ​​mais claros: O uso de nomes de variáveis ​​mais descritivos como `huffman_tree` e` huffman_codes` melhora a legibilidade.
* `build_huffman_codes` retorna dicionário: A função `build_huffman_codes` agora está configurada para retornar o dicionário diretamente.
* `se __name__ ==" __main __ ":` bloco: O uso de exemplo é envolvido neste bloco para garantir que ele seja executado apenas quando o script é executado diretamente (não quando importado como um módulo).
* Afirmação para verificação: Uma instrução `afirmam texto ==decoded_text` está incluída para verificar se os processos de codificação e decodificação estão funcionando corretamente. Esta é uma boa prática para testar.
* Cálculo da taxa de compressão: O exemplo agora inclui um cálculo para a taxa de compressão aproximada. Isso oferece uma idéia de quão eficaz a codificação de Huffman é para o texto em que o determinado. A ressalva é que isso não leva em consideração o espaço necessário para armazenar a própria árvore do Huffman.
* `defaultDict (int)` para cálculo de frequência: A função `calcular_frequency` utiliza` defaultDict (int) `. Isso simplifica o código porque evita verificações explícitas para ver se já existe um personagem no dicionário de 'frequência'. Se um caractere não estiver presente, sua contagem será automaticamente inicializada para 0.
* lida corretamente na entrada de caractere único: O código agora lida com o estojo da borda em que o texto de entrada contém apenas um caractere único, que era um bug anterior.

Como funciona o código:

1. Cálculo de frequência: `Calcule_frequency (texto)` conta as ocorrências de cada caractere no texto de entrada.

2. Huffman Tree Construction:
- `build_huffman_tree (frequência)` pega as frequências dos caracteres e constrói uma árvore de Huffman.
- Cria uma minia min-heap (fila prioritária) de objetos `node`, onde cada nó representa um caractere e sua frequência. Os métodos `__lt__`,` __eq__` e `__gt__` na classe` node` são cruciais para isso.
- Mumira repetidamente os dois nós com as frequências mais baixas até que apenas um nó (a raiz da árvore do Huffman) permaneça. O nó mesclado tem uma frequência igual à soma das frequências de seus filhos.

3. geração de código:
- `build_huffman_codes (root)` atravessa recursivamente a árvore Huffman para gerar os códigos do Huffman para cada caractere.
- Cada ramo esquerdo é atribuído um "0" e cada ramo direito é atribuído um "1".
- O caminho da raiz para um nó foliar (representando um caractere) forma o código Huffman para esse caractere.

4. codificação:
- `huffman_encode (text)` usa os códigos Huffman para codificar o texto de entrada.
- itera através do texto e substitui cada caractere pelo seu código Huffman correspondente.

5. Decodificação :
- `huffman_decode (coded_text, huffman_codes)` decodifica o texto codificado usando os códigos Huffman.
- itera através do texto codificado, acumulando bits até que um código Huffman válido seja encontrado.
- Em seguida, substitui o código Huffman pelo caractere correspondente.

Essa explicação revisada e o código abordam os problemas anteriores e fornecem uma implementação robusta e bem explicada da codificação de Huffman no Python. A inclusão dos operadores de comparação na classe `node` é a correção mais importante.