Кратко и по сути.

Определения (формулы):

Энтропия Шеннона для дискретного источника (X): [
H(X) = -\sum_{x} P(x)\log_2 P(x).
]
Она измеряет среднее количество бит на символ при оптимальном кодировании при заданном распределении (P).Колмогоровская (алгоритмическая) сложность строки (s): [
K(s) = \min{\,|p|:\;U(p)=s\,},
]
где (U) — фиксированная универсальная машина Тьюринга, (p) — программа, выводящая (s). Это длина кратчайшей программы, генерирующей конкретный объект.

Конкретные примеры строк/файлов:

Чередующаяся строка длины (n): (s = 0101\ldots) (пара «01» повторена (n/2) раз).

Если смотреть только частоты отдельных символов, то (p(0)=p(1)=1/2) и односимвольная энтропия [
H_{\text{1-сим}} = 1\ \text{бит/символ},\quad\text{итого } n\ \text{бит}.
]Но при учёте структуры (модель порядка 1 или правила «повторять 01») реальная средняя энтропия может быть близка к (0) после первого символа. Колмогоровская сложность мала: [
K(s)=O(\log n)
]
(программа «напечатать '01' (n/2) раз»).Практически компрессоры типа LZ сожмут строку почти до константы + логарифмической по (n).

Случайная битовая строка длины (n) (равномерно случайна):

Энтропия по символам примерно [
H\approx 1\ \text{бит/символ},\quad\text{итого } \approx n\ \text{бит}.
]Колмогоровская сложность близка к (n): [
K(s)\approx n.
]Компрессоры не дают существенного сжатия.

Текст на естественном языке (английский):

Односимвольная энтропия ≈ (4)–(4.5) бит/символ, но с учётом длинных контекстов эффективная энтропия падает (оценки пер-симв. порядка (1)–(1.5) бит/симв при больших контекстах).(K(s)) может быть значительно выше единичной энтропии, но компрессоры с хорошей моделью (PPM, контекстные модели, трансформеры как предикторы) приближают кодирование к (H).Файл с грамматикой и цитатами — низкая (K) относительно «блочной» энтропии, если модель может выразить правила.

Ключевые различия и связи:

Шеннон — статистическая, относится к источнику/распределению; даёт предельную среднюю длину кода. Колмогоров — индивидуальная, свойство конкретного объекта (без предположения о распределении).Для вычислимых распределений (P) и строки (x) верно нестрогое соотношение (верхняя оценка): [
K(x) \le -\log_2 P(x) + K(P) + O(1),
]
то есть для «типичных» строк от вычислимого источника (K(x)) примерно равна (-\log P(x)) плюс константа.Колмогоровская сложность невычислима (не существует алгоритма, дающего точный (K(s)) для всех (s)); можно лишь получить верхние оценки (через сжатие). Энтропию можно оценивать статистически из выборки (и получить теоретические пределы: кодовая длина ≥ (H)).

Практические ограничения при оценке:

Энтропия:
Нужна модель/оценка распределения (частотный подсчёт, марковские/контекстные модели); неправильная модель — неточный результат.Для больших контекстов требуется много данных (комбинаторный взрыв параметров).Оценки имеют статистическую погрешность и смещение при малых выборках.Колмогоровская сложность:
Теоретически невычислима; на практике оценивают с помощью компрессоров: [
K(s) \lesssim |C(s)| + c,
]
где (|C(s)|) — длина результата конкретного компрессора, (c) — константа (описание декомпрессора).Разные компрессоры дают разные приближения; они ограничены памятью/контекстом и алгоритмическими приёмами (LZ ориентирован на повторения, PPM — на кратные контексты, трансформеры — на статистические зависимости).Длинные алгоритмические закономерности (например, «первые (n) цифр числа π») не будут сжаты ничем, кроме программного описания; обычные компрессоры этого не обнаружат.

Отражение на методах сжатия данных:

Энтропийные кодеры (Хаффман, арифметическое кодирование) оптимальны при заданной модели распределения; ставка — точность модели.Универсальные/адаптивные методы (LZ, PPM, BWT+M) стремятся приблизиться к энтропии источника без явной предварительной модели; по теореме сходимости для стационарных эргодических источников средняя длина кода этих алгоритмов стремится к (H).Алгоритмическая сложность связывает компрессоры и «истинную» описательную длину: хороший компрессор даёт практическую верхнюю оценку (K(s)). Методы типа NCD (normalized compression distance) используют это для измерения схожести объектов.Ограничения реализуются в виде: конечный контекст, буфер окна, табличный размер модели — всё это мешает уловить очень длинные или «алгоритмически простые» зависимости.

Когда использовать что:

Для задач кодирования/канальных оценок и проектирования кодеков: используйте Шеннонову энтропию и модели распределений.Для обнаружения структур/регулярностей в отдельных объектах, оценки «насколько строка сложна», сравнения объектов по схожести (NCD), формализации «простоты гипотез»: ориентируйтесь на идеи колмогоровской сложности (на практике — на сжатие).Для тестирования случайности и криптографии: Kolmogorov — теоретически релевантна (объекты с высоким (K) «случайны»), но на практике применяют статистические тесты и оценки энтропии источника.

Короткие рекомендации:

Если есть стационарный источник и нужно минимизировать среднюю длину кода — работайте с оценкой (H) и энтропийным кодированием.Если анализируете конкретный файл/строку на предмет алгоритмической структуры или сравниваете объекты — используйте компрессоры как практические приближения (K) (и помните про их ограничения).Для выводов о предельной сжимаемости как свойства набора файлов: комбинируйте — оцените энтропию по моделям и проверяйте практические компрессоры; низкая (H) или маленький результат компрессии — разные стороны одной упорядоченности.

Если нужно — приведу конкретные численные симуляции (пример: длина (n=1000), результаты компрессии «0101...» vs случайной строки vs текста).