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

Добавлено @ 18:13
Есть следующая функция, до которой я додумался



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

Это сообщение отредактировал(а) Bugrimov - 26.11.2012, 18:15

А что значит энтропия текста ?

http://ru.wikipedia.org/wiki/%C8%ED%F4%EE%...%F0%EE%EF%E8%FF

Добавлено через 6 минут и 45 секунд
http://www.sernam.ru/book_tec.php?id=53

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

Есть какие-нибудь соображения по поводу кода

На вид, должно быть не log(total), а log(256) (ну, или если Вы все знаки препинания свалили в одну кучу, то логарифм меньшего числа, чем 256).


Судя по учебнику, должно быть 

Но в тексте файла могут не использоваться все символы (256). Максимальная энтропия не рассчитывается от размера алфавита например текст "aaacccbbms" - размер алфавита 5, т.е. 5 символов, поправьте меня если я ошибаюсь. Как тогда должен выглядеть программный код?

Могут, но Вы же их учитываете (посмотрите, как формируется total), учитываете даже пробелы, табуляцию, перенос строк, различаете строчные буквы от прописных. 

Потом, если в тексте не встретилась какая-то буква алфавита, то это не значит, что её существование можно проигнорировать (как раз нет, просто она редко встречается). 



Ограничьте себя английским алфавитом или русским. Не различайте строчные и прописные буквы. Если есть необходимость в учёте знаков препинания - учитывайте. Все остальные символы игнорируйте. Соответственно вместо 256 получится 26/27 или 32/33/34 (если учитывать ё и пунктуацию) символов.

Рекурсия здесь не нужна абсолютна.

По поводу энтропии. вы ее никогда точно не посчитаете.
Приблизительно её можно оценить с помощью архиватора.
Архиваторы, асимтотично стремятся к некому пределу сжатия.
У кого-то лучше получается, у кого-то хуже.
Со временем появляются новые архиваторы, которые сжимают текст еще лучше.
Но ни один архиватор никогда не сможет сжать текст ниже уровня энтропии.
А вот каков он этот предел... кто ответит?   

Я пытался добиться следующего:
Открыть любой текстовый файл. Рассчитать его энтропию (регистр не учитывается - строчные и прописные символы одинаковые, все знаки препинания подсчитать как один символ - любой символ), максимальную энтропию и избыточность текста. В коде рассмотрен еще один вариант - для пар символов. Я полагал, что есть определенная формула по расчету энтропии, максимальной энтропии, избыточности. С энтропией и избыточностью вроде разобрался с макс. энтропией вообще ничего не понятно. Есть у кого-нибудь образец кода.

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


А при чём здесь образец кода, когда максимальная энтропия достигается при равных вероятностях для всех букв алфавита?


где m - число букв алфавита (с учётом пунктуации).

Подскажите пожалуйста как в моем куске кода можно сделать, чтобы регистр не учитывался, знаки препинания (табуляция и пробелы) считались как один символ. 
Число букв алфавита m.
Для большего понимания. Например текст: фффаааяяя qqrrr (6 букв алфавита). Я верно понимаю? Или учитываются все буквы алфавита. Если например текст латинница - все буквы латинского языка, если русский - то русского.

Это сообщение отредактировал(а) Bugrimov - 29.11.2012, 04:46

Честно говоря, для большей ясности лучше спросить у заказчика)))
Лично я бы тупо ограничился английским алфавитом, завёл бы массив из 27 позиций (26 на буквы, 1 на остальные символы) и сделал бы аналогично Вашему коду, только иначе бы вычислял индекс массива: 

Будут открываться текстовые файлы на русском или английском языке, возможно это предусмотреть как-нибудь в коде.
 Этот вопрос так же актуален...  

А что по этому поводу говорит "заказчик"?

Заказчик говорит: "составить программу, определяющую энтропию текстового файла. Энтропию необходимо вычислить 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). Можете продемонстрировать в коде. 

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

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

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


да в том то и дело, что частоты не известны. И получение этих частот выходит далеко за рамки этой темы.

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

Формулу эту я встречал, но практической реализации ее не видел. 


Вот все что есть по этому поводу. Хотя уже понятно, что log(2), вместо log(2.7).
Можете что-нибудь подсказать на уже имеющемся программном коде. 

Ну, просто возникло устойчивое чувство, что я вместо Вас делаю Вашу лабораторную работу   

Давайте подсчитаем вероятность встречи в тексте пары символов AB:

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

Подготовившись таким образом, мы можем вычислить p(A):

как и для первого этапа, но с учётом специфики пар, то есть ранее оговоренной тонкости.

Подсчитаем вероятность буквы B, если перед ней стояла буква A:

Если как следует подумать, то придёт понимание, что {общее число пар, где первой является A} есть просто число букв A в тексте (с учётом ранее оговоренной тонкости) (хотя в коде, если не лень и нет веры, можно подсчитать в цикле))) То есть:

Итого:
А с учётом того, что {число всех букв в тексте, начинающих пару символов} есть просто-напросто {общее число пар символов в тексте}, получаем невероятный, умопомрачительный результат
  

Осталось всё это подставить в 

и получить готовый результат.


Мне безумно хочется получить от Вас значение для максимальной энтропии пар. Оно интересно и весьма поучительно.

Добавлено через 4 минуты и 10 секунд
У Вас в коде файл два раза закрывается:

Чувствую, даже попыток вычислить искомое не будет   
А жаль. Всё вычисляется элементарно...