📚 基礎編：算術符号って何？
🤔 まず、なんで符号化が必要なの？
コンピュータはデジタルな世界です。文字や画像、音声などの情報を0と1の組み合わせ（ビット列）で表現する必要があります。でも、どんな情報でも同じ長さで表現していたら、めちゃくちゃ無駄になってしまいます。
🌟 身近な例で考えてみよう
日本語の文字頻度：
- 「あ」「い」「う」→ よく使う
- 「ぢ」「づ」「を」→ あまり使わない
よく使う文字は短く、あまり使わない文字は長く符号化すれば、全体として短くできるはず！
📊 算術符号の基本アイデア
算術符号は、文字列全体を0と1の間の一つの小数で表現する符号化方法です。
🎯 ポイント： 各文字の出現確率に応じて、0-1の区間を分割していきます。よく出る文字ほど広い区間を割り当てるので、効率的な符号化ができます。
🔢 超簡単な例で理解しよう
例：「A」「B」の2文字だけの世界
確率：A = 0.7, B = 0.3
区間の分割：
- A: [0, 0.7)
- B: [0.7, 1.0)
文字列「AB」を符号化すると...
ステップ1： 最初の区間は [0, 1)
ステップ2： 「A」が来た → [0, 0.7) に絞る
ステップ3： 「B」が来た → [0, 0.7) を A:B = 0.7:0.3 で分割
A の範囲: [0, 0.7×0.7) = [0, 0.49)
B の範囲: [0.49, 0.7)
→ B を選ぶので [0.49, 0.7)
A の範囲: [0, 0.7×0.7) = [0, 0.49)
B の範囲: [0.49, 0.7)
→ B を選ぶので [0.49, 0.7)
結果： 「AB」は [0.49, 0.7) で表現される
この区間内の任意の値（例：0.6）が「AB」の符号となる
この区間内の任意の値（例：0.6）が「AB」の符号となる
🤓 なんでこれがすごいの？
- 理論的に最適： エントロピーに近い符号長を実現
- 柔軟性： どんな確率分布にも対応
- 連続性： 1文字ずつ処理できる
📖 理解編：数学的に理解しよう
📐 数学的定義
アルファベット Σ = {s₁, s₂, ..., sₙ} で、各シンボル sᵢ の確率を pᵢ とします。
累積確率：F(sᵢ) = Σⱼ₌₁ⁱ⁻¹ pⱼ (F(s₁) = 0)
🔄 符号化アルゴリズム
初期化：
low = 0.0
high = 1.0
各文字 sᵢ に対して：
range = high - low
high = low + range × F(sᵢ₊₁)
low = low + range × F(sᵢ)
出力：
[low, high) 区間内の任意の値
📊 具体例で計算してみよう
例：文字列「CAB」を符号化
シンボル確率：
| シンボル | 確率 | 累積確率 |
|---|---|---|
| A | 0.4 | 0.0 |
| B | 0.3 | 0.4 |
| C | 0.3 | 0.7 |
初期状態：
[low, high) = [0.0, 1.0)
「C」を符号化：
range = 1.0 - 0.0 = 1.0
low = 0.0 + 1.0 × 0.7 = 0.7
high = 0.0 + 1.0 × 1.0 = 1.0
→ [0.7, 1.0)
「A」を符号化：
range = 1.0 - 0.7 = 0.3
low = 0.7 + 0.3 × 0.0 = 0.7
high = 0.7 + 0.3 × 0.4 = 0.82
→ [0.7, 0.82)
「B」を符号化：
range = 0.82 - 0.7 = 0.12
low = 0.7 + 0.12 × 0.4 = 0.748
high = 0.7 + 0.12 × 0.7 = 0.784
→ [0.748, 0.784)
🔍 復号化アルゴリズム
符号化された値から元の文字列を復元します。
入力：符号値 code, 文字列長 n
復号化：
for i = 1 to n:
range = high - low
value = (code - low) / range
// value が属する区間を見つける
シンボル s を決定（F(s) ≤ value < F(s+1)）
// 区間を更新
high = low + range × F(s+1)
low = low + range × F(s)
出力 s
⚠️ 実装上の注意点
精度の問題： 文字列が長くなると区間が非常に小さくなり、浮動小数点数の精度では表現できなくなります。実用的な実装では、整数演算や区間の正規化などの工夫が必要です。
🎓 応用編：実用的な算術符号
🔧 実装上の課題と解決法
1. 精度の問題
浮動小数点数の精度は有限なので、長い文字列では区間が小さくなりすぎて正確に表現できなくなります。
解決法：整数演算の使用
区間を整数で表現し、必要に応じて正規化（スケーリング）を行います。
区間を整数で表現し、必要に応じて正規化（スケーリング）を行います。
2. オーバーフロー対策
E1スケーリング： [0, 0.5) の場合
low = 2 × low
high = 2 × high
出力「0」
E2スケーリング： [0.5, 1.0) の場合
low = 2 × (low - 0.5)
high = 2 × (high - 0.5)
出力「1」
E3スケーリング： [0.25, 0.75) の場合
low = 2 × (low - 0.25)
high = 2 × (high - 0.25)
カウンタを増加
📈 適応的算術符号
事前に確率が分からない場合、符号化しながら確率を更新していく手法です。
適応的モデルの例
初期状態：全シンボルの確率を均等に設定
更新規則：シンボルが出現するたびに、そのカウントを増やす
count[s] += 1
total_count += 1
probability[s] = count[s] / total_count
🌟 コンテキストベース算術符号
直前の文字や文脈に応じて確率を変える、より高度な手法です。
PPM (Prediction by Partial Matching)
過去のn文字のパターンに基づいて、次の文字の確率を予測
- 「th」の後は「e」が来やすい
- 「qu」の後は「u」が来やすい
⚡ 性能と圧縮率
理想的符号長 = -log₂(P(文字列))
エントロピー = -Σ pᵢ log₂(pᵢ)
エントロピー = -Σ pᵢ log₂(pᵢ)
算術符号は理論的にエントロピーの下限に達することができる唯一の実用的な符号化方法です。
🔗 他の圧縮手法との比較
| 手法 | 圧縮率 | 計算量 | 特徴 |
|---|---|---|---|
| ハフマン符号 | 良い | 低 | 文字単位、整数ビット |
| 算術符号 | 最適 | 中 | 理論的最適、小数ビット |
| LZ系 | 実用的 | 低 | 辞書ベース、高速 |
💪 演習編：問題を解いてマスターしよう
問題1：基本的な符号化
シンボル A, B, C の確率がそれぞれ 0.5, 0.3, 0.2 である。文字列「AB」を算術符号で符号化せよ。
解答：
累積確率：
A: [0.0, 0.5)
B: [0.5, 0.8)
C: [0.8, 1.0)
「A」を符号化：
[low, high) = [0.0, 0.5)
「B」を符号化：
range = 1/3
low = 0 + (1/3) × (1/2) = 1/6
high = 0 + (1/3) × (3/4) = 1/4
区間：[1/6, 1/4)
カウント更新：A=2, B=2, C=1 (total=5)
3文字目 'A'：
新確率：P(A)=2/5, P(B)=2/5, P(C)=1/5
A: [0, 2/5), B: [2/5, 4/5), C: [4/5, 1)
range = 1/4 - 1/6 = 1/12
low = 1/6 + (1/12) × 0 = 1/6
high = 1/6 + (1/12) × (2/5) = 1/6 + 1/30 = 2/15
最終区間： [1/6, 2/15) ≈ [0.167, 0.200)
🎮 インタラクティブ算術符号シミュレータ
ここに結果が表示されます
チャレンジ問題：実装課題
以下の仕様で算術符号の簡単な実装を考えてみよう：
- 4文字以下の文字列に対応
- 3つのシンボル A, B, C をサポート
- 固定確率分布を使用
- 浮動小数点演算を使用（精度問題は無視）
Python実装例：
def arithmetic_encode(string, probabilities):
symbols = ['A', 'B', 'C']
cumulative = [0.0]
for p in probabilities:
cumulative.append(cumulative[-1] + p)
low = 0.0
high = 1.0
for char in string:
if char not in symbols:
continue
idx = symbols.index(char)
range_size = high - low
high = low + range_size * cumulative[idx + 1]
low = low + range_size * cumulative[idx]
return (low + high) / 2
def arithmetic_decode(code, length, probabilities):
symbols = ['A', 'B', 'C']
cumulative = [0.0]
for p in probabilities:
cumulative.append(cumulative[-1] + p)
result = ""
low = 0.0
high = 1.0
for _ in range(length):
range_size = high - low
value = (code - low) / range_size
for i in range(len(symbols)):
if cumulative[i] <= value < cumulative[i + 1]:
result += symbols[i]
high = low + range_size * cumulative[i + 1]
low = low + range_size * cumulative[i]
break
return result
# 使用例
probs = [0.5, 0.3, 0.2] # A, B, C
encoded = arithmetic_encode("AB", probs)
decoded = arithmetic_decode(encoded, 2, probs)
print(f"符号値: {encoded}")
print(f"復号結果: {decoded}")
📝 試験対策のまとめ
試験でよく出るポイント：
- 基本概念：区間の分割、累積確率の計算
- 符号化手順：low, highの更新式
- 復号化手順：符号値から文字を特定する方法
- 効率性：理論的符号長の計算
- 実装上の課題：精度問題とその対策
覚えておくべき公式：
符号化: high = low + range × F(s+1), low = low + range × F(s)
理論符号長: -log₂(P(文字列))
エントロピー: H = -Σ pᵢ log₂(pᵢ)
符号化: high = low + range × F(s+1), low = low + range × F(s)
理論符号長: -log₂(P(文字列))
エントロピー: H = -Σ pᵢ log₂(pᵢ)