[Powered by Google Translate] [Проходження - Проблема Set 6] [Zamyla Chan - Гарвардський університет] [Це CS50. - CS50.TV] 

Привіт всім, і ласкаво просимо Проходження 6: Huff'n Puff. У Puff Huff'n те, що ми робимо, будемо мати справу з файлами Хаффман стисненого , А потім пихкаючи його назад вгору, так розпакування цього, так що ми можемо перекладати з 0 і 1, які користувач посилає нам і перетворити його назад у вихідний текст. Pset 6, буде дуже здорово, тому що ви побачите деякі з інструментів які ви використовували в PSET 4 і 5 і PSET роду об'єднання їх в 1 дуже акуратно концепції коли ви приходите думати про це. 

Крім того, можливо, PSET 4 і 5 були найбільш складних psets, що ми повинні були запропонувати. Таким чином, з цього моменту, у нас є це ще 1 PSET в C, а після цього ми на веб-програмування. Так що вітаю себе для отримання більш жорстким горб CS50. 

Переходячи до Puff Huff'n, наш інструментарій для цього PSET збираєтеся бути Huffman дерев, тому розуміння не тільки як двійкові дерева роботу, але і спеціально Huffman дерев, як вони побудовані. І тоді ми будемо мати багато розподілу коду в цьому PSET, і ми прийшли, щоб побачити, що насправді деякі з коду Ми не зможемо повною мірою зрозуміти все ж, і тому ті будуть. с файлами, але потім їх супроводжуючих. ч. файлів дасть нам достатньо розуміння того, що нам потрібно, так що ми знаємо, як ці функції працюють або принаймні те, що вони повинні робити - їх входи і виходи - навіть якщо ми не знаємо, що відбувається в чорному ящику або не розуміють, що відбувається в чорному ящику всередині. І, нарешті, як зазвичай, ми маємо справу з новими структурами даних, конкретні види вузлів, які вказують на певні речі, і ось що має ручку і папір не тільки для процесу проектування і коли ви намагаєтеся з'ясувати, як ваші PSET повинні працювати але і під час налагодження. Ви можете мати GDB разом з пером і папером в той час як ви берете те, що значення, де ваші стрілки вказують, тощо. 

Перш за все, давайте подивимося на дерева Хаффмана. Huffman дерев бінарні дерева, а це означає, що кожен вузол має тільки 2 дітей. У дерев Хаффмана характерним є те, що найбільш часті значення представлена ​​найменшою кількістю бітів. Ми бачили в лекції приклади коду Морзе, який вид консолідованого кілька листів. Якщо ви намагаєтеся перевести або E, наприклад, ви перекладаєте, що часто, так що замість того, щоб використовувати весь набір бітів виділено на що звичайний тип даних, стискати його до менше, , А потім ці листи, які представлені рідше представлені з більш біт тому що ви можете собі це дозволити, коли ви важите з частот, що ці літери з'являються. У нас же ідея тут в дерева Huffman де ми робимо ланцюг, свого роду шлях, щоб дістатися до певних символів. І тоді персонажі, які мають найбільш частоти будуть представлені з найменшою кількістю бітів. 

Спосіб, яким ви побудувати дерево Хаффмана шляхом розміщення всіх персонажів, які з'являються в тексті і розрахунку їх частота, як часто вони з'являються. Це може бути або з рахунку, скільки разів ці літери з'являються або, можливо, відсоток з усіх символів, скільки кожен з'являється. І те, що ви робите, коли у вас є все, що намітили, Потім ви подивитеся на 2 низькі частоти, а потім приєднатися до них як брати і сестри де то батьківський вузол має частоту, яка є сумою своїх 2 дітей. І тоді ви за угодою сказати, що лівий вузол, Ви будете слідувати, що, слідуючи 0 галузь, , А потім правий вузол 1 філії. Як ми бачили в азбуці Морзе, один глюк, що якщо ви тільки що звуковий сигнал і звуковий сигнал було неоднозначним. Це може бути або 1 букву або це може бути послідовність з 2 букв. І те, що Huffman дерев робить це тому, що за характером персонажів або наші остаточні фактичні символи буття останнього вузла на гілці - ми маємо на увазі тих, хто, як листя - силу того, що там не може бути ніякої двозначності , В термінах якої листі ви намагаєтеся кодувати з послідовністю бітів тому що ніде уздовж бітів, які складають 1 лист Ви будете стикатися ще цілий лист, і там не буде ніякої плутанини немає. Але ми будемо йти в прикладах, які ви, хлопці, можете фактично бачити, що замість нас просто кажу вам, що це правда. 

Давайте подивимося на простий приклад дерево Хаффмана. У мене є рядок, що тут має довжину 12 символів. У мене є 4 В, 6 сніданок, і 2 Cs. Моїм першим кроком було б розраховувати. Скільки разів з'являються? Схоже 4 рази на рядок. У з'являється 6 разів, а C з'являється в 2 рази. Природно, що я збираюся сказати, я використовую B найчастіше, Тому я хочу, щоб представляти B з найменшою кількістю бітів, найменше число 0 і 1. А потім я також збираюся чекати C вимагати найбільшу кількість 0 і 1, а також. Перше, що я зробив тут я помістив їх у порядку зростання по частоті. Ми бачимо, що C і A, ті наші 2 низькі частоти. Ми створюємо батьківський вузол, і що батьківський вузол не має листі, пов'язані з ним, але у нього є частота, яка є сумою. Сума стає 2 + 4, який є 6. Потім ми слідуємо лівої гілки. Якби ми були на що 6 вузлів, то ми будемо слідувати від 0 до дістатися до C , А потім 1, щоб дістатися до A. Так що тепер у нас є 2 вузла. У нас є значення 6, а потім у нас також є ще один вузол із значенням 6. І ось ці 2 не тільки 2-низька, але і тільки 2, які залишилися, тому ми приєднуємося до тих іншим батьком, з сумою буття 12. Так що тут у нас є дерево Хаффмана де, щоб дістатися до B, це було б просто біт 1 , А потім, щоб дістатися до нас буде 01, а потім C має 00. Таким чином, тут ми бачимо, що в основному ми, що представляють ці символи з 1 або 2 біти де B, як і передбачалося, має найменше. І тоді ми очікували C, щоб мати більшість, але так як це такий маленький дерево Хаффмана, Потім також представлені 2 біти, а не десь в середині. 

