Презентація використовується під час пояснення теми "Стиснення інформації" у 9 класі для розуміння учнями процесу стиснення інформації. Тут застосовано метод Хаффмана, суть якого пояснюється на прикладах скоромовок.
Алгоритм стиснення Девіда Хаффмана Дэвід Хаффман - автор відомого алгоритму стискування текстових даних. Він народився в 1925 році в американському штаті Огайо. У 18 років Дэвід отримав ступінь бакалавра електротехніки в університеті штату. Основну концепцію кодування даних Хаффман розробив під час Другої світової війни, коли служив на есмінцеві офіцером-зв'язківцем. Окрім створення методу мінімально-надлишкових кодів, Хаффман зробив важливий крок в розвитку багатьох перспективних областей електроніки. За свою діяльність він отримав безліч нагород, у тому числі медаль Річарда Хаммінга від Інституту інженерів електрики і електроніки (IIEE) за винятковий вклад в теорію інформації.
Був розроблений у 1952 році під час написання курсової роботи в аспірантурі Массачусецького технологічного інституту. Сьогодні використовується в багатьох програмах стиснення даних. Ідея, покладена в основу кодування Хаффмана, грунтується на частоті появи символу в послідовності. Символ, який зустрічається в послідовності найчастіше, отримує новий дуже маленький код, а символ, який зустрічається найрідше, отримує довгий код. Алгоритм стиснення Девіда Хаффмана
Ворона проворонила вороненя. 28 символів х 1 байт (8 бітів) = 28 байт (224 біти) В – 3; О – 7; Р – 4; Н – 4; А – 2; П – 1; И – 1; Л – 1; Е – 1; Я – 1; Пробіл – 2; Крапка – 1. О – 7 Р – 4 Н – 4 В – 3 А – 2 Пробіл – 2 П – 1 И – 1 Л – 1 Е – 1 Я – 1 Крапка – 1 2 1 0 2 1 0 2 1 0 4 1 0 4 1 0 5 1 0 8 1 0 8 1 0 13 1 0 15 1 0 28 1 0 О – 11; Р – 101; Н -100; В – 011; А – 010; Пробіл – 0011; П – 00101; И – 00100; Л – 00011; Е – 00010; Я – 00001; Крапка – 00000. 0111110111100010001100101101110111110111100001000001101000110111110111100000101000000100000 Довжина коду - 91 біт
Боронила борона по боронованому полю. 37 символів х 1 байт (8 бітів) = 37 байтів (296 бітів) Б - 3 О - 10 Р - 3 Н - 4 И - 1 Л - 2 А - 3 П - 2 В - 1 М - 1 Ю - 1 У - 1 Пробіл - 4 . - 1 О - 10 Пробіл - 4 Н - 4 Б - 3 Р - 3 А - 3 Л - 2 П - 2 И - 1 В - 1 М - 1 У - 1 Ю - 1 . - 1 2 1 0 2 1 0 2 1 0 4 1 0 4 1 0 5 1 0 6 1 0 8 1 0 8 1 0 11 1 0 18 1 0 19 1 0 37 1 0 О – 11; Пробіл – 101; Н – 100; Б – 0111; Р – 0110; А – 0101; Л – 0100; П – 0011; И – 00101; В – 00100; М – 00011; У – 00010; Ю – 00001; Крапка – 00000.
Боронила борона по боронованому полю. О – 11; Пробіл – 101; Н – 100; Б – 0111; Р – 0110; А – 0101; Л – 0100; П – 0011; И – 00101; В – 00100; М – 00011; У – 00010; Ю – 00001; Крапка – 00000. 01111101101110000101010001011010111110110111000101101001111101 0111110110111001100100010110011000110001010100111101000000100000 Довжина коду - 126 бітів