2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Дано текстовое сообщение,найти частоту символов,энтропию,...
Сообщение17.10.2017, 11:58 
Добрый день дана следующая задача c которой хочется разобраться
Дано слово "Раскраска". Подсчитать частоты встречаемости символов и найти:
- количество информации в сообщении;
- энтропию с помощью полученных частот;
- абсолютную избыточность кодирования;
- теоретическую максимальную степень сжатия сообщения;

Я нашёл частоту встречаемости символов таким образом. Для начала выписал сколько раз встречается каждый символ и применял следующую формулу

$freq = \frac{n}{kol}  100 \%$ (где n - количество конкретного символа,kol - количество символов в слове)

Р=2 раза $= 22.22 \%$
А=3 раза $= 33.33 \%$
С=2 раза $= 22.22 \%$
К=2 раза $= 22.22 \%$

Формулы нахождения количества информации и энтропии(как и все дальнейшие формулы) были взяты из методички
1)Количество информации $I=\log L$
2)Энтропия $H=\frac{I}{n}=-\sum\limits_{i=1}^{m}p_{i} \log p_{i}$
3)абсолютную избыточность кодирования $D = R - r$
4)теоретическую максимальную степень сжатия сообщения $\frac{D}{R}$

Последующие пункты требуют уточнения
Вопросы.
1)Правильно я понимаю что при нахождении энтропии вместо вероятностей $p_{i}$ я должен использовать свои полученные частоты но в виде $\frac{1}{freq}$

2) Для нахождения $r$ и $R$ используются следующие формулы

$r = EH(M_{t}\mid M_{t-1},M_{t-2},M_{t-3},...)$ - Информационное содержание одного сообщения в потоке

$R = \log(M)$ -$ R$ логарифм числа символов в алфавите сообщений

Опять же как я понял E это энтропия полученная с помощью частот,а вот что означает $H(M_{t}\mid M_{t-1},M_{t-2},M_{t-3},...)$? Это условная энтропия?

И по поводу $R$ здесь получается нахождения логарифма количества символов в строке?

 
 
 
 Re: Дано текстовое сообщение,найти частоту символов,энтропию,...
Сообщение17.10.2017, 17:20 
1. У слова "раскраска" энтропия равна нулю. Неопределенности нет - вот оно слово, всем показано.
2. А вот у загаданного слова ###### (6 символов) энтропия уже не равна нулю. В такой постановке задачи энтропия равна бесконечности, так как неизвестен алфавит. Может надпись китайскими иероглифами загадал или на инопланетном языке?
3. Другое дело, если я буду утверждать, что слово написано кириллическими символами. Энтропия уменьшится.
4. Еще меньше энтропия будет, если я скажу, относятся ли буква "ё", цифры, знаки препинания, пробел к тому самому загадочному кириллическому алфавиту или нет (перечислю все символы алфавита).
5. Энтропия уменьшится еще, если станут известны частоты кириллических символов в текстах, и я подтвержу, что слово осмысленное из словаря русского языка.
6. Я могу назвать часть речи, к которой относится слово. Это уменьшит энтропию.
7. И, наконец, энтропия резко уменьшится, если я открою некоторые буквы.
8. Можно еще уменьшить энтропию, если получить сведения о частотах слогов в русских текстах.
...

Вот такая вот история с энтропией.

seven-red в сообщении #1256307 писал(а):
- теоретическую максимальную степень сжатия сообщения;

Вы удивитесь, но всегда можно предложить архиватор, которое заданное слово сожмёт до 1 бита.

 
 
 
 Re: Дано текстовое сообщение,найти частоту символов,энтропию,...
Сообщение19.11.2017, 14:16 
Mihaylo в сообщении #1256381 писал(а):
Вы удивитесь, но всегда можно предложить архиватор, которое заданное слово сожмёт до 1 бита.
До нуля.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group