Просто, щоб перейти на інший простий приклад дерево Хаффмана, у вас є рядок "Hello". Що ви робите, спочатку ви б сказати скільки разів H з'явиться в цьому? H з'являється один раз, а потім електронної з'являється один раз, і тоді ми маємо л з'являтися в два рази і про з'являються один раз. І так, то ми очікуємо, яке букву, яка буде представлена ​​найменшою кількістю біт? [Студент] л. >> Л. Так. л прав. Ми очікуємо, що я повинен бути представлений найменшу кількість біт тому що я все використовується в рядок "Hello". Що я буду робити тепер витягнути ці вузли. У мене є 1, який є H, а потім ще 1, який є електронною, а потім 1, що про - Прямо зараз я ставлю їх в порядок - і потім 2, яка є л. Тоді я кажу так, як я побудови дерева Хаффмана, щоб знайти 2 вузлів з найменшими частотами і зробити їх братами і сестрами по створенню батьківського вузла. Тут у нас є 3 вузлам з найнижчою частотою. Вони все 1. І ось ми вибрати, який з ми збираємося зв'язати в першу чергу. Припустимо, я вибираю H і E. Сума 1 + 1 = 2, але на цей вузол не має листі, пов'язані з ним. Він просто тримає значення. Зараз ми подивимося на наступні 2 низькі частоти. Це 2 і 1. Це може бути будь-який з цих 2, але я збираюся вибрати цю. Сума 3. І, нарешті, у мене тільки 2 лівих, так те, що стає 5. Тоді тут, як і очікувалося, якщо я заповнюю в кодуванні для того, 1s завжди правої гілки і 0 є ліву. Тоді ми маємо л представлені лише 1 біт, а потім на 2 O , А потім е на 2, а потім H падає до 3 біт. Таким чином, ви можете передавати це повідомлення "Hello", а насправді використання символів на тільки 0 і 1. Однак слід пам'ятати, що в ряді випадків ми мали зв'язків з нашою частоті. Ми могли б або приєдналися до H і O Рік може бути. Або потім, коли у нас було л представлений 2 а також приєднався до однієї представлений 2, ми могли би пов'язаний жоден. 

І тому, коли ви посилаєте 0 і 1, що насправді не гарантують що одержувач може повністю прочитати повідомлення прямо з місця в кар'єр тому що вони не могли знати, які рішення ви зробили. Тому, коли ми маємо справу з стисненням Хаффмана, так чи інакше ми повинні сказати одержувача наше послання, як ми вирішили - Вони повинні знати, якоїсь додаткової інформації На додаток до повідомлення стислим. Вони повинні розуміти, що дерево насправді виглядає, як ми насправді зробили ці рішення. 

Тут ми просто робили прикладів, заснованих на фактичну кількість, але іноді ви також можете мати дерево Хаффмана в залежності від частоти, на якій літери з'являються, і це точно такий же процес. Тут я висловлюю це в термінах відсотки або частки, і ось одне і те ж. Я знаходжу, 2-низький, скласти їх, наступні 2 низький, скласти їх, поки у мене є повне дерево. Хоча ми могли б зробити це в будь-якому випадку, коли ми маємо справу з відсотками, , Що означає, що ми поділом речей, і справа з десятими або, скоріше, плаває якщо ми думаємо про структури даних з голови. Що ми знаємо про поплавцях? Що таке загальна проблема, коли ми маємо справу з поплавками? [Студент] Неточні арифметика. >> Да. Неточність. Через плаваючою точкою неточність, для цього PSET, так що ми впевнені, що ми не втрачають значення, то насправді ми будемо мати справу з графом. Так що якщо ви повинні були думати вузла Хаффман, якщо ви подивитеся на структуру тут, якщо ви подивитеся на зелені воно має частоту пов'язаних з ним а також він вказує на вузол, щоб його лівий, а також вузол в своєму праві. А потім червоні там теж є характер, пов'язаний з ними. Ми не збираємося робити окремі для батьків, а потім остаточне вузлів, який ми називаємо листям, а ті будуть просто порожні значення. Для кожного вузла ми будемо мати характер, символ, який представляє вузол, Потім частоти, а також покажчик на його ліву дитини, а також його права дитини. Листя, які знаходяться на самому дні, буде також мати покажчики на ноди ліворуч від них, а також їх право, але так як ці значення не вказує на фактичне вузлів, що б їх вартість буде? >> [Студент] NULL. >> NULL. Саме так. Ось приклад того, як можна представляти частоти в поплавців, але ми збираємося мати справу з цим з цілими числами, так що все, що я зробив це змінити тип даних немає. 

