2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Дано текстовое сообщение,найти частоту символов,энтропию,...
Сообщение17.10.2017, 11:58 


17/10/17
1
Добрый день дана следующая задача 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 


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

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

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

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

 Профиль  
                  
 
 Re: Дано текстовое сообщение,найти частоту символов,энтропию,...
Сообщение19.11.2017, 14:16 


27/08/16
5107
Mihaylo в сообщении #1256381 писал(а):
Вы удивитесь, но всегда можно предложить архиватор, которое заданное слово сожмёт до 1 бита.
До нуля.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group