FGK符号

FGKの名は、三名の発案者Faller、Gallagher、Knuthのそれぞれの頭文字を取ったものである。

静的ハフマン符号は、一度入力をすべて走査してハフマンツリーを作ってから再度同じ入力をして符号化する。つまり入力を二度読まねばならない。

また文字と符号(ハフマンツリー)との対応関係を保存する必要があるため、符号以外の無駄な情報を含まねばならないという問題もある。

そこで、1970年代にFallerとGallagherにより考案されたものが「動的ハフマン符号」(動的ハフマン符号)で、入力一文字毎にハフマンツリーを再構成することで、常にその時点での最適状態が維持されるようにした。但しその代わり、再計算のためにかなりの処理時間が掛かってしまう。

これに改良を加えたのがKnuthで、1985(昭和60)年にFGKとして開発された。