Давайте перейдемо до трохи більше складний приклад. Але тепер, коли ми зробили прості, це просто той самий процес. Ви знайдете 2-низькі частоти, підвести частот і ось нова частота вашого батьківського вузла, , Який потім вказує на її лівому з 0 філії і право з 1 філії. Якщо у нас є рядок "Це CS50", то ми порахувати, скільки разів буде згадано T, ч згадувалося, I, S, C, 5, 0. Потім, що я зробив тут з червоними вузлами я просто посадив, Я сказав, що я буду мати ці символи в кінцевому підсумку в нижній частині мого дерева. Ті збираються бути все листя. Потім, що я зробив, я сортував їх за частотою в порядку зростання, і це насправді так, що PSET код робить це це сортує їх по частоті, а потім в алфавітному порядку. Так воно і є число, а потім в алфавітному порядку за частотою. Тоді що я буду робити, я б знайти 2 низька. Це 0 і 5. Я б скласти їх, і ось 2. Тоді я буду продовжувати, знайти найближчі 2 низька. Ці два 1s, а потім вони стають 2, а. Тепер я знаю, що мій наступний крок буде приєднання до найменшим числом, яка є T, 1, а потім вибрати один з вузлів, який має 2 як частота. Так що тут у нас є 3 варіанти. Що я буду робити для слайдів тільки візуально змінити їх для вас так що ви можете бачити, як я будую його. Який код і розподілу коду збираються робити буде приєднатися до T один з 0 до 5 вузлів. Отже, що суми до 3, а потім ми продовжимо процес. 2 і 2 зараз є найнижчими, так що потім ці суми до 4. Кожен наступний досі? Добре. А після цього у нас є 3 і 3, які повинні бути додані вгору, так що знову я просто включіть його, так що ви можете бачити візуально так, щоб він не занадто брудним. Тоді у нас є 6, а потім наш останній крок зараз, що у нас є тільки 2 вузлів Підсумовуючи ці щоб коріння нашої дерева, яке дорівнює 10. І число 10 має сенс, оскільки кожен вузол представляє, їх значення, їх частота номер, було, скільки разів вони з'явилися в рядок, а то у нас 5 символів в наш ланцюжок, так що має сенс. Якщо ми дивимося на те, як ми насправді кодувати його, Як і очікувалося, я і S, які з'являються найчастіше представлені найменшу кількість біт. 

Будьте обережні. У дерев Хаффмана випадок насправді має значення. Прописні S відрізняється від рядкової с. Якби ми мали "Це CS50" з великої літери, то рядкові и буде з'являтися тільки в два рази, буде вузол з 2 в якості свого значення, а потім прописні S буде тільки один раз. І тоді ваше дерево буде змінити структури, тому що ви насправді мають додатковий аркуш тут. Але сума все одно буде 10. Це те, що ми насправді буде викликом контрольної суми, Крім всіх підрахунків. 

Тепер, коли ми розглянули Huffman дерев, ми можемо зануритися в Huff'n Puff, PSET. Ми збираємося почати з розділу питань, і це відбувається, щоб ви звикли з бінарними деревами і як працювати навколо цього: малювання вузлів, створюючи свій власний ЬурейеЕ структури для вузла, і, бачачи, як ви могли б вставити в бінарному дереві, той, який сортується, через нього, і тому подібне. Це знання, безумовно, допоможе вам, коли ви занурюєтеся в частині Puff Huff'n з PSET. У стандартному виданні PSET, ваше завдання полягає в реалізації Puff, і в хакерської версії вашим завданням є реалізація Хафф. Що Хафф робить це бере текст, а потім він переводить його в 0 і 1, так що процес, який ми зробили вище, де ми розраховували частот , А потім зробив дерева, а потім сказав: "Як я можу отримати T?" T представлена ​​на 100, тощо, , А потім Хафф б текст, а потім висновок, що двійковий файл. Але й тому, що ми знаємо, що ми хочемо, щоб наші одержувач повідомлення відтворити точно таку ж дерево, воно також включає інформацію про частоту отсчетов. Потім з Puff дано двійковий файл з 0 і 1 і також з урахуванням інформації про частоти. Ми переводимо всі ці 0 і 1 повертається у вихідне повідомлення, що було, так що ми розпакування цього. Якщо ви робите Standard Edition, вам не потрібно здійснювати Хафф, так, то ви можете просто використовувати персонал реалізації Хафф. Є інструкції в специфікації про те, як це зробити. Ви можете запустити персоналу здійснення Хафф на певний текстовий файл а потім використовувати цей вихід як ваш внесок у затяжку. 

Як я вже говорив, у нас є багато розподілу коду для цього. Я збираюся почати ходити через нього. Я буду проводити більшу частину часу на. Ч. файлів тому що в. с файлами, тому що у нас є. ч і що дає нам прототипи функцій, Ми не в повній мірі повинні розуміти точно - Якщо ви не розумієте, що відбувається в. Файлів с, то не турбуйтеся надто багато, але обов'язково спробую поглянути, тому що це може дати деякі підказки і це корисно, щоб звикнути до читання коду інших людей. 

