[Powered by Google Translate] [Валктхроугх - Проблем Сет 6] [Замила Цхан - Универзитет Харвард] [Ово је ЦС50. - ЦС50.ТВ] 

Поздрав свима, и добродошли у Валктхроугх 6: Хуфф'н Пуфф. У Хуфф'н Пуфф шта ми радимо ће се бавити Хуффман компримоване датотеке па хукће га назад, тако да декомпримовање, тако да можемо да преведе из 0с и 1с да корисник нам шаље и претворити га назад у оригиналном тексту. Псет 6 ће бити прилично кул јер идете да видите неке од алата које сте користили у псет 4 и 5 псет и врсте њиховог комбиновања у 1 прилично уредан концепта када дођете да мислим о томе. 

Такође, вероватно, псет 4 и 5 су најизазовније псетс које смо имали у понуди. Дакле, од сада, имамо ту још 1 псет у Ц, и после тога смо на веб програмирање. Дакле честитам себе за добијање преко најтежу грба у ЦС50. 

Померање на за Хуфф'н Пуфф, наш тоолбок за ову псет ће бити Хафман дрвеће, па разумевању не само како бинарни дрвеће рад, већ и конкретно Хафман дрвеће, како су они изграђени. А онда ћемо имати много дистрибутивне кода у овом псет, и ми ћемо доћи да видимо да заиста неке од кода можда нећемо бити у могућности да у потпуности разумеју ипак, па они ће бити ц филес., али онда њихови пратећи х фајлове. ће нам дати довољно разумевања да нам је потребно да знамо како те функције раде или бар оно што би требало да раде - њихови улази и излази - чак и ако не знамо шта се дешава у црној кутији или не разумеју шта се дешава у црној кутији изнутра. И онда на крају, као и обично, ми се суочавамо са новим структурама података, специфичне врсте чворова који указују на одређене ствари, па овде има оловку и папир, не само за процес пројектовања и када покушавате да схватите како ваш псет треба да раде али и током дебаговање. Можете имати ГДБ поред вашег папиром и оловком, док се ви доле шта су вредности, где се ваши стрелице пажњу, и такве ствари. 

Прво погледајмо Хуффман дрвећа. Хуффман дрвеће бинарна стабла, што значи да сваки чвор има само 2 деце. У Хуффман стабала карактеристично је да су најчешћи вредности су представљени са најкраћим битова. Видели смо у предавању примерима Морзеова азбука, која врста консолидоване нека слова. Ако покушавате да преведе А или Е, за пример, ви превођење тако често, тако да уместо да користи цео скуп битова издвојено за ту уобичајени тип података, можете га сабити до мање, и онда та писма које су се представиле ређе су заступљени са дужим бита јер можете себи приуштити да кад одмерити фреквенције које та писма појављују. Имамо исту идеју овде у Хуффман дрвећу где смо праве ланац, врста путу да дођемо до одређених ликова. А онда су ликови који имају највише фреквенције ће бити представљени са најмањим битова. 

Начин на који сте изгради Хуффман трее је постављањем свих ликова који се појављују у тексту и израчунавање њихову учесталост, колико често се појављују. Ово би могао да буде или бројање колико је пута та писма појављују или можда проценат од свих ликова колико сваки од њих се појављује. И шта треба да урадите је када имате све те зацртали, онда тражити 2 најнижим фреквенцијама и затим их придруже као браћу и сестре где онда родитељ чвор има фреквенцију која је збир његових 2 деце. И онда по обичају кажу да лево чвор, пратите да је после 0 грану, а затим десна крајња чвора је 1 грана. Као што смо видели у Морзеова азбука, један готцха је да ако сте имали само бип и тон било је двосмислено. Или би могао да буде 1 писмо или би могао да буде низ од 2 слова. И шта Хафман дрвеће ради је због природе ликова или наши финални стварни ликови као последњи чворови на грани - мислимо на оне као лишће - на основу тога не може бити никакве двосмислености у смислу које слово које покушавате да кодира са низом битова јер нигде дуж битова који представљају 1 писмо ћете наићи на још једну целу слово, и неће бити забуне. Али ми ћемо ићи у примерима да ви заправо видите да уместо нас само ти кажем да је то истина. 

Хајде да погледамо једноставан пример Хуффман дрвета. Имам ниску овде који је 12 знакова. Имам 4 ас, 6 БС, и 2 ЦС. Мој први корак би био да се рачунају. Колико пута се појављују? Изгледа 4 пута у низу. Б појављује 6 пута, и Ц се појављује 2 пута. Наравно, ја ћу рећи да сам помоћу Б најчешће, тако да желим да представљају Б са најмањим бројем битова, најмањи број 0с и 1с. А онда сам ћу да очекују Ц да захтевају највише количину 0с и 1с, као добро. Прво што сам урадио је да сам овде да их ставља у растућем редоследу у погледу учесталости. Видимо да је Ц и то су наши 2 најниже фреквенције. Ми стварамо родитељ чвор, а да родитељ чвор нема писмо у вези са њом, али има фреквенцију, што је сума. Збир постаје 2 + 4, што је 6. Затим пратимо леву грану. Ако смо били на том чвору 6, онда ће уследити 0 доћи до Ц и онда 1 доћи до А. Дакле, сада имамо 2 чворова. Имамо вредност 6, а онда имамо и другу чвор са вредношћу 6. И тако они 2 нису само 2 најнижа али само 2 да су отишли, тако да смо се придруже онима други родитељ, а сума бити 12. Дакле, овде имамо Хуффман дрво где да дођете до Б, да би само био мало 1 и онда доћи до ћемо имати 01, а затим Ц имају 00. Дакле, овде видимо да је у основи смо представљање ове знакова са 1 или 2 бита где је Б, као што је предвиђено, има најмање. И онда смо очекивали Ц имају већину, али пошто је то што мали Хафман дрво, онда је такође представљен 2 бита насупрот негде у средини. 

