Logo Home   >>   F.A.Q.

F.A.Q.


Q. А какая разница между Информацией и Энтропией?

A. Нет никакой связи между этими понятиями.

Например, в известной фразе "казнить нельзя помиловать" положение запятой никоим образом не влияет на ее шенновскую энтропию. Энтропия любых анаграмм, скажем, "марс" и "срам" идентична. Если рассматривать задачу транспорта информации, то символы (коды) сообщения играют роль тары,

Энтропия - удельная мощность сообщения (на единицу тары), Избыточность - коэффициент заполнения тары.

Если требуется транспортировать 0.5 л, то это можно осуществить с помощью трех стаканов по 200 (с некоторой избыточностью), но нельзя с помощью трех стаканов по 150, поскольку это меньше "энтропийного предела" (~167).

При этом, совершенно неважно, 0.5 чего - воды, спирта, уксуса...


Q. Кривые Пеано (Гильберта) - что в них примечательного?

A. Как человек далекий от математики :-)

я бы начал с понятия инварианта: есть объект, который можно деформировать ("преобразование"), есть свойство, которое при деформации сохраняется ("инвариант"). Если, например, разлить 0.5 в три стакана, то суммарный объем налитого будет равен исходному - Инвариант !

Три неполных стакана мало похожи на полную бутылку, но "с точки зрения объема" - они эквивалентны.

Свойства, сохраняющиеся при декомпозиции системы на части важны для многих применений (в Физике они называются Законами Сохранения (Массы, Энергии итд.)) Но там, где физик ставит эксперимент с бутылкой, математик "разливает" абстрактное множество точек - и наблюдает за сохраненными свойствами - инвариантами преобразования.

Простейшим вариантом разбиения, наверное, будет деление на равные части. Более сложным - на неравные. Еще более сложным - поделить бесконечное число раз (рекурсивно).

Сами правила преобразования могут быть при этом очень просты. Например - полное отражение. Получаем стоячую волну и лазер.

Или чуть более сложными - получаем, например, кривую Гильберта или Мортона итд. Фракталы - это вариант разбиения на самоподобные части (такие, как в преобразовании Фурье, например), то есть бесконечное повторение какого-то простого приема (трансформации).

В тривиальном случае получаем бесконечное повторение самого себя (как, например, в гармоническом осцилляторе), в нетривиальном - "колебание" с бесконечным периодом. Физики будут при этом говорить о сохранении массы / энергии, математики - о сохранении размерности (равномощности).

Для фрактальных объектов важно еще, насколько "плотно" расположены точки множества: если "с зазором", то такой объект можно "сжать". Помножив "объем" на "плотность", получаем "массу" - инвариант сжатия. В Теории Информации, например, фрактальная плотность широко используется под названием "Энтропия". Помножив (удельную) энтропию на длину сообщения, получаем "количество информации нетто" - инвариант сжатия (обычно, говорят про "Энтропийный предел").


Q. Задачка на алгоритм Хаффмана

На вход алгоритма Хаффмана подается n частот кодируемых символов. Какова наибольшая длина кодов символов в худшем случае? в лучшем?

A. Две экстремальные ситуации - это полностью сбалансированное дерево (минимальной высоты) и дерево Фибоначчи (максимальной высоты). Эти деревья двойственны (дуальны) и, в вырожденном случае, совпадают. По этой причине, попытка сжатия "алфавитной" последовательности (0,1,2..n) или любой ее пермутации бессмысленна. А максимальное "сжатие" получается при инверсии - замене дерева Фибоначчи на сбалансированное.

Высота сбалансированного дерева: h = Log2(n) // округляем вверх до целого

Высота дерева Фибоначчи: h = n - 1

Это очевидно, если просто нарисовать их рядом.

В любом случае, необходимый и достаточный критерий "сжимаемости" - незаполненность пространства состояний (наличие "запрещенных" кодовых комбинаций в исходном сообщении).

Исходный и "сжатый" текст можно рассматривать как инвариантный объект в исходных и штрихованных координатах (системах кодовых последовательностей). "Сжатие" - на самом деле, (пере)кодирование - при этом эквивалентно повороту к собственной (симметрированной) системе координат - к системе наименьшего объема (максимальной информационной энтропии). Уже симметричный объект ("шар"), естественно, несжимаем. Способ поворота (метод "сжатия") - LZ, Huffman или что угодно другое, неважен, это детали реализации.


Q. Теорема Шеннона

Согласно теореме Шеннона "Элемент Si, вероятность появления которого P(Si), выгоднее всего представить - Log2(P(Si)) битами"

То есть, это минимальное значение.

В некоторых случаях при кодировании методом Хаффмана получаются коды, короче расчитанных по приведенной выше формуле. Почему так получается?

