Теория информации и теория шифрования: формулы Хартли и Шеннона

[Mihaylo]

druggist в сообщении #1429146 писал(а):

Можно ли в эту стройную систему включить еще и шифрование - защиту информации, не технологии, а смысл?

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

А с синтаксисом хорошо работает формула Хартли. Вообще эта формула более универсальна.

Формула Шеннона работает только в случае известного ансамбля вероятностей, но забавно, что при добавлении допущения из нее можно получить формулу Хартли и считается, что формула Шеннона универсальнее. Однако никто не обращает на природу того самого допущения, которое звучит примерно так: "а давайте рассмотрим более общий случай, когда вероятности неизвестны...". И самое интересное, что из формулы Хартли можно вывести формулу Шеннона. Да на самом деле на практике без разницы, какая из этих формул универсальнее. Но строго математически...

[angor6]

Mihaylo в сообщении #1430843 писал(а):

И самое интересное, что из формулы Хартли можно вывести формулу Шеннона.

(Оффтоп)

Хотелось бы узнать, как это сделать.

[arseniiv]

Да, мне тоже интересно, зачем так цепляться за исторические понятия, которые замечательно уже покрыты более универсальными и имеющими ясные причины существовать (представьте, что на этом месте была бы «релятивистская масса»). Когда мы не знаем распределение символов, мы можем явным образом применить принцип максимальной энтропии и получить своё вожделенное равномерное распределение, и это по-моему более сознательно.

Ну или если формула Хартли выводится так же аккуратно как формула Шеннона, и при этом без даже неявного упоминания вероятностей, я вчитаюсь и наверняка скажу «ладно, защищайте её сколько угодно». Достаточно ссылки.

Mihaylo в сообщении #1430843 писал(а):

Однако никто не обращает на природу того самого допущения, которое звучит примерно так: "а давайте рассмотрим более общий случай, когда вероятности неизвестны...".

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

[Mihaylo]

arseniiv в сообщении #1430990 писал(а):

Когда мы не знаем распределение символов, мы можем явным образом применить принцип максимальной энтропии и получить своё вожделенное равномерное распределение, и это по-моему более сознательно.

Можем. А можем придумать еще тысячу способов вычисления числа степеней свободы $N$. Не надо накладывать ограничение на формулу Хартли.

arseniiv в сообщении #1430990 писал(а):

Ну или если формула Хартли выводится так же аккуратно как формула Шеннона, и при этом без даже неявного упоминания вероятностей, я вчитаюсь и наверняка скажу «ладно, защищайте её сколько угодно». Достаточно ссылки.

https://de.ifmo.ru/bk_netra/page.php?in ... utindex=13
Комментарий в двух словах: применяется формула Стирлинга-Муавра. Вместо вероятности можете говорить о частоте символов в тексте.

arseniiv в сообщении #1430990 писал(а):

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

С формулой Шеннона все сложнее. Популярны попытки вычислять энтропию (плотность энтропии) непрерывных величин с помощью формулы Шеннона. Так вот там получается почти красивый результат, но с корявой дельтой, которая далеко не стремится к нулю. Эту дельту отбрасывают и называют это дифференциальной энтропией, типа мы сравниваем информационные меры двух непрерывных величин, корявая дельта сокращается, нас интересует относительная информация, а не абсолютная. Пруф здесь, формулы 6.22 и 6.23: https://studref.com/475212/tehnika/info ... oobscheniy
При применении формулы Хартли эта дельта не образуется. Так это еще одно свидетельство того, что формула Шеннона является приблизительной.

[arseniiv]

Mihaylo в сообщении #1431060 писал(а):

Популярны попытки вычислять энтропию (плотность энтропии) непрерывных величин с помощью формулы Шеннона.

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

Mihaylo в сообщении #1431060 писал(а):

https://de.ifmo.ru/bk_netra/page.php?index=25&layer=3&tutindex=13
Комментарий в двух словах: применяется формула Стирлинга-Муавра. Вместо вероятности можете говорить о частоте символов в тексте.

Так это ж не про формулу Хартли.

Mihaylo в сообщении #1431060 писал(а):

При применении формулы Хартли эта дельта не образуется.

Это очень интересно было бы увидеть в деталях.

Кстати если кому интересно, вот одна из уже корректно определённых в непрерывном случае величин:
(en.wikipedia) Kullback—Leibler divergence (что упоминается в разделе Properties).

[Mihaylo]

arseniiv в сообщении #1431326 писал(а):

Так это ж не про формулу Хартли.

Ну вот же она, явно применена в формуле (3) по ссылке:
$I = H_0 - H_1 = \ln(\frac{N!}{N_1!N_2!...N_M!}) - \ln(2) = \frac{1}{\ln(2)}\cdot \ln(\frac{N!}{N_1!N_2!...N_M!})$

