Як працює стиснення даних без втрат | Журнал Quanta

Щодня Інтернетом подорожує понад 9 мільярдів гігабайт інформації, тому дослідники постійно шукають нові способи стиснення даних у менші пакети. Передові методи зосереджені на підходах із втратами, які досягають стиснення шляхом навмисної «втрати» інформації з передачі. Google, наприклад, нещодавно оприлюднив стратегію з втратами, коли комп’ютер-відправник видаляє деталі із зображення, а комп’ютер-одержувач використовує штучний інтелект, щоб вгадати відсутні частини. Навіть Netflix використовує підхід із втратами, знижуючи якість відео щоразу, коли компанія виявляє, що користувач дивиться на пристрої з низькою роздільною здатністю.

Навпаки, наразі проводиться дуже мало досліджень щодо стратегій без втрат, коли передачі зменшуються, але не приноситься в жертву суть. Причина? Підходи без втрат вже надзвичайно ефективні. Вони працюють у всьому, від стандарту зображень JPEG до повсюдної утиліти програмного забезпечення PKZip. І все через аспіранта, який просто шукав вихід із важкого випускного іспиту.

Сімдесят років тому професор Массачусетського технологічного інституту на ім’я Роберт Фано запропонував студентам у своєму класі теорії інформації вибір: скласти традиційний випускний іспит або вдосконалити провідний алгоритм стиснення даних. Фано міг або не повідомляв своїх студентів, що він є автором цього існуючого алгоритму, або що він роками шукав удосконалення. Що ми знаємо, так це те, що Фано запропонував своїм студентам наступний виклик.

Розгляньте повідомлення, яке складається з літер, цифр і знаків пунктуації. Простим способом кодування такого повідомлення було б призначити кожному символу унікальне двійкове число. Наприклад, комп’ютер може представити літеру A як 01000001, а знак оклику як 00100001. Це призводить до кодів, які легко розібрати — кожні вісім цифр або бітів відповідають одному унікальному символу — але жахливо неефективно, оскільки те саме число двійкових цифр використовується як для поширених, так і для незвичайних записів. Кращим підходом було б щось на кшталт азбуки Морзе, де часта літера E представлена ​​лише однією крапкою, тоді як менш поширена Q вимагає довшого та трудомісткого тире-тире-крапка-тире.

Проте азбука Морзе теж неефективна. Звичайно, деякі коди короткі, а інші довгі. Але оскільки довжина коду різна, повідомлення азбукою Морзе неможливо зрозуміти, якщо вони не включають короткі періоди мовчання між передачею кожного символу. Дійсно, без цих дорогих пауз одержувачі не мали б способу відрізнити повідомлення Морзе тире крапка-тире-крапка крапка тире крапка («банальне») від тире крапка-тире-крапка крапка-тире-крапка («правда» ).

Фано вирішив цю частину проблеми. Він зрозумів, що може використовувати коди різної довжини, не потребуючи дорогих пробілів, якщо він ніколи не використовує той самий шаблон цифр як повний код, так і як початок іншого коду. Наприклад, якби літера S була настільки поширеною в певному повідомленні, що Фано присвоїв їй надзвичайно короткий код 01, тоді жодна інша літера в цьому повідомленні не кодувалася б тим, що починалося б з 01; такі коди, як 010, 011 або 0101, будуть заборонені. У результаті закодоване повідомлення можна було прочитати зліва направо без будь-якої двозначності. Наприклад, якщо літері S присвоєно 01, літері A присвоєно 000, літері M присвоєно 001 і літері L присвоєно 1, раптом повідомлення 0100100011 може бути негайно перекладено словом «маленький», навіть якщо L представлено одним цифра, S по дві цифри, а інші літери по три.

Щоб фактично визначити коди, Фано побудував двійкові дерева, розмістивши кожну необхідну букву в кінці візуальної гілки. Потім код кожної літери визначався шляхом зверху вниз. Якщо шлях розгалужувався ліворуч, Фано додавав 0; праві гілки отримали 1. Структура дерева дозволила Фано уникнути цих небажаних накладень: як тільки Фано розмістить літеру в дереві, ця гілка закінчуватиметься, тобто жоден майбутній код не зможе починатися так само.

Щоб вирішити, які літери куди міститимуться, Фано міг би вичерпно перевірити всі можливі шаблони для досягнення максимальної ефективності, але це було б непрактично. Тож замість цього він розробив наближення: для кожного повідомлення він упорядковував відповідні літери за частотою, а потім призначав літери гілкам так, щоб літери зліва в будь-якій заданій парі гілок використовувалися в повідомленні приблизно таку ж кількість разів, як і літери праворуч. Таким чином, часто використовувані символи потраплятимуть на коротші, менш щільні гілки. Невелика кількість високочастотних літер завжди врівноважує більшу кількість низькочастотних.

Результатом було надзвичайно ефективне стиснення. Але це було лише наближення; мала існувати краща стратегія стиснення. Тож Фано викликав своїх студентів знайти його.

Фано будував свої дерева зверху вниз, зберігаючи якомога більшу симетрію між парними гілками. Його учень Девід Хаффман перевернув процес з ніг на голову, будуючи ті самі типи дерев, але знизу вгору. Хаффман прийшов до висновку, що, що б не трапилося, в ефективному коді два найменш поширених символи повинні мати два найдовші коди. Отже, Хаффман визначив два найменш поширених символи, згрупував їх разом як розгалужену пару, а потім повторив процес, цього разу шукаючи два найменш поширені записи серед символів, що залишилися, і пари, яку він щойно створив.

Розглянемо повідомлення, де підхід Фано дає збої. У «шкільній кімнаті» O з’являється чотири рази, а S/C/H/L/R/M кожен з’являється по одному разу. Балансуючий підхід Фано починається з присвоєння О та ще однієї літери лівій гілці, причому п’ять загальних використань цих літер урівноважують п’ять появ решти літер. Отримане повідомлення вимагає 27 біт.

Хаффман, навпаки, починає з двох незвичайних літер — скажімо, R і M — і групує їх разом, розглядаючи пару як одну букву.

Потім його оновлена ​​частотна діаграма пропонує йому чотири варіанти: O, що з’являється чотири рази, новий комбінований вузол RM, який функціонально використовується двічі, і окремі літери S, C, H і L. Хаффман знову вибирає два найменш поширених варіанти, відповідаючи (скажи) H з L.

Діаграма знову оновлюється: O все ще має вагу 4, RM і HL тепер мають вагу 2, а літери S і C стоять окремо. Хаффман продовжує звідти, на кожному кроці групуючи два найменш часті варіанти, а потім оновлюючи як дерево, так і діаграму частот.

Зрештою, «шкільна кімната» стає 11101111110000110110000101, трохи позбавляючи підходу Фано «зверху вниз».

Один біт може здатися невеликим, але навіть невеликі заощадження значно збільшуються при масштабуванні мільярдами гігабайтів.

Дійсно, підхід Хаффмана виявився настільки потужним, що сьогодні майже кожна стратегія стиснення без втрат повністю або частково використовує розуміння Хаффмана. Потрібен PKZip для стиснення документа Word? Перший крок включає в себе ще одну розумну стратегію для виявлення повторів і, таким чином, стиснення розміру повідомлення, але другий крок полягає в тому, щоб взяти результуюче стиснене повідомлення та пропустити його через процес Хаффмана. Зберегти зображення як JPEG? Ваш комп’ютер спочатку перетворює зображення на текстове подання, а потім знову використовує кодування Хаффмана для стиснення цього тексту.

Непогано для проекту, спочатку мотивованого бажанням аспіранта пропустити випускний іспит.