Przeczytaj

Już wiesz

W roku 1952 David Huffman opracował prefiksową metodę kompresji bezstratnejkompresja bezstratnakompresji bezstratnej.

Mówimy, że kodowanie jest prefiksowe, gdy żadne słowo kodoweSłowo kodowesłowo kodowe nie jest początkiem innego słowa.

Słowem kodowym w kontekście kodowania Huffmana określamy ciągi bitów, które jednoznacznie interpretują jakiś znak.

Problem 1

Zbadajmy przykład zastosowania kodów o stałej długości, kodując pojedynczą literę za pomocą ciągu binarnego o długości 2. W podobny sposób skonstruowany jest system ASCIIASCIIASCII.

Linia 1. kratka przygotujemy funkcje do kodowania i odkodowywania. Linia 2. def koduj otwórz nawias okrągły tekst dwukropek str przecinek slownik dwukropek dict zamknij nawias okrągły dwukropek. Linia 3. wynik znak równości cudzysłów cudzysłów. Linia 4. for znak in tekst dwukropek. Linia 5. wynik plus znak równości slownik otwórz nawias kwadratowy znak zamknij nawias kwadratowy. Linia 6. return wynik. Linia 8. def dekoduj otwórz nawias okrągły tekst dwukropek str przecinek slownik dwukropek dict zamknij nawias okrągły dwukropek. Linia 9. wynik znak równości cudzysłów cudzysłów. Linia 11. kratka wycinamy z kodu po 2 znaki. Linia 12. elementy znak równości otwórz nawias kwadratowy tekst otwórz nawias kwadratowy i dwukropek i plus 2 zamknij nawias kwadratowy for i in range otwórz nawias okrągły 0 przecinek len otwórz nawias okrągły tekst zamknij nawias okrągły przecinek 2 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 13. for element in elementy dwukropek. Linia 14. wynik plus znak równości slownik otwórz nawias kwadratowy element zamknij nawias kwadratowy. Linia 15. return wynik. Linia 17. kratka wykonamy prosty przykład. Linia 18. print otwórz nawias okrągły koduj otwórz nawias okrągły cudzysłów AABCBBACC cudzysłów przecinek otwórz nawias klamrowy cudzysłów A cudzysłów dwukropek cudzysłów 00 cudzysłów przecinek cudzysłów B cudzysłów dwukropek cudzysłów 01 cudzysłów przecinek cudzysłów C cudzysłów dwukropek cudzysłów 10 cudzysłów zamknij nawias klamrowy zamknij nawias okrągły zamknij nawias okrągły. Linia 19. kratka 000001100101001010. Linia 21. print otwórz nawias okrągły dekoduj otwórz nawias okrągły cudzysłów 000001100101001010 cudzysłów przecinek otwórz nawias klamrowy cudzysłów 00 cudzysłów dwukropek cudzysłów A cudzysłów przecinek cudzysłów 01 cudzysłów dwukropek cudzysłów B cudzysłów przecinek cudzysłów 10 cudzysłów dwukropek cudzysłów C cudzysłów zamknij nawias klamrowy zamknij nawias okrągły zamknij nawias okrągły. Linia 22. kratka AABCBBACC.

# przygotujemy funkcje do kodowania i odkodowywania
def koduj(tekst: str, slownik: dict):
	wynik = ""
	for znak in tekst:
		wynik += slownik[znak]
	return wynik
    
def dekoduj(tekst: str, slownik: dict):
	wynik = ""

	# wycinamy z kodu po 2 znaki
	elementy = [tekst[i:i+2] for i in range(0,len(tekst),2)]
	for element in elementy:
		wynik += slownik[element]
	return wynik

# wykonamy prosty przykład
print(koduj("AABCBBACC", {"A": "00", "B": "01", "C": "10"}))
# 000001100101001010

print(dekoduj("000001100101001010", {"00": "A", "01": "B", "10": "C"}))
# AABCBBACC

Spróbujmy teraz zastosować kody o zmiennej długości.

# przyjmijmy kodowanie: A = 0, B = 01, C = 110
# przykład zakodowanego ciągu cyfr
# 01010
# jaki jest pierwszy znak: A, czy B ?

Ważne!