Само да иде преко другог једноставног пример Хуффман дрвета, Рецимо да имате ниску "Здраво." Шта треба да урадите је прво што би рекли колико пута БиХ појављује у ово? БиХ се појављује једном и затим е се појављује једном и онда имамо л појављује два пута и о појави једном. И тако онда очекујемо које писмо да представља најмањи број битова? [Ученик] л. >> Л. Да. Ја је у праву. Очекујемо сам да представља најмањи број битова зато што сам се највише користи у низу "Здраво." Оно што ћу сада да урадим је извући ове чворове. Имам 1, која је Х, а затим још један 1, који је с, а затим 1, који су о - сада сам их стављајући у реду - и онда 2, који је сам. Онда кажем да је начин на који сам се изгради Хуффман стабло је да пронађе 2 чворове са најмањим фреквенцијама и да их браћу и сестре стварањем родитељ чвор. Овде имамо 3 чворова са најнижом учесталошћу. Они су све 1. Дакле, овде бирамо којих је једна ћемо прво повезати. Рецимо бирам Х и Е. Збир 1 + 1 је 2, али то чвор нема писмо у вези са њом. То је само држи вредност. Сада гледамо у наредне 2 најнижим фреквенцијама. То је 2 и 1. То би могао бити један од оних 2, али ја ћу изабрати ову. Ова сума је 3. И на крају, имам само 2 лево, па онда то постаје 5. Онда овде, како се очекује, ако попуните кодирања за то, 1с су увек у праву грана и 0с су лева. Онда имамо ја представљена само 1 бит а затим и ои од 2 а потом е по 2 и онда је Х падне на 3 бита. Дакле, можете да пренесе ову поруку "Здраво" уместо заправо користе знакове за само 0с и 1с. Међутим, имајте у виду да је у неколико случајева смо имали везе са нашим фреквенцију. Могли смо или придружили Х и о Прво можда. Или касније када смо имали л представљен 2 као и придружио један представљен са 2, могли смо повезани ни један. 

И тако, када сте послали 0с и 1с, који заправо не гарантује да прималац може у потпуности прочитао Вашу поруку директно ван палицом јер они не би знали која одлука коју сте дали. Дакле, када се бавимо Хуффман компресије, некако морамо рећи примаоца нашу поруку како смо одлучили - Они морају да знају неку врсту додатне информације Поред компримованог поруку. Они морају да схвате шта је дрво заиста изгледа, како смо заправо те одлуке. 

Овде смо само радили примере на основу стварног бројања, али понекад можете имати Хуффман дрво на основу учесталости којом слова појављују, и то је потпуно исти процес. Овде сам га изражавајући у смислу процента или део, па овде је потпуно исти ствар. Сматрам 2 најниже, сумирамо их, поред 2 најнижи их саберете, док имам пуну дрво. Иако смо могли то урадити ни начин, када имамо посла са процентима, то значи да смо поделу ствари и суочавања са децималама односно плута ако размишљате о структурама података у главу. Шта ми знамо о сплавова? Шта је чест проблем када имамо посла са сплавова? [Ученик] Непрецизно аритметика. >> Да. Непрецизности. Због непрецизности у покретном зарезу, за ову псет, тако да смо сигурни да не изгубимо никакве вредности, онда смо стварно ћемо се бавити пребројавања. Дакле, ако сте били да мислимо о Хуффман чвор, ако се осврнете на структуру овде, ако се осврнемо на зеленим оне што има фреквенцију у вези са њом као и да указује на чвору на својој левој, као и чвор да његове десне стране. А онда су црвене и тамо имају карактер повезан са њима. Нећемо да одвојене оне за родитеље и тада завршних чворови, што ми називамо лишће, већ они који ће тек имати НУЛЛ вредности. За сваки чвор ћемо имати карактер, симбол да је чвор представља, онда фреквенција, као и показивач на својој левој детету, као и њену десну детета. Листови, који су на самом дну, би такође имати чворова показиваче њиховој левој и на њихово право, али пошто те вредности нису указују на стварне чворова, шта би њихова вредност била? >> [Ученик] НУЛЛ. >> НУЛЛ. Управо тако. Ево примера како можете да представљају фреквенцију сплавова, али ми ћемо се бавити тим са целих бројева, па све што сам урадио је да промените ту тип података. 