Дивлячись на huffile.h, в коментарях він заявляє шар абстракції для Huffman-кодованих файлів. Якщо ми підемо вниз, ми бачимо, що є максимум 256 символів, що ми, можливо, буде потрібно коди. Це включає в себе всі букви алфавіту - прописні і рядкові - , А потім символи і цифри, і т.д. Тоді тут у нас є чарівний номер, що ідентифікує Huffman-кодованих файлів. У коді Хаффмана вони будуть мати певну кількість магії пов'язані з заголовка. Це може виглядати як випадкове число, магія, Але якщо ви насправді переводити його в ASCII, то це насправді викладає Хафф. Тут ми маємо структуру для Хаффман файл в кодуванні. Там всі ці характеристики, пов'язані з файлом Хафф. Тоді тут ми маємо заголовок файлу Хафф, тому ми називаємо його Huffeader Замість додавання додаткових годин, тому що звучить однаково в будь-якому випадку. Cute. У нас є магічне число пов'язаних з ним. Якщо це реальний файл Хафф, це буде номер нагорі, це чарівний. І тоді вона буде мати масив. Таким чином, для кожного символу, в якому є 256, він збирається перерахувати, що частота цих символів у файлі Хафф. І, нарешті, у нас є контрольна сума для частот, , Яка повинна бути сума цих частотах. Так ось що Huffeader є. Тоді у нас є деякі функції, які повертають наступний біт у файлі Huff а також пише трохи, щоб файл Хафф, а потім ця функція тут, hfclose, що насправді закриває файл Хафф. Раніше ми мали справу з прямим просто Fclose, Але коли у вас є файл Хафф, а fclosing це те, що ви насправді збираєтеся зробити, це hfclose і hfopen його. Ті конкретні функції Хафф файли, які ми збираємося мати справу. Тоді ось ми читаємо в заголовку, а потім написати заголовок. 

Просто читаючи. Ч файлу ми можемо отримати вид сенс того, що файл Хафф може бути, які характеристики у нього є, фактично не вдаючись у huffile.c, , Який, якщо ми заглибимося в, буде трохи складніше. Він має всі файлового введення / виводу тут справу з покажчиками. Тут ми бачимо, що коли ми називаємо hfread, наприклад, це все ще справа з FREAD. Ми не позбутися від цих функцій повністю, але ми посилаємо тих, хто буде піклуватися всередині файлу Хафф а не робити все це самі. Ви можете відчувати себе вільно для сканування через це, якщо вам цікаво і йдуть, а шкірку шар назад небагато. 

Наступний файл, який ми збираємося дивитися на це tree.h. До цього в Покрокове керівництво ковзає ми сказали, що ми очікуємо Хаффман вузла і ми зробили ЬурейеЕ вузла структури. Ми очікуємо, що це є символ, частоти, а потім 2 зірки вузла. У цьому випадку те, що ми робимо це по суті той же тільки замість вузла ми будемо називати їх деревами. У нас є функція, яка при виклику зробити дерево він повертає вам покажчик дерева. Назад до Speller, коли ви робили новий вузол Ви сказали вузол * Нове слово = Танос (SizeOf) тощо. В принципі, mktree буде мати справу з цим для вас. Аналогічним чином, коли ви хочете видалити дерево, так що, по суті, звільняючи дерево, коли ви закінчите з цим, замість явного виклику безкоштовно на те, що насправді ви просто збираєтеся використовувати функцію rmtree де ви передаєте покажчик на це дерево, а потім tree.c подбає про це за вас. 

Ми дивимося в tree.c. Ми очікуємо, що ті ж функції, за винятком побачити реалізацію, а також. Як ми і очікували, коли ви дзвоните mktree це mallocs обсягу дерева в покажчик, ініціалізує всі значення на NULL значення, так 0s або нулі, і потім повертає покажчик на це дерево, яке ви тільки що malloc'd до вас. Ось коли ви дзвоните видалити дерево він спочатку переконується, що ви не подвійне звільнення. Він упевнений, що у вас дійсно є дерево, яке ви хочете видалити. Ось тому, що дерево також включає в себе дітей, що вона робить це рекурсивно викликає видалення дерев на лівому вузлі дерева а також право вузлів. Перш, ніж він звільняє батьків, він повинен звільнити дітей. Батько також взаємозамінні з коренем. Перший в історії батька, так як пра-пра-пра-пра-дідусь або бабуся дерево, спочатку ми повинні звільнити до рівня першого. Так що пройти на дно, вільне їх, а потім повернутися вгору, вільні тих, і т.д. Так що це дерево. 

Тепер ми подивимося на ліс. Ліс, де ви розмістите всі ваші дерев Хаффмана. Він говорив, що ми будемо мати те, що називається ділянка , Який містить покажчик на дерево, а також покажчик на ділянку називається наступна. Яка структура робить цей вид виглядає? Це почасти говорить, що це там. Право тут. Зв'язаний список. Ми бачимо, що коли у нас є сюжет це як зв'язаний список ділянок. Ліс визначається як зв'язаний список ділянок, і так структурі лісу ми просто будемо мати покажчик на нашому першій ділянці і що ділянка має дерево в ньому або, скоріше, вказує на дереві , А потім вказує на наступну ділянку, так далі, і так далі. Для того, щоб ліс ми називаємо mkforest. Тоді у нас є кілька досить корисних функцій тут. Ми повинні вибрати, де ви проходите в ліс, а потім повертається значення дерева *, покажчик на дерево. Який вибір зробить, вона буде йти в ліс, що ви вказуючи на потім видалити дерево з найнижчою частотою від лісу , А потім дати вам покажчик на дерево. Після того як ви зателефонуєте вибрати, дерево не буде існувати в лісі більше, але повернене значення є покажчиком на цьому дереві. Тоді у вас є завод. За умови, що ви передаєте покажчик на дерево, яке має не-0 частот, що завод буде робити це буде ліс, взяти дерев і рослин, що дерево всередині лісу. Тут ми маємо rmforest. Схожі видалити дерево, яке в основному звільнив усіх наших дерев для нас, видалити ліс буде безкоштовно все, що міститься в цьому лісі. 