W przypadku zastosowania kodów o zmiennej długości żaden kod nie może być prefiksem innego kodu. Ten warunek zapewnia, że tekst będzie dało się odkodować jednoznacznie. W powyższym przykładzie znak A jest prefiksem B, dlatego kodowanie jest błędne.

Ciekawostka

Binarne drzewo Huffmana ma pewną właściwość – jest ono regularne, co oznacza, że każdy węzeł ma zero lub dwóch potomków.

Przykład 1

Funkcja, którą napisaliśmy powyżej, równie dobrze nada się do kodowania tekstu o dowolnej długości słów kodowych.

def koduj(tekst: str, slownik: dict):
	wynik = ""
	for lit in tekst:
		wynik += slownik[lit]
	return wynik

# wykonamy kodowanie
print(koduj("BACA", {"A": "111", "B": "00", "C": "10"}))
# 0011110111

Zdekodowanie takiej wiadomości nie będzie już tak proste. Wynika to z faktu, że nie możemy podzielić wiadomości na określoną liczbę części, a następnie odkodować każdej z nich po kolei.

Problem 2

Aby dobrze zaprojektować drzewo, wykorzystamy tabelę częstości pojawiania się znaków w ciągu do zakodowania. Zdefiniujemy klasę zawierającą odpowiednie metody oraz funkcję tworzącą drzewo.

Musimy pamiętać o posortowaniu elementów tabeli. Dzięki dynamicznemu obliczaniu częstościczęstości występowania znaków otrzymamy wydajny algorytm. Stosując go, za każdym razem uzyskamy optymalny wynik: najkrótszy kod będzie odpowiadał najczęściej pojawiającemu się znakowi (zaś kod najdłuższy – najrzadziej występującej literze). Np. tworząc drzewo dla wierzchołków o częstości kolejno 1, 2, 3, najpierw połączymy ze sobą wierzchołki 1 i 2. Kolejnym krokiem będzie połączenie nowo utworzonego węzła z wierzchołkiem o częstości 3. Węzły, które łączymy najpierw, będą ostatecznie znajdowały się głębiej w drzewie, co oznacza, że trzeba będzie przejść po większej liczbie gałęzi, aby do nich dotrzeć. Podczas kodowania każda z gałęzi odpowiada jednemu znakowi. Oznacza to, że im płycej w drzewie położony jest dany wierzchołek, tym mniejsza będzie długość jego kodu.

Wymaga to zapamiętywania tablicy kodów znaków.

Poniżej przykład implementacji i wywołania funkcji, tworzącej posortowaną tabelę częstości dla zadanego parametru napis. Funkcja dla każdego znaku występującego w ciągu znaków napis, zlicza liczbę jego wystąpień, a następnie zebrane dane sortuje nierosnąco po liczbie wystąpień.

Linia 1. def tworz podkreślnik tabele podkreślnik czestosci otwórz nawias okrągły napis dwukropek str zamknij nawias okrągły dwukropek. Linia 2. wynik znak równości otwórz nawias klamrowy zamknij nawias klamrowy. Linia 3. for litera in napis dwukropek. Linia 4. if litera in wynik dwukropek. Linia 5. wynik otwórz nawias kwadratowy litera zamknij nawias kwadratowy plus znak równości 1. Linia 6. else dwukropek. Linia 7. wynik otwórz nawias kwadratowy litera zamknij nawias kwadratowy znak równości 1. Linia 8. kratka po zliczeniu liczby wystąpień danej litery sortujemy w kolejności nierosnącej. Linia 9. wynik znak równości sorted otwórz nawias okrągły wynik kropka items otwórz nawias okrągły zamknij nawias okrągły przecinek key znak równości lambda x dwukropek x otwórz nawias kwadratowy 1 zamknij nawias kwadratowy przecinek reverse znak równości True zamknij nawias okrągły. Linia 10. return wynik. Linia 12. kratka przykład wywołania. Linia 13. napis znak równości cudzysłów ABAABBBCCDEEEEAAA cudzysłów. Linia 14. print otwórz nawias okrągły cudzysłów Częstości liter dla ciągu znaków dwukropek cudzysłów przecinek napis zamknij nawias okrągły. Linia 15. tablica znak równości tworz podkreślnik tabele podkreślnik czestosci otwórz nawias okrągły napis zamknij nawias okrągły. Linia 16. print otwórz nawias okrągły cudzysłów Tablica dwukropek cudzysłów przecinek tablica zamknij nawias okrągły. Linia 18. kratka Częstości liter dla ciągu znaków dwukropek ABAABBBCCDEEEEAAA kropka. Linia 19. kratka Tablica dwukropek otwórz nawias kwadratowy otwórz nawias okrągły apostrof A apostrof przecinek 6 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof B apostrof przecinek 4 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof E apostrof przecinek 4 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof C apostrof przecinek 2 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof D apostrof przecinek 1 zamknij nawias okrągły zamknij nawias kwadratowy.

