5.2. 5.2. Shannon-Fano algoritmus, tetszőleges eloszlás esetén

Most nézzük, hogy mit kell tennünk, ha az intervallumok egyenletes felosztása helyett a felosztást tetszőleges módon végezzük el.

Legyen

tetszőleges forráseloszlás, továbbá legyen

az optimális bemeneti eloszlás. Ekkor a lépések a következők:

  1. Rendezzük a eloszlás valószínűségeit csökkenő sorrendbe;

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

  3. Ábrázoljuk ezen értékeket a intervallumon. Majd osszuk fel az intervallumot a valószínűségek arányában ( a kódábécé elemeinek száma);

  4. 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;

  5. A kódszó az hosszúságú intervallumok megfelelő sorszámából áll, amelyekben benne van.

Mint észrevehetjük ez a megoldás csak az intervallumok felosztásának módjában tér el a korábban ismertetett eljárástól. Ezzel a módszerrel a kódolás additív költség esetén is elvégezhető.

Nézzünk egy példát az egyenletes esetre:

5.1. Példa. Legyen bemeneti eloszlás, valamint a kódábécé legyen . A rendezés után képezzük az értékeket, amire kapjuk:

Ekkor az értékekhez a generált kódszavak a következők: