# Стэнфорд: неравенство Крафта и пределы сжатия данных

Источник: https://www.youtube.com/watch?v=kbAif7XhlTI
Канал: Stanford Online
Опубликовано: 18.04.2024

---

## Введение в сжатие данных: неравенство Крафта и энтропия
[[JUMP:0:05]]

Лекция №3 курса EE274 в Стэнфордском университете посвящена теоретическим основам сжатия данных без потерь (lossless compression). Ведущий подробно рассматривает две фундаментальные концепции: неравенство Крафта, определяющее структуру кодов, и энтропию — математический предел эффективности сжатия. Учебный материал дополняется знакомством с библиотекой SCL (Stanford Compression Library), предназначенной для реализации алгоритмов сжатия в исследовательских целях.

## 📚 Stanford Compression Library (SCL)
[[JUMP:1:02]]

Stanford Compression Library — это инициатива, запущенная для того, чтобы сделать изучение алгоритмов сжатия более доступным. По словам ведущего, поиск понятных и читаемых реализаций алгоритмов часто затруднен, так как большинство готовых решений написаны на низкоуровневом C или используют сложные SIMD-инструкции, что мешает пониманию теории.

Цели создания SCL:

*   Обеспечение читаемости кода для начинающих исследователей.
*   Создание гибкого фреймворка, позволяющего расширять существующие алгоритмы.
*   Углубление понимания самих исследователей через процесс написания кода.

Инструментарий библиотеки включает вспомогательные функции для преобразования массивов битов в байты (так как компьютеры оперируют байтами, а алгоритмы часто работают с битами) и манипуляций с деревьями. Библиотека является ключевым ресурсом для выполнения домашних заданий курса.

## ⚖️ Неравенство Крафта
[[JUMP:11:04]]

Неравенство Крафта предлагает математическую характеристику префиксных кодов. Это фундаментальный инструмент, позволяющий определить, может ли существовать префиксный код с заданными длинами кодовых слов $l_1, \dots, l_k$.

Основные положения:

*   **Прямая теорема:** для любого префиксного кода выполняется условие $\sum_{i=1}^{k} 2^{-l_i} \le 1$.
*   **Обратная теорема:** если набор целых чисел $l_1, \dots, l_k$ удовлетворяет этому неравенству, то существует префиксный код с такими длинами.

Ведущий подчеркивает, что знание этого неравенства позволяет проверять коды, даже не глядя на сами кодовые слова, а лишь на их длины. Для оптимального кода это неравенство должно выполняться как равенство.

## 📉 Энтропия и пределы сжатия
[[JUMP:26:58]]

Энтропия определяется как величина $H(X) = \sum P_i \log \frac{1}{P_i}$ и измеряется в битах. Она является мерой неопределенности или количества информации в источнике.

Ключевые выводы лекции:

*   **Фундаментальный предел:** ни один префиксный код не может иметь среднюю длину кодового слова меньше, чем энтропия.
*   **Достижимость:** Shannon code (код Шеннона) всегда находится в пределах одного бита от энтропии ($H(X) \le L < H(X) + 1$).
*   **Блочное кодирование:** для достижения энтропии с любой степенью точности необходимо использовать блочное кодирование (объединение символов в блоки по $n$ штук), что позволяет уменьшить зазор до $1/n$.

Ведущий отмечает, что, хотя коды Шеннона просты в реализации, они часто проигрывают по эффективности кодам Хаффмана или более современным методам, таким как арифметическое кодирование и ANS (Asymmetric Numeral Systems), которые будут подробно рассмотрены в будущих лекциях.