Entropia (teoria informacji).html

Ten artykuł dotyczy pojęcia z dziedziny teorii informacji. Zobacz też: inne znaczenia tego terminu.

Niektóre informacje zawarte w artykule wymagają weryfikacji.
Do weryfikacji: patrz dyskusja

Entropia w ramach teorii informacji jest definiowana jako średnia ilość informacji, przypadająca na znak symbolizujący zajście zdarzenia z pewnego zbioru. Zdarzenia w tym zbiorze mają przypisane prawdopodobieństwa wystąpienia.

Wzór na entropię:

$H(x)=\sum_{i=1}^np(i)\log_r \frac{1}{p(i)}= - \sum_{i=1}^np(i)\log_r {p(i)}\,\!$

gdzie p(i) - prawdopodobieństwo zajścia zdarzenia i. W przypadku kodowania ciągu znaków jest to prawdopodobieństwo wystąpienia i-tego znaku. W teorii informacji najczęściej stosuje się logarytm o podstawie r =2, wówczas jednostką entropii jest bit. Dla r= e jednostka ta nazywa się nat(nit), natomiast dla r=10 - dit lub hartley.

Entropię można interpretować jako niepewność wystąpienia danego zdarzenia elementarnego w następnej chwili. Jeżeli następujące zdarzenie występuje z prawdopodobieństwem równym 1, to z prostego podstawienia wynika, że entropia wynosi 0, gdyż z góry wiadomo co się stanie - nie ma niepewności.

Własności entropii:

jest nieujemna
jest maksymalna, gdy prawdopodobieństwa zajść zdarzeń są takie same
jest równa 0, gdy stany systemu przyjmują wartości 0 albo 1
własność superpozycji - gdy dwa systemy są niezależne to entropia sumy systemów równa się sumie entropii.

Definicja informacyjna była pierwotnie próbą ujęcia tradycyjnego pojęcia entropii znanego z termodynamiki w kategoriach teorii informacji. Okazała się jednak, że definicja ta jest przydatna w ramach samej teorii informacji.

Pojęcie entropii jest bardzo przydatne w np: dziedzinie kompresji informacji. Entropię zerowego rzędu można obliczyć znając histogram ciągu symboli. Jest to iloczyn entropii i ilości znaków w ciągu. Osiągi kodowania Huffmana są często zbliżone do tej granicy, ale istnieją lepsze sposoby np. kodowanie arytmetyczne.

Przyjęcie modelu, w którym uwzględnia się kontekst znaku, pozwala zwykle na bardzo duże obniżenie entropii.

edytuj Przykład

Moneta, która wyrzuca z takim samym prawdopodobieństwem orły i reszki, ma 1 bit entropii na rzut:

$- p_{O} \log_2 p_{O} - p_{R} \log_2 p_{R} = - \frac 1 2 \log_2 \frac 1 2 - \frac 1 2 \log_2 \frac 1 2 = \frac 1 2 + \frac 1 2 = 1$

Ogólniej każde źródło dające $N$ równie prawdopodobnych wyników ma $l o g 2 N$ bitów na symbol entropii:

$- \sum_{i=1}^N \frac 1 N \log_2 \frac 1 N = - N \frac 1 N \log_2 \frac 1 N = -\log_2 \frac 1 N = \log_2 N$

edytuj Zobacz też

Typy kompresji:

Wybrane algorytmy bezstratne:

Program do kompresji plików