[Powered by Google Translate] [Opis przejścia - Set Problem 6] [Zamyla Chan - Harvard University] [To jest CS50. - CS50.TV] 

Witam wszystkich i zapraszamy do Walkthrough 6: Puff Huff'n. W Puff Huff'n co robimy ma być do czynienia z pliku skompresowanego Huffmana a następnie zaciągając go ponownie, więc go dekompresji, tak, że możemy tłumaczyć z 0s i 1s, że użytkownik wysyła nam i przekształcić ją z powrotem do oryginalnego tekstu. Pset 6 będzie całkiem fajne, bo masz zamiar zobaczyć niektóre z narzędzi że stosowane w Pset 4 i Pset 5 i rodzaj łącząc je w 1 koncepcji całkiem zgrabny gdy przyjdziesz do myśleć o tym. 

Także, prawdopodobnie, pset 4 i 5 były najtrudniejszych psets które mieliśmy do zaoferowania. Tak więc od teraz mamy ten 1 więcej PSET w C, a po, że jesteśmy do programowania. Więc gratuluję siebie dla uzyskania nad najtrudniejszym garbu w CS50. 

Przechodząc do Puff Huff'n nasz przybornik do tego Pset będą drzewa Huffman więc zrozumienie nie tylko, jak drzewa binarnego pracę, ale także konkretnie drzewa Huffmana, jak są one zbudowane. I wtedy będziemy mieć dużo kodu dystrybucyjnego w tym zbior, a my się, aby zobaczyć, że rzeczywiście niektóre z kodu nie może być w pełni zrozumieć jeszcze więc te będą pliki. c, ale towarzyszące im pliki. h da nam wystarczająco dużo zrozumienia, że ​​musimy tak, że wiemy, jak te funkcje działają lub przynajmniej to, co mają robić - ich wejścia i wyjścia - nawet, jeśli nie wiemy, co dzieje się w czarnej skrzynce lub nie rozumieją, co się dzieje w czarnym pudełku wewnątrz. I w końcu, jak zwykle, mamy do czynienia z nowymi strukturami danych, szczególne rodzaje węzłów, które wskazują na pewne rzeczy, a więc o papier i pióro nie tylko dla procesu projektowania i gdy starasz się dowiedzieć w jaki sposób powinien działać pset ale także podczas debugowania. Możesz mieć GDB obok pióra i papieru podczas zdjąć jakie wartości są gdzie strzałki wskazują, i tego typu rzeczy. 

Najpierw spójrzmy na drzewa Huffmana. Drzewa Huffman są binarne drzewa, co oznacza, że ​​każdy węzeł ma tylko 2 dzieci. W drzewach Huffman charakterystyczną jest to, że najczęściej wartości reprezentuje najmniejszą liczbą bitów. Widzieliśmy w przykładach wykładowych alfabetem Morse'a, jaki rodzaj skonsolidowanego niektóre litery. Jeśli starasz się przetłumaczyć A lub e, na przykład, pan tłumaczyć, że często, więc zamiast korzystać z pełnego zestawu bitów przyznanej dla tego zwykłego typu danych, skompresować go do mniej, a następnie te litery, które są reprezentowane rzadziej reprezentowane są przy dłuższych bitów bo można sobie na to pozwolić, gdy zważyć, że częstotliwości te litery pojawiają się. Mamy ten sam pomysł tu drzew Huffmana gdzie robimy łańcuch, rodzaj drogi, aby dostać się do niektórych znaków. A potem bohaterowie, którzy mają najwięcej częstotliwości będą stanowiły o najmniejszej ilości bitów. 

Sposób, że można skonstruować drzewo Huffmana jest umieszczanie wszystkich znaków, które pojawiają się w tekście i obliczania ich częstotliwość, jak często się pojawiają. Może to być zarówno liczba, ile razy te litery pojawiają czy może procent spośród wszystkich znaków, ile każdy z nich występuje. A więc to, co możesz zrobić, to gdy już wszystkie tego wyznaczoną, potem poszukaj 2 częstotliwości najniższych, a następnie połączyć je jako rodzeństwo gdzie następnie węzeł nadrzędny ma częstotliwość, która jest sumą swoich 2 dzieci. A potem umownie powiedzieć, że lewy węzeł, przestrzegać, że po 0 filię, i prawej stronie węzeł jest 1 oddział. Jak widzieliśmy w alfabetem Morse'a, jeden haczyk, że jeśli miał tylko dźwięk i sygnał dźwiękowy to było dwuznaczne. To może być albo 1 litera lub może to być sekwencja 2 liter. A więc to, co robi, to drzewa Huffman, ponieważ z natury z bohaterów albo nasze końcowe rzeczywiste znaki jako ostatni węzeł w branży - tym, że odnosi się liści - ze względu, że nie może być niejasności zgodnie z którą pismo próbujesz kodowania z serii bitów bo nigdzie wzdłuż bitów reprezentujących 1 list natkniesz się cały list, i nie będzie żadnego zamieszania tam. Ale pójdziemy do przykładów, że chłopaki mogą zobaczyć, że faktycznie zamiast nam po prostu mówię, że to prawda. 