Идемо на мало више од сложене пример. Али сада, када смо урадили једноставне моји, то је само исти процес. Можете наћи 2 најниже фреквенције, збир фреквенција и то је нова фреквенција вашег матичног чвора, што онда указује на њене леве стране са 0 гране и право са 1 гране. Ако имамо ниску "Ово је цс50", онда можемо рачунати колико пута се помиње Т, х поменуо, и, с, ц, 5, 0. Онда оно што сам овде урадио је са црвеним чворовима сам засада, Ја сам рекао да ћу имати ове знакове на крају на дну мог дрвета. Они ће бити све од лишћа. Онда оно што сам урадио је да сам их сортирају по фреквенцији у растућем редоследу, и то је заправо начин на који то ради код псет Она га је сортира по фреквенцији и затим по абецедном реду. Тако да има бројеве, а затим по абецедном реду по фреквенцији. Онда шта бих урадио је да сам ће наћи 2 најниже. То је 0 и 5. Ја би их саберете, а то је 2. Онда бих даље, наћи следећи 2 најниже. То су два 1с, а онда они постају 2 као добро. Сада знам да је мој следећи корак ће се придружити најмањи број, који је Т, 1, а затим изабрати један од чворова који има 2 као фреквенције. Дакле, овде имамо 3 опције. Оно што ћу да урадим за слајд је само визуелно их преуредили за вас тако да можете да видите како сам га изградњу. Шта код и ваша дистрибуција код ће урадити да се придружи Т један са 0 и 5 чвора. Па онда да се сумира до 3, и онда смо наставили процес. Од 2 и 2 сада су најниже, па онда они збир 4. Сви пратећи до сада? Ок. После тога имамо 3 и 3 који треба да се саберу, па опет ја само то пребацивање, тако да можете видети визуелно, тако да не добијете превише неуредан. Онда имамо 6, а онда је наш коначни корак је да имамо само 2 чворове саберемо оне чине корен нашег дрвета, које је 10. И број 10 има смисла јер је сваки чвор представљен, њихова вредност, њихова учесталост број, био је колико пута су се појавили у низу, и онда имамо 5 знакова у нашем низу, тако да има смисла. Ако погледамо горе како смо заправо би га кодирати, као што се очекује, ја и ова, која се појављују најчешће заступа најмањим бројем бита. 

Будите опрезни овде. У Хуффман дрвећа случај заправо битно. Слово С је другачија од малих слова с. Ако смо имали "Ово је ЦС50" са словима, а затим слово с би се појавити само два пута, би чвор са 2 као своје вредности, а затим велика С ће бити само једном. Дакле стабло ће променити структуру јер сте стварно овде додатни лист. Али сума ће и даље бити 10. То је оно што ми заправо ћеш се зовем цхецксум, додавање свих тачака оптужнице. 

Сада када смо покривени Хафман стабала, можемо заронити у Хуфф'н Пуфф, псет. Идемо да почну са једном делу питања, и то ће вас навикли са бинарним стаблима и како да раде око тога: цртање чворови, стварајући сопствени типедеф струцт за чвор, и видим како сте могли укључити у бинарном стаблу, онај који је сортиран, попречно га, и ствари попут тога. То знање је дефинитивно ће вам помоћи када зароните у Хуфф'н Пуфф дела од псет. У стандардном издању псет, ваш задатак је да спроведе Пуфф, и у хакерске верзији ваш задатак је да спроведе Хуфф. Шта Хуфф ради је потребно текст и онда га претвара се у 0с и 1с, тако да је процес који смо горе урадили где смо рачунали фреквенције а затим је дрво, а затим рекао: "Како ћу добити Т?" Т је представљен са 100, такве ствари, и онда Хуфф ће узети текст и онда излаз који бинарно. Али и због тога што знамо да желимо да дозволи нашу примаоца поруке да поново исти дрво, она такође садржи информације о учесталости бројања. Затим са Пуфф нам је дат бинарни фајл 0с и 1с и даје такође информације о фреквенцијама. Ми преводимо све оне 0с и 1с назад у оригиналној поруци која је, тако да смо декомпримовање то. Ако радиш стандардну верзију, не треба да спроведу Хуфф, па онда само можете да користите спровођење особља Хуфф. Постоје инструкције у спец како да се то уради. Можете да покренете спровођење особља Хуфф након одређеног текстуалној датотеци и онда користите тај излаз као улаз на Пуфф. 

Као што сам раније поменуо, имамо доста дистрибуцију кода за овај један. Ја ћу кренути кроз њега. Ја ћу да проводе већину времена на х датотеке. јер у ц фајлове., јер имамо х. и да нам даје прототипови функција, не треба у потпуности да разумеју тачно - Ако не разумете шта се дешава у Ц фајлове., Онда не брините превише, али дефинитивно покушати да погледамо, јер то може дати неке савете и то је корисно да се користи за читање код других људи. 

