4.5. 4.5. Gilbert-Moore kód

Nagyméretű forrásábécé esetén a sorbarendezés költsége magas lehet. Erre ad megoldást a következő kód, amelynél nincs szükség sorbarendezésre.

4.28. Tétel. Létezik prefix kód, hogy

Bizonyítás. A bizonyítás konstruktív és az elkészített kódot Gilbert-Moore kódnak nevezzük.

Most pedig nézzük, hogy az algoritmus milyen lépésekből áll.

Legyen

tetszőleges forráseloszlás.

Ekkor a lépések a következők:

  1. Képezzük az értékeket a következőképpen:

    1. Ábrázoljuk ezen értékeket a intervallumon és osszuk fel a intervallumot egyenlő részre ( a kódábécé elemeinek száma).

    2. Azokat az intervallumokat, melyek egynél több értéket tartalmaznak osszuk fel újra egészen addig míg mindegyik más intervallumba nem kerül.

    3. A kódszó az hosszúságú intervallumok megfelelő sorszámából áll, amelyekben benne van, ahol a kódszó hossza, illetve az osztáslépések száma.

A konstrukcióból látszik, hogy prefix kódot kapunk.

Megmutatjuk, hogy

ahol

Az értéket tartalmazó utolsó előtti, hosszúságú intervallumban legalább még egy pont van, azaz az és az közül legalább az egyik. Tehát mindenképpen igaz, hogy

Képezzük mindkét oldal logaritmusát, majd negatívját és összegezzük minden -re, akkor kapjuk, hogy

Ezzel az állítást bizonyítottuk.

4.7. ábra - Példa a Gilbert-Moore kódolásra (intervallumfelosztás)

Példa a Gilbert-Moore kódolásra (intervallumfelosztás)

4.8. ábra - Példa a Gilbert-Moore kódolásra (kódfa)

Példa a Gilbert-Moore kódolásra (kódfa)

4.9. ábra - Példa a Gilbert-Moore kódolásra (kód)

Példa a Gilbert-Moore kódolásra (kód)

4.10. ábra - Példa a Gilbert-Moore kódolásra (intervallumfelosztás)

Példa a Gilbert-Moore kódolásra (intervallumfelosztás)

4.11. ábra - Példa a Gilbert-Moore kódolásra (kódfa)

Példa a Gilbert-Moore kódolásra (kódfa)

4.12. ábra - Példa a Gilbert-Moore kódolásra (kód)

Példa a Gilbert-Moore kódolásra (kód)