2. LZW kódolás

SzóFa

$|\Sigma |=d,S\subseteq {\Sigma }^{\ast }$

minden csucsnak van legfeljebb $d$ ele amik egyesevel az ABC betuit jelolik
a szófa minden csucsahoz hozzatartozik egy szo, csak elkezdjuk olvasni az elek menten a betuket a gyokertol kezdve
minden csucshoz tartozik egy kulonleges spec pointer ami jeloli hogy a csucshoz tartozo szo benne van-e a szotartban vagy sem (ha nincs benne akkor nil pointert olvasunk)

Lempel-Ziv-Welch (LZW)

fix $\Sigma$ ABC, szo-kod fix hosszal (pl 12 bit)
tehat mindegyik szonak lesz egy kodja ami 12 bites lesz

wikipedia cikk LZW

Eros komponensek

Elvegzunk egy melysegi keresest egy iranyitatlan grafon, ebbol kapunk egy iranyitott erdot
milyen elek lehetnek az eredeti grafban?

• elore el: az iranyitott erdoben egy csucsbol az egyik leszarmazottjaba mutato el
• vissza el: az iranyitott erdoben egy csucsbol az egyik osebe mutato el
• kereszt el: az iranyitott erdoben jobbrol balra mutato el (komponenseken keresztul, kesobbi komponensbol korabbiba)

Tetel: $xy\in E$ akkor

• vissza el, ha $MSZ(y)<MSZ(x)$ es $BSZ(y)>BSZ(x)$

• fa vagy elore el, ha $MSZ(y)>MSZ(x)$ es $BSZ(y)<BSZ(x)$
  ezen ket tipus kozul a fa el, ha $p(y)=x$ azaz $y$ szuloje az $x$

• kereszt el, ha $MSZ(y)<MSZ(x)$ es $BSZ(y)<BSZ(x)$

All.: Egy $G$ graf aciklikus $⟺$ nem letezik benne visszael
Biz.: $⟹$ trivi.
$⟸$ a melysegi kereses utan a befejezesi szam (BSZ) egy forditott topologikus sorrendet ad

Reszfa-lemma:
$x\in V$
$S_x=\{y\in V:\exists x\to y\text{ ut, melnyek }\forall v\text{ csucsara }MSZ(v)\ge MSZ(x)\}$
$T_x=\{y\in V:y\text{ leszarmazottja az }x\text{-nek a melysegi erdoben}\}$

A lemma azt mondja ki, hogy $S_x=T_x$

Biz.:
$T_x\subseteq S_x$ trivialis, mert a faelek menten csak nohet a melysegi szam
$S_x\subseteq T_x$ inderekten feltesszuk, hogy $\exists y\in S_x\setminus T_x$
Ez azt jelenti, hogy letezik olyan $P$ ut mely $x$-bol $y$-ba vezet es $\forall w\in P:MSZ(w)\ge MSZ(x)$
legyen $v^{\prime }$ az elso olyan csucs az uton amelyik nem eleme a $T_x$-nek, ilyen van mert $y\notin T_x$
legyen $v$ a $v^{\prime }$ szuloje a $P$ uton

$T_x$ beli csucsoknak a melysegi szama egy osszefuggo sorozatot alkot pl $\{k,k+1,\dots ,k+m\}$
$v^{\prime }$ nincs benne ebben az osszefuggo sorozatban, es csak nagyobb lehet mert a szuloje $v$ benne van
ebbol kovetkezik, hogy $MSZ(v^{\prime })>MSZ(v)$ amibol kovetzkezik, hogy $v{v}^{\prime }$ fa, vagy elore el tehat $v^{\prime }\in T_x$ ELLENTMONDAS

Def.: $G$ iranyitott graf $x\sim y$, ha $\exists x\to y$ es $y\to x$ ut

All.: A(z) ($\sim$) infix operator egy ekvivalencia relacio.

Def.: Ennek az ekvivalencia relacionak az osztalyait hivjuk eros komponenseknek.

All.: Legyen $K\subseteq V$ egy eros komponens es vegyuk ennek ket csucsat $x,y\in K$. Ekkor:

1. $\exists x\to y$ ut melynek minden csucsa $K$-beli.
2. $\forall x\to y$ utnak minden cucsa $K$-beli.

Legyen $P$ az $x\to y$ ut es $v\in P$
indirekt tegyuk fel, hogy $v\notin K$
Ekkor letezik $v$-bol $y$-ba ut es $y$-bol $x$-be ut ezert letezik $x$-bol $v$-be ut tehat $x\sim v$ $⟹v\in K$

Def.: Redukalt graf (jel.: $red(G)$) ugy kapjuk, hogy minden eros komponenst osszehuzunk egy csucsba. Tehat minden eros komponensnek lesz egy reprezentativ csucsa melynek azok a masik reprezentativ csucsok a szomszedai amelyik komponensbe megy el a jelen komponensbol.

All.: Tetszoleges $G$ iranyitott grafnak a redukaltja aciklikus.
Biz.: Ha van komponenseknek egy sorozata mely kort alkot akkor ezen kor menten minden komponens egy nagy komponenst alkot.

Algoritmus:

1. Csinalunk egy DFS-t a $G$ grafon, $B(i)=\{v:BSZ(v)=i\}$
2. Eloallitjuk a $G^{\prime }$ forditott grafot
3. Csinalunk egy DFS-t a $G^{\prime }$ forditott grafon
   FOR $i=n\dots 1$ ($-1$)
   IF $p(i)=0$ THEN $M{B}_{G^{\prime }}(i)$

source: Kosaraju’s algorithm

Tetel: A 3. pont fenyoi az eros komponensek, tovabba a sorrendjuk megadja a $red(G)$-nek a topologikus sorrendjet
Biz.:
I.) Ha $K$ egy eros komponens, akkor a csucsai a 2. melysegi keresesnel egy fenyobe kerulnek
altalban igaz, hogy ha $K$ eros komponens, akkor minden melysegi kereses utan 1 fenyobe lesznek a csucsai

$v:=K$-nak a legkisebb melysegi szamu csucsa
Azt allitom, hogy $K\subseteq S_v$ hiszen $v$-bol mindenkibe vezet egy ut a $K$-n belul, de ha $v$ a legkisebb melysegi szamu akkor ennek az utnak minden myelsegi szama nagyobb
Reszfa lemme miatt $S_v=T_v$ tehat $K\subseteq T_v$

II.) Legyen $v$ a 3.) pontu melysegi keresesben egy gyoker.
Ekkor a $G^{\prime }$ forditott grafban $T_v^{\prime }\subseteq T_v$
Tehat aki az elso keresesben a $v$ leszarmazottja az a masodik keresesben is a $v$ leszarmazottja.

Ebbol az kovetkezik, hogy $\forall y\in T_v^{\prime }:v\sim y$

Valasszunk ki egy tetszoleges $x\in T_v^{\prime }$ csucsot, ekkor $\exists P\subseteq T_v^{\prime }$ ut $G$-ben mely $x$-bol $v$-be megy az eredeti grafban
a) $\forall w\in P:BSZ(w)\le BSZ(v)$ (az eredeti grafban az elso keresesnel)

Legyen $x^{\prime }$ az a csucs a $P$ ut menten melynek a melysegi szama minimalis
Mivel $x^{\prime }$ a legkisebb a melysegi szama a $P$-ben ezert $P$ menten az $x^{\prime }\to x$ uton mindegyik csucs eleme $S_{x^{\prime }}$-nek, ezert $v\in S_{x^{\prime }}$
A reszfa lemma miatt $S_{x^{\prime }}=T_{x^{\prime }}$ ezert a $v$ leszarmazottja $x^{\prime }$ -nek ezert $BSZ(x^{\prime })\ge BSZ(v)$

Tehat $x^{\prime }=v$ mert csak ekkor lehet $BSZ(x^{\prime })=BSZ(v)$

Meg annyit kell belatnunk, hogy $P\subseteq T_v$
$y\in P$
$MSZ(y)\ge MSZ(v)=MSZ(x^{\prime })$
$BSZ(y)\le BSZ(v)$
$⟹v$ ose $y$-nak