Spójrzmy na prosty przykład drzewa Huffmana. Mam ciąg znaków, który jest tu 12 znaków. Mam 4 As, 6 i 2 BS, CS. Moim pierwszym krokiem byłoby liczyć. Ile razy pojawia się? Wydaje się 4 razy w ciągu. B pojawia się 6 razy, a pojawia się 2 razy C. Oczywiście, mam zamiar powiedzieć, używam B najczęściej więc chcę reprezentować B z najmniejszą liczbę bitów, najmniejszą liczbę 0s i 1s. I wtedy ja również będzie oczekiwać C wymagać Najwiecej 0s i 1s, jak również. Pierwsze co zrobiłem, jest tutaj I umieścił je w kolejności rosnącej pod względem częstotliwości. Widzimy, że C i A, to nasze 2 najniższych częstotliwościach. Tworzymy węzeł nadrzędny, a węzeł nadrzędny nie posiada litera skojarzona z nią ale ma częstotliwość, która jest sumą. Suma się 2 + 4, które to 6. Następnie kierujemy się w lewo gałąź. Gdybyśmy byli w tym 6 węzłów, wówczas kierujemy 0 dostać się do C a następnie 1, aby uzyskać do A. Więc teraz mamy 2 węzły. Mamy wartość 6, a potem mamy też inny węzeł z wartością 6. I tak te 2 nie tylko 2, ale także tylko najniższy 2, które są w lewo, więc dołączyć do tych, przez innego rodzica, z sumą jest 12. Więc tutaj mamy drzewa Huffmana gdzie się do B, że będzie tylko 1 bit , a następnie dostać się do mielibyśmy 01, a następnie o 00 C. Więc widzimy, że w zasadzie jesteśmy reprezentujących te znaki z 1 lub 2 bity gdzie B, zgodnie z przewidywaniami, ma najmniej. A potem się spodziewaliśmy C mają większość, ale ponieważ jest to takie małe drzewo Huffman to jest reprezentowane przez 2 bity, w przeciwieństwie do gdzieś w środku. 

Wystarczy iść na inny prosty przykład drzewa Huffmana, Powiedzmy, że masz ciąg znaków "Hello". Co zrobić, jest najpierw powiesz, ile razy ma H występują w tym? H pojawia się raz, a potem pojawia się e raz, a potem mamy l pojawiający dwukrotnie oraz o pojawiające się raz. I tak to się spodziewać, jaka litera jest reprezentowana przez najmniejszą liczbą bitów? [Uczeń] l. L. >> Tak. l ma rację. Oczekujemy l być reprezentowana przez najmniejszą liczbę bitów bo l jest używany najczęściej w ciąg "Hello". Co mam teraz zrobić, to wyciągnąć te węzły. Mam 1, który jest H, a następnie kolejną 1, która jest e, a następnie na 1, czyli o - teraz jestem, umieszczając je w kolejności - a następnie 2, która jest l. Potem mówią, że sposób zbudować drzewo Huffmana jest znalezienie 2 węzły z najmniejszych częstotliwościach i uczynić je rodzeństwo, tworząc węzeł nadrzędny. Tutaj mamy 3 węzły z najniższej częstotliwości. Oni wszyscy 1. Więc tutaj wybrać, który mamy zamiar połączyć pierwszy. Powiedzmy, że mogę wybrać H i E. Suma 1 + 1 jest 2, a węzeł nie ma litera skojarzona z nią. To po prostu przechowuje wartość. Teraz patrzymy na najbliższe 2 częstotliwości najniższych. To jest 2 i 1. To może być jeden z tych 2, ale mam zamiar wybrać ten jeden. Suma jest 3. I w końcu, mam tylko 2 w lewo, więc wtedy, że staje się 5. To tutaj, zgodnie z oczekiwaniami, jeśli wypełnienie kodowanie, że 1s zawsze rację oddział i 0s są lewe. Następnie mamy l reprezentowany przez tylko 1 bit, a następnie przez 2 Ö e, a następnie przez 2, a następnie spada z H 3 bitów. Więc można przekazać ten komunikat "Hello" zamiast rzeczywiście pomocą znaków po prostu 0s i 1s. Należy jednak pamiętać, że w kilku przypadkach mieliśmy więzi z naszym częstotliwości. Mogliśmy albo przyłączył się do H i O 1-sza może. Lub później, kiedy mieliśmy l reprezentowany przez 2 oraz połączone było reprezentowane przez 2, że nie związany jeden. 

I tak podczas wysyłania 0s i 1s, że faktycznie nie gwarantuje że odbiorca może w pełni odczytać wiadomość tuż nietoperza bo nie może wiedzieć, co decyzja, którą tworzył. Tak więc, gdy mamy do czynienia z kompresją Huffmana, jakoś musimy powiedzieć odbiorcy naszej wiadomości, jak zdecydowaliśmy - Muszą wiedzieć, jakiś dodatkowych informacji Ponadto do wiadomości sprężonego. Muszą zrozumieć, co faktycznie wygląda drzewo, jak rzeczywiście te decyzje. 

Tu właśnie robi przykłady oparte na rzeczywistej liczby, ale czasem można również drzewa Huffmana na podstawie częstotliwości, przy której pojawiają się litery, i jest dokładnie taki sam sposób. Tutaj jestem wyrażając ją w kategoriach procentów lub części, a więc dokładnie to samo. Uważam, 2 mniejsze, sumują je, obok 2 mniejsze, sumują je, dopóki nie ma pełnego drzewa. Nawet jeśli możemy to zrobić tak czy inaczej, kiedy mamy do czynienia z procentów, co oznacza, że ​​mamy podział rzeczy i do czynienia z po przecinku, a raczej płynie jeśli myślimy o strukturach danych o głowę. Co wiemy o pływaków? Co znajduje się typowy problem, gdy mamy do czynienia z pływaków? [Uczeń] Nieprecyzyjne arytmetyki. >> Tak. Nieścisłości. Z powodu zmiennej precyzji punktów, w tym zbior abyśmy upewnić że nie stracisz żadnych wartości, to mamy rzeczywiście będzie mieć do czynienia z hrabią. Więc jeśli były, aby myśleć o węźle Huffman, jeśli spojrzeć na strukturę tutaj jeśli spojrzeć na zielone to ma częstotliwość z nim związane a także wskazuje na jej lewej stronie węzła oraz węzeł do prawej. , A następnie z nich jest czerwony znak również związane z nimi. Nie idziemy do tych, osobne dla rodziców, a następnie węzłów końcowych, które nazywamy liśćmi, ale raczej tych, będą po prostu wartości NULL. Dla każdego węzła musimy znak, symbol, że węzeł reprezentuje, Następnie częstotliwość oraz wskaźnik do dziecka z lewej, jak również jego dziecko prawej. Liście, które są na samym dole, miałby także węzłów wskaźniki po ich lewej stronie i ich prawa, ale ponieważ wartości te nie są skierowane do faktycznych węzłów, co by ich wartość będzie? >> [Uczeń] NULL. NULL. >> Dokładnie. Oto przykład, jak można reprezentować częstotliwość w pływaków, ale będziemy mieć do czynienia z tym z liczb całkowitych, więc wszystko zrobiłem to zmienić typ danych tam. 

