12.2. Mohó algoritmus

A dinamikus programozásnál több érték közül választottuk ki az optimálisat. Bizonyos esetekben nem kell több lehetőséget végigpróbálni, már elsőre kiválaszthatjuk a legjobbat. Egy ilyen módszer a Huffman kódolás. Tegyük fel, hogy egy 10000 hosszúságú üzenetben csak a, . . . , f betűk szerepelnek, s a gyakoriságok rendre legyenek 30%, 10%, 5%, 10%, 25% és 20%. Ha minden betűt három bittel kódolunk, akkor 30000 bit segítségével tárolhatjuk vagy továbbíthatjuk az üzenetet. Ha viszont eltérő hosszúságú bitsorozatokkal kódoljuk a betűket, akkor spórolhatunk a bitekkel. Ha a kódolásunk a következő a-00, b-0100, c-0101, d-011, e-10 és f-11, akkor 24000 bit is elegendő.

Ebben az esetben is egyértelműen dekódolható az üzenet, ugyanis egyik betű kódja sem prefixe egy másiknak. Sőt mi több, ez a kódolás optimális, azaz nem kódolható rövidebben az üzenet. A kód elkészítéséhez a következőket tételezzük fel: a betűk halmaza az n elemű C halmaz, és minden egyes x betűhöz tartozik egy x.f gyakorisági érték.

Az algoritmus dinamikus halmaz két legkisebb gyakoriságú elemét összeragasztja, s ezt addig folytatja, amíg csak egy pont marad. Az összeragasztás során feljegyeztük, hogy melyik betűnek hol a helye, s ennek alapján a keletkezett fából leolvasható a kód. (Ha balra kell haladni a keresésnél, akkor 0-t fűzünk a kódhoz, egyébként 1-et.) A tanult gráfalgoritmusok nagy része hasonlóan mohó algoritmusnak tekinthető.