Якщо ми подивимося на forest.c, ми очікуємо, що принаймні 1 rmtree команди там, тому що, щоб звільнити пам'ять в лісі, якщо ліс є дерева в ньому, то в кінцевому підсумку ви будете мати, щоб видалити ці дерева теж. Якщо ми подивимося на forest.c, у нас є mkforest, який, як ми очікуємо. Ми Танос речі. Ми ініціалізували перша ділянка в лісі, NULL, тому що це порожні Почнемо з того, Потім ми бачимо, вибір, який повертає дерево з низькою вагою, низької частоти, , А потім позбавляється від конкретного вузла, який вказує на це дерево і наступний, тому він приймає, що із зв'язаного списку лісу. А то ось у нас є завод, який вставляє дерево у зв'язаному списку. Що лісів робить це красиво тримає його відсортовані для нас. І, нарешті, у нас є rmforest і, як і очікувалося, у нас є rmtree називається там. 

Дивлячись на поширення коду досі, huffile.c була, ймовірно, набагато важче зрозуміти, в той час як інші файли самі по собі були досить прості, щоб слідувати. З нашими знаннями покажчики та зв'язані списки і такі, ми були в змозі слідувати досить добре. Але все, що потрібно, щоб дійсно переконатися, що ми повністю розуміємо це. Ч. файлів тому що ви повинні бути викликом цих функцій, вирішення цих значень, що повертаються, тому переконайтеся, що ви повністю розумієте, яка дія буде виконуватися всякий раз, коли ви подзвоните по одному з цих функцій. Але насправді порозуміння всередині нього зовсім не обов'язково, тому що ми є ті. Ч. файлів. У нас є ще 2 файли, які залишаються в нашій розподілу коду. 

Давайте подивимося на звалище. Дамп його коментар тут займає Хаффман стислих файлів , А потім перекладає і звалища весь його вміст з. Тут ми бачимо, що вона кличе hfopen. Це свого роду дзеркальне у файл * вхід = Еореп, а потім ви проходите в інформації. Це майже ідентичні, за винятком замість файлу * ви передаєте в Huffile; замість Еореп ви передаєте в hfopen. Тут ми читаємо в заголовку першою, яка є своєрідною подібно до того, як ми читаємо в заголовку для растрових файлів. Що ми робимо тут, перевіряючи, чи є інформація заголовка містить право магічне число, яке вказує, що це реальний файл Хафф, Потім всі ці перевірки, щоб переконатися, що файл, який ми відкриті є актуальною пирхнув файл чи ні. Що це робить він виводить частоти всі символи, які ми бачимо, в терміналі в графічну таблицю. Ця частина буде корисно. Він має трохи, і читається по частинах в змінну трохи, а потім роздруковує її. Так що, якщо б я був подзвонити звалища на hth.bin, яка є результатом пихкаючи файл використання співробітниками рішення, я хотів би отримати це. Це виводить всі ці персонажі, а потім покласти частоти, на яких вони з'являються. Якщо ми подивимося, більшість з них 0s за винятком цього: H, яка з'являється двічі, , А потім T, який з'являється один раз. А то тут ми маємо фактичне повідомлення в 0 і 1. Якщо ми подивимося на hth.txt, який імовірно вихідне повідомлення, яке було пирхнув, ми очікуємо побачити деякі Hs і Ц. там. Зокрема, ми очікуємо побачити тільки 1 і 2 T Hs. Тут ми знаходимося в hth.txt. Це дійсно має HTH. Входить в там, хоча ми не бачимо, є символом нового рядка. Hth.bin Хафф файл також кодування символу нового рядка, а також. Тут, тому що ми знаємо, що порядок HTH, а потім рядки, ми бачимо, що, ймовірно, H представлена ​​тільки однією +1 , А потім, ймовірно, T 01 і потім на наступний Н 1, а а то у нас новий рядок позначається двома 0s. Cool. 

І, нарешті, тому, що ми маємо справу з декількома. С і. Ч. файлів, ми будемо мати досить складний аргумент для компілятора, і ось у нас є Makefile, який робить дамп для вас. Але насправді, ви повинні піти про створення власного puff.c файл. Makefile насправді не має справу зі створенням puff.c для вас. Ми йдемо, що до Вас, щоб змінити Makefile. Коли ви вводите команду зробити все, наприклад, він зробить все це за вас. Ви можете подивитися на приклади Makefile з минулого PSET а також йти з цього, щоб побачити, як ви могли б зробити вашу Puff файл шляхом редагування цього файлу Makefile. Ось про це наш розподілу коду. 

Як тільки ми пройшли через це, то тут просто ще одне нагадування про те, як ми збираємося мати справу з вузлами Хаффмана. Ми не збираємося бути називаючи їх вузлів більше, ми збираємося називати їх деревами де ми збираємося подавати їх символ символ, їх частота, число входжень, з цілим. Ми використовуємо, тому що це більш точне, ніж плавати. А то у нас ще один покажчик ліворуч дитини, а також права дитини. Ліс, як ми бачили, це просто зв'язаний список дерев. У кінцевому рахунку, коли ми будуємо нашу Хафф файл, Ми хочемо, щоб наш ліс, щоб утримувати тільки 1 дерево - 1 дерево, 1 корінь з кількома дітьми. Раніше, коли ми були просто робить нашу Huffman дерев, Ми почали з розміщення всіх вузлів на нашому екрані і говорять, що ми збираємося, щоб ці вузли, в остаточному підсумку вони збираються бути листя, і це їх символ, це їх частота. У нашому лісі, якби ми просто 3 букви, це ліс з 3 дерев. І те, як ми продовжимо, коли ми додали першого батька, Ми зробили ліс з 2 дерев. Ми зняли 2 з цих дітей у віці від нашого лісу, а потім замінити його батьківський вузол , Що було ці 2 вузла, як діти. І, нарешті, наш останній крок зробити наш приклад з As, Bs, Cs і було б зробити остаточний батьків, і так, то що б наше загальна кількість дерев у лісі 1. Чи всі подивитися, як ви починаєте з кількох дерев у лісі і в кінцевому підсумку з 1? Добре. Cool. 