def tworz_tabele_czestosci(napis: str):
	wynik = {}
	for litera in napis:
		if litera in wynik:
			wynik[litera] += 1
		else:
			wynik[litera] = 1
	# po zliczeniu liczby wystąpień danej litery sortujemy w kolejności nierosnącej
	wynik = sorted(wynik.items(), key=lambda x: x[1], reverse=True)
	return wynik

# przykład wywołania
napis = "ABAABBBCCDEEEEAAA"
print("Częstości liter dla ciągu znaków: ", napis)
tablica = tworz_tabele_czestosci(napis)
print("Tablica: ", tablica)

# Częstości liter dla ciągu znaków: ABAABBBCCDEEEEAAA.
# Tablica: [('A', 6), ('B', 4), ('E', 4), ('C', 2), ('D', 1)]

Bazując na przygotowanej tabeli, utworzymy klasę, dzięki której zbudujemy drzewo binarne. Zdefiniujemy też funkcję, która będzie odpowiadać za skonstruowanie słownika tablicy kodów znaków oraz jego odwróconej wersji.

Linia 1. kratka klasa opisująca węzeł drzewa. Linia 2. class Wezel podkreślnik Huffmana dwukropek. Linia 3. lewy podkreślnik syn znak równości None. Linia 4. prawy podkreślnik syn znak równości None. Linia 6. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek lewy podkreślnik syn przecinek prawy podkreślnik syn zamknij nawias okrągły dwukropek. Linia 7. self kropka lewy podkreślnik syn znak równości lewy podkreślnik syn. Linia 8. self kropka prawy podkreślnik syn znak równości prawy podkreślnik syn. Linia 10. def dzieci otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 11. return otwórz nawias okrągły self kropka lewy podkreślnik syn przecinek self kropka prawy podkreślnik syn zamknij nawias okrągły. Linia 13. def podkreślnik podkreślnik str podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 14. return str otwórz nawias okrągły self kropka lewy podkreślnik syn zamknij nawias okrągły plus str otwórz nawias okrągły self kropka prawy podkreślnik syn zamknij nawias okrągły. Linia 16. kratka funkcja generująca słownik zawierający ciąg binarny dla jednego znaku. Linia 17. def drzewo podkreślnik huffmana otwórz nawias okrągły wezel przecinek lewy podkreślnik syn znak równości True przecinek kod znak równości apostrof apostrof zamknij nawias okrągły dwukropek. Linia 18. if type otwórz nawias okrągły wezel zamknij nawias okrągły is str dwukropek. Linia 19. return otwórz nawias klamrowy wezel dwukropek kod zamknij nawias klamrowy. Linia 20. otwórz nawias okrągły l przecinek r zamknij nawias okrągły znak równości wezel kropka dzieci otwórz nawias okrągły zamknij nawias okrągły. Linia 21. d znak równości dict otwórz nawias okrągły zamknij nawias okrągły. Linia 22. d kropka update otwórz nawias okrągły drzewo podkreślnik huffmana otwórz nawias okrągły l przecinek True przecinek kod plus apostrof 0 apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 23. d kropka update otwórz nawias okrągły drzewo podkreślnik huffmana otwórz nawias okrągły r przecinek False przecinek kod plus apostrof 1 apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 24. return d. Linia 26. kratka funkcja tworząca słownik z wszystkimi znakami użytymi w napisie. Linia 27. def tworz podkreślnik slownik podkreślnik huffmana otwórz nawias okrągły tabela podkreślnik czestosci dwukropek list zamknij nawias okrągły dwukropek. Linia 28. while len otwórz nawias okrągły tabela podkreślnik czestosci zamknij nawias okrągły zamknij nawias ostrokątny 1 dwukropek. Linia 29. otwórz nawias okrągły wezel podkreślnik prawy podkreślnik syn przecinek wartosc podkreślnik czest podkreślnik 1 zamknij nawias okrągły znak równości tabela podkreślnik czestosci otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy. Linia 30. otwórz nawias okrągły wezel podkreślnik lewy podkreślnik syn przecinek wartosc podkreślnik czest podkreślnik 2 zamknij nawias okrągły znak równości tabela podkreślnik czestosci otwórz nawias kwadratowy minus 2 zamknij nawias kwadratowy. Linia 32. kratka za pomocą mechanizmu wycinków odcinamy ostatnie dwa elementy listy. Linia 33. tabela podkreślnik czestosci znak równości tabela podkreślnik czestosci otwórz nawias kwadratowy dwukropek minus 2 zamknij nawias kwadratowy. Linia 35. kratka tworzymy obiekty klasy. Linia 36. nowy podkreślnik wezel znak równości Wezel podkreślnik Huffmana otwórz nawias okrągły wezel podkreślnik lewy podkreślnik syn przecinek wezel podkreślnik prawy podkreślnik syn zamknij nawias okrągły. Linia 38. kratka dodajemy do listy krotkę zawierającą węzeł i sumę częstości. Linia 39. krotka znak równości otwórz nawias okrągły nowy podkreślnik wezel przecinek wartosc podkreślnik czest podkreślnik 1 plus wartosc podkreślnik czest podkreślnik 2 zamknij nawias okrągły. Linia 40. tabela podkreślnik czestosci kropka append otwórz nawias okrągły krotka zamknij nawias okrągły. Linia 42. kratka sortujemy nierosnąco listę według drugiego elementu przecinek a więc sumy częstości. Linia 43. tabela podkreślnik czestosci znak równości sorted otwórz nawias okrągły tabela podkreślnik czestosci przecinek key znak równości lambda x dwukropek x otwórz nawias kwadratowy 1 zamknij nawias kwadratowy przecinek reverse znak równości True zamknij nawias okrągły. Linia 45. kratka wywołujemy rekurencyjną funkcję przecinek która zwróci słownik przypisań przecinek korzystając. Linia 46. kratka z przejścia pomiędzy gałęziami drzewa przecinek rozpoczynając od lewej gałęzi korzenia. Linia 47. slownik podkreślnik huffmana znak równości drzewo podkreślnik huffmana otwórz nawias okrągły tabela podkreślnik czestosci otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły. Linia 49. kratka gdybyśmy chcieli zakodować wiadomość złożoną z tylko jednego unikalnego znaku przecinek to drzewo się nie zbuduje przecinek więc rozwiązujemy to w ten sposób. Linia 50. if type otwórz nawias okrągły tabela podkreślnik czestosci otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły znak równości znak równości str dwukropek. Linia 51. slownik podkreślnik huffmana znak równości otwórz nawias klamrowy tabela podkreślnik czestosci otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy dwukropek 1 zamknij nawias klamrowy. Linia 53. kratka tworzymy odwrotny słownik. Linia 54. slownik podkreślnik odwrotny znak równości otwórz nawias klamrowy wartosc dwukropek klucz for klucz przecinek wartosc in slownik podkreślnik huffmana kropka items otwórz nawias okrągły zamknij nawias okrągły zamknij nawias klamrowy. Linia 56. return otwórz nawias okrągły slownik podkreślnik huffmana przecinek slownik podkreślnik odwrotny zamknij nawias okrągły. Linia 58. kratka przykład wywołania bazujący na napisie. Linia 59. tablica znak równości otwórz nawias kwadratowy otwórz nawias okrągły apostrof A apostrof przecinek 6 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof B apostrof przecinek 4 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof E apostrof przecinek 4 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof C apostrof przecinek 2 zamknij nawias okrągły przecinek otwórz nawias okrągły apostrof D apostrof przecinek 1 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 60. slownik przecinek odwrotny znak równości tworz podkreślnik slownik podkreślnik huffmana otwórz nawias okrągły tablica zamknij nawias okrągły. Linia 61. print otwórz nawias okrągły cudzysłów Słownik dwukropek cudzysłów przecinek slownik zamknij nawias okrągły. Linia 62. print otwórz nawias okrągły cudzysłów Odwrotny dwukropek cudzysłów przecinek odwrotny zamknij nawias okrągły. Linia 64. kratka Słownik dwukropek otwórz nawias klamrowy apostrof A apostrof dwukropek apostrof 00 apostrof przecinek apostrof B apostrof dwukropek apostrof 01 apostrof przecinek apostrof E apostrof dwukropek apostrof 10 apostrof przecinek apostrof C apostrof dwukropek apostrof 110 apostrof przecinek apostrof D apostrof dwukropek apostrof 111 apostrof zamknij nawias klamrowy. Linia 65. kratka Odwrotny dwukropek otwórz nawias klamrowy apostrof 00 apostrof dwukropek apostrof A apostrof przecinek apostrof 01 apostrof dwukropek apostrof B apostrof przecinek apostrof 10 apostrof dwukropek apostrof E apostrof przecinek apostrof 110 apostrof dwukropek apostrof C apostrof przecinek apostrof 111 apostrof dwukropek apostrof D apostrof zamknij nawias klamrowy.