Гледајући хуффиле.х у коментарима проглашава слој апстракције за Хафман-кодираних датотека. Ако идемо на доле, видимо да постоји максимум 256 симбола који би нам треба кодове за. Ово укључује сва слова азбуке - велика и мала - а затим симболе и бројеве, итд Онда овде имамо чаробни број идентификације Хафман кодираних датотеку. У оквиру Хуффман кода они ће имати одређени број чаробну повезан са заглављем. То може изгледати као обична случајног магични број, али ако сте заиста га преведете на АСЦИИ, онда је то заправо набраја Хуфф. Овде имамо струцт за Хафман-кодираног фајл. Ту је све од ових карактеристика повезаних са Хуфф датотеку. Онда овде имамо заглавље за Хуфф фајл, па га зовемо Хуффеадер уместо додавања екстра х јер звучи исто свеједно. Слатко. Имамо чаробни број у вези са њом. Ако је стварна Хаф фајл, то ће бити број горе, ово магија једна. А онда ће имати низ. Дакле, за сваки симбол, од којих су 256, то ће навести шта је учесталост тих симбола су у Хуфф датотеке. И на крају, имамо цхецксум за фреквенције, који би требало да буде збир тих фреквенција. Дакле, то је оно што је Хуффеадер. Онда имамо неке функције које дају следећи бит у Хуфф фајлу као и пише мало у Хуфф фајлу, и онда ова функција овде, хфцлосе, који заправо затвара Хуфф датотеку. Пре него смо се бавили само стрејт фцлосе, али када имате Хуфф фајл, уместо да фцлосинг шта сте заправо ћеш да урадиш је да хфцлосе и хфопен га. То су специфичне функције на Хуфф датотека које ћемо да се бавимо. Онда ми овде читамо у заглављу, а затим написати заглавље. 

Само читајући х фајл. Можемо некако добили осећај шта Хаф датотека може бити, Које особине има, без одласка у хуффиле.ц, које, ако се зарони у, ће бити мало сложенија. Она има све датотеке И / О овдје баве показивача. Овде видимо да када зовемо хфреад, на пример, још увек има посла са фреад. Нећемо отарасили тих функција у потпуности, али ми шаљемо оне буду збринути унутар хуфф фајлу уместо радиш све то ми сами. Можете слободно да скенира кроз ово ако сте радознали и иди и пилинг слоју леђа мало. 

Следећи фајл који ћемо да погледамо је трее.х. Пре на Крсти клизи смо рекли да очекујемо Хуффман чвор и ми смо направили типедеф струцт цвор. Очекујемо да имају симбол, фреквенцију, а затим 2 чворова звезде. У овом случају оно што ми радимо је да је ово у суштини исти осим уместо чвора ћемо их зову дрвеће. Имамо функцију када зовете да вам то дрво враћа стабла показивач. Назад на Спеллер, када су правили нову чвор рекли сте чвор * нова реч = маллоц (сизеоф) и сличне ствари. У суштини, мктрее ће се бавити то за тебе. Слично томе, када желите да уклоните дрво, тако да је у суштини ослобађајући дрво кад завршиш са тим, уместо на експлицитно позивају бесплатно на то, ви заправо само планирате да користите функцију рмтрее где прође показивача на том дрвету и онда трее.ц ће се побринути за то уместо вас. 

Гледамо у трее.ц. Очекујемо исте функције, осим на имплементацију, као добро. Као што смо очекивали, када позовете мктрее га маллоцс величине стабла у показивача, иницијализује све вредности на НУЛЛ вредност, тако 0с или НУЛЛс, а онда се враћа показивач на том дрвету које сте управо маллоц'д вама. Овде када зовете уклонити дрво прво проверава да ниси дупло ослобађајуће. То чини сигурни да сте заиста имате дрво које желите да уклоните. Овде јер дрво такође укључује своје деце, шта је ово ради је то рекурзивно позива уклони дрво на левој чвор стабла као и право чвора. Пре него што је ослобађа родитеља, потребно је да ослободи децу, као добро. Родитељ је заменљива корена. Први икада родитељ, па као да је пра-пра-пра-пра-деда или баба дрво, прво морамо да ослободимо доле прво ниво. Дакле, пређите на дно, без њих, а онда се врати горе, без оних, итд Дакле, то је дрво. 

Сада гледамо шуму. Шума је место где можете поставити све ваше Хуффман дрвећа. Он каже да ћемо имати нешто зове завера који садржи показивач на дрвету, као и показивач на парцели поред назива. Шта структура чини ову врсту изгледају? Некако то каже тамо. Право овамо. Повезана листа. Видимо да када имамо заплет је као повезану листу парцела. Шума се дефинише као повезану листу парцела, па структура шума је да смо само ћемо морати показивач на нашем првом плаца и да парцела има стабло у њој односно указује на дрвету а затим указује на следећи заплет, и тако даље и тако даље. Да би шуму зовемо мкфорест. Онда имамо овде неке прилично корисне функције. Имамо изабрати где пролазе у шуми, а онда је повратна вредност је дрво * показивач на дрвету. Шта ће урадити јесте избор да ће отићи у шуму да си указујући затим извадите дрво са најнижом учесталошћу од тој шуми и онда вам дати показивач тог дрвета. Када позовете пицк, дрво неће постојати у шуми више, али је повратак вредност је показивач на том дрвету. Онда имате биљку. Под условом да прође у показивач на дрвету које има не-0 фреквенцију, шта биљка ће урадити је да ће бити потребно шуму, узми дрво, а биљка то дрво унутар шуме. Овде имамо рмфорест. Слично уклоне стабло, које у основи ослобођен свих наших стабала за нас, уклонити шуму ће ослободити све садржано у тој шуми. 

Ако погледамо у форест.ц ћемо очекујемо да видимо најмање 1 рмтрее команду тамо, јер да слободне меморије у шуми ако шума има стабала у њој, онда на крају ћеш морати да уклони те превише дрвећа. Ако погледамо у форест.ц, имамо мкфорест, који је као што смо очекивали. Ми маллоц ствари. Ми покрене прву радњу у шуми као НУЛЛ јер је празан на почетку, онда видимо трзалицу, који враћа на дрво са најнижим тежине, најниже фреквенције, и онда добија ослободити од тог чвора који указује на то дрво и следећи, тако да је потребно да од повезаног листи шуме. А онда овде имамо фабрику, која умеће лужњака на повезану листу. Шта шума не је то лепо држи га сортирају за нас. И на крају, имамо рмфорест и, како се очекује, имамо рмтрее зове тамо. 

Гледајући дистрибуције код до сада хуффиле.ц је вероватно далеко најтеже разумети, док остали фајлови сами били прилично једноставно да пратите. Са нашим знањем тројке и повезаних листама и таквих, били смо у могућности да пратимо прилично добро. Али, сви морамо да се заиста уверите се да смо у потпуности разумели је Х фајлове. зато што треба да се зове оне функције, које се баве тим повратак вредности, тако да проверите да ли сте у потпуности разумели шта радња ће се извршити кад год позовете једну од тих функција. Али заправо разумевање унутар ње није баш неопходно, јер ми имамо оне х фајлова.. Имамо још 2 датотеке које су преостале у нашем дистрибутивном коду. 

Погледајмо депонији. Думп својим коментаром овде узима Хафман-компресовани фајл и онда се преноси и депоније сви садржаја оут. Овде видимо да се то зове хфопен. То је врста мирроринг да поднесе * Инпут = фопен, и онда прође у информацији. То је готово идентична, осим уместо датотека * ви пролази у Хуффиле; уместо фопен сте пролазу у хфопен. Овде читамо у заглављу Први, који је некако слично како читамо у заглављу за битмап фајл. Оно што ми радимо овде проверава да ли информације у заглављу садржи прави чаробни број који указује да је стварни Хуфф фајл, онда све од ових провера да се уверите да датотека које смо отворено стварни хуффед фајл или не. Шта ово ради је она излази фреквенције свих симбола који можемо видети унутар терминала у графичком табели. Овај део ће бити корисна. Она има мало и чита мало по мало у променљивом мало и онда га исписује. Дакле, ако сам био да позове на депонију хтх.бин, што је резултат дувао датотеку коришћењем особља решење, ја бих ово. То је добијање свих ових ликова, а затим стављање фреквенцију на којој се појаве. Ако погледамо, већина њих су 0с осим за ово: Х, која се појављује два пута, и онда Т, који се јавља једном. А онда овде имамо стварну поруку у 0с и 1с. Ако погледамо хтх.ткт, што је вероватно оригинална порука која је хуффед, очекујемо да видимо неке Хс и ТС тамо. Конкретно, ми очекујемо да видимо само 1 Т и 2 ХС. Овде смо у хтх.ткт. Он заиста има ХТХ. Укључени тамо, мада не можемо да га видимо, нови ред карактер. Хаф датотека хтх.бин је такође кодира нови ред карактер као добро. Овде јер знамо да је наређење ХТХ па нови ред, можемо видети да је вероватно Х представља само један 1 и онда је Т је вероватно 01 и онда следећег БиХ је 1, као и и онда имамо нови ред означен два 0с. Кул. 

И на крају, јер смо се баве вишеструким Ц. И. Х датотеке, ћемо имати прилично сложен аргумент компајлером, па овде имамо Макефиле који чини депонију за вас. Али заправо, мораш да идеш о прављењу сопственог пуфф.ц датотеку. Макефиле заправо не бави са прављењем пуфф.ц за вас. Одлазимо да је до вас да уредите Макефиле. Када унесете команду као да све, на пример, то ће учинити све од њих за тебе. Слободно погледајте примере Макефиле из протекле псет као и да одлутају од ове да видим како би могли да направите датотеку Пуфф уређивањем ове Макефиле. То је отприлике то за нашу дистрибутивну коду. 