Chodźmy na nieco trochę bardziej złożonego przykładu. Ale teraz, że zrobiliśmy te proste, to tylko sam proces. Znajdziesz 2 najniższych częstotliwości, Podsumowując częstotliwości i to jest nowa częstotliwość węzła nadrzędnego, które następnie wskazuje na jego lewej stronie z 0 oddział i prawa z 1 oddział. Jeśli mamy ciąg "To jest CS50", a następnie możemy liczyć, ile razy jest T wspomniano, h wspomniano, I, S, C, 5, 0. Więc co ja tutaj jest z czerwonych węzłów po prostu obsadzone, Powiedziałem, że będę miała te znaki w końcu na dole mojego drzewa. Te będą wszystkie liści. Wtedy to, co zrobiłem to ja sortując je według częstotliwości w porządku rosnącym, i to jest rzeczywiście sposób, że kod pset robi Czy to sortuje go przez częstotliwość, a następnie alfabetycznie. Tak więc ma numery a potem alfabetycznie częstotliwości. Wtedy to, co chciałbym zrobić, to znajdę 2 najniższy. To 0 i 5. Chciałbym podsumować je, i to 2. Następnie chciałbym kontynuować, znajdź następne 2 najniższy. Są dwa 1s, a następnie te się 2, a także. Teraz wiem, że moim następnym krokiem ma być połączenie najniższą liczbę, T, który jest, 1, a następnie wybiera jeden z węzłów ma 2 jako częstotliwości. Więc tutaj mamy 3 opcje. Co mam zamiar zrobić dla slajdu jest tylko wizualnie zmienić je dla Ciebie tak aby można było zobaczyć, jak buduję go. Jaki kod i kod dystrybucja zrobi będzie dołączyć jeden T z 0 do 5 węzła. Tak więc, że środki na 3, a potem kontynuować proces. 2 i 2 teraz są najniższe, więc wtedy te kwoty do 4. Wszyscy po tej pory? Okay. Następnie, po, że mamy 3 i 3, które muszą być sumowane, więc znowu ja tylko przełączając go tak aby można zobaczyć wizualnie tak, że nie będzie zbyt brudny. Następnie mamy 6, a następnie nasz ostatni krok jest teraz, że mamy tylko 2 węzły podsumować te do korzenia naszego drzewa, które jest 10. A liczba 10 ma sens, ponieważ każdy węzeł reprezentowany, ich wartości, ich liczbę częstotliwości, było, ile razy pojawił się w ciągu, a następnie mamy 5 znaków w naszym łańcuchu, więc to ma sens. Jeśli przyjrzymy się w jaki sposób możemy właściwie zakodować, zgodnie z oczekiwaniami, I i S, które najczęściej się reprezentuje najmniejszą liczbą bitów. 

Bądź ostrożny. W drzewach Huffman sprawa rzeczywiście ważne. Wielka litera S jest inny niż małą s. Jeśli mieliśmy "To CS50" dużymi literami, a następnie s małe tylko wystąpiły dwukrotnie będzie węzeł z 2 jako wartość, a następnie wielkie S będzie tylko raz. Więc drzewo zmieni struktur bo rzeczywiście mają dodatkowy liść tutaj. Ale suma nadal będzie 10. To, co mamy w rzeczywistości będzie wywołanie kontrolną, dodanie wszystkich przypadkach. 

Teraz, gdy już objęte drzewa Huffmana, możemy zanurzyć się Puff Huff'n, zbior. Zamierzamy zacząć od części pytania, i to będzie Ci przyzwyczajeni binarnych drzew i jak działają wokół, że: węzły rysunkowe, tworząc własne typedef struct dla węzła, i zobaczyć, jak można wstawić do drzewa binarnego, jeden, który jest sortowane, przemierzając go, a takie rzeczy. Ta wiedza jest na pewno ci pomoże, gdy wkraczają w części Huff'n Puff z PSET. W standardowej edycji PSET, twoim zadaniem jest wdrożenie Puff, oraz w wersji hacker twoim zadaniem jest wdrożenie Huff. Co Huff robi jest potrzebny tekst, a potem przekłada go na 0s i 1s, więc proces, który zrobiliśmy powyżej, gdzie liczyliśmy częstotliwości a następnie wykonany z drzewa, a następnie powiedział: "Jak dostać T?" T jest reprezentowany przez 100, takie rzeczy, a następnie Huff weźmie tekst, a następnie wyjściowy binarny. Ale także dlatego, że wiemy, że chcemy umożliwić naszym odbiorcę wiadomości odtworzyć dokładnie to samo drzewo, ale także zawiera informacje na temat liczby częstotliwości. Następnie z Puff dostajemy plik binarny z 0s i 1s również biorąc pod uwagę i informacji o częstotliwości. Tłumaczymy wszystkie te plecy 0s i 1s do oryginalnej wiadomości, że był, więc jesteśmy dekompresji to. Jeśli robisz standardową edycję, nie musi wdrażać Huff, tak to możesz tylko korzystać z implementacji kadrowej Huffa. Istnieją instrukcje w specyfikacji, w jaki sposób to zrobić. Można uruchomić realizację kadrowej Huff o pewnych pliku tekstowego a następnie użyć tego wyjścia jako wkładu Puff. 

Jak już wspomniałem wcześniej, mamy dużo kodu dystrybucji dla tej jednej. Zamierzam uruchomić przez niego przechodzi. Mam zamiar spędzić większość czasu na pliki. H ponieważ w plików. c, ponieważ mamy. H i to daje nam prototypów funkcji, nie w pełni muszą zrozumieć dokładnie - Jeśli nie rozumieją, co się dzieje w plików. C, to nie martw się zbyt wiele, ale na pewno spróbować spojrzeć, ponieważ może to dać pewne wskazówki i jest to przydatne, aby przyzwyczaić się do czytania kodu innych ludzi. 

Patrząc na huffile.h, w komentarzach deklaruje warstwę abstrakcji dla plików zakodowanych Huffman. Jeśli idziemy w dół, widzimy, że jest maksymalnie 256 znaków, które możemy potrzebować kody. Obejmuje to wszystkie litery alfabetu - wielkich i małych - a następnie symbole i numery, itp. Następnie mamy tu magicznej liczby identyfikujące Huffman kodowalne plik. W ramach kodu Huffmana, że ​​będziemy mieć pewne magiczne związane z nagłówka. Może to wyglądać jak zwykłe liczby losowej magii, jeśli jednak to przetłumaczyć na ASCII, to faktycznie literuje Huffa. Tutaj mamy struct dla pliku Huffman zakodowany. Nie wszystkie z tych cech związanych z plikiem Huff. Potem tu mamy nagłówek pliku Huff, więc nazywamy to Huffeader zamiast dodawania dodatkowej godziny, ponieważ dźwięki tak samo. Cute. Mamy magiczną liczbę z nim związane. Jeśli jest to właściwy plik Huff, to będzie numer górze, ta magia jeden. A potem będzie miał tablicę. Tak więc dla każdego symbolu, które są 256 to będzie lista, co częstotliwość tych symboli są w pliku Huff. I w końcu, mamy sumy kontrolnej częstotliwości, które powinny być suma tych częstotliwości. Więc to Huffeader jest. Następnie mamy do niektórych funkcji, które zwracają następny bit w pliku Huff oraz zapisuje w pliku bitu Huff, a następnie funkcja tu hfclose, faktycznie zamyka Huff. Wcześniej, mamy do czynienia z prostą tylko fclose, ale gdy masz plik Huff zamiast fclosing go co się naprawdę dzieje zrobić to hfclose i hfopen go. To są konkretne zadania do plików Huff, że idziemy do czynienia. To tutaj czytamy w nagłówku, a następnie napisać nagłówek. 

Tuż po przeczytaniu pliku. H możemy trochę zorientować się, co plik Huff może być, jakie cechy posiada, bez konieczności wchodzenia w huffile.c, które, jeśli będziemy nurkować w, będzie nieco bardziej złożona. Posiada on wszystkie pliku I / O tutaj do czynienia ze wskaźnikami. Tutaj widzimy, że gdy nazywamy hfread, na przykład, to jeszcze do czynienia z fread. Nie mamy pozbyć tych funkcji do końca, ale wysyłamy które będą pod opieką wewnątrz pliku Huff zamiast robić wszystko sami. Możesz tutaj skanować przez to, jeśli jesteś ciekawy i iść i skórką warstwy tylnej bitowym mało. 

Następny plik, że będziemy patrzeć na to tree.h. Przed w Walkthrough slajdy powiedzieliśmy oczekujemy Huffman węzeł i zrobiliśmy typedef struct węzeł. Spodziewamy się, że ma symbol, częstotliwość, a następnie 2 węzłów gwiazdy. W tym przypadku to, co robimy, jest to w zasadzie takie same wyjątkiem zamiast węzła będziemy nazywać ich drzew. Mamy funkcję, która podczas rozmowy, aby drzewo to powrót wskaźnika drzewa. Powrót do Speller, kiedy robili nowy węzeł mówiłeś node * new word = malloc (sizeof) i takie rzeczy. Zasadniczo mktree będzie się zajmować, że dla Ciebie. Podobnie, gdy chcesz usunąć drzewo, więc to zasadniczo uwalniając drzewo kiedy skończysz z nim, zamiast jawne wywołanie bezpłatny, że jesteś rzeczywiście tylko będzie użyć funkcji rmtree gdzie przechodzą w wskaźnik do tego drzewa, a następnie tree.c zajmie to za Ciebie. 

Patrzymy w tree.c. Oczekujemy te same funkcje z wyjątkiem patrz realizacji, jak również. Zgodnie z naszymi oczekiwaniami, gdy dzwonisz mktree to mallocs wielkość drzewa do wskaźnika, inicjalizuje wszystkie wartości na NULL, więc 0s lub wartości null, i zwraca wskaźnik do tego drzewa, które właśnie malloc'd do Ciebie. Oto kiedy zadzwonić usunąć drzewo najpierw upewnia się, że nie jesteś podwójnie uwolnienie. To daje pewność, że faktycznie masz drzewo, które chcesz usunąć. Tu, ponieważ drzewo obejmuje również jego dzieci, co to robi to rekursywnie wywołuje usunąć drzewo na lewym węźle drzewa oraz prawego węzła. Przed uwalnia rodzica, musi uwolnić dzieci, jak również. Dominująca jest też zamiennie z korzenia. Pierwszy w historii rodzic, więc jak pra-pra-pra-pra-dziadek lub drzewa babcia, najpierw musimy uwolnić dół poziom pierwszy. Więc przechodzić do dna, wolne osoby, a następnie wrócić do góry, uwolnić tych, itd. Więc to drzewo. 

Teraz patrzymy na las. Las jest gdzie umieścić wszystkie drzewa Huffmana. Jest powiedzenie, że będziemy mieć coś, co nazywa działki które zawiera wskaźnik do drzewa oraz wskaźnik do powierzchni zwanej dalej. Co robi struktura tego rodzaju wygląda? To niby mówi to tam. Prawo tutaj. Połączonej listy. Widzimy, że gdy mamy działkę to jak połączonej listy działek. Las zdefiniowane jako połączonego listy działek i tak struktura lasu jest my po prostu będziemy mieć wskaźnik do naszej pierwszej działce i że działka ma drzewo w jego obrębie, a raczej wskazuje na drzewie i wskazuje następną działki, itd. itd.. Aby do lasu nazywamy mkforest. Następnie mamy kilka bardzo przydatnych funkcji, tutaj. Musimy wybrać, gdzie przechodzą w lesie, a następnie zwracana jest wartość * Drzewo, wskaźnik do drzewa. Jakie pick będzie zrobić to to pójdzie do lasu, że jesteś wskazując następnie usunąć drzewo o najniższej częstotliwości z tego lasu a następnie daje wskaźnik do tego drzewa. Kiedy zadzwonić pick, drzewo nie będzie istnieć w lesie już, ale zwracana wartość jest wskaźnikiem do tego drzewa. Następnie trzeba roślinę. Pod warunkiem, że jest przekazywana w postaci wskaźnika do drzewa, które ma non-0 częstotliwości, co roślina będzie zrobić to potrwa do lasu, trochę drzew i roślin, że w środku drzewo z lasu. Tutaj mamy rmforest. Podobne do usunięcia drzewa, które w zasadzie uwolnił wszystkich naszych drzew, dla nas, usunąć las uwolni co jest zawarte w tym lesie. 

