FGK符号
読み：エフジーケイふごう
外語：FGK: Faller-Gallagher-Knuth

　ハフマン符号化の問題点を改善し、効率を高めたもの。
目次
概要
　FGKの名は、三名の発案者Faller、Gallagher、Knuthのそれぞれの頭文字を取ったものである。
特徴
　静的ハフマン符号は、一度入力をすべて走査してハフマンツリーを作ってから再度同じ入力をして符号化する。つまり入力を二度読まねばならない。
　また文字と符号(ハフマンツリー)との対応関係を保存する必要があるため、符号以外の無駄な情報を含まねばならないという問題もある。
　そこで、1970年代にFallerとGallagherにより考案されたものが「動的ハフマン符号」(動的ハフマン符号)で、入力一文字毎にハフマンツリーを再構成することで、常にその時点での最適状態が維持されるようにした。但しその代わり、再計算のためにかなりの処理時間が掛かってしまう。
　これに改良を加えたのがKnuthで、1985(昭和60)年にFGKとして開発された。
再検索