InfElmTetel9

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style>

Shannon-Fano kód

Szeretnénk kódolni egy $X$ valószínűségi változót, amelynek eloszlása a következő. (Ha a következő nem teljesül, átindexeljük.)

Feltesszük, hogy $p(x_{1})\geq p(x_{2})\geq \ldots \geq p(x_{n})>0$.

$w_{i}$ az (i-1) legnagyobb valószínűségű érték valószínűségeinek összege, amire a kódoláshoz szükségünk lesz.
Legyen
$w_{1}=0$
$w_{i}=\sum _{l=1}^{i-1}{p(x_{l})}$
ahol $i=2\ldots n$.

Felírjuk $w_{i}$ számokat $s$-alapú számrendszerben, a $w_{j}$-hez tartozó törtet olyan pontosságig, ahol először különbözik a többi $w_{i}$, $w_{i}\neq w_{j}$ felírástól. Az így kapott $n$ db véges hosszú törtből elhagyjuk az egészrészt, ez lesz $f(x_{i})$. Az így kapott kód prefix, és $E|f(X)|<{\frac {H(X)}{\log {s}}}+1$

Látható, hogy minden kódolásnál kevesebb mint egy kódbetű "veszik el", ezért célszerű minél nagyobb blokkméretet használni. A blokkméret növelésével az átlagos kódszóhosszra vonatkozó alsó határ tetszőlegesen megközelíthető. -- Sales - 2006.06.23.

TODO: ez nem bizonyítás! Én nem is fogom ideírni:) TK-ban megvan illetve: jogvédett, de elektronikus formában elérhető anyag
Algoritmus másképpen, ahogy digitből is tanultuk és ahogy könyebb elképzelni:

• 0/1 kiegészítgetés*:
  A Shannon-Fano kód konstruálása során fát építhetünk(Legyen bináris a fa; s = 2). A valószínűségeken rendezés adott, ahogy a Shannon-kódnál. A rendezett sorozatot kétfelé vágjuk, hogy a két rész összsúlya(valószínűségek összege) a lehető legközelebb legyen egymáshoz. A két szakaszt jelezzük 0-val illetve 1-el a fa két új csúcsában(a gyökér alá téve ezeket) ami a sorozatot reprezentálja ezek után. Ez rekurzívan (a sorozat szétbontása a sorozathoz tartozó csúcs alá kerül, mint új gyökér alá) amíg egy elemű sorozatokat kapunk. A kódszavakat kiolvashatjuk, ha a gyökértől a levélekig bejárjuk az utakat, és kiolvassuk a csúcsokba írt számot(0/1).

-- hippi - 2007.06.13.