Entropia (teoria informacji)

Skocz do: nawigacji, szukaj
Ten artykuł dotyczy pojęcia z dziedziny teorii informacji. Zobacz też: inne znaczenia tego terminu.
Grafika:Cmbox content.png
 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.
  • jeśli ze źrodła danych pobierane są k-literowe ciągi, wówczas entropia wynosi H(x(k)) = kH(x)

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 danych. 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, jednak lepszą efektywnością charakteryzuje się 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 log2N 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:
Źródło: „http://pl.wikipedia.org/wiki/Entropia_(teoria_informacji)”