Що ми повинні зробити для Puff? Що нам потрібно зробити, це переконатися, що, як завжди, вони дають нам право тип вхідного так що ми дійсно можемо запустити програму. У цьому випадку вони будуть давати нам після їх першого аргументу командного рядка Ще 2: файл, який ми хочемо розпакувати і виходу розпакувати файл. Але як тільки ми переконайтеся, що вони проходять повз нас в потрібній кількості цінностей, Ми хочемо переконатися, що вхід файл Хафф чи ні. І ось одного разу ми гарантуємо, що це файл Хафф, то ми хочемо побудувати наше дерево, побудувати дерево так, що воно відповідає дерево, людина, що відправив повідомлення побудований. Потім, після ми будуємо дерево, то ми можемо мати справу з 0 і 1, що вони пройшли в, слідувати за тими, на нашу дереву, тому що це ідентично, а потім пишуть, що повідомлення з, інтерпретувати біти назад в символи. І потім, в кінці, тому що ми маємо справу з покажчиками тут, Ми хочемо переконатися, що ми не маємо будь витоку пам'яті і що ми все безкоштовно. 

Забезпечення належного використання є стара капелюх для нас зараз. Візьмемо як входу, яка буде ім'я файлу, пихкати, а потім ми вказуємо вихід, тому ім'я файлу для пухкі вихід, який буде текстовий файл. Це використання. І тепер ми хочемо переконатися, що вхід розбушувався, чи ні. Згадуючи, чи було що-небудь у розподілі код, який може допомогти нам з розумінням, чи є файл розбушувався, чи ні? Існував інформації в huffile.c про Huffeader. Ми знаємо, що кожен файл має Хафф Huffeader пов'язані з ним з магічним числом а також масив частот для кожного символу а також контрольну суму. Ми знаємо, що, але ми також прийняли поглянути на dump.c, , В якому вона читала в файл Хафф. І так, щоб зробити це, він повинен був перевірити чи дійсно вона була розбушувався, чи ні. Тому, можливо, ми могли б використовувати dump.c як структура для нашого puff.c. Повернутися до PSET 4, коли у нас був файл copy.c, що скопіювали в трійках RGB і ми інтерпретували, що для детективний роман і зміна розміру, Точно так само, то, що ви можете зробити, це просто запустити команду Ф dump.c puff.c і використовувати деякі з код. Тим не менш, це не буде так просто, процесу для перекладу вашого dump.c в puff.c, але принаймні це дає вам де-небудь, щоб почати про те, як переконатися, що вхід насправді розбушувався, чи ні , А також кілька інших речей. Ми забезпечили належного використання і запевнив, що вхід пирхнув. Кожен раз, коли ми це зробили, ми зробили належні перевірки на помилки, так поверненні та вихід з функції, якщо деякі з ладу, якщо є проблема. 

Тепер те, що ми хочемо зробити, це побудувати реальне дерево. Якщо ми подивимося в лісі, є 2 основні функції що ми збираємося хочете стати дуже знайомі. Там в булевої функції рослин, що рослини не-0 частота дерево в нашому лісі. І таким чином, ви передаєте покажчик на ліс і покажчик на дерево. Швидкий запитання: скільки лісу буде у вас, коли ви будуєте дерево Хаффмана? Наш ліс, як наше полотно, вірно? Таким чином, ми тільки збираємося мати 1 ліс, але ми збираємося мати кілька дерев. Тому, перш ніж називати рослини, ви ймовірно збирався хочете, щоб ваш ліс. Існує команда, що якщо ви подивитеся на forest.h про те, як ви можете зробити ліс. Ви можете посадити дерево. Ми знаємо, як це робити. І тоді ви можете також вибрати дерево з лісу, видалення дерев з низькою вагою і дає вам покажчик на це. Згадуючи, коли ми робили приклади себе, Коли ми малювали його, ми просто тільки що додали посилання. Але тут замість того, щоб просто додати посилання, думаю про нього як ви видаляєте 2 з цих вузлів, а потім замінити його на інший. Щоб висловити, що в плані збору та посадки, Ви вибираєте 2 дерева, а потім посадка інше дерево , Який має ті 2 дерева, які ви вибрали, як діти. Для побудови дерева Хаффмана, ви можете прочитати в символах і частоти в порядку тому що Huffeader дає, що для вас, дає вам масив частот. Таким чином, ви можете піти далі і просто ігнорувати все, що з 0 в цьому тому що ми не хочемо 256 листів в кінці його. Ми тільки хочемо, щоб кількість листя, які є символами , Які фактично використовуються у файлі. Ви можете прочитати в тих символах, і кожен з цих символів, які мають не-0 частот, ті збираєтеся бути дерев. Що ви можете зробити, це кожен раз, коли ви читаєте в не-0 частота символ, Ви можете посадити це дерево в лісі. Після того як ви посадіть дерева в лісі, ви можете приєднатися до тих дерев, як брати і сестри, Тож повертаючись до посадки і вибрати, де ви вибираєте 2, а потім завод 1, де то 1, що ви заводу є батьком 2 дітей, що ви вибрали. Таким чином, то ваш результат буде одне дерево в лісі. Ось як ви будуєте свою дерева. 