# klasa opisująca węzeł drzewa
class Wezel_Huffmana:
	lewy_syn = None
	prawy_syn = None

	def __init__(self, lewy_syn, prawy_syn):
		self.lewy_syn = lewy_syn
		self.prawy_syn = prawy_syn

	def dzieci(self):
		return (self.lewy_syn, self.prawy_syn)

	def __str__(self):
		return str(self.lewy_syn) + str(self.prawy_syn)

	# funkcja generująca słownik zawierający ciąg binarny dla jednego znaku
	def drzewo_huffmana(wezel, lewy_syn = True, kod = ''):
		if type(wezel) is str:
			return {wezel: kod}
		(l, r) = wezel.dzieci()
		d = dict()
		d.update(drzewo_huffmana(l, True, kod + '0'))
		d.update(drzewo_huffmana(r, False, kod + '1'))
		return d

	# funkcja tworząca słownik z wszystkimi znakami użytymi w napisie
	def tworz_slownik_huffmana(tabela_czestosci: list):
		while len(tabela_czestosci) > 1:
			(wezel_prawy_syn, wartosc_czest_1) = tabela_czestosci[-1]
			(wezel_lewy_syn, wartosc_czest_2) = tabela_czestosci[-2]

			# za pomocą mechanizmu wycinków odcinamy ostatnie dwa elementy listy
			tabela_czestosci = tabela_czestosci[:-2]

			# tworzymy obiekty klasy
			nowy_wezel = Wezel_Huffmana(wezel_lewy_syn, wezel_prawy_syn)

			# dodajemy do listy krotkę zawierającą węzeł i sumę częstości
			krotka = (nowy_wezel, wartosc_czest_1 + wartosc_czest_2)
			tabela_czestosci.append(krotka)

			# sortujemy nierosnąco listę według drugiego elementu, a więc sumy częstości
			tabela_czestosci = sorted(tabela_czestosci, key=lambda x: x[1], reverse=True)

	# wywołujemy rekurencyjną funkcję, która zwróci słownik przypisań, korzystając
	# z przejścia pomiędzy gałęziami drzewa, rozpoczynając od lewej gałęzi korzenia
	slownik_huffmana = drzewo_huffmana(tabela_czestosci[0][0])

	#gdybyśmy chcieli zakodować wiadomość złożoną z tylko jednego unikalnego znaku, to drzewo się nie zbuduje, więc rozwiązujemy to w ten sposób
	if type(tabela_czestosci[0][0]) == str:
		slownik_huffmana = {tabela_czestosci[0][0]: 1}

	#tworzymy odwrotny słownik
	slownik_odwrotny = {wartosc: klucz for klucz, wartosc in slownik_huffmana.items()}

	return (slownik_huffmana, slownik_odwrotny)

