| [Відвідувач (58.214.*.*)]Відповіді [Китайський ] | Час :2022-12-17 |  Коли Хаффман запропонував цю кодування на початку п'ятдесятих років минулого століття, він побудував найкоротшу кодування середньої довжини, засновану на ймовірності появи символів. Це кодування змінної довжини. У кодуванні, якщо довжина кожного кодового слова строго розташована в зворотному порядку ймовірності появи символу, відповідного кодовому слову, середня довжина кодування найменша. (Примітка: кодове слово - це код, отриманий після кодування символу Хаффманом, і його довжина різна в залежності від ймовірності появи символу, тому код Хаффмана є більш тривалим кодуванням.) А Хаффман кодує за піддеревом батькові, в той час як його читання - прямо протилежне.
статичне кодування
Даний метод кодування є статичним кодуванням Хаффмана, яка сканує дані, що кодуються двічі: перший прохід відраховує частоту кожного символу в вихідних даних, використовує отримане значення частоти для створення дерева Хаффмана і повинен зберегти інформацію про дерево, тобто значення частоти символу 0-255 (2^8=256) зберігається в порядку довжини 2-4БАЙТ, (значення частоти зберігається в довжині 4Байт, а значення частоти виражається в діапазоні 0--2^). 32-1, чого достатньо, щоб вказати, як часто символи з'являються у великих файлах), щоб те саме дерево Хаффмана створювалося для декомпресії при розпаковці; Другий пропуск кодує дерево Хаффмана, отримане в результаті першого сканування, і зберігає закодовані кодові слова.СТАТИЧНИЙ МЕТОД КОДУВАННЯ ХАФФМАНА МАЄ І ДЕЯКІ НЕДОЛІКИ: ПО-ПЕРШЕ, КОДУВАННЯ ЗАНАДТО КОРОТКИХ ФАЙЛІВ НЕ МАЄ ВЕЛИКОГО ЗНАЧЕННЯ, ТОМУ ЩО ПРОСТО ДЛЯ ЗБЕРІГАННЯ ІНФОРМАЦІЇ ДЕРЕВА ХАФФМАНА ДОВЖИНОЮ В 4 БАЙТИ ПОТРІБНО 1024 БАЙТИ МІСЦЯ ДЛЯ ЗБЕРІГАННЯ; По-друге, при здійсненні кодування Хаффмана, при зберіганні закодованої інформації, якщо вона буде використовуватися з мережею зв'язку, це викличе велику затримку; По-третє, при кодуванні великих файлів частий доступ до читання і запису диска сповільнить швидкість кодування даних...
Динамічне кодування
Тому пізніше був запропонований динамічний метод кодування Хаффмана. Динамічне кодування Хаффмана використовує динамічно змінюється дерево Хаффмана, кодування символу t 1 базується на дереві Хаффмана, отриманому першими символами t в вихідних даних, кодування і декодування використовують одне і те ж початкове дерево Хаффмана, кожен символ, оброблений, кодування і декодування використовують один і той же метод для модифікації дерева Хаффмана, тому немає необхідності зберігати інформацію дерева Хаффмана для декодування. Час, необхідний для кодування та декодування символу, пропорційний довжині кодування цього символу, тому динамічне кодування Хаффмана можна здійснювати в режимі реального часу. Динамічне кодування Хаффмана набагато складніше, ніж статичне кодування Хаффмана, і зацікавлені читачі можуть звернутися до книг про структури даних і алгоритмах.Вищезгаданий JPEG використовує кодування Хаффмана, не те, що JPEG використовує лише кодування Хаффмана, а зображення після декількох кроків для отримання списку значень, ці значення Хаффмана кодуються для зберігання або передачі. Метод кодування Хаффмана відносно простий для розуміння, і ви можете написати власні програми кодування та декодування Хаффмана відповідно до його методу кодування.
Алгоритм побудови дерев Хаффмана.
const maxvalue= 10000; {Визначте максимальну вагу}
maxleat=30; {Визначте кількість листових вузлів на дереві Хаффмана}
maxnode=maxleaf*2-1;
введіть HnodeType=record
вага: ціле число;
батько: ціле число;
lchild: ціле число;
rchild: ціле число;
кінець;
HuffArr:масив[0..maxnode] HnodeType;
вар ......
процедура CreatHaffmanTree(var HuffNode: HuffArr); {Алгоритм побудови дерева Хаффмана}
var i,j,m1,m2,x1,x2,n: ціле число;
починатися
readln(n); {Введіть кількість листових вузлів}
for i:=0 to 2*n-1 do {array HuffNode[ ] ініціалізувати}
починатися
HuffNode.вага=0;
HuffNode.parent=-1;
HuffNode.lchild=-1;
HuffNode.rchild=-1;
кінець;
для i:=0 до n-1 do read(HuffNode.weight); {Введіть вагу n листових вузлів}
для i:=0 до n-1 do {побудувати дерево Хаффмана}
починатися
m1:=MAXVALUE; m2:=MAXVALUE;
х1:=0; х2:=0;
для j:=0 до n i-1 do
якщо (HuffNode[j].weight＜m1) і (HuffNode[j].parent=-1) тоді
початок m2:=m1; х2:=х1;
m1:=HuffNode[j].weight; х1:=дж;
кінець
інакше якщо (HuffNode[j].weight＜m2) і (HuffNode[j].parent=-1) тоді
початок m2:=HuffNode[j].weight; х2:=дж; кінець;
{Об'єднайте два піддерева, визначені в одне піддерево}
HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;
HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;
HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;
кінець;
кінець; |
|