Када смо стекли кроз то, онда ево само још један подсетник о томе како ћемо да се баве Хуффман чворова. Нећемо бити називајући их чворови више, ми ћемо да их зове дрвеће где идемо да представља њихов симбол са цхар, њихова учесталост, број појава, са интегер. Ми користимо јер је то прецизнији од флоат. А онда имамо још једну показивач на леву детету, као и право детета. Шума, као што смо видели, само повезана листа дрвећа. Коначно, када градимо нашу Хуфф фајл, Ми желимо да наша шума садржи само 1 дрво - 1 дрво, 1 корен са више деце. Раније, када смо само давали наше Хафман дрвеће, смо почели стављањем свих чворова на нашим екранима и рекао да ћемо имати ове чворове, на крају они ће бити лишће, а ово је њихов симбол, то је њихова учесталост. У нашој шуми, ако имамо само 3 слова, то је шума од 3 дрвећа. А онда као да идемо даље, кад смо додали први родитељ, смо направили шуму 2 дрвећа. Уклонили смо 2 од те деце из наше шуме, а затим заменио га са матичном чвору који су имали те 2 чворове као деца. И на крају, наш последњи корак са прављењем наш пример са АС, БС, а Цс би да направи коначну родитеља, па онда донети нашу укупан број стабала у шуми на-1. Да ли сви виде како си почне са више стабала у свом шуми и завршити са 1? Ок. Кул. 

Шта ми треба да урадимо за Пуфф? Оно што треба да урадимо је да се обезбеди да, као и увек, они нам дају одговарајући тип уноса тако да ми заправо можемо покренути програм. У том случају они ће да нас даје после првог аргумента командне линије 2 више: фајл који желимо да декомпресију и излаз распакује фајл. Али, када смо се уверили да су нам пролазе у правом износу од вредности, желимо да се осигура да је улаз Хаф фајл или не. И онда кад ми гарантујемо да је Хаф фајл, онда желимо да градимо наш дрво, изградити стабло такав да одговара на дрво да особа која је послала поруку изграђен. Онда након што смо изградити стабло, онда можемо да се суочи са 0с и 1с да донет, следе оне заједно нашег стабла јер је идентична, и онда написати ту поруку напоље, тумаче бита назад у карактера. И онда на крају, јер се бавимо показивача овде, желимо да се уверите да немамо никакве цурење меморије и да смо слободни све. 

Обезбеђивање одговарајуће употребе је стари шешир за нас до сада. Ми се у улазу, која ће бити име фајла на пуфф, а онда смо навели излаз, тако да име датотеке за надима излаз, који ће бити текст фајл. То је употреба. А сада желимо да се осигура да је улаз хуффед или не. Присетите, да ли је нешто у дистрибутивном кода који би нам помогне са разумевањем да ли датотека хуффед или не? Било је информација у хуффиле.ц о Хуффеадер. Ми знамо да сваки Хаф датотека има Хуффеадер повезан са њим са магичним бројем као и низ фреквенција за сваки симбол као и цхецксум. Ми то знамо, али смо такође узели завирити у думп.ц, у којој је читао у Хуфф датотеку. И тако да се то уради, то је да се провери да ли је то заиста био хуффед или не. Дакле, можда бисмо могли да користе думп.ц као структура за наше пуфф.ц. Назад на псет 4 када смо имали датотеке цопи.ц да копира у РГБ тројке и ми тумачити да за детективски роман и величину, Слично томе, оно што можете да урадите је само покрените команду као цп думп.ц пуфф.ц и користили неки од кода тамо. Међутим, то неће бити тако једноставан процеса за превођење своју думп.ц у пуфф.ц, али барем вам даје негде да почне како би се осигурало да је улаз заправо хуффед или не као и неколико других ствари. Су обезбедили смо правилно коришћење и обезбедити да је улаз хуффед. Сваки пут када смо урадили да смо урадили наш прави грешке проверу, па повратак и одвикавање функцију ако неко дође до грешке, ако постоји проблем. 

Сада оно што ми желимо да урадимо је да се изгради стварни дрво. Ако погледамо у шуми, постоје 2 основне функције да ћемо желети да постане веома упознат са. Ту је Булова функција биљка која биљке не-0 фреквенција дрвећа унутар нашег шуми. И тако прође у показивач у шуму и показивач на дрвету. Брзо питање: Колико шуме ћете имати када правите Хуффман дрво? Наша Шума је попут наше платну, зар не? Тако смо само ћемо морати 1 шуму, али ми ћемо имати више стабала. Дакле, пре него што позовете фабрику, ви вероватно ћеш желети да направите шуму. Постоји команда за то, ако се осврнемо на форест.х о томе како можете направити шуму. Можете да засади дрво. Ми знамо како да то урадите. А онда можете одабрати дрво из шуме, уклањање стабла са најмањим тежине и даје вам показивач на то. Присетите се када смо радили на примерима себе, када смо га извлачење, ми смо једноставно додао линкове. Али овде, уместо да само додавање везе, мислите о томе више као ви уклањања тих 2 чворова, а затим замените га другом. Да изразимо то у смислу брање и садње, бирате 2 дрвеће, а затим другу садњу стабла да има те 2 дрвећа које сте изабрали као деца. Да изгради Хуффман је стабло, можете прочитати у симболима и фреквенцијама у циљу јер Хуффеадер даје то теби, даје Вам низ фреквенција. Дакле, можете ићи напред и само игнорисати ништа са 0 у њему јер не желимо 256 листова на крају њега. Ми само желимо да број листова који су карактери који су стварно користе у датотеци. Можете прочитати у тим симболима, а сваки од тих симбола који имају не-0 фреквенције, они ће бити дрвеће. Шта можете да урадите је да сваки пут када прочитате у не-0 фреквенција симбол, можете посадити то дрво у шуми. Када засадити дрвеће у шуми, можете се придружити те дрвеће као браћу и сестре, па да се вратимо на садње и бербе, где можете одабрати 2 и онда биљка 1, где је 1 биљка коју је родитељ на 2 деце која сте одабрали. Дакле, онда ваш резултат на крају ће бити једна дрво у шуми. Тако да изградите своје дрво. 

