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

Ну, это так задача сформулирована. А уточнить условия у него можно? Особенно по этому вопросу:




То есть, на каком-то одном? Тогда можно сделать 2а варианта программы - для английского языка и русского отдельно. Можно попробовать сделать гибрид - если встречаются русские буквы, тогда русский текст, если английские - тогда английский, если и те, и другие - тогда смешанный текст...  

Смешанный текст...... Т.е. возможны русские и английские буквы в тексте.

Как-то в задании говорится о русском или английском, но не о и русском, и английском одновременно. Мне кажется, лучше всего, всё-таки, уточнить условие задачи.

И если речь идёт именно о естественном языке, то, думаю, нужно учитывать все буквы алфавита, даже которые в тексте не встретились (для больших текстов это маловероятно).

Но если хочется смешанный текст, то стОит сделать гибрид:

• отдельно считаются английские буквы
• отдельно считаются русские буквы
• отдельно считаются знаки препинания (точно к ним относятся все остальные символы?)

Для виндовой кодировки:
И в конце уже смотреть, русский, английский или смешанный тип:

Правда, в таком случае придётся немного по-разному считать частоту парных символов...


Более грамотно, конечно, воспользоваться функциями setlocale, isalpha, tolower. В этом случае энтропию для одиночных символов и для парных символов можно считать за один проход файла (за одно чтение):


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


Это сообщение отредактировал(а) feodorv - 2.12.2012, 07:00

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

  Ну так число букв для каждого языка ведь известно? Достаточно сложить:


Тупо по определению:

Я имел в виду в моем коде, он получается кардинально не верен  Последний пример понятен. Это проверка на присутствие в тексте русских или латинских символов (так же их отсутствие или "гибрид"). Просто на вашем примере 
не совсем понятно - расчеты для символа и для пары символов (поясните пожалуйста некоторые строки). И как это будет вписываться в мой код? Это на сколько я понял идет проверка и подсчет символов перед расчетами энтропии.

Какие именно? Просто вместо 

пишется, например, такое:
При этом одновременно считается и code и code_p (за один проход файла). Чтобы isalpha и tolower отрабатывали на русских буквах, нужно установить нужную локаль.

Ну а затем считается энтропия как у Вас в первоначальном коде.

Еще вопрос! А для пары символов энтропия и максимальная энтропия у меня верно определяются? Мне сказали, что я ошибаюсь. Или все верно достаточно подставить подсчитанные значения. И еще верно, что для пары символов нужно использовать log(2.7) вместо log(2)

Правильно сказали)))

Должна быть двойная сумма 
где p(ij) - вероятность появления j-го символа после i-го (то есть пары символов ij).
Условная энтропия

Соответственно, максимальная условная энтропия достигается при равенстве всех вероятностей (то есть при условии независимости следования символов друг за другом и одинаковой частоты появления символов алфавита). Высчитывается аналогично первому случаю, надеюсь, Вы легко её определите 

Добавлено @ 10:28

Если в первом случае используется логарифм по основанию 2, то и во втором тоже должно использоваться это же основание. Не вижу оснований для смены основания)))

В формуле Шенона используется некая константа, которая является, на самом деле, калибровочной константой. Например, можно так откалибровать понятие энтропии, что максимальная энтропия примет значение 1. Смена основания логарифма ведёт просто-напросто к изменению этой константы, поэтому 

Интересно, что при выборе единичного значения для калибровочной константы 

Откуда взялась в Ваших записях константа 2.7, мне сказать трудно, тем более она очень близка к значению числа e. Но единицы измерения энтропии должны быть одинаковы, что в первом случае, что во втором. В битах - значит, в битах)))

Это сообщение отредактировал(а) feodorv - 3.12.2012, 10:30

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

Добавлено через 5 минут и 51 секунду

так что после сжатия оптимальным образом (в два прохода, с построением таблицы частот), энтропия вычисляется просто.

Не совсем понятно как происходит вычисление sum(i:total), sum(j:total) и p(ij). Можете продемонстрировать в коде. 

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

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