LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mashuel(恵瑠 真珠)

新手のentropy符号Valli-Encoding

Posted at

毎度おなじみの圧縮関連技術について。組み合わせ論(二項式/多項式)を使用する圧縮手法を紹介します。詳細は本家参照。そっちをほぼ日本語化したような内容ですが怪しいもんだ…。

導入

これは、記号の正確な頻度を利用して、組み合わせ論で入力列を圧縮するものです。出力は、0 ～ 頻度表の記号の順列の数未満 までの間の数値になります。入力列は、各記号を配置する前に発生する可能性のある組み合わせの数 (二項式) を使用して、一度に 1 つの一意の記号で処理され、その合計によって 1 つの記号の符号化が生成されます。これらの符号化は、先行する各記号の順列の数に基づいて組み合わせることができます。
出力量は、常に、記号頻度表(多項式とも呼ばれる)が与えられた記号の順列の合計数の大きさになります。

A、B、C、... = 記号数、
T = 記号の合計数 = A + B + C + ...
bit総量 = log2(T! / (A! * B! * C! * ...))

多くの場合、この手法の出力は他のentropy符号の実装よりも小さくなります

動作原理

符号化

手順

  1. 平文内の各記号の出現回数を数えて頻度表を作成
  2. encoding_accumulator = 0に設定します。この値は各記号の符号化 Dataを累積し、最終的な符号化値を含みます
  3. 最後を除く頻度表の各記号を反復処理します
    1. symbol_binomial_sum = 0に設定; 現在符号化されている記号の二項和を保持します
    2. combiner = 1を設定します。これは、現在の記号の前の全ての記号の順列の数です(詳細については例を参照してください)
    3. 現在の記号に遭遇するまで平文を反復します。
      • 二項式 N を計算してK を選択します。ここで、N は記号位置(0以上)のindex、K は現在の記号数(1、2、3、...)です
      • 平文の反復処理を続行し、前の手順で計算された全ての二項式をsymbol_binomial_sumに合計します
    4. 記号の平文の終わりに達した場合
      • encoding_accumulator = encoding_accumulator + symbol_binomial_sum * combinerと設定します
      • combiner = combiner * (message_size choose symbol_count)を設定します。これは次の記号反復で使用されます
      • 平文から符号化された記号を削除します(配列の幅変更は計算量が多いため、code内で最適化され、代わりに、位置を数えないことを示すためにnull値が使用されます)
    5. 集合内の最後の記号に到達するまで処理を続けます。最後の値は、他の全ての記号の位置から推測できるため、符号化されません
  4. encoding_accumulator は最終的に符号化されたDataになります

符号化例

msg h i d e h o h e d e h e
Index 0 1 2 3 4 5 6 7 8 9 10 11

Dataを頻度と記号で並べ替えて、次の頻度表に整理します

Count Symbol
1 i
1 o
2 d
4 e
4 h
初期値
message_length = 12
combiner = 1
encoding_accumulator = 0
Symbol 'i'
symbol_binomial_sum = 0
# First 'i' in message at index 1
symbol_binomial_sum = symbol_binomial_sum + (location choose count) = 0 + (1 choose 1) = 1
no more 'i' locations
encoding_accumulator = encoding_accumulator + combiner * symbol_binomial_sum
encoding_accumulator = 0 + 1 * 1 = 1
combiner = combiner * (message_length choose symbol_count)
combiner = 1 * (12 choose 1) = 12
message_length = message_length - symbol count 
message_length = 12 - 1 = 11
# Remove 'i' from message
msg h d e h o h e d e h e
Index 0 1 2 3 4 5 6 7 8 9 10
Symbol 'o'
symbol_binomial_sum = 0
# first 'o' in message at index 4
symbol_binomial_sum = 0 + 4 choose 1 = 4
# no more 'o' locations
encoding_accumulator = 1 + 12 * 4 = 49
combiner = 12 * (11 choose 1) = 132
message_length = 11 - 1 = 10
# remove 'o' from message
msg h d e h h e d e h e
Index 0 1 2 3 4 5 6 7 8 9
Symbol 'd'
# First 'd' at index 1
symbol_binomial_sum = 0 + 1 choose 1 = 1
# Second 'd' at index 6
symbol_binomial_sum = 1 + 6 choose 2 = 16
# no more 'd' locations
encoding_accumulator = 49 + 132 * 16 = 2161
combiner = 132 * (10 choose 2) = 5940
message_length = 10 - 2 = 8
# Remove 'd' from message
msg h e h h e e h e
Index 0 1 2 3 4 5 6 7
Symbol 'e'
First 'e' at index 1
symbol_binomial_sum = 0 + 1 choose 1 = 1
Second 'e' at index 4
symbol_binomial_sum = 1 + 4 choose 2 = 7
Third  'e' at index 5
symbol_binomial_sum = 7 + 5 choose 3 = 17
Fourth 'e' at index 7
symbol_binomial_sum = 17 + 7 choose 4 = 52
no more 'e' locations
encoding_accumulator = 2161 + 5940 * 52 = 311041
msg h h h h
Index 0 1 2 3

残りの位置は全て「h」ですが、可能な順列は 1 つだけなので、符号化する必要はありません。平文が全て 1 つの文字である場合も同様です。その場合、手法は基本的に頻度表を使用した連長符号化です。
これで符号化が完了し、保存する最終値は 311041 になります。保存には 3 bytes(19 bits)が必要ですが、元の平文は 12 bytes(96 bits)でした。

復号化

入力

  1. 符号化された圧縮文
  2. 各記号/文字の頻度表

手順

  1. 符号化されたDataを整数と頻度表に読み込みます
  2. 頻度の合計である平文を保持するための配列を作成します
    • この配列に、復号する最後の記号を入力します。これが最頻出記号であるため、配置する場所の合計が少なくなります
  3. 符号化と同じ順序で記号を反復処理します。最後の記号の位置は推測されるため、最後の記号は含めません
    1. 現在の記号が最後から2番目の記号(例の平文では「e」)の場合
      • symbol_binomial_sum = 符号化されたData
    2. それ以外
      • uncombinerを計算します = (合計位置 - 復号された位置)現在の記号数を選択します
      • uncombinerによって符号化されたDataを余りで割ります
        • 剰余は、現在の記号の二項式の合計です
        • 商は、現在の記号が含まれない符号化されたDataであり、次の反復で使用されます
    3. 各記号頻度は、K = total_symbol_countから始まり、1まで遡ります
      • 二項式Nを見つけてKを選択します。ここでKは現在の記号数で、
        • (NはKを選択) < symbol_binomial_sums および
        • 記号二項和 < ((N+1) Kを選択)
      • 以前に配置された記号によって生じたoffsetを数えます。これは、符号化後に平文から記号を削除する符号化に似ており、それらの記号が存在しないかのように記号の最終的な位置を計算する必要があります。素朴ですが、単純な手順は次のようになります
        • offset=0
        • for i = 0 to N+offset: if message[i]!='h': offset++
      • 平文配列のK番目の記号をN+offset(0以上)の位置に配置する
    4. 記号数 == 1 になるまで記号を配置し続けると、推定は不要になり、N = symbol_binomial_sum になります
  4. 記号の反復が完了すると、配列の内容で平文が復号されます

復号化例

初期値 頻度表

Count Symbol
1 i
1 o
2 d
4 e
4 h 
encoded_data = 311041
remaining_positions = message_length = 12

配列内に充填されている最後の文字と位置の対応

msg h h h h h h h h h h h h
Index 0 1 2 3 4 5 6 7 8 9 10 11

//は整数除算(切り捨て)を示します

Symbol 'i'
uncombiner = remaining_positions choose count = 12 choose 1 = 12
symbol_binomial_sum = combined_data % uncombiner
symbol_binomial_sum = 311041 % 12 = 1 
encoded_data = encoded_data // uncombiner 
encoded_data = 311041 // 12 = 25920
decode first 'i'
# location estimate & verification not needed for count==1
# for an example go to symbol 'd'
location_estimate = symbol_binomial_sum = 1
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# no non-'h' symbols found, offset = 0
message[location_estimate + offset => 1 + 0 => 1] = 'i'
no more 'i' locations
remaining_positions = remaining_positions - count = 12 - 1 = 11
msg h i h h h h h h h h h h
Index 0 1 2 3 4 5 6 7 8 9 10 11
Symbol 'o'
uncombiner = 11 choose 1 = 11
symbol_binomial_sum = 25920 % 11 = 4 
encoded_data = 25920 // 11 = 2356
# decode first 'o'
# location estimate & verification not needed for count==1
# for an example go to symbol 'd'
location_estimate = symbol_binomial_sum = 4
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i; offset = 1
message[4+1=>5] = 'o'
# no more 'o' locations
remaining_positions = 11 - 1 = 10
msg h i h h h o h h h h h h
Index 0 1 2 3 4 5 6 7 8 9 10 11
Symbol 'd'
uncombiner = 10 choose 2 = 45
symbol_binomial_sum = 2356 % 45 = 16 
encoded_data = 2356 // 45 = 52
# decode first 'd'
# symbol count > 1, estimate location
location_estimate = (symbol_binomial_sum * count!)^(1/count) + count//2
location_estimate = (16*2!)^(1/2)+2//2 = 6
# verify estimate
# check overestimate, can only overestimate by 1 with this approach
current_binomial = location_estimate choose count = 6 choose 2 = 15
if current_binomial > symbol_binomial_sum:
    # 15 > 16 => false, no underestimation
    location_estimate -= 1
else:
    # if the next location's (N+1) binomial is larger than symbol_binomial_sum
    # then the estimate is correct
    # else, loop until larger is found
    next_binomial = location_estimate+1 choose count = 7 choose 2 = 21
    while(next_binomial < symbol_binomial_sum):
        # 21 < 16 => false, no correction needed, no underestimation
        location_estimate += 1
        next_binomial = location_estimate choose count
# location_estimate = 7
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i,d; offset = 2
message[location_estimate+offset=6+2=>8] = 'd'
symbol_binomial_sum -= location_estimate choose count = 15
symbol_binomial_sum = 1
# decode second 'd'
# location estimate & verification not needed for count==1
location_estimate = symbol_binomial_sum = 1
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i; offset = 1
message[1+1=>2] = 'd'
# no more 'd' locations
remaining_positions = 10 - 2 = 8
msg h i d h h o h h d h h h
Index 0 1 2 3 4 5 6 7 8 9 10 11
Symbol 'e'
# for the second to last symbol (last to be decoded)
# the uncombiner is not needed and symbol_binomial_sum = encoded_data
symbol_binomial_sum = encoded_data = 52

# decode first 'e'
location_estimate = (52*4!)^(1/4)+4//2 = 7
# check overestimate
current_binomial = 7 choose 4 = 35
# 35 > 52 => false, no overestimation
if current_binomial > symbol_binomial_sum:
    location_estimate -= 1
else:
    # check underestimate
    next_binomial = location_estimate+1 choose count = 8 choose 4 = 70
    # 70 < 52 => false, no correction needed, no underestimation
    while(next_binomial < symbol_binomial_sum):
        location_estimate += 1
        next_binomial = location_estimate choose count
# location_estimate = 7
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i,d,h,o; offset = 4     
message[7+4=>11] = 'e'
symbol_binomial_sum -= location_estimate choose count => 7 choose 4 => 35
symbol_binomial_sum = 17

# decode second 'e'
location_estimate = (17*3!)^(1/3)+3//2 = 5
# check overestimate
current_binomial = 5 choose 3 = 10
#   10 > 17 => false, no overestimation
# check underestimate
next_binomial = 6 choose 3 = 20
#   20 < 17 => false, no underestimation
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i,d,h,o; offset = 4     
message[5+4=>9] = 'e'
symbol_binomial_sum -= 5 choose 3 => 10
symbol_binomial_sum = 7

# decode third 'e'
location_estimate = (7*2!)^(1/2)+2//2 = 4
# check overestimate
    current_binomial = 4 choose 2 = 6
#   6 > 7 => false, no overestimation
# check underestimate
    next_binomial = 5 choose 2 = 10
#   10 < 7 => false, no underestimation
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i,d,o; offset = 3
message[4+3=>7] = 'e'
symbol_binomial_sum -= 4 choose 2 => 6
symbol_binomial_sum = 1

# decode fouth 'e'
# location estimate & verification not needed for count==1
location_estimate = symbol_binomial_sum = 1
# calculate offset
offset = 0
for i = 0 to location_estimate+offset: if message[i]!='h': offset++
# found i,d; offset = 2
message[1+2=>3] = 'e'

# no more 'e' locations
# remaining_positions no longer needed
# decoding complete
msg h i d e h o h e d e h e
Index 0 1 2 3 4 5 6 7 8 9 10 11

といった具合です

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?