Постоји неколико ствари које може да крене наопако овде јер се бавимо израдом нових стабала и суочавања са показивачима и такве ствари. Пре него када смо се бавили показивача, кад год смо маллоц'д желимо да се уверите да то није нас врати НУЛЛ вредност показивача. Дакле, на неколико корака у овом процесу постоје ће бити неколико случајева где ваш програм би могао да пропадне. Шта желите да урадите је да желите да се уверите да сте руковати те грешке, и у спец пише да их обради грациозно, па бих одштампате поруку кориснику говорећи им зашто програм мора да престане и онда га одмах дао отказ. Да би то урадили руковање грешци, имајте на уму да желите да проверите сваки пут када би могло да буде промашај. Сваки пут када правите нову показивач Ви желите да се уверите да је то успешан. Пре него што смо навикли да урадимо је да направимо нови показивач и маллоц га, и онда бисмо проверили да ли је показивач НУЛЛ. Тако да ће бити неки случајеви где само можете да урадите, али понекад се стварно зовеш функцију иу тој функцији, то је онај који је раде маллоцинг. У том случају, ако се осврнем на неке од функција у оквиру кода, неки од њих су Булове функције. У апстрактном случају ако имамо Булову функцију зове фоо, суштини, можемо претпоставити да је поред раде шта год трла ради, пошто је Булова функција враћа труе или фалсе - Истина, ако успе, фалсе ако није. Дакле, желимо да проверите да ли је повратна вредност фоо је истинита или лажна. Ако је лажна, то значи да ћемо желети да одштампате неку поруку а затим затворите програм. Оно што ми желимо да урадимо је да проверите повратну вредност од фоо. Ако фоо враћа нетачно, онда знамо да смо наишли на неку врсту грешке и ми треба да престане наш програм. Начин да то урадите је да стање у којима стварна сама функција је ваше стање. Рецимо трла узима у к. Можемо имати као услов иф (Фоо (к)). У суштини, то значи да ако на крају извршења фоо враћа истина, онда можемо да урадимо јер функција има за процену фоо у циљу процене цео стање. Па онда је то како да урадите нешто, ако функција враћа труе и успешна. Али када сте грешака, желите само да престане ако ваша функција враћа фалсе. Шта можете да урадите је да само додајте == труе или једноставно додајте прасак испред ње а онда имате ако (ФОО!). У оквиру тог тела тог стања би сте све грешке руковања, па као, "Не могу да направим ово дрво", а затим се вратите 1 или нешто слично томе. Шта то ради, међутим, да иако трла вратио лажно - Реци трла враћа истина. Онда не морате да позовете фоо поново. То је уобичајена заблуда. Пошто је то било у твом стању, то је већ вреднован, тако да већ имате резултат ако користите да дрво или нешто слично или постројења или трзалица или тако нешто. Она већ има ту вредност. Већ је погубљен. Тако да је корисно да употребите Булове функције, као услов јер без обзира да ли стварно изврши тело петље, извршава свеједно функцију. 

Наш други на последњем кораку пише поруку на датотеку. Када градимо Хуффман стабло, онда писање поруку фајла је прилично једноставно. То је прилично једноставно сада само пратите 0с и 1с. И тако по конвенцији знамо да у Хуффман дрвету указују оставили 0с и 1с указују праву. Дакле, ако сте прочитали у мало по мало, сваки пут када добијете 0 ћете пратити леви огранак, и онда сваки пут када прочитате у 1 идете да пратите прави грану. А онда ћемо наставити док не погодите лист јер лишће ће бити на крају гране. Како можемо рећи да ли смо погодили лист или не? Ми то рекао. [Ученик] Ако су показивачи су НУЛЛ. >> Да. Можемо рећи да смо погодили лист ако показивачи на оба леви и десни дрвећа су НУЛЛ. Савршено. Знамо да желимо да прочитате у мало по мало у нашу Хуфф фајл. Као што смо видели раније у думп.ц, шта су они урадили је што чита мало по мало у Хуфф фајл и само штампани шта ти бита били. Нећемо да радимо то. Ми ћемо да радимо нешто што је мало сложенија. Али оно што можемо да урадимо је да можемо узети ту мало кода који чита се на мало. Овде имамо цео мало представља тренутну мало да смо на. Ова стара итератинг свих битова у датотеци док си ударио крај датотеке. На основу тога, онда ћеш желети да имају неку врсту Итератор да прођу стабло. А онда на основу ли бит 0 или 1, ћеш желети да преместите тај итератор лево или преместите га на десно све док не погодите лист, па све до тог чвора да сте на не указују на било више чворова. Зашто ово радимо са Хуффман фајл, али не Морзеова азбука? Јер у Морзеова азбука има мало двосмислености. Могли би бити као, ох чекања, ми смо погодио писмо успут, па можда ово је наша писма, а ако смо наставили само мало дуже, онда би ударио друго писмо. Али то се неће десити у Хуффман кодирање, тако да можемо бити сигурни да једини начин на који ћемо погодити карактер је ако тај чвор је лева и десна деца су НУЛЛ. 