Jeśli spojrzymy na forest.c będziemy oczekiwać co najmniej 1 rmtree polecenia tam, bo do wolnej pamięci w lesie, jeśli las ma drzew w nim, następnie w końcu będziesz musiał usunąć te drzewa też. Jeśli spojrzymy na forest.c, mamy mkforest, który jest, jak oczekujemy. Mamy malloc rzeczy. Inicjujemy pierwszą działkę w lesie za nieważną, ponieważ jest pusta, aby rozpocząć, wtedy widzimy kostkę, która zwraca drzewo o najniższej masie, najniższej częstotliwości, a potem pozbywa się tego konkretnego węzła, który wskazuje na to drzewo, a następny, tak, że trwa, że ​​z połączonej listy lasu. A potem mamy tutaj rośliny, która wstawia się drzewo do połączonej listy. Co to jest las nie ładnie utrzymuje go posortowane dla nas. I w końcu, mamy rmforest i, zgodnie z oczekiwaniami, mamy rmtree nazywany tam. 

Patrząc na kod dystrybucji dotąd huffile.c było prawdopodobnie zdecydowanie najtrudniejszy do zrozumienia, natomiast inne pliki same były dość proste do naśladowania. Dzięki naszej wiedzy i listy wskaźników powiązanych oraz takich, byliśmy w stanie śledzić całkiem dobrze. Ale wszystko, czego potrzebujesz, aby naprawdę mieć pewność, że w pełni zrozumieć, jest pliki. H bo trzeba być wywołaniem tych funkcji, do czynienia z tych wartości powrotnych, więc upewnij się, że w pełni zrozumieć, jakie działanie ma być wykonywane kiedy tylko zadzwonić pod jeden z tych funkcji. Ale w rzeczywistości zrozumienie jej wnętrzu nie jest bardzo potrzebne, bo mamy te pliki. H. Mamy 2 więcej plików pozostawionych w naszym kodzie dystrybucji. 

Spójrzmy na wysypisko. Dump przez jego komentarz tutaj zajmuje Huffman-skompresowany plik a następnie przekłada i zrzuca wszystkie jego zawartości na zewnątrz. Tutaj widzimy, że to dzwoni hfopen. Jest to rodzaj dublowanie się plik wejściowy * = fopen, a następnie przesuń w informacji. To jest prawie identyczne, z wyjątkiem zamiast pliku * jesteś przechodzącej w Huffile; zamiast fopen jesteś przejazdem w hfopen. Oto czytamy w nagłówku pierwsze, co jest raczej podobny do tego, jak czytamy w nagłówku dla plików graficznych. Co my tu robimy jest sprawdzenie, czy informacje nagłówka zawiera odpowiednią liczbę magiczną wskazującą, że jest to właściwy plik Huff to wszystko z tych kontroli, aby upewnić się, że plik jest otwarty, że rzeczywista huffed plik czy nie. Co to znaczy, że wyprowadza częstotliwości wszystkie symbole, które możemy zobaczyć w terminalu w graficznym tabeli. Ta część będzie przydatna. Ma trochę i czyta po trochu do zmiennej trochę i następnie drukuje go. Więc gdybym miał zadzwonić zrzut na hth.bin, co jest wynikiem huffing plik używając roztworu personel, że dostanę to. To wyprowadzanie tych wszystkich znaków, a następnie oddanie częstotliwość ich wyświetlania. Jeśli spojrzeć, większość z nich to 0s poza tym: H, który pojawia się dwukrotnie, i T, które pojawia raz. A potem mamy tutaj rzeczywistą wiadomość w 0s i 1s. Jeśli spojrzymy na hth.txt, która jest przypuszczalnie oryginalna wiadomość, która została wzburzona, możemy spodziewać się jakiś Hs i TS tam. W szczególności, możemy spodziewać się w odległości zaledwie 1 T i 2 HS. Jesteśmy w hth.txt. To rzeczywiście ma HTH. Zawarte w tam, choć nie możemy go zobaczyć, to znak nowej linii. Hth.bin plik Huff jest również kodowanie znak nowej linii, jak również. Tutaj, bo wiemy, że zamówienie jest HTH i linią, widzimy, że prawdopodobnie H jest reprezentowany przez tylko 1 pojedynczym T i 01 i jest prawdopodobnie to następne H 1 oraz a następnie mamy newline pokazywane dwoma 0s. Cool. 

I wreszcie, ponieważ mamy do czynienia z wieloma. C i pliki. H, będziemy mieć całkiem złożone argument do kompilatora, i tak mamy tu sprawia, że ​​zrzut Makefile dla ciebie. Ale faktycznie, trzeba przejść o własne puff.c plik. Makefile w rzeczywistości nie zajmuje się co puff.c dla Ciebie. Wychodzimy, że do ciebie należy edytować plik Makefile. Po wpisaniu polecenia jak zrobić wszystko, na przykład, to pozwoli im wszystkim za Ciebie. Zapraszam do obejrzenia przykładów Makefile z przeszłości Pset jak również nie schodzili z tym jednym, aby zobaczyć jak może być w stanie zrobić plik Puff edytując tę ​​Makefile. To wszystko dla naszego kodu dystrybucyjnego. 

Gdy staliśmy się przez to, to tutaj jest po prostu kolejne przypomnienie jak będziemy mieć do czynienia z węzłami Huffmana. Nie zamierzamy się nazywając je węzły już, idziemy się nazywając je drzewa gdzie będziemy reprezentować ich symbolu z char, ich częstotliwości, liczba zdarzeń, z całkowitą. Używamy, bo to jest bardziej dokładny niż pływaka. A potem mamy kolejny wskaźnik do lewego dziecka, jak i dla dziecka w prawo. Las, jak widzieliśmy, jest tylko linked lista drzew. Ostatecznie, gdy budujemy nasz plik Huff chcemy, aby nasz las zawierać tylko 1 drzewo - 1 drzewo, 1 korzeń z wieloma dziećmi. Wcześniej, gdy byliśmy tylko co nasze drzewa Huffmana, zaczęliśmy poprzez umieszczenie wszystkich węzłów na naszym ekranie i mówiąc będziemy mieć te węzły, W końcu będziesz w liście, i to jest ich symbol, to jest ich częstotliwość. W naszym lesie, jeśli mamy tylko 3 litery, to las 3 drzew. A potem jak iść dalej, gdy dodaliśmy pierwszego rodzica, zrobiliśmy las 2 drzew. Usunęliśmy 2 z tych dzieci z naszego lasu, a potem zastąpił go węzła nadrzędnego że mieli te 2 węzły jak dzieci. I w końcu, nasz ostatni krok w dokonaniu nasz przykład z AS, BS i Cs byłoby dokonać ostatecznego rodzica, a więc wtedy, że przyniesie naszą całkowitą liczbę drzew w lesie 1. Czy wszyscy zobaczyć, jak zaczniesz się z wielu drzew w lesie i kończy się z 1? Okay. Cool. 

Co musimy zrobić dla Puff? Co musimy zrobić, to upewnić się, że, jak zawsze, dają nam odpowiedni rodzaj wejścia tak, że rzeczywiście możemy uruchomić program. W tym przypadku, że będą dawać nam po pierwszym argument wiersza polecenia 2 więcej: Plik, który chcemy rozpakować i wyjście rozpakowanego pliku. Ale gdy mamy pewność, że mijają nas w odpowiedniej ilości wartości, to mieć pewność, że wejście jest plik Huff, czy nie. A następnie raz możemy zagwarantować, że jest to plik Huff, to chcemy budować naszą drzewo zbudować drzewo tak, że pasuje do drzewa, że ​​osoba, która wysłała wiadomość zbudowany. Następnie po budujemy drzewo, to może mamy do czynienia z 0s i 1s, że minęli się, nazwom wzdłuż naszego drzewa, ponieważ jest identyczny, a potem napisać, że przesłanie, interpretują bity z powrotem do znaków. A potem na końcu, ponieważ mamy do czynienia ze wskaźnikami tutaj Chcemy się upewnić, że nie mamy żadnych wycieków pamięci i że mamy wolne wszystko. 

Zapewnienie prawidłowego użytkowania jest stary kapelusz dla nas teraz. Bierzemy w wejście, które ma być nazwa pliku, sapać, a potem określić wyjście, więc nazwa pliku na dmuchanej wyjścia, który będzie plikiem tekstowym. To użytkowania. I chcemy obecnie aby wejściowy huffed lub nie. Wracając, było coś w kodzie dystrybucji, które mogą pomóc nam ze zrozumieniem, czy plik jest wzburzona, czy nie? Nie było informacji w huffile.c o Huffeader. Wiemy, że każdy plik Huff ma Huffeader skojarzony z magicznej liczby a także tablica z częstotliwości dla każdego symbolu jak również sumy kontrolnej. Wiemy o tym, ale wzięliśmy również okiem na dump.c, w którym czytał w pliku Huff. I tak, aby to zrobić, musiał sprawdzić, czy to naprawdę była wzburzona, czy nie. Więc może moglibyśmy użyć dump.c jako struktury naszego puff.c. Powrót do PSET 4 kiedy mieliśmy copy.c pliku, skopiowany w trójek RGB i interpretować, że kryminał i rozmiaru, podobnie, co można zrobić, to uruchomić polecenie jak cp dump.c puff.c i korzystać z niektórych kodu tam. Jednakże, nie będzie w prosty procesu do tłumaczenia się dump.c do puff.c, ale przynajmniej daje gdzieś zacząć jak zapewnić, że sygnał wejściowy jest albo nie faktycznie huffed jak również kilku innych rzeczy. Mamy zapewnione prawidłowego użytkowania i zapewnił, że wejście jest wzburzona. Za każdym razem, że zrobiliśmy, że wykonaliśmy naszą prawidłowe sprawdzanie błędów, więc powrót i wyjście z funkcji, jeśli niektóre wystąpienia awarii, jeśli jest problem. 

Teraz to, co chcemy zrobić, to zbudować rzeczywiste drzewo. Jeśli spojrzymy w lesie, są 2 główne funkcje że będziemy chcieli się bardzo znane. Jest logiczne, że rośliny, roślin, funkcja non-0 drzewo częstotliwości wewnątrz naszego lasu. I tak nie jest przekazywana w postaci wskaźnika do lasu oraz wskaźnik do drzewa. Szybkie pytanie: Ile lasów trzeba będzie kiedy budowanie drzewa Huffmana? Nasz las jest jak nasz płótnie, prawda? Więc jesteśmy tylko będziemy mieć 1 las, ale będziemy mieć wiele drzew. Więc zanim zadzwonisz zakład, jesteś prawdopodobnie będzie chciał dokonać las. Jest poleceniem, że jeśli spojrzeć na forest.h jak można zrobić las. Możesz zasadzić drzewo. Wiemy, jak to zrobić. A następnie można również wybrać się na drzewo z lasu, usunięcie drzewa z najmniejszej masie i daje wskaźnik do tego. Wracając do tego, kiedy robiliśmy przykłady siebie, kiedy byliśmy rysowania go, po prostu po prostu dodaje linki. Ale tutaj zamiast dodawania linków myśleć bardziej jak jesteś usunięcie 2 z tych węzłów, a następnie zastąpienie go innym. Aby wyrazić, że w zakresie zbierania i sadzenie, jesteś zbierając 2 drzew i sadzenia inne drzewo że ma te 2 drzewa, które wybrałeś jako dzieci. Aby zbudować drzewo Huffmana jest, można przeczytać w symbole i częstotliwości w celu bo Huffeader daje to do ciebie, daje tablicę częstotliwości. Tak więc można śmiało i po prostu zignoruj ​​z 0 w nim bo nie chcemy 256 Liście na koniec. Chcemy tylko liczbę liści, które są znaki które są używane w pliku. Można przeczytać w tych symboli, a każdy z tych symboli, które non-0 częstotliwości, te będą drzewa. Co możesz zrobić, to za każdym razem czytać w non-0 symbol częstości można sadzić, że drzewa w lesie. Kiedy sadzić drzewa w lesie, można dołączyć te drzewa jako rodzeństwo, więc wracając do sadzenia i zbierania gdzie wybrać 2, a następnie roślin 1, jeżeli 1, że roślina jest rodzic z 2 dzieci, które wybrałeś. Więc Twój wynik końcowy będzie pojedyncze drzewa w lesie. W ten sposób można zbudować swoje drzewo. 

