データ圧縮における最新アルゴリズム［Ⅴ#12539;完］: 算術符号，乱数生成と区間アルゴリズム

摘要

本稿で扱う乱数生成，ホモフォニック符号（Homo－phonic code），算術符号も，情報源（確率過程）から出力される系列を，与えられた条件を満たす系列に変換する問題としてとらえられる．二つの離散情報源ZとXを考える．確率変数Z，Xの取り得る値の有限集合（情報源アルファベット）をそれぞれZ＝｛0，…，M－1｝，χ＝｛0，…，N－1｝，その離散確率分布をp＝（p_0，p_1，…，p_(M-1)），p_i＝Pr｛Z＝i｝＞0（0≤i≤M－1）；q＝（q_0,q_1, …，q_(N－1)），q_j＝Pr｛X＝j｝＞0（0≤j≤N－1）とする．以下では，情報源としては，定常無記憶（i，i，d）情報源を考える．