На крају, желимо да ослободимо све наше меморије. Желимо да и на крају Хаф фајл који смо се бавили као и уклонити све дрвећа у нашој шуми. На основу вашег примени, вероватно ћеш желети да позовете уклонити шуму уместо заправо пролази кроз све и сами дрвећа. Али, ако сте направили било какве привремене дрвеће, ви ћете желети да ослободи тога. Ви најбоље познајете своје кода, тако да знате где сте доделу меморије. И тако ако одете у, почети чак контролу Ф'инг за маллоц, видим кад год маллоц и да се уверите да сте ослободити све то али онда само пролазе кроз ваш код, разумевање где би сте додељени меморију. Обично се само могу рећи: "На крају фајла ћу само да уклони шуму на мојој шуми" Дакле, у основи јасно да меморију, слободан да, "И онда сам ћу да затворите датотеку, а затим мој програм ће престати." Али да ли је то једини пут да је ваш програм се затвара? Не, јер понекад има можда био грешка што се десило. Можда нисмо могли отворити датотеку или нисмо могли да још дрво или нека врста грешке се десило у процесу доделе меморије и тако се вратио НУЛЛ. Грешка се десило и онда смо се вратили и отказ. Па онда желите да се уверите да сваки могући пут да се ваш програм отказ, желите да ослободите сву своју меморију тамо. То није само ће бити на самом крају главног функције коју напусти свој код. Хоћеш да се осврнем на сваки пример, да је ваш код потенцијално може превремено вратити и онда слободно шта год меморија има смисла. Рецимо да је позвао да шуму и да се вратио лажна. Онда вероватно нећете морати да уклоните шуму јер још увек немамо шуму. Али у сваком тренутку у коду где сте можда прерано вратити желите да се уверите да сте слободни евентуални меморију. 

Дакле, када се бавимо ослобађањем меморије и има потенцијалних цурења, желимо не само да користимо наше расуђивање и нашу логику али такође користе Валгринд да утврди да ли смо ослободили све наше сећање исправно или не. Можете да покренете Валгринд на Пуфф, а онда мораш да се то прође Право број аргумената у командној линији да Валгринд. Можете да покренете, али излаз је мало криптичан. Смо стекли смо мало користи да са њим Спеллер, али ми и даље треба мало више помоћи, па онда ради са још неколико застава, као цурења провери = пун, да ће нам вероватно дати још мало корисне излаз на Валгринд. 

Затим још један користан савет кад дебаговање је разлика команда. Можете приступити имплементацији особља за Хуфф, трчи да на текстуалне датотеке, и онда је излаз у бинарни фајл, бинарни Хаф фајл, да будем прецизнији. Затим, ако покренете сопствени дим на том бинарном фајлу, онда идеално, ваш излазног текстуална датотека ће бити идентични првобитном који сте прошли унутра Ево ја користим хтх.ткт као пример, а то је један говорио у спец. То је буквално само ХТХ, а затим нови ред. Али дефинитивно осећам слободно и да се дефинитивно подстичу да користе дуже примере за текстуалној датотеци. 

Можете чак и да преузме пуцао на можда компримовање и затим декомпресује неке од датотека које сте користили у Спеллер попут рата и мира или Џејн Остин, или нешто слично томе - то би било кул - или Аустин Поверс, врста суочавања са већим фајловима јер неће доћи до тога ако смо користили следећу алатку овде, лс-л. Навикли смо да ЛС, који је у основи наводи све садржаје у нашем тренутном директоријуму. Пролазак у заставом-л заправо приказује величину тих фајлова. Ако идете кроз псет спецификације, то је заправо вас води кроз креирање бинарни фајл, од мршти се, и видећете да за веома мале датотеке простор цена је компримовање и превођење свих тих информација свих фреквенција и ствари као што то превазилази конкретну корист компресије фајл на првом месту. Али ако га покренете на неким дужим текстуалних фајлова, онда ћете можда видети да почнете да се мало користи у компресовање те фајлове. 

И на крају, имамо стару другар гдб, који ће дефинитивно доћи превише. 

Да ли имате питања на Хуфф дрвећа или процес прављења можда дрвеће или било које друге питања о Хуфф'н Пуфф? Ок. Ја ћу остати око за мало. 

Хвала свима. Ово је Валктхроугх 6. И срећно. 

[ЦС50.ТВ]