Jest kilka rzeczy, które mogą pójść źle tutaj ponieważ mamy do czynienia z wykonaniem nowych drzew i radzenia sobie z wskaźniki i tego typu rzeczy. Wcześniej, kiedy mieliśmy do czynienia ze wskaźnikami, ilekroć malloc'd chcieliśmy się upewnić, że nie zwróci nam wartość NULL wskaźnika. Tak więc w kilku etapach w tym procesie nie będą kilka przypadków gdzie program może się nie powieść. Co chcesz zrobić, to chcesz się upewnić, że można obsłużyć te błędy, w specyfikacji jest napisane, aby obsługiwać je z wdziękiem, tak jak wydrukować wiadomość do użytkownika mówiąc im, dlaczego program ma zakończyć a następnie szybko zamknąć go. Aby to zrobić, obsługę błędów, pamiętaj, że chcesz, aby to sprawdzić za każdym razem, że nie może być porażką. Za każdym razem, że robisz nowy wskaźnik chcesz się upewnić, że to jest sukces. Przed tym, co kiedyś zrobić, to nowy wskaźnik i malloc to, i wtedy możemy sprawdzić, czy wskaźnik jest NULL. Więc nie będą pewne przypadki, gdzie po prostu można zrobić, ale czasami jesteś rzeczywiście wywołanie funkcji oraz w ramach tej funkcji, to jest taki, który robi się mallocing. W tym przypadku, jeśli spojrzymy na niektóre z funkcji w kodzie, niektóre z nich są funkcje logiczne. W abstrakcyjnym przypadku jeśli mamy logiczną funkcję o nazwie foo, w zasadzie można przyjąć, że oprócz robi cokolwiek foo robi, ponieważ jest to funkcja logiczna, zwraca true lub false - true, jeśli sukces, false jeśli nie. Dlatego chcemy, aby sprawdzić, czy wartość zwracana foo jest prawdziwe lub fałszywe. Jeśli jest fałszywe, to oznacza, że ​​będziemy chcieli wydrukować jakieś wiadomości a następnie zamknij program. To, co chcemy zrobić, to sprawdzić wartość zwracaną foo. Jeśli foo zwraca false, wtedy wiemy, że napotkał jakiś błąd i musimy zakończyć nasz program. Sposobem na to jest mieć stan, w którym rzeczywista funkcja sam jest twój stan. Powiedz foo bierze w x. Możemy mieć za warunek if (foo (x)). Zasadniczo oznacza to, czy pod koniec realizacji foo zwraca prawda możemy to zrobić, ponieważ funkcja ma ocenić foo W celu oceny stanu cały. Więc to jest to, jak można zrobić coś, jeśli funkcja zwraca true i jest sukces. Ale kiedy jesteś sprawdzanie błędów, chcesz tylko rzucić, jeśli funkcja zwraca false. Co można zrobić, to po prostu dodaj == false lub po prostu dodać huk przed nim a potem masz if (! foo). W ramach tego organu tego warunku można mieć wszystkie obsługi błędów tak jak, "Nie można utworzyć tego drzewa", a następnie powrót 1 lub coś podobnego. Co to robi, jednak to, że nawet jeśli foo zwrócone false - Powiedz foo zwraca true. Wtedy nie trzeba wywołać foo ponownie. To błędne przekonanie. Dlatego, że był w stanie, to już ocenione, więc masz już wynik jeśli używasz zrobić drzewo czy coś takiego roślin lub pick czy coś. Ma już tę wartość. To już wykonana. Więc jest to przydatne do korzystania z funkcji boolowskich jako warunek z powodu tego, czy rzeczywiście wykonania tej pętli, wykonuje funkcję tak. 

Nasz drugi do ostatniego kroku jest pisanie wiadomości do pliku. Gdy budujemy drzewa Huffmana, to pisanie wiadomości do pliku jest bardzo proste. Jest to dość proste, teraz wystarczy wykonać 0s i 1s. I tak umownie wiemy, że w drzewie Huffmana na 0s wskazują lewo i 1s wskazać prawo. Więc jeśli czytasz w bit po bicie, za każdym razem, że masz 0 pójdziesz za lewą gałąź, a następnie za każdym razem czytać w 1 będziesz podążać właściwą gałąź. A potem idziesz dalej, aż trafisz liść ponieważ liście będzie na końcu gałęzi. Jak można powiedzieć, czy mamy uderzyć liść czy nie? Powiedzieliśmy wcześniej. [Uczeń] Jeżeli wskaźniki są NULL. >> Tak. Możemy powiedzieć, czy mamy uderzyć liść czy wskaźniki do drzew zarówno lewego i prawego są NULL. Perfect. Wiemy, że chcemy czytać krok po kroku do naszego pliku Huff. Jak widzieliśmy wcześniej w dump.c, to co zrobili to czytali w bit po bicie do pliku Huff i po prostu wydrukować, co te bity były. My nie zamierzamy tego robić. Będziemy robić coś, co jest nieco bardziej złożona. Ale co możemy zrobić, to możemy przyjąć, że fragment kodu, który czyta się na chwilę. Tutaj mamy trochę całkowitą reprezentującą aktualny trochę, że żyjemy. To pozwala na iterację wszystkich bitów w pliku aż dojdziesz do końca pliku. Na podstawie tego, to będziesz chciał mieć jakiś iterator przechodzenie drzewa. , A następnie na podstawie tego, czy bit jest 0 lub 1, będziesz chciał albo przenieść te iteracyjnej w lewo lub przesunąć go w prawo do końca, aż trafisz na skrzydło, tak do końca, aż w tym węźle, na której jesteś nie wskazuje na jakiekolwiek inne węzły. Dlaczego możemy to zrobić z plikiem, ale nie Huffmana alfabetem Morse'a? Ponieważ w kodzie Morse'a jest trochę niejasności. Moglibyśmy być jak, oh wait, mamy hit list po drodze, więc może to jest nasz list, natomiast jeżeli będziemy kontynuować tylko nieco dłużej, to wtedy mają trafić kolejne pismo. Ale to nie wydarzy się w kodowaniu Huffmana, więc możemy mieć pewność, że tylko w ten sposób mamy zamiar uderzyć znak jest, jeśli ten węzeł jest lewa i prawa dzieci są NULL. 

Wreszcie, chcemy uwolnić wszystkie z naszej pamięci. Chcemy zarówno zamknąć plik Huff, że mamy do czynienia z , jak również usunięcie wszystkich drzew w naszym lesie. W oparciu o swoje życie, pewnie będzie chciał zadzwonić usunąć las zamiast rzeczywiście będzie przez wszystkie drzewa samodzielnie. Ale jeśli masz już tymczasowe drzewa, będziemy chcieli, aby uwolnić to. Wiesz kod najlepiej, więc wiesz, gdzie jesteś przydzielania pamięci. A więc jeśli jesteś w, zaczynaj nawet kontrolować F'ing dla malloc, widząc kiedykolwiek malloc i upewniając się, że wszystko to uwolnić ale potem po prostu się przez kod, zrozumienie, gdzie mogłeś przydzielonej pamięci. Wysyłka może po prostu powiedzieć: "Na końcu pliku Idę do usunięcia lasu na moim lesie" więc w zasadzie jasne, że pamięć, wolne, że ", A następnie Mam zamiar zamknąć plik, a następnie mój program będzie zamknąć." Ale jest to, że tylko raz, że program zostanie zamknięty? Nie, bo czasami może być błąd, że się stało. Może nie mógł otworzyć pliku lub nie mogliśmy dokonać innego drzewa lub jakiś błąd się w proces alokacji pamięci i dlatego zwróciło NULL. Wystąpił błąd, a potem wróciliśmy i zamknąć. Więc chcesz, aby upewnić się, że każdy możliwy czas, że program można zamknąć, Aby zwolnić wszystkich pamięci tam. To nie tylko będzie na samym końcu głównej funkcji, którą zamknąć kod. Chcesz spojrzeć na każdy przykład, że Twój kod potencjalnie może wrócić przedwcześnie a następnie wolne cokolwiek pamięci sens. Powiedzmy, że nazwał się las i że wrócił false. To prawdopodobnie nie będzie trzeba usunąć las bo nie masz jeszcze las. Ale w każdym miejscu w kodzie, gdzie można wrócić przedwcześnie Aby upewnić się, że ewentualne zwolnienia pamięci. 

Tak więc, gdy mamy do czynienia z zwolnienie pamięci i konieczności ewentualnych nieszczelności, Chcemy nie tylko wykorzystać nasz osąd i logiki ale również użyć Valgrind aby ustalić, czy my wszyscy uwolnieni naszej pamięci prawidłowo. Można uruchomić Valgrind na Puff i wtedy musisz również przekazać je właściwa liczba argumentów wiersza polecenia do Valgrind. Można uruchomić, ale wyjście jest nieco tajemnicze. Staliśmy się trochę przyzwyczaić do Speller, ale nadal potrzebujemy nieco więcej pomocy, tak to działa to z kilku flag bardziej jak szczelne check = pełna, które prawdopodobnie dać nam trochę więcej jako wyjście na Valgrind. 

Następnie kolejna przydatna wskazówka kiedy jesteś debugowania jest komenda diff. Możesz przejść personel na realizację Huff, biegać, że w pliku tekstowym, , a następnie wyświetli ją do pliku binarnego, plik binarny Huff, za szczególne. Następnie, jeśli prowadzisz własną puff tego pliku binarnego, potem idealnie, Twój wyprodukowania plik tekstowy ma być identyczna do pierwotnego, który przeszedł w. Tutaj używam hth.txt jako przykład, i to jest jeden mówił o w spec. To dosłownie HTH a następnie linią. Ale na pewno czuć się swobodnie i jesteś zdecydowanie zachęca się do używania dłuższych przykładów do pliku tekstowego. 

Możesz nawet być może szansę na kompresowanie i dekompresję niektóre z plików, które wykorzystywane w Speller jak wojny i pokoju lub Jane Austen, czy coś w tym stylu - to byłoby fajne - czy Austin Powers, rodzaj czynienia z większymi plikami, ponieważ nie chciał przyjść do niego jeśli użyliśmy następne narzędzie tutaj, ls-l. Jesteśmy przyzwyczajeni do ls, które zasadniczo wymienia wszystkie treści w naszym katalogu. Przekazując flag-l rzeczywiście wyświetla wielkość tych plików. Jeśli przejdziesz przez spec PSET, faktycznie poprowadzi Cię przez proces tworzenia pliku binarnego, z huffing go, a zobaczysz, że dla bardzo małych plików Koszt przestrzeń ściskając go i tłumaczenie wszystkich tych informacji wszystkich częstotliwości i tego typu rzeczy przewyższają rzeczywiste korzyści sprasowania plik w pierwszej kolejności. Ale jeśli go uruchomić na kilka dłuższych plików tekstowych, to może zobaczyć, że zaczynają się pewne korzyści w kompresji tych plików. 

I w końcu mamy naszą starą GDB PAL, która na pewno będzie przydatna, too. 

Czy mamy jakiekolwiek pytania dotyczące drzew Huff lub proces może dokonywania drzewa lub jakiekolwiek inne pytania dotyczące Puff Huff'n? Okay. Zostanę wokół na trochę. 

Dzięki wszystkim. To był Walkthrough 6. Powodzenia. 

[CS50.TV]