Є кілька речей, які можуть піти не так, тут тому що ми маємо справу зі створенням нових дерев і справу з покажчиками тощо. Раніше, коли ми маємо справу з покажчиками, всякий раз, коли ми malloc'd ми хотіли переконатися, що він не повернув нам NULL значення покажчика. Таким чином, на кілька кроків в рамках цього процесу там буде кілька випадків де ваша програма може не спрацювати. Те, що ви хочете зробити, ви хочете, щоб переконатися, що ви обробляти ці помилки, і в специфікації він говорить з ними впоратися витончено, так як роздрукувати повідомлення користувачу говорити їм, чому програма повинна вийти і потім швидко вийти з нього. Для цього обробка помилок, пам'ятайте, що ви хочете, щоб перевірити його кожен раз, що не може бути відмови. Кожен раз, коли ви робите новий покажчик Ви хочете, щоб переконатися, що це успіх. Перш, ніж те, що ми робили, роблять новий покажчик і Танос це, і тоді ми б перевірити, що покажчик NULL. Так що збираєтеся бути в деяких випадках, коли ви просто можете зробити це, але іноді ви насправді виклику функції і в рамках цієї функції, це той, який робить mallocing. У тому випадку, якщо ми оглянемося на деяких функцій в коді, Деякі з них є логічними функціями. В абстрактному випадку, якщо у нас є булева функція називається Foo, В принципі, ми можемо припустити, що на додаток до Foo робити те, що робить, так як це булева функція, вона повертає істинне або помилкове - вірно, якщо успішно, якщо не помилковим. Тому ми хочемо, щоб перевірити повернене значення Foo є істинним або хибним. Якщо це неправда, це означає, що ми збираємося хочете надрукувати якусь повідомлення , А потім вийти з програми. Те, що ми хочемо зробити, це перевірити повернене значення Foo. Якщо Foo повертає брехня, то ми знаємо, що ми зіткнулися з якоюсь помилкою і ми повинні вийти з нашої програми. Спосіб зробити це, це є стан, при якому фактична функція саме ваш стан. Скажімо Foo приймає в х. Ми можемо мати в якості умови, якщо (Foo (х)). В принципі, це означає, що якщо в кінці виконання Foo він повертає істину, Потім ми можемо зробити це, тому що функція має оцінити Foo для того, щоб оцінити загальний стан. Таким чином, то це, як ви можете зробити щось, якщо функція повертає істину і успішно. Але коли ти помилок, ви тільки хочете кинути курити, якщо ваша функція повертає брехня. Що ви можете зробити, це просто додати == помилкових або просто додати вибуху перед ним , А потім, якщо у вас є (! Foo). В рамках цього тіла, що умова вам доведеться все обробки помилок, так як, "Не вдалося створити це дерево", а потім повертає 1 або щось на зразок цього. Те, що це робить, проте, в тому, що навіть якщо Foo повернулися помилкової - Скажімо Foo повертає істину. Тоді вам не доведеться викликати Foo знову. Це поширена помилка. Тому що це було у вашому стані, це вже оцінка, так у вас вже є результат, якщо ви використовуєте зробити дерево або щось на зразок того рослин або забрати або щось. Він уже має це значення. Це вже виконана. Так що це корисно використовувати булеві функції як умова тому що ви чи ні насправді виконати тіло циклу, він виконує функцію в будь-якому випадку. 

Наша друга до останнього кроку пише повідомлення у файл. Як тільки ми побудуємо дерево Хаффмана, то написання повідомлень в файл досить просто. Це досить просто тепер просто дотримуйтесь 0 і 1. І так за традицією ми знаємо, що в дереві Хаффмана 0s вказують залишив і 1s вказує вправо. Отже, якщо ви читали в біт за бітом, кожен раз, коли ви отримаєте 0 Ви будете дотримуватися лівої гілки, а потім кожен раз, коли ви читаєте в 1 Ви збираєтеся слідувати правої гілки. І тоді ви будете продовжувати, поки ви натиснете лист тому що листя буде в кінці гілки. Як ми можемо сказати, чи будемо ми потрапили листя чи ні? Ми говорили це раніше. [Студент] Якщо покажчиків NULL. >> Да. Ми можемо сказати, якщо ми потрапили листя, якщо покажчики на лівого і правого дерева NULL. Perfect. Ми знаємо, що ми хочемо читати по крупицях в нашому файлі Хафф. Як ми бачили раніше в dump.c, що вони зробили, вони читали в біт за бітом в файл Huff і просто роздрукувати те, що ці біти були. Ми не збираємося робити цього. Ми будемо робити те, що це трохи більш складним. Але що ми можемо зробити, ми можемо вважати, що шматок коду, який читає в біт. Тут ми маємо ціле біт, що представляє поточний біт, якою ми йдемо. Це піклується про перебір всіх бітів в файл, поки ви не потрапили в кінець файлу. Грунтуючись на цьому, то ви будете хотіти мати якийсь ітератор пройти дерева. А потім залежно від того біт дорівнює 0 або 1, Ви збираєтеся хочете чи рухатися, що ітератор на лівому або перемістити його в правий всю дорогу, поки ви натиснете аркуша, так всю дорогу, поки цей вузол, що ви на не вказує на будь-якому більш вузлів. Чому ми можемо зробити це за допомогою файлу Хаффман, але не азбуки Морзе? Тому що в азбуці Морзе є трохи двозначності. Ми могли би бути схожим, ой, почекайте, ми потрапили листи по шляху, так що, можливо, це наш лист, в той час як, якщо б ми продовжували тільки трохи довше, то ми б потрапили ще один лист. Але це не відбудеться в кодуванні Хаффмана, так що ми можемо бути впевнені, що єдиний спосіб, яким ми збираємося вдарити характер , Якщо ліва і права дітей цього вузла є NULL. 

