Энтропия файла

[Bugrimov]

Доброе время суток!
Столкнулся с проблемой. Необходимо вычислить энтропию файла для символа и пары символов. Подскажите пожалуйста алгоритм решения задачи. Информации нашел массу, но ничего из прочитанного не могу понять, какие-то общие фразы, может позднее время суток сказывается. Может кто-нибудь сталкивался с подобным решением и более доходчиво объяснит..... Направьте так сказать. Заранее спасибо.

[Abstraction]

1) Задача в такой формулировке, вообще говоря, бессмысленна. Это достаточно важно осознать, и я постараюсь показать это ниже, а уже потом предположить, каким образом можно интерпретировать условие.

2) Энтропия информации (называемая также энтропией Шеннона) - это, по своей идее, аддитивная мера неожиданности информации (иначе, информационной насыщенности сигнала). Сам Шеннон формулировал понятие для следующего случая: пусть у нас есть источник, который порождает сигналы. При этом источник недетерминированный, так что каждый раз мы не знаем в точности, какой именно сигнал мы от него получим. Рассмотрим пока простой пример: пусть сигналы идут равномерно (т.е. в задаче нет времени, есть только последовательность значений) и сигнал может быть либо 0, либо 1.
Далее - и это важно, - у нас должно быть априорное предположение о том, какой сигнал с какой вероятностью мы ожидаем получить. Пусть мы ожидаем получить сигнал 1 с вероятностью p и сигнал 0 с вероятностью q=1-p. Тогда для одиночного сигнала x энтропия сигнала H(x)=-p*log2(p)-q*log2(q). Эта функция обладает аддитивностью: если мы получаем сигнал x и y и эти сигналы независимы, то для пары xy у нас есть уже четыре варианта, и формально надо было бы расписать вероятности всех четырёх и сложить четыре слагаемых, но так получается, что H(xy)=H(x)+H(y). Таким образом, если вероятности 1 и 0 не меняются от сигнала к сигналу и сигналы независимы, энтропия кортежа из n сигналов - это n*(энтропию одного сигнала).
Теперь внимание, вопрос: какова энтропия сигнала, если p=1, q=0? Ответ: ноль. Это предопределённый сигнал, и потому он не несёт никакой энтропии, он уже известен, он не может нас "удивить" и потому не может передать никакой информации. Какова энтропия сигнала, если p=q=1? Ответ: 1. Энтропия одного сигнала, который с равной вероятностью может быть 0 или 1 - это "единичная" энтропия, один бит информации.
Поскольку энтропия аддитивна, то энтропия одной восьмёрки таких сигналов, одного совершенно случайного байта, равна 8 бит.

3) Теперь пусть у нас есть записанный сигнал из многих-многих единичек и ноликов, файл. Какова его энтропия? Да какая угодно: если источник был таким, что он всегда выдаёт именно такую последовательность, то энтропия... правильно, ноль. Если источник выдавал последовательность совершенно случайных, независимых символов, энтропия файла - (количество единичек и ноликов) бит. Все прочие предположения об источнике дадут результат между этими крайностями.
То есть, ещё раз: понятие энтропии данных возникает тогда, когда у нас есть какие-то предположения о том, какими эти данные могли бы быть. Нет предположений - нет понятия энтропии. Если предположение таково, что данные не могли быть иными - энтропия всегда ноль.

4) Теперь предположим, что у нас есть полученный из источника файл, и ровно одно предположение об источнике: что каждый кортеж из восьми единичек/ноликов, байт, он генерирует независимо от прочих и по одним и тем же правилам. Тогда нижняя граница возможной энтропии файла поднимается от нуля до какой-то ненулевой величины (если, конечно, файл не заполнен одним-единственным байтом, повторенным сколько-то раз). Верхняя граница - заметьте! - остаётся неизменной: всегда можно сказать, что источник генерировал все байты с равными вероятностями, просто нам так повезло, что одних много, а других мало. Но среди всех возможных предположений есть одно выделенное, предположение максимального правдоподобия: источник порождал каждый символ с ровно такой вероятностью, какова частота этого символа в получившемся тексте. Энтропия одиночного байта в рамках этой гипотезы может быть посчитана, и именно она иногда, допуская некоторую вольность речи, называется "энтропией текста". Как её найти? Посчитать частоты всех байт в файле, по формуле найти энтропию одиночного байта (сумма произведений частоты на минус двоичный логарифм от этой частоты), домножить на число байт.

5) Считая, что файл имеет однобайтовую кодировку, т.е. "один байт"="один символ", на первый вопрос мы уже ответили. Со вторым всё немножко запутаннее, общепризнанного варианта здесь нет. Можно предположить, что источник порождает независимые пары символов (только тогда надо решить, что делать, если всего в файле символов нечётное число - ведь подобный файл из такого источника не получишь) - и тогда задача принимает прежний вид, но считать надо частоты уже пар символов.

[Bugrimov]

Буду перечитывать.... Спасибо. Хотя эта информация мало чем отличается от прочитанного мной.

[Bugrimov]

Есть конкретные примеры решения задачи???

[Abstraction]

Втупую:

std::ifstream file;
file.open("myfile", ifstream::in);
int statistics[256]={0};

int ch = file.get();
while(file.good()) {
  statistics[ch]++;
  ch = file.get();
}

int total=0;
for(int i=0; i<256; ++i) total+=statistics[i];

float enthropy=0;
for(int i=0; i<256; ++i) enthropy-=statistics[i]*log(((float)statistics[i])/total);
enthropy /= log(2);

[Bugrimov]

Поясни пожалуйста последние 3-и строки кода

[Bugrimov]

И как это можно применить для пары символов, это я так понимаю посимвольная энтропия....

[Abstraction]

Поясни пожалуйста последние 3-и строки кода

H(x) = Sum(-p*log2(p)). Формула в действии, в сочетании с домножением на количество символов total и формулой перехода между основаниями логарифмов.

Для пар символов - см. пункт 5) поста выше. Общепринятого понятия нет, а додумывать его можно разными способами.

[Bugrimov]

А что за понятие избыточность текста в контексте темы.....

[Bugrimov]

int ch = file.get();
while(file.good()) {
  statistics[ch]++;
  ch = file.get();
}

Я пишу программу на Си, по этому с С++ у меня неразбериха.
Это посимвольное чтение файла и подсчет количество символов в файле?