1．は　じ　め　に

　データ圧縮符号のうち，データ系列を一文字ごとに可変長の符号語に符号化する符号は，FV符号（Fixed-to-Variable length code）と呼ばれる．ここでは，符号語がの二元系列である二元FV符号を考える．FV符号のうち，任意のデータ系列を誤りなく復号できるものを一意復号可能符号という．一意復号可能符号のうち，各符号語の最終ビットを読み込んだ時点でその符号語の復号を完了できる符号を瞬時符号という．瞬時符号は，任意の符号語が他の全ての符号語の語頭と異なっているため，語頭符号（prefix code）とも呼ばれる⁽¹⁾．

　FV符号は符号木を用いて表現することができる．情報源アルファベットに対する符号木の例を図1に示す．符号木の根から文字が割り振られた節点までのパスが，の符号語を表している．瞬時符号（語頭符号）となるためには，全ての文字は葉に割り振られなければならない．

　文字の生起確率と符号長をとで表すと，その平均符号長はで与えられるが，ハフマン符号⁽²⁾は瞬時符号の中で最小の平均符号長を達成することができる．また，マクミランの定理⁽³⁾から，一意復号可能符号の符号長はクラフトの不等式を満たさなければならず，クラフトの定理⁽⁴⁾から，符号長がクラフトの不等式を満たせば，その符号長を持つ瞬時符号を作ることができる．したがって，任意の一意復号可能符号に対して，それと同じ符号長を持つ瞬時符号を作れるため，瞬時符号の中で最適なハフマン符号は一意復号可能符号の中でも最適な符号となる．

　その結果，1956年にマクミランの定理が証明されて以来，約60年にわたりハフマン符号より圧縮率の良い一意復号可能なFV符号を作る試みは全くされていなかった．しかし，マクミランの定理は一つの符号木を用いる一意復号可能符号に対して証明されているため，複数の符号木を用いることにより，ハフマン符号より平均符号長の小さい一意復号可能符号を構成できる可能性がある．実際，2015年にYamamoto, Tsuchihashi, Hondaは，2個の符号木を用いるAIFV符号を提案し，ハフマン符号より小さい平均符号長を達成できることを示した⁽⁵⁾．瞬時符号ではない一意復号可能符号は，一般には大きな復号遅延が生じる可能性があり，そのような符号は実用的ではない．AIFV符号では，復号遅延が2ビット以下になるように作られており，この特性から「準瞬時（almost instantaneous）」と名付けられている．