# przykład wywołania bazujący na napisie
tablica = [('A', 6), ('B', 4), ('E', 4), ('C', 2), ('D', 1)]
slownik, odwrotny = tworz_slownik_huffmana(tablica)
print("Słownik:",slownik)
print("Odwrotny: ",odwrotny)

# Słownik: {'A': '00', 'B': '01', 'E': '10', 'C': '110', 'D': '111'}
# Odwrotny: {'00': 'A', '01': 'B', '10': 'E', '110': 'C', '111': 'D'}

Teraz możemy już zdefiniować funkcje, które używając słownika, zakodują i odkodują ciąg znaków.

Linia 1. kratka funkcja kodująca. Linia 2. def koduj podkreślnik huffmana otwórz nawias okrągły tekst dwukropek str przecinek slownik dwukropek dict zamknij nawias okrągły dwukropek. Linia 3. wynik znak równości cudzysłów cudzysłów. Linia 4. for lit in tekst dwukropek. Linia 5. wynik plus znak równości slownik otwórz nawias kwadratowy lit zamknij nawias kwadratowy. Linia 6. return wynik. Linia 8. kratka funkcja odkodowująca. Linia 9. def odkoduj podkreślnik huffmana otwórz nawias okrągły zakodowany dwukropek str przecinek slownik dwukropek dict zamknij nawias okrągły dwukropek. Linia 10. wynik znak równości cudzysłów cudzysłów. Linia 11. kod znak równości cudzysłów cudzysłów. Linia 12. for znak in zakodowany dwukropek. Linia 13. kod plus znak równości znak. Linia 14. zakodowany znak równości zakodowany otwórz nawias kwadratowy 1 dwukropek zamknij nawias kwadratowy kratka reszta. Linia 15. if kod in slownik dwukropek. Linia 16. wynik plus znak równości slownik otwórz nawias kwadratowy kod zamknij nawias kwadratowy. Linia 17. kod znak równości cudzysłów cudzysłów. Linia 18. return wynik. Linia 20. kratka przykładowe wykonanie. Linia 21. napis znak równości cudzysłów ABAABBBCCDEEEEAAA cudzysłów. Linia 22. slownik znak równości otwórz nawias klamrowy apostrof A apostrof dwukropek apostrof 00 apostrof przecinek apostrof B apostrof dwukropek apostrof 01 apostrof przecinek apostrof E apostrof dwukropek apostrof 10 apostrof przecinek apostrof C apostrof dwukropek apostrof 110 apostrof przecinek apostrof D apostrof dwukropek apostrof 111 apostrof zamknij nawias klamrowy. Linia 23. odwrotny znak równości otwórz nawias klamrowy apostrof 00 apostrof dwukropek apostrof A apostrof przecinek apostrof 01 apostrof dwukropek apostrof B apostrof przecinek apostrof 10 apostrof dwukropek apostrof E apostrof przecinek apostrof 110 apostrof dwukropek apostrof C apostrof przecinek apostrof 111 apostrof dwukropek apostrof D apostrof zamknij nawias klamrowy. Linia 24. zakodowany znak równości koduj podkreślnik huffmana otwórz nawias okrągły napis przecinek slownik zamknij nawias okrągły. Linia 25. print otwórz nawias okrągły cudzysłów Napis zakodowany cudzysłów przecinek zakodowany zamknij nawias okrągły. Linia 26. odkodowany znak równości odkoduj podkreślnik huffmana otwórz nawias okrągły zakodowany przecinek odwrotny zamknij nawias okrągły. Linia 27. print otwórz nawias okrągły cudzysłów Napis odkodowany cudzysłów przecinek odkodowany zamknij nawias okrągły. Linia 29. kratka Napis zakodowany 0001000001010111011011110101010000000. Linia 30. kratka Napis odkodowany ABAABBBCCDEEEEAAA.

