Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 2
Lekce 2: Moderní teorie informaceMatematická teorie komunikace
Claude Shannon ukázal, jak lze generovat "anglicky vypadající" text pomocí Markovovských řetězců. Tvůrce: Brit Cruise.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.
Transkript
Shannon právě skončil vývoj teorií
vztahujících se k šifrování a proto si byl dobře vědom,
že lidská komunikace je směsí náhodnosti a statistických závislostí. Písmena v naších zprávách byla zjevně
do určité míry závislá na předchozích písmenech. V roce 1949 publikoval
přelomový článek "A Mathematical Theory of Communication". Využívá v něm Markovovy modely
jako nástroj k pochopení komunikace. Začíná s ukázkovým příkladem. Představte si, že se setkáte s textem
napsaným v abecedě písmen "A" "B" a "C". O tomto jazyce nic nevíte. Ale všimnete si, že se "áčka" drží spolu
zatímco "béčka" a "céčka" ne. Pak ukázal, že můžete navrhnout stroj
pro generování podobně vypadajícího textu použítím Markovova řetězce. Začal aproximací nultého řádu, kde jsme jen nezávisle vybrali každý symbol (A, B nebo C) náhodně
a vytvořili řetězec. Tento řetězec ale nevypadá
jako ten původní. Shannon ukázal, že lepší je
aproximace 1. řádu, kde jsou písmena vybrána nezávisle, ale podle pravděpodobnosti s jakou se
daná písmena v řetězci objevují. Tohle už je trochu lepší,
protože "áčka" se objevují více, ale stále to nezachycuje strukturu. Další krok je klíčový. Aproximace druhého řádu,
bere v potaz každý pár symbolů. V tomto případě máme 3 stavy. První stav představuje všechny páry
začínající na "A", druhý páry začínající na "B"
a třetí páry začínající na "C". Všimněte si, že kelímek s "A"
má mnoho párů "AA", protože podmíněná pravděpodobnost
"A" po "A" je v naší původní zprávě větší. Teď můžeme vytvářet sekvence
pomocí modelu 2. řádu takto: Začneme kdekoli, vybereme kostičku a napíšeme první písmeno a posuneme se ke kelímku
podle druhého písmena. Pak vybereme novou kostičku
a tento proces opakujeme donekonečna. Tato posloupnost již začíná
vypadat jako naše původní zpráva, protože tento model zahrnuje
podmíněné závislosti mezi písmeny. Dalšího zlepšení dosáhneme
pomocí aproximace 3. řádu, která zahrnuje skupiny 3 písmen -
triagramy. V tomto případě potřebujeme 9 stavů. Shannon poté použil stejný postup
na reálný anglický text a použil statistiku, která byla
známa pro písmena, páry, triagramy atd. Ukázal to samé zlepšení
pro přechody od aproximací 0. řádu, 1. řádu, 2. řádu a 3. řádu. Poté zkusil to samé
pomocí slov místo písmen. Napsal:
"Podobnost s běžným anglickým textem..." ...se velmi zvyšuje s každým řádem." A opravdu, tyto stroje produkovaly
sice bezobsažný text, ale obsahovaly podobnou
statistickou strukturu, kterou je možno vidět v angličtině. Shannon poté definoval
kvantitativní míru informace, když si uvědomil,
že množství informace ve zprávě musí souviset s návrhem stroje, který by mohl být použit
ke generování podobných sekvencí. To nás přivádí ke konceptu entropie.