Teoria informacji/TI Ćwiczenia 1

Ćwiczenia dotyczące kodów.

Ćwiczenie

Mamy dane zbiory:

{0,01,11}

{0,11,10}

{00,01,10}

{00,001,100}

{1,010,110,001,000,101}

Określ:

Które z nich są kodami?

Które są bezprefiskowe?

Które są maksymalne bezprefiksowe?

Rozwiązanie

{0,01,11} - Jest kodem, nie jest bezprefiksowy (0 jest prefiksem 01).

{0,11,10} - Jest kodem bezprefiksowym maksymalnym (łatwo rozrysować drzewo).

{00,01,10} - Jest kodem bezprefiksowym, ale nie maksymalnym (można dodać 11).

{00,001,100} - Nie jest kodem (ciąg 00100 można zapisać na dwa sposoby).

{1,010,110,001,000,101} - Nie jest kodem (nie spełnia nawet nierówności Krafta).

Ćwiczenie

Czy istnieje algorytm, który dla dowolnego skończonego zbioru X nad alfabetem $\mathrm{\Sigma }$ stwierdza czy X jest kodem?

Wskazowka

Należy sprawdzić czy jakiś ciąg znaków można uzyskać na więcej niż jeden sposób. Czy można jakoś ograniczyć z góry długość ciągów jakie wystarczy sprawdzić?

Rozwiązanie

Algorytm taki istnieje. Przyda się do niego operacja odwrotna do konkatenacji słów. Jeśli x i y są słowami takimi że x jest prefiksem y, to niech $z=x^{-1}y⟺xz=y$.

function Code(X:set of words):boolean;
//Dla danego zbioru X określamy czy jest on kodem
var x,y : word;
    U1,U2: set of words;
begin
  U1:=$\mathrm{\varnothing }$;
  forall x in X do
    forall y in X do
      if x < y then U1:=$U1\cup \{x^{-1}y\}$;
  U2:=U1;
  while U2=U1 do begin
    U1=U2;
    forall x in U1 do
      forall y in X do
        if x $\le$ y then U2:=$U2\cup \{x^{-1}y\}$;
  end;
  if $\epsilon \in U2$ then Code:=0; 
  else Code:=1;
end;

Powyższy algorytm generuje wszystkie krótkie sufiksy ciągów możliwych do uzyskania przy pomocy słów ze zbioru X. Jeśli w którymś momencie trafi na słowo puste, oznacza to że zbiór X nie jest ciągiem.

Ćwiczenie

Załóżmy że X jest maksymalnym zbiorem bezprefiksowym nad alfabetem $\mathrm{\Sigma }$ (żaden jego nadzbiór nie jest bezprefiskowy). Czy w takim przypadku nierówność Krafta zamienia się w równość (tzn. $\sum _{s\in X}\frac{1}{r^{\ell (s)}}=1$)?

Wskazowka

Czy odpowiedź zależy od tego czy X jest skończony?

Rozwiązanie

{{{3}}}

W przypadku skończonego X rzeczywiście tak jest. Niech $\ell$ będzie maksymalną długością słowa w X. Wtedy jeśli nierówność Krafta jest ścisła, to któreś słowo długości $\ell$ nie posiada żadnego prefiksu w X - czyli można X rozszerzyć o to słowo.

Inna sytuacja ma miejsce gdy X jest nieskończony. Wtedy nawet dla niewielkiej sumy Krafta możemy zapewnić żeby każde słowo było prefiksem jakiegoś słowa w X. Przykładowo dla alfabetu binarnego weźmy zbiór słów $W3=\{www:w\in {\mathrm{\Sigma }}^{*}\}$, i usuńmy z niego wszystkie słowa które są prefiksami innych (zauważmy że ta operacja nie usunie wszystkich słów). Tak uzyskany zbiór jest maksymalny bezprefiksowy, a suma Krafta dla niego jest nie większa niż suma Krafta dla W3, wynosząca $\sum _{s\in W3}\frac{1}{2^{\ell (s)}}=\sum _{i=1}^{\mathrm{\infty }}\frac{2^i}{2^{3i}}=\sum _{i=1}^{\mathrm{\infty }}{4}^{-i}=\frac{1}{3}$.