# funkcja kodująca
def koduj_huffmana(tekst: str, slownik: dict):
	wynik = ""
	for lit in tekst:
		wynik += slownik[lit]
	return wynik

# funkcja odkodowująca
def odkoduj_huffmana(zakodowany: str, slownik: dict):
	wynik = ""
	kod = ""
	for znak in zakodowany:
		kod += znak
		zakodowany = zakodowany[1:] # reszta
		if kod in slownik:
			wynik += slownik[kod]
			kod = ""
	return wynik

# przykładowe wykonanie
napis = "ABAABBBCCDEEEEAAA"
slownik = {'A': '00', 'B': '01', 'E': '10', 'C': '110', 'D': '111'}
odwrotny = {'00': 'A', '01': 'B', '10': 'E', '110': 'C', '111': 'D'}
zakodowany = koduj_huffmana(napis, slownik)
print("Napis zakodowany ", zakodowany)
odkodowany = odkoduj_huffmana(zakodowany, odwrotny)
print("Napis odkodowany ", odkodowany)

# Napis zakodowany 0001000001010111011011110101010000000
# Napis odkodowany ABAABBBCCDEEEEAAA

Ciekawostka

W tej sekcji w programie wykorzystaliśmy słowo kluczowe lambda. W języku Python pozwala ono na deklarowanie funkcji anonimowych.

Wyrażenia lambda używamy jako argumentu funkcji wyższego rzędu (czyli funkcji, która przyjmuje inne funkcje jako argumenty).

Te funkcje w programach często stosuje się przy okazji sortowania. Stanowią one wyrażenia zwracające klucz (wartość), według którego mają zostać posortowane elementy.

Dana jest następująca lista:

szczyty = [
	('Mount Everest',8848,1953),
	('Lhotse',8516,1956),
	('Kanczendzonga',8586,1955),
	('Makalu',8481,1955),
	('Czogori',8611,1954)
]

W jaki sposób możemy ją wykorzystać?

sorted(szczyty) – posortuje listę według pierwszego elementu każdej tupli, czyli nazwy szczytu;
sorted(szczyty, key=lambda x: x[1]) – posortuje listę według klucza zwróconego przez jednoargumentową funkcję lambda, w tym wypadku będzie to wysokość szczytu (nazwa szczytu znajduje się pod indeksem 0, a rok zdobycia szczytu pod indeksem 2);
max(szczyty, key=lambda x: x[1]) – zwróci najwyższy szczyt;
min(szczyty, key=lambda x: x[2]) – zwróci szczyt najwcześniej zdobyty.

Przyjrzyjmy się przykładowemu programowi.

szczyty = [
	('Mount Everest',8848,1953),
	('Lhotse',8516,1956),
	('Kanczendzonga',8586,1955),
	('Makalu',8481,1955),
	('Czogori',8611,1954)
]

print(min(szczyty, key=lambda x: x[2]))

Dana jest lista szczyty, która składa się z pięciu krotek. Każda krotka zawiera dane o nazwie szczytu, jego wysokości oraz roku, w którym szczyt został zdobyty.

Chcemy wyświetlić krotkę przechowującą informacje o najwcześniej zdobytym szczycie, dlatego skorzystamy z polecenia print.

print()

Wykorzystamy wbudowaną w język Python funkcję min().

print(min())

Przeszukujemy listę szczyty.

print(min(szczyty))

Opcjonalny argument key opisuje, jak porównać elementy, aby znaleźć minimum.

print(min(szczyty, key))

Wykorzystamy wyrażenie lambda.

print(min(szczyty, key=lambda))

Do wyrażenia lambda przekażemy poszczególne trójelementowe krotki reprezentujące informacje na temat szczytów.

Do zmiennej x argumentu wyrażenia lambda podstawiana jest krotka, a następnie wyznaczana jest wartość x[2], która z trójelementowej krotki pobiera rok zdobycia szczytu.

szczyty = [
	('Mount Everest',8848,1953),
	('Lhotse',8516,1956),
	('Kanczendzonga',8586,1955),
	('Makalu',8481,1955),
	('Czogori',8611,1954)
]

print(min(szczyty, key=lambda x: x[2]))

Wynik działania programu:

('Mount Everest', 8848, 1953)

Słownik

ASCII

(ang. American Standard Code for Information Interchange) pierwotnie siedmiobitowy system kodowania znaków (współcześnie rozszerzony do ośmiu bitów); w oryginalnej wersji kodom z zakresu 0–127 przyporządkowano 26 liter łacińskich, 10 cyfr (0–9) oraz dodatkowe znaki

częstość występowania znaków alfabetu

specyficzna cecha wszystkich języków naturalnych; w przypadku każdego z nich można określić, jak często w słowniku pojawiają się poszczególne litery alfabetu; dla języka polskiego takie częstości zbadał i przedstawił m.in. A. Przepiórkowski z Instytutu Podstaw Informatyki Polskiej Akademii Nauk

kompresja bezstratna

metoda kompresji zapewniająca możliwość odtworzenia oryginalnej (niezmienionej) postaci informacji pierwotnej z danych skompresowanych

słowo kodowe

słowo, wyrażenie, znak lub ciąg bitów odpowiadające jakiemuś słowu, które chcemy zakodować; we wczesnych etapach rozwoju kryptografii słowa kodowe były układane w ramach książek kodowych i wykorzystywane do szyfrowania wiadomości

Wprowadzenie

Film samouczek

Słownik