[arseniiv]

Mihaylo
А, это вы отвечали на вопрос angor6 больше тогда. Но кроме того вы сейчас написали что-то не то: в тексте $H_0, H_1$ не упоминаются, и правый знак равенства вообще в общем случае неверен, в смысле что $\ln a - \ln b\not\equiv \frac1{\ln b} \ln a$, откуда вы вообще так решили, и не издеваетесь ли вы часом.

-- Вс дек 22, 2019 20:38:29 --

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

[Mihaylo]

Точно ведь.
Там была идея такая:
$\log_2\frac{N!}{N_1!N_2!...N_M!} = \frac{1}{\ln(2)}\cdot \ln \frac{N!}{N_1!N_2!...N_M!}$

[angor6]

Mihaylo
В учебниках формула Хартли рассматривается как частный случай формулы Шеннона. Поскольку я изучаю теоретические основы информатики по учебникам, постольку мне было интересно узнать про обратный вывод. Но исходя из результатов обсуждения, я понял, что формула Шеннона не выводится из формулы Хартли. К чему тогда Вы сообщаете недостоверные сведения?

[Mihaylo]

На экзамене, конечно, следует говорить, что формула Хартли - частный случай, иначе схлопочете неуд.

А вообще, самым загадочным является число $N$, а не вероятность $p_i$. Вероятность $p_i$ - это вполне конкретная вероятность. Если Вы под $N$ понимаете нечто в узком смысле - число букв в алфавите, например, то да, формула Хартли становится настолько частным случаем, что ужасно подумать.

Фактически же $N$ - это число комбинаций, а комбинаций чего - это специально не оговаривается, и это правильный подход. Смотря какую информацию хотите измерить, то число и подставляется. Не надо ограничиваться размером алфавита! И в этом случае формула Хартли становится более универсальной, чем формула Шеннона. Вот такие вот делишки творятся.

Рассмотрите частный случай
$N = \frac{M!}{N_1!N_2!...N_M!}$ - это число перестановок букв алфавита размером $M$ с повторениями.

Для перехода к формуле Шеннона нужно применить формулу Стирлинга-Муавра и определение частоты символа
$p_i \approx f_i = \frac{N_i}{M}$

Данный факт широко известен. Можете подсмотреть в классической книге Л. Бриллюэна "Наука и теория информации", перевод А.А. Харкевича 1960, страница 24.

Этот факт редко попадает в современные перепечатки классических трудов, и он до сих пор не понят.

[novichok2018]

Mihaylo - спасибо за Стирлинга-Муавра, исторически правильно.

[arseniiv]

Mihaylo в сообщении #1431562 писал(а):

Там была идея такая:
$\log_2\frac{N!}{N_1!N_2!...N_M!} = \frac{1}{\ln(2)}\cdot \ln \frac{N!}{N_1!N_2!...N_M!}$

Ну это даже не идея, это банальное школьное выражение логарифма по одному основанию через логарифм по другому.

Mihaylo в сообщении #1431704 писал(а):

Фактически же $N$ - это число комбинаций, а комбинаций чего - это специально не оговаривается, и это правильный подход. Смотря какую информацию хотите измерить, то число и подставляется. Не надо ограничиваться размером алфавита! И в этом случае формула Хартли становится более универсальной, чем формула Шеннона. Вот такие вот делишки творятся.

Вы про то, что мы можем считать некоторые буквы алфавита тождественными, а так же считать за буквы нового алфавита последовательности букв старых? Так это никто не запрещает делать, тут нет никаких волшебных не учитываемых кем-то там вещей, всё банально.

[Mihaylo]

arseniiv в сообщении #1431717 писал(а):

Вы про то, что мы можем считать некоторые буквы алфавита тождественными, а так же считать за буквы нового алфавита последовательности букв старых? Так это никто не запрещает делать, тут нет никаких волшебных не учитываемых кем-то там вещей, всё банально.

Именно. Но из этого следуют важные вещи.

[druggist]

Mihaylo в сообщении #1431704 писал(а):

А вообще, самым загадочным является число $N$,

А что тут такого сильно загадочного? Возьмите, например, в качестве $N$ кусок текста длины $N$ на языке с алфавитом длины $M$ (включая пробел), если текст достаточно длинный, применяйте на здоровье формулу Стирлинга. Другой пример - термодинамика, Больцман(Хартли) и Гиббс(Шеннон), там "текст" длинный по определению

[arseniiv]

Mihaylo в сообщении #1431758 писал(а):

Но из этого следуют важные вещи.

Ну из многого следуют важные вещи; какие именно в этом случае?