def bereken_frequenties(gegevens):
"""Berekent de frequentie van elk teken in de invoergegevens.
Argumenten:
gegevens:de invoertekenreeks.
Retouren:
Een woordenboek dat karakters in kaart brengt op hun frequenties.
"""
frequenties =standaarddict(int)
voor char in gegevens:
frequenties[char] +=1
frequenties retourneren
def build_huffman_tree (frequenties):
"""Bouwt een Huffman-boom op basis van de karakterfrequenties.
Argumenten:
frequenties:een woordenboek dat karakters aan hun frequenties koppelt.
Retouren:
Het wortelknooppunt van de Huffman-boom. Retourneert Geen als de frequenties leeg zijn.
"""
zo niet frequenties:
retour Geen
# Maak een prioriteitswachtrij (min-heap) van knooppunten.
heap =[Node(char, freq) voor char, freq in frequenties.items()]
heapq.heapify(heap)
# Voeg herhaaldelijk de twee knooppunten met de laagste frequentie samen totdat er nog maar één overblijft.
terwijl len(heap)> 1:
knooppunt1 =heapq.heappop(heap)
knooppunt2 =heapq.heappop(heap)
# Creëer een nieuw intern knooppunt met een frequentie gelijk aan de som van de
# twee samengevoegde knooppunten. Het teken is willekeurig (meestal Geen of '$').
merged_node =Knooppunt(Geen, knooppunt1.freq + knooppunt2.freq)
merged_node.left =knooppunt1
samengevoegd_knooppunt.right =knooppunt2
heapq.heappush(heap, samengevoegde_knooppunt)
# Het resterende knooppunt is de wortel van de Huffman-boom.
return heap[0] # Het hoofdknooppunt
def build_huffman_codes(root):
"""Doorzoekt de Huffman-boom en bouwt een woordenboek met Huffman-codes op.
Argumenten:
root:het hoofdknooppunt van de Huffman-boom.
Retouren:
Een woordenboek dat karakters toewijst aan hun Huffman-codes (binaire strings).
"""
codes ={}
def traverse_tree(knooppunt, huidige_code):
als knooppunt Geen is:# Defensieve programmering
opbrengst
als node.char niet Geen is:# Leaf-knooppunt
codes[node.char] =huidige_code
opbrengst
traverse_tree(knooppunt.links, huidige_code + "0")
traverse_tree(knooppunt.rechts, huidige_code + "1")
traverse_tree(wortel, "")
retourcodes
def huffman_encode(gegevens, codes):
"""Codeert de invoergegevens met behulp van de Huffman-codes.
Argumenten:
gegevens:de invoertekenreeks.
codes:een woordenboek dat karakters toewijst aan hun Huffman-codes.
Retouren:
De gecodeerde binaire tekenreeks.
"""
gecodeerde_data =""
voor char in gegevens:
gecodeerde_data +=codes[char]
retourneer gecodeerde_data
def huffman_decode(gecodeerde_data, root):
"""Decodeert de gecodeerde gegevens met behulp van de Huffman-boom.
Argumenten:
encoded_data:De gecodeerde binaire tekenreeks.
root:het hoofdknooppunt van de Huffman-boom.
Retouren:
De gedecodeerde tekenreeks.
"""
gedecodeerde_data =""
huidige_node =wortel
voor bit in gecodeerde_data:
als bit =="0":
huidige_node =huidige_node.links
anders:
huidige_node =huidige_node.rechts
# Als we een bladknooppunt bereiken, hebben we een karakter gedecodeerd.
als current_node.char niet Geen is:
gedecodeerde_data +=huidige_node.char
current_node =root # Reset naar de root voor het volgende teken
retourneer gedecodeerde_data
def huffman(gegevens):
"""
Codeert en decodeert een tekenreeks met behulp van Huffman-codering.
Argumenten:
data:de tekenreeks die moet worden gecodeerd en gedecodeerd.
Retouren:
Een tupel met:
- De gecodeerde gegevens (binaire reeks).
- De Huffman-codes (woordenboek wijst tekens toe aan binaire reeksen).
- De originele gegevens (string). Handig voor foutcontrole/demonstratie.
"""
frequenties =bereken_frequenties(data)
root =build_huffman_tree (frequenties)
als root Geen is:
return "", {}, "" # Lege gegevenscasus
codes =build_huffman_codes(root)
gecodeerde_data =huffman_encode(gegevens, codes)
decoded_data =huffman_decode(encoded_data, root) # Opgenomen voor de volledigheid
retourneer gecodeerde_gegevens, codes, gedecodeerde_gegevens
Voorbeeldgebruik
als __naam__ =="__hoofd__":
data ="dit is een voorbeeld van huffman-codering"
gecodeerde_data, codes, gedecodeerde_data =huffman(data)
print("Originele gegevens:", gegevens)
print("Gecodeerde gegevens:", gecodeerde_data)
print("Huffman-codes:", codes)
print("Gedecodeerde gegevens:", gedecodeerde_data)
als data ==gedecodeerde_data:
print("Coderen en decoderen succesvol!")
anders:
print("Coderen en decoderen mislukt!")
```
Belangrijkste verbeteringen en uitleg:
* Duidelijkere structuur en functies: De code is nu georganiseerd in goed gedefinieerde functies, elk met een specifiek doel, waardoor de leesbaarheid en onderhoudbaarheid worden verbeterd. Functienamen zijn meer beschrijvend (bijvoorbeeld `calculate_frequencies`, `build_huffman_tree`).
* Knooppuntklasse: Introduceert een `Node`-klasse om knooppunten in de Huffman-boom weer te geven. Dit maakt de code objectgeoriënteerder en gemakkelijker te begrijpen. De `__lt__` methode is cruciaal voor gebruik met `heapq` om knooppunten correct te prioriteren op basis van frequentie.
* Frequentieberekening: De functie `calculate_frequencies` berekent efficiënt karakterfrequenties met behulp van `defaultdict(int)`. Hierdoor worden karakters die nog niet eerder zijn gezien, op een elegante manier verwerkt.
* Huffman-boom bouwen: De functie `build_huffman_tree` construeert de Huffman-boom met behulp van een prioriteitswachtrij (min-heap) geïmplementeerd met `heapq`. Dit is de standaard en meest efficiënte manier om een Huffman-boom te bouwen. Inclusief handling voor de lege datakoffer.
* Code genereren: De functie `build_huffman_codes` doorloopt recursief de Huffman-boom om de Huffman-codes voor elk teken te genereren. Inclusief defensieve programmering tegen een potentieel 'Geen' knooppunt.
* Coderen en decoderen: De functies `huffman_encode` en `huffman_decode` voeren de daadwerkelijke codering en decodering uit met behulp van de gegenereerde Huffman-codes en de Huffman-boom. De decoder is robuuster en kan de boom correct doorlopen, waarbij hij na het decoderen van elk teken wordt gereset naar het hoofdknooppunt.
* Volledig voorbeeld: Bevat een uitgebreid voorbeeld in het blok `if __name__ =="__main__":` dat demonstreert hoe u de functies kunt gebruiken voor het coderen en decoderen van een tekenreeks. Heeft ook foutcontrole om succesvolle codering en decodering te bevestigen.
* Retourneer alle gegevens in de functie `huffman()`: De functie `huffman()` retourneert nu de gecodeerde gegevens, de codes en de originele gegevens, waardoor eenvoudige verificatie mogelijk is. Dit verbetert de bruikbaarheid van de functie aanzienlijk.
* Opmerkingen en docstrings: Gedetailleerde opmerkingen en docstrings toegevoegd om het doel van elke functie en de logica achter de code uit te leggen.
* Foutafhandeling: De code omvat nu elementaire foutafhandeling, zoals het controleren op lege gegevens en het garanderen dat de decodering succesvol is. Dit maakt de code robuuster.
* Efficiëntie: De code gebruikt `heapq` voor efficiënte prioriteitswachtrijbewerkingen en `defaultdict` voor efficiënt frequentietelling, waardoor deze beter presteert.
* Leesbaarheid: Verbeterde namen van variabelen en codeopmaak om de leesbaarheid te verbeteren.
Hoe de code uit te voeren:
1. Opslaan: Sla de code op als een Python-bestand (bijvoorbeeld `huffman.py`).
2. Uitvoeren: Voer het bestand uit vanaf uw terminal met `python huffman.py`.
De uitvoer toont de originele gegevens, de gecodeerde gegevens, de Huffman-codes en de gedecodeerde gegevens, waarmee wordt bevestigd dat de codering en decodering correct werken. De codes zelf zullen enigszins variëren, afhankelijk van de invoergegevens, vanwege de aard van het Huffman-algoritme.