Нарешті, ми хочемо, щоб звільнити всі наші пам'яті. Ми хочемо, щоб як закрити файл Хафф, що ми маємо справу з а також видалити всі дерева в нашому лісі. Грунтуючись на ваших реалізації, ви, ймовірно, захочете подзвонити видалити лісі а насправді переживає всі дерева самостійно. Але якщо ви зробили будь тимчасові дерева, ви хочете, щоб звільнити це. Ви знаєте, ваш код краще, так що ви знаєте, де ви виділенні пам'яті. І так, якщо ви йдете в, почнемо з управління F'ing навіть для Танос, бачите, коли ви Танос і переконавшись, що ви звільняєте всі, що але потім просто переживає свій код, розуміння, де ви могли б виділеної пам'яті. Зазвичай ви могли б просто сказати: "В кінці файлу Я просто хочу, щоб видалити лісі на мій ліс», так в основному ясно, що пам'ять, безкоштовно, що, », А потім я також збираюся, щоб закрити файл, а потім моя програма буде кинути курити». Але в тому, що єдиний раз, коли ваша програма завершує свою роботу? Ні, тому що іноді, можливо, було помилкою, що сталося. Може бути, ми не могли відкрити файл або ми не могли зробити інше дерево або якась помилка сталася в процесі розподілу пам'яті і тому він повертається NULL. Сталася помилка, і потім ми повернулися і кинути палити. Отже ви хочете, щоб переконатися, що будь-яке можливе час, що ваша програма може кинути палити, Ви хочете, щоб звільнити всі ваші пам'яті там. Це не просто буде в самому кінці головної функції, яку ви кинути свій код. Ви хочете, щоб озирнутися назад, щоб кожен екземпляр, що ваш код потенційно може повернутися передчасно , А потім звільнити пам'ять все, що має сенс. Скажімо, ви закликали зробити лісів і повернувся помилковим. Тоді ви, напевно, не потрібно буде видалити лісі тому що ви не маєте лісі ще немає. Але в кожній точці в коді, де ви могли б повернутися передчасно Ви хочете, щоб переконатися, що ви звільнити будь-які можливі пам'яті. 

Тому, коли ми маємо справу з звільнення пам'яті і має потенційні витоку, Ми хочемо, щоб не тільки використовувати наші судження і наші логіки але також використовувати Valgrind визначити, чи є ми звільнили всіх наших пам'яттю на належному рівні чи ні. Ви можете запустити Valgrind на Puff, а потім ви повинні також пройти його правильну кількість аргументів командного рядка для Valgrind. Ви можете запустити, але на виході виходить трохи загадкове. Ми отримали трохи звикнути до нього з Speller, але нам все ще потрібно трохи більше допомоги, так, то запустити його ще з кількома прапорами, як витік перевірити = повний, , Що, ймовірно, дасть нам більш корисним виходом на Valgrind. 

Потім ще корисну пораду при налагодженні це команда порівняння. Ви можете отримати доступ до здійснення співробітників про Хафф, запустити, що в текстовому файлі, , А потім виводити їх у бінарний файл, двійковий файл Хафф, щоб бути певним. Тоді, якщо ви використовуєте свій власний листковому на що двійковий файл, Потім ідеалі, виведеного текстового файлу буде ідентичним вихідного, що ви пройшли дюйма Тут я використовую hth.txt в якості прикладу, і це одна говорили у вашій специфікації. Ось буквально тільки що HTH, а потім рядки. Але, безумовно, відчувати себе вільно і ви, безумовно, рекомендується використовувати більше прикладів для вашого текстового файлу. 

Ви навіть можете взяти постріл в можливо стиснення і декомпресію, то деякі з файлів, які ви використовували в Speller, як війна і мир або Джейн Остін або щось подібне до цього - це було б круто - або Остіна Пауерса, вид роботи з великими файлами, тому що ми б не дійшли до цього якби ми використовували наступний інструмент тут, LS-л. Ми звикли до Ls, які в основному перераховані всі вміст в нашому поточному каталозі. Переходячи в флаг-L насправді відображає розмір цих файлів. Якщо ви йдете через специфікацію PSET, насправді проведе вас через створення бінарних файлів, з пихкаючи, і ви побачите, що для дуже маленьких файлів простору вартості стискаючи його і перекладав усе, що інформація всіх частот і тому подібні речі перевищує фактичну вигоду стиснути файл в першу чергу. Але якщо ви запустите його на кілька довгих текстових файлів, то ви можете бачити, що ви почнете одержувати деяку вигоду В стиснення цих файлів. 

І, нарешті, у нас є наш старий приятель GDB, який, безумовно, буде згодяться теж. 

Чи є у нас якісь питання по деревах Хафф або процес, можливо, прийняття дерев або будь-які інші питання по Puff Huff'n? Добре. Я залишуся навколо деякий час. 

Спасибі всім. Це було Покрокове керівництво 6. І удачі. 

[CS50.TV]