A. По этой формуле получается средняя длина кода. Коды Хаффмана (неравномерное кодирование) начинаются с однобитных - и дальше вверх. При этом средняя длина кода, обычно, больше теоретической.

IMHO, использование в ТИ аппарата теории вероятностей (влияние Н.Винера?) только препятствует пониманию.

Я бы начал с деревьев (выбора). При двоичном выборе, расщепление пространства состояний пополам отвечает продвижению на один уровень (один шаг) по дереву выбора.

Например, имеется упорядоченная последовательнось из восьми чисел: 1..8, в которой загадано одно число.

Сколько вопросов, ответ на которые Да / Нет, нужно задать для отгадывания числа? Методом деления пополам, разбиваем пространство состояний 1..8 на блоки по 4, по 2, по 1 - число угадано.

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

Это дерево идеально сбалансировано (дерево Хартли) и длина пути из корня ко всем узлам одинакова:

H = LOG2(8) = 3

Но, Шеннон избавляется от абсолютных значений (кратностей) и переходит к относительным (частотам), а, кроме того, нормирует размер пространства состояний, принимая его за 1 (100%). Таким образом, появляется "вероятность".

Для сбалансированного дерева, вес каждого узла будет 1/8 полного веса, и это и есть то самое Pi

Иными словами, от "прямых" абсолютных единиц подсчета мы перешли к "обратным" относительным.

Но само дерево от этого, естественно, не изменилось. Его высота, по-прежнему, три, но выражается через обратные величины:

H = -LOG2(1/8) = 3

Пока все это мало отличается от того, что было предложено Хартли, не считая неудобной формы записи.

И вот здесь, Шеннон вносит революционное предложение: вводит в рассмотрение несбалансированные деревья.

При этом, как всякий математик, старается свести задачу к уже известной - путем введения поправочных коэффициентов.

Если деревья Хартли были "прямыми" - в том смысле, что длина (вес) всех дуг между узлами была одинакова (1), то Шеннон строит "косое" дерево, с дугами неравной длины (неравными весами).

Для несбалансированного дерева, Шеннон вводит компенсирующие весовые коэффициенты.

Если представить теперь дерево как систему трубок (сосудов), где втекающий в корень поток жидкости разветвляется по более мелким трубкам, то эти коэффициенты выбираются из условий неразрывности потока: сколько в корне втекло, столько в сумме из всех листьев вытекло.

Запись этого условия (Закона сохранения) для потока вероятности и есть знаменитая формула Шеннона.

***

Понятно, что для "косого" дерева, длина пути от корня к листу может и не быть целым числом.

Но, когда используется целочисленное кодирование (например, коды Хаффмана), длина любого кода выражается целым числом бит. Иными словами, в общем случае, дерево Хаффмана на будет совпадать с деревом Шеннона, но будет близко к нему.

Как удалось доказать Хаффману (в то время, студенту Фано), не существует других целочисленных кодов (деревьев), которые отличались бы от дерева Шеннона меньше, чем дерево Хаффмана.

Таким образом, код Хаффмана является кодом с минимальной избыточностью (наилучшим дискретным приближением к непрерывному представлению Шеннона).

При этом, длина конкретного целочисленного кода, естественно, может быть как меньше, так и больше парного ему точного значения для непрерывного кода. Это НЕ ошибка формулы Шеннона - это ошибка аппроксимации точных непрерывных объектов кусочно-линейной моделью (a la вписанным / описанным в круг многоугольником).


Q. Что такое эффективное кодирование?

A. Подобно тому, как в математике важную роль играют теоремы существования и единственности, в инженерной практике важны критерии физической реализуемости и эффективности. Технические решения редко бывают единствено возможными, и важно показать, что выбранное решение не хуже любого другого реализуемого при заданных ограничениях, то есть оптимально (с точностью до изоморфизма).

Очень часто, критерием оптимальности служат относительные характеристики (КПД, коэффициент использования материала, соотношение цена/качество итд.). Клод Шеннон, занимаясь вопросами транспорта информации, ввел понятие коэффициента использования тары (информационной энтропии).

Идеальное значение КПД - единица (бит/бит) - разумеется, недостижимо, но с увеличением длины сообщения можно асимптотически у нему приближаться. Эффективное кодирование - это именно способ наилучшего заполнения тары.

Например, если в емкости 0.7 л у вас налито только 0.5 л жидкости (неважно, чего: воды, коньяка, уксуса, крысиного яда), то тара использована неэффективно и то же самое содержимое может быть помещено в упаковку меньшего объема (сжато).



© Gazlan 2009-2014 * gazlan@yandex.ru