通信用語の基礎知識 IPv4
戻る
全国のICカードこれひとつ

FGK符号

辞書:電算用語の基礎知識 ファイル圧縮編 (PFCP)
読み:エフジーケイふごう
外語:FGK: Faller-Gallagher-Knuth 英語
品詞:固有名詞
1998/11/09 作成
2008/07/16 更新

ハフマン符号化の問題点を改善し、効率を高めたもの。

目次

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

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

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

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

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

関連する用語
ハフマン符号

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04 (07-Mar-2021)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club