Алфавітний нерівномірне двійкове кодування
Алфавітний нерівномірне двійкове кодування - кодування при якому символи деякого первинного алфавіту кодуються комбінаціями символів двійкового алфавіту (тобто 0 і 1), причому, довжина кодів і, відповідно, тривалість передачі окремого коду, можуть відрізнятися.
Префіксний код в теорії кодування - код зі словом змінної довжини, що має таку властивість (виконання умови Фано): якщо в код входить слово a, то для будь-якої непорожній рядки b слова ab в коді не існує. Хоча префіксний код складається з слів різної довжини, ці слова можна записувати без розділового символу.
Наприклад, код, що складається з слів 0, 10 і 11, є префіксним, і повідомлення 01001101110 можна розбити на слова єдиним чином:
0 10 0 11 0 11 10
Код, що складається зі слів 0, 10, 11 і 100, префіксним не є, і те саме повідомлення можна трактувати декількома способами.
0 10 0 11 0 11 10
0 100 11 0 11 10
Ідея, покладена в основу кодування Хаффмана, заснована на частоті появи символу в послідовності. Символ, який зустрічається в послідовності найчастіше, отримує новий дуже маленький код, а символ, який зустрічається найрідше, отримує, навпаки, дуже довгий код. Це потрібно, так як ми хочемо, щоб, коли ми обробили весь введення, самі частотні символи зайняли найменше місця (і менше, ніж вони займали в оригіналі), а рідкі - побільше (але так як вони рідкісні, це не має значення ). У даній статті я вирішив, що символ буде мати довжину 8 біт, тобто, буде відповідати друкованого знаку.
Припустимо, у нас є рядок «beep boop beer!», Для якої, в її теперішньому вигляді, на кожен знак витрачається по одному байту. Це означає, що вся рядок цілком займає 15 * 8 = 120 біт пам'яті. Після кодування рядок займе 40 біт.
Щоб отримати код для кожного символу рядка «beep boop beer!», На основі його частотності, нам треба побудувати бінарне дерево, таке, що кожен лист цього дерева буде містити символ (друкований знак з рядка). Дерево буде будуватися від листя до кореня, в тому сенсі, що символи не так часто будуть далі від кореня, ніж символи з більшою. Скоро ви побачите, для чого це потрібно.
Щоб побудувати дерево, ми скористаємося злегка модифікованої чергою з пріоритетами - першими з неї будуть вилучатись елементи з найменшим пріоритетом, а не найбільшим. Це потрібно, щоб будувати дерево від листя до кореня.
Для початку порахуємо частоти всіх символів:
Після обчислення частот ми створимо вузли бінарного дерева для кожного знака і додамо їх в чергу, використовуючи частоту в якості пріоритету:
Тепер ми дістаємо два перших елемента з черги і пов'язуємо їх, створюючи новий вузол дерева, в якому вони обидва будуть нащадками, а пріоритет нового вузла буде дорівнює сумі їх пріоритетів. Після цього ми додамо вийшов новий вузол назад в чергу.
Повторимо ті ж кроки і отримаємо послідовно:
Ну і після того, як ми зв'яжемо два останніх елемента, вийде підсумкове дерево:
Тепер, щоб отримати код для кожного символу, треба просто пройтися по дереву, і для кожного переходу додавати 0, якщо ми йдемо вліво, і 1 - якщо направо:
Якщо ми так зробимо, то отримаємо наступні коди для символів:
Щоб розшифрувати закодовану рядок, нам треба, відповідно, просто йти по дереву, згортаючи в відповідну кожному біту сторону до тих пір, поки ми не досягнемо листа. Наприклад, якщо є рядок «101 11 101 11» і наше дерево, то ми отримаємо рядок «pepe».
Важливо мати на увазі, що кожен код не є префіксом для коду іншого символу. У нашому прикладі, якщо 00 - це код для "b", то 000 не може виявитися чиєюсь кодом, тому що інакше ми отримаємо конфлікт. Ми ніколи не досягли б цього символу в дереві, так як зупинялися б ще на "b".