Уявіть, що вам потрібно переписати від руки книгу. Якщо в ній кожне слово трапляється рівно один раз і жодна фраза не повторюється — вам доведеться переписати кожен символ. Але якщо книга містить повторювані слова, фрази, навіть цілі абзаци — ви могли б домовитися з читачем: "тут — те саме, що й там". Саме на цій ідеї тримається вся теорія стиснення інформації.
Слід усвідомити спочатку, що патерн це не просто "щось, що повторюється". Це структура, яка несе в собі передбачуваність. А передбачуваність — це те, що дозволяє нам не говорити зайвого.
Ентропія: міра непередбачуваності
Клод Шеннон 1948 року запропонував поняття, яке перевернуло розуміння інформації. Він назвав його ентропією — за аналогією з термодинамікою, але в зовсім іншому сенсі.
"Кількість інформації в повідомленні визначається не його довжиною, а його непередбачуваністю." — Клод Шеннон, "Математична теорія комунікації", 1948
Формально ентропія джерела виражається так:
$$H = -\sum_{i} p_i \log_2 p_i$$
де \( p_i \) — ймовірність появи кожного символу. Якщо якийсь символ зустрічається дуже часто — він несе мало інформації. Якщо рідко — несе багато. Це й є математична основа того, чому патерни дозволяють стискати дані: там, де є повторення, ентропія низька, і значить — є простір для скорочення.
Простий приклад: рядок AAAAAААААA має майже нульову ентропію. Нам не потрібно зберігати десять символів — достатньо записати "A, 10 разів". Саме так і працює метод RLE (Run-Length Encoding) — один із найстаріших і найпростіших алгоритмів стиснення.
Алгоритми, що "шукають" патерни
Реальні дані рідко складаються з однакових символів поспіль. Але патерни в них все одно є — просто менш очевидні. Алгоритми стиснення навчилися їх знаходити.
LZ77 і словникове стиснення
1977 року Авраам Лемпел і Якоб Зів запропонували підхід, який змінив галузь. Ідея полягала в тому, щоб замість повторення фрагмента тексту вставляти посилання на попереднє місце, де він вже траплявся.
Уявіть такий рядок:
abcabcabcЗамість того щоб зберігати всі 9 символів, алгоритм записує: abc, а потім — "повтори попередні 3 символи двічі". Замість 9 символів — значно менше. На цьому принципі побудовані формати gzip, ZIP, PNG і багато інших.
Алгоритм Хаффмана: коли частота вирішує все
Девід Хаффман у 1952 році розробив метод, що базується на іншому виді патернів — статистичних. Якщо якийсь символ зустрічається частіше, йому призначається коротший код. Рідкісні символи отримують довші коди.
Це схоже на абетку Морзе: "е" — крапка, "ж" — три крапки і тире. Найчастіші — найкоротші. В результаті середня довжина повідомлення скорочується. Алгоритм Хаффмана досі використовується в JPEG, MP3 і PDF.
Що таке надлишковість інформації і чому вона важлива
Надлишковість (redundancy) — це та частина повідомлення, яка не додає нової інформації, але допомагає відновити її у разі втрати або помилки. Природня мова має надлишковість близько 50%: якщо в рядку відсутні кожна друга літера, текст усе одно читається. Це пояснює, чому стиснення без втрат можливе для тексту, але обмежене для вже стиснених даних — там надлишковість вже усунена.
Патерни у машинному навчанні
Тут починається найцікавіше. Стиснення і навчання — це, по суті, одне й те саме, якщо дивитися під правильним кутом.
Коли нейронна мережа навчається на мільярдах текстів, вона не "запам'ятовує" кожне речення. Вона знаходить патерни — граматичні конструкції, типові асоціації між словами, логічні структури — і кодує їх у ваги. Модель з мільярдом параметрів, навчена на петабайтах даних, — це і є форма стиснення: величезний обсяг інформації "упакований" у компактне представлення.
Ілля Суцкевер і ряд інших дослідників прямо формулювали цю думку: мовна модель, що добре передбачає наступний токен, є хорошим компресором. І навпаки — хороший компресор потребує "розуміння" структури даних.
Це не метафора. Це перевірений факт: алгоритм PAQ, один із найефективніших компресорів, внутрішньо використовує нейроноподібні моделі для передбачення символів.
Приховані патерни і латентний простір
Автоенкодери — клас нейронних мереж — навчаються стискати вхідні дані у вектор меншої розмірності, а потім відновлювати їх. Якщо мережа справляється із цим завданням — значить, у даних є структура, патерн, який вдалося вловити і закодувати.
Цей "латентний простір" — по суті словник патернів. Зображення обличчя можна описати не мільйоном пікселів, а кількома десятками координат у просторі, де закодовані форма носа, розріз очей, вираз. Стиснення через розуміння структури.
Людський мозок: природній компресор
Ми рідко думаємо про власне мислення як про алгоритм стиснення — але саме так воно і працює.
Мозок не зберігає кожен кадр побаченого — він зберігає патерни, схеми, правила. Ми не пам'ятаємо кожне слово почутого вчора розмови, але пам'ятаємо суть. Це і є стиснення з втратами — аналог JPEG для пам'яті.
- концепції замінюють конкретні факти;
- правила — окремі приклади;
- прототипи — конкретні об'єкти;
- наративи — послідовності подій.
Дитина не запам'ятовує кожну побачену собаку окремо — вона формує поняття "собака" як патерн із ключовими ознаками. Це когнітивне стиснення дозволяє нам орієнтуватися у світі, не перевантажуючи пам'ять.
"Розуміти — означає бачити патерни там, де інші бачать хаос." — Дуглас Хофштадтер, "Гедель, Ешер, Бах"
Мова як система стиснення
Мова — це ще один рівень. Слово "дерево" замінює детальний опис кожного конкретного дерева. Метафора — це стиснення складної ідеї в коротку форму. Навіть граматика — це система патернів, що дозволяє передавати нові думки за допомогою знайомих структур.
Не випадково дослідники в галузі NLP виявили, що мови з багатшою морфологією (де одне слово може виражати те, що в іншій мові потребує п'яти) стискаються ефективніше в одному вимірі, але гірше в іншому. Мови ніби "вибирають", де тримати надлишковість — у граматиці чи у словнику.
Межі стиснення: коли патернів немає
Існує теоретична нижня межа — і це знову Шеннон. Стиснути дані нижче їхньої ентропії неможливо. Якщо в даних немає жодного патерну, жоден алгоритм не зменшить їхній обсяг.
Саме тому вже стиснений файл стискається погано: патерни вже усунені. Саме тому абсолютно випадкова послідовність бітів не може бути стиснена — в ній немає структури, немає передбачуваності, немає нічого, за що міг би зачепитися алгоритм.
Це має практичні наслідки:
- Шифрування навмисно підвищує ентропію даних, роблячи їх схожими на випадковий шум — тому шифрувати треба до стиснення, а не після.
- Тестові дані для генераторів випадкових чисел перевіряють саме на нестисненість.
- Ефективність стиснення є непрямою мірою структурованості даних.
Теорема Шеннона про кодування джерела
Теорема про кодування джерела (перша теорема Шеннона) стверджує: неможливо стиснути дані в середньому до менш ніж H бітів на символ без втрат, де H — ентропія джерела. Разом з тим, існують коди, які дозволяють наблизитися до цієї межі як завгодно близько. Це означає, що ентропія — не просто абстрактна міра, а реальна фізична межа ефективності будь-якого алгоритму.
Від бітів до сенсу: єдиний принцип
Те, що об'єднує ZIP-архів, нейронну мережу і людську пам'ять — це пошук і використання повторюваних структур. Алгоритм LZ77 шукає дублікати в потоці байтів. Трансформер знаходить патерни уваги в мільярдах речень. Мозок будує схеми з повторюваного досвіду.
На всіх цих рівнях діє один принцип: якщо щось можна передбачити — його не треба передавати повністю. Якщо є правило — не треба перелічувати всі випадки. Якщо є патерн — достатньо його назви.
Це наводить на думку, що "розуміння" в найширшому сенсі — це здатність знаходити ефективні патерни у складних даних. А стиснення — не технічний трюк, а фундаментальний принцип організації інформації, від квантового рівня до культурного.
Питання, яке варто поставити собі: якщо найефективніші алгоритми стиснення наближаються до моделей, схожих на людське мислення — чи означає це, що наш мозок просто дуже добре еволюціонував як компресор реальності? Поділіться думкою в коментарях — це одна з тих тем, де межа між інформатикою і філософією стає зовсім тонкою.
Схожі публікації
