Властивості ентропії
Ентропія, як кількісна міра інформативності джерела, має наступні властивості:
1. Ентропія є величина дійсна, обмежена і невід’ємна. Ці її властивості випливають з вигляду виразу для Н(x), а також з врахуванням того, що 0 < P(xi) < 1.
2. Ентропія детермінованних повідомлень дорівнює нулеві, тобто Н(x) = 0, якщо хоча б одне з повідомлень має імовірність, рівну одиниці.
3. Ентропія максимальна, якщо повідомлення xi рівноймовірні, тобто
P(x1) = P(x2) = ....... P(xk) = 1/K , і тоді:
(1.7)
Як видно з останнього виразу, у випадку рівноймовірних повідомлень ентропія росте зі збільшенням обсягу алфавіту джерела (ростом числа повідомлень). При нерівноймовірних елементарних повідомленнях xi ентропія, відповідно, зменшується.
4. Ентропія двійкового джерела (K = 2) може змінюватися від нуля до одиниці. Дійсно, ентропія системи з двох повідомлень x1 і x2
(1.8)
З останнього вираpe видно, що ентропія дорівнює нулеві при P(x1)= 0; P(х2)=1, або P(х1) = 1; P(х2) = 0; при цьому максимум ентропії буде мати місце, коли P(х1)=P(х2)=1/2 і її максимальне значення буде дорівнює 1 біт.
Завдання
Знайти ентропію дискретної випадкової величини Х, заданої розподілом P(xi) (значення P(xi) взяти з табл. 1.1 згідно варіанту). Де М – кількість повідомлень.
За допомогою сучасних середовищ програмування (Pascal, Delfi, C++, Visual C, Bilder) розробити програму для визначення ентропії довільного текстового блоку сформованого з символів українського алфавіту. В програмі передбачити наступні функції:
можливість роботи з символами однієї з кириличних кодових таблиць (cyrilic windows, koi8ru, або ін..);
можливість вводу та копіювання текстового блоку;
відображення загальної кількості символів у текстовому блоці;
розмір текстового блоку повинен бути не менше 2000 символів;
при обчисленні ентропії враховувати символи знаків пунктуації (коми, крапки, тире та ін..);
відображення імовірностей появи символів у текстовому блоці;
відображення обчисленого значення ентропії;
відображення інформації про розробника (курс, група, прізвище та ініціали);
виконання без застосування середовища програмування використаного для створення програми.
За допомогою розробленої програми визначити ентропію для десяти блоків україномовного тексту різної тематики (художня література, вірші, технічні тексти, медичні тексти).
Провести порівняльну оцінку одержаних результатів.
Оформити звіт.
Примітка: Збережіть отримані в результаті виконання лабораторної роботи програмні коди. Вони використовуватимуться в наступних лабораторних роботах.
Таблиця 1.1 – Розподіл дискретної випадкової величини
|
Вар. |
M |
q |
P(x1) |
P(x2) |
P(x3) |
P(x4) |
P(x5) |
P(x6) |
P(x7) |
P(x8) |
P(x9) |
P(x10) |
|
1 |
10 |
4 |
0,22 |
0,1 |
0,11 |
0,05 |
0,08 |
0,32 |
0,06 |
0,03 |
0,01 |
0,02 |
|
2 |
9 |
4 |
0,21 |
0,11 |
0,13 |
0,1 |
0,2 |
0,11 |
0,04 |
0,06 |
0,04 |
– |
|
3 |
8 |
4 |
0,2 |
0,12 |
0,05 |
0,13 |
0,14 |
0,15 |
0,1 |
0,11 |
– |
– |
|
4 |
10 |
3 |
0,19 |
0,13 |
0,09 |
0,1 |
0,11 |
0,14 |
0,03 |
0,1 |
0,04 |
0,07 |
|
5 |
9 |
3 |
0,18 |
0,14 |
0,4 |
0,11 |
0,01 |
0,03 |
0,04 |
0,04 |
0,05 |
– |
|
6 |
8 |
3 |
0,17 |
0,15 |
0,1 |
0,03 |
0,15 |
0,3 |
0,02 |
0,08 |
– |
– |
|
7 |
10 |
5 |
0,36 |
0,18 |
0,19 |
0,04 |
0,05 |
0,05 |
0,012 |
0,05 |
0,05 |
0,018 |
|
8 |
9 |
5 |
0,3 |
0,15 |
0,16 |
0,06 |
0,16 |
0,1 |
0,05 |
0,01 |
0,01 |
– |
|
9 |
8 |
5 |
0,11 |
0,09 |
0,08 |
0,15 |
0,06 |
0,16 |
0,13 |
0,22 |
– |
– |
|
10 |
10 |
4 |
0,06 |
0,08 |
0,3 |
0,12 |
0,14 |
0,09 |
0,03 |
0,06 |
0,08 |
0,04 |
|
11 |
9 |
4 |
0,15 |
0,35 |
0,01 |
0,06 |
0,11 |
0,15 |
0,07 |
0,02 |
0,08 |
– |
|
12 |
8 |
4 |
0,08 |
0,076 |
0,4 |
0,032 |
0,25 |
0,06 |
0,05 |
0,052 |
– |
– |
|
13 |
10 |
3 |
0,22 |
0,1 |
0,05 |
0,015 |
0,008 |
0,25 |
0,15 |
0,1 |
0,05 |
0,057 |
|
14 |
9 |
3 |
0,05 |
0,09 |
0,04 |
0,08 |
0,07 |
0,15 |
0,36 |
0,15 |
0,01 |
– |
|
15 |
8 |
3 |
0,05 |
0,2 |
0,1 |
0,3 |
0,15 |
0,13 |
0,025 |
0,045 |
– |
– |
|
16 |
10 |
4 |
0,2 |
0,11 |
0,3 |
0,2 |
0,02 |
0,03 |
0,05 |
0,01 |
0,06 |
0,02 |
|
17 |
9 |
4 |
0,31 |
0,106 |
0,2 |
0,14 |
0,03 |
0,12 |
0,06 |
0,02 |
0,014 |
– |
|
18 |
8 |
4 |
0,39 |
0,1 |
0,04 |
0,16 |
0,09 |
0,08 |
0,13 |
0,01 |
– |
– |
|
19 |
10 |
3 |
0,2 |
0,01 |
0,16 |
0,4 |
0,02 |
0,03 |
0,08 |
0,01 |
0,07 |
0,02 |
Таблиця 1.1 – Продовження
|
Вар. |
M |
q |
P(x1) |
P(x2) |
P(x3) |
P(x4) |
P(x5) |
P(x6) |
P(x7) |
P(x8) |
P(x9) |
P(x10) |
|
20 |
9 |
3 |
0,31 |
0,2 |
0,1 |
0,05 |
0,04 |
0,08 |
0,03 |
0,01 |
0,18 |
– |
|
21 |
8 |
3 |
0,39 |
0,2 |
0,1 |
0,05 |
0,09 |
0,08 |
0,08 |
0,01 |
– |
– |
|
22 |
10 |
5 |
0,25 |
0,11 |
0,15 |
0,15 |
0,02 |
0,02 |
0,06 |
0,03 |
0,18 |
0,03 |
|
23 |
9 |
5 |
0,29 |
0,2 |
0,04 |
0,05 |
0,11 |
0,08 |
0,13 |
0,01 |
0,09 |
– |
|
24 |
8 |
5 |
0,27 |
0,2 |
0,2 |
0,15 |
0,03 |
0,08 |
0,06 |
0,01 |
– |
– |
|
25 |
10 |
4 |
0,31 |
0,006 |
0,15 |
0,1 |
0,12 |
0,02 |
0,03 |
0,03 |
0,104 |
0,13 |
|
26 |
9 |
4 |
0,29 |
0,2 |
0,04 |
0,06 |
0,09 |
0,08 |
0,149 |
0,01 |
0,081 |
– |
|
27 |
8 |
4 |
0,26 |
0,19 |
0,1 |
0,15 |
0,15 |
0,08 |
0,058 |
0,012 |
– |
– |
|
28 |
10 |
3 |
0,35 |
0,15 |
0,15 |
0,08 |
0,07 |
0,07 |
0,05 |
0,03 |
0,03 |
0,02 |
|
29 |
9 |
3 |
0,37 |
0,16 |
0,14 |
0,11 |
0,09 |
0,06 |
0,03 |
0,02 |
0,02 |
– |
|
30 |
9 |
3 |
0,31 |
0,2 |
0,1 |
0,05 |
0,04 |
0,08 |
0,03 |
0,01 |
0,18 |
– |