3. Gegeben sei eine Quelle Q mit p sowie ein Parameter b jQj.
Wir konstruieren iterativ einen Teilbaum des Baumes aller W¨orter ¨ uber
Q mit h¨ochstens b Bl¨attern und Beschriftungen an den Ecken. Eingangs
besteht der Baum nur aus der Ecke ", die mit 1 beschriftet wird (diese ist
ein Blatt in dem von ihr induzierten Baum). Solange der Baum h¨ochstens
b (jQj 1) Bl¨atter hat, w¨ahlen wir unter den Bl¨attern eines aus, dessen
Beschriftung maximal ist. F¨ ur jedes Zeichen q des Quellalphabets f ¨ugen
wir dasWort wq hinzu und beschriften es mit x p(q).
Sei C die Menge aller Bl¨atter des so konstruierten Baumes.
(i) Man f ¨ uhre die Konstruktion exemplarisch f ¨ ur die Quelle Q =
fA; D; E; P; R; S; T; g mit der empirischen Verteilung p der Buchstaben
im Wort w := PER ASPERA AD ASTRA jeweils f ¨ ur b = 8, b = 16
und b = 32 durch. L¨aßt sich w jeweils in Codew¨orter zerlegen, und
wenn ja, in wieviele?