自由研究ノート(仮)

とかいう名前の備忘録

最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~


最大公約数と最小公倍数を求める ~1/3 割れるだけ割ってみる~
最大公約数と最小公倍数を求める ~2/3 素因数分解を利用する~
最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~ ←この記事

 
最後に ユークリッドの互除法 という手法を利用して、
最大公約数と、最小公倍数を求める方法について勉強してみる

 


ユークリッドの互除法を利用する

2つの数のうち、大きい方を A、小さい方を B と表すことにする。

1. AB で割ってあまり r を求める。
ここで r=0 であれば  B が2つの数A,B の最大公約数になる。

2. r \gt 0 ならば、AB の数を 、Br の数を入れて、再度割り算を行う。

あまりが 0 になるまで、この「2.」の手順を繰り返し、あまりが 0 になったとき、その割り算に使った"割った数" の方が、2つの数 A,B の 最大公約数 になる。

f:id:DarkCrowCorvus:20171206010823j:plain

これによる最大公約数の求め方をユークリッドの互除法と呼ぶ。

また、求まった最大公約数で A,B のどちらか一方を割って、その結果を割っていない方に掛けた結果が、2つの数 A,B最小公倍数 になる。

f:id:DarkCrowCorvus:20171206013321j:plain

 

関連する事実 

本題の前に ある事実を紹介

■ 事実..

A{\div}B のあまりを r とするとき、
AB の最大公約数は Br の最大公約数でもある。

 

■ 証明..

AB で割って求まる商を q
あまりを r とする時、この関係を以下の式で表す

{\hspace{6pt}}r=A-Bq\ {\cdots}

AB の公約数を d とするとき
① の A と B から d を引っ張り出して式を整理する

{\hspace{6pt}}r=A'd-B'dq
{\hspace{12pt}}=(A'-B'q)d

右辺は d の倍数。
よって、左辺 rd の倍数。
つまり、dr の約数である

dB の約数なので、
dBr の公約数になる

f:id:DarkCrowCorvus:20171212014111j:plain

次に ① を 「 A を左辺とする式」に書き換えてみる

{\hspace{6pt}}A=Bq+r\ {\cdots}

Br の公約数を d' とするとき、
② の Br から d' を引っ張り出して式を整理する

{\hspace{6pt}}A=(B'q+r')d'

右辺は d' の倍数。
よって、左辺 Ad' の倍数。
つまり、d'A の約数である

d'B の約数なので、
d'AB の公約数になる

以上のことから、
AB の公約数 d は、Br の公約数であり (d\ {\subseteqq}\ d')
Br の公約数 d' は、AB の公約数である (d\ {\supseteqq}\ d')

よって双方の公約数は、もれなく一致する。
"どちらか片方にだけある" という公約数は存在しない...その結果、AB の最大公約数は、ちょうど Br の最大公約数と一致する。

自分なりに解釈 (最大公約数)

AB で割ってあまりが出る場合、AB の数を、B にあまり r の数を入れて、割り算を繰り返す。

「あまりの数で割り、そのあまりの数で割り…」の繰り返しになるため、あまり r はその度にだんだんと小さくなり、いずれ r=0 に行き着く

f:id:DarkCrowCorvus:20171212015213j:plain

r=0 になったとき、つまりは繰り返しの中で A_iB_i で割り切れるタイミングが来たとき、その B_i の数が、 A_iB_i にとっての最大公約数になる

B_i の最大の約数は B_i 自身である。 A_iB_i で割り切れるなら、B_iA_iB_i の最大公約数になる

また、前述の事実に従って、繰り返しの中の AB の最大公約数、並びに Br の最大公約数は、どれも常に一致し、ずっと変わらない。

f:id:DarkCrowCorvus:20171212015438j:plain

よって、A_iB_i の最大公約数は、そのまま 初めの AB の最大公約数になる

自分なりに解釈 (最小公倍数)

上で求まった最大公約数を使って 2つの数のどちらか一方を割り、得られた商を "割っていない方" に掛けた結果が、2つの数の最小公倍数になる。

2つの数を A,B、最大公約数を G
そのGによって割られた 2つの数を a,b
とするとき、最小公倍数 L を求めるこの計算は

{\hspace{6pt}}L=aB{\hspace{8pt}}もしくは {\hspace{8pt}}L=Ab

{\hspace{6pt}}{\therefore}{\hspace{6pt}}L=aGb{\hspace{8pt}} である。

これより先は 「割れるだけ割ってみる」 の記事で説明したとおり。

 

3つ以上の数の最大公約数と最小公倍数

3つ以上の数の最大公約数は、まずその中のどれか 2つの数から ユークリッドの互除法によって 2つの数の最大公約数を求め、

その数と、また別の残っている数を使って ユークリッドの互除法によって3つの数の最大公約数を求め… を繰り返すことによって求まる。

3つ以上の数の最小公倍数を求めるために、ユークリッドの互除法を使うサンプルは、今回見つけることができなかった。

最小公倍数を求める対象が3つ以上になる場合は、「割れるだけ割ってみる」または「素因数分解を利用する」の記事で紹介した方法を使って解くのがよろしそう。 

 


最大公約数と最小公倍数の求め方を、
自分の納得がいくまで調べてみたつもり。

ユークリッドの互除法は、この用途とは別に
1次不定方程式の解を求めるためにも利用できるらしい。

その辺の理屈を調べてみるのは、また今度気が向いた時にでも (やらない)


参考にした書籍/サイトさん

書籍
なっとくする群・環・体 (Amazon)

 
最小公倍数/最大公約数
最大公約数と最小公倍数

最大公約数と最小公倍数を求める ~2/3 素因数分解を利用する~


最大公約数と最小公倍数を求める ~1/3 割れるだけ割ってみる~
最大公約数と最小公倍数を求める ~2/3 素因数分解を利用する~  ←この記事
最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~

 

ここでは 素因数分解 を使って
最大公約数と、最小公倍数を求める方法を勉強する

 


素因数分解を利用する

前の記事の事前知識で述べた通り、2 以上の数は素数1つ、またはいくつかの素数の掛け合わせによって表現できる

ここで、2 以上のある数を X
それから抽出できる素因数を p としたとき
それらの関係を

{\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\times}p_4{\cdots}

のような 掛け算の式で表現することを 素因数分解 と呼ぶ

f:id:DarkCrowCorvus:20171202081223j:plain

この素因数分解を使って2つの値の最大公約数と最小公倍数を求める。

■求め方..
2つの値を素因数分解する。

見つかった素因数のうち、同じ素因数を 指数 を使ってまとめる。
2つの数の素因数分解の結果は、どちらも次の通りに表現できるようになるはず

{\hspace{6pt}}X=(p_1)^{r1}{\times}(p_2)^{r2}{\times}(p_3)^{r3}{\times}(p_4)^{r4}{\cdots}

f:id:DarkCrowCorvus:20171202205657j:plain

その後、2つの式を縦に並べて、同じ素因数の「指数が小さい方」を片側に、「指数が大きい方」をもう片側に寄せる。

f:id:DarkCrowCorvus:20171202222530j:plain
なおここでは、片方にあって、もう片方にはない素因数が存在する場合、
ない方の式でその素因数を (p_i)^{0} のように表現する

そうしてできた指数の小さい方を集めた式の答えが 2つの数の 最大公約数
指数の大きい方を集めた式の答えが 2つの数の 最小公倍数 になる

f:id:DarkCrowCorvus:20171202222557j:plain

 

素因数分解の一意性

これの理解のために、
先に「素因数分解の一意性」について知っておきたい

 

素因数分解の一意性とは...

ある数を素因数分解するとき、素因数の並び順を考慮しないとするならば、それを表す式はただ一通りしか存在しない..という定理

またこの「素因数分解の一意性」の理解のために、先に「ユークリッド補題」について知っておきたい

 

ユークリッド補題とは...

ある2つの数の積 ab を、
ある数 p で割り切ることができるならば、

pab
少なくともどちらか一方を割り切ることができる…という定理


この定理は一見アタリマエのように見える。数学ではこれを 自明である というらしいのだけど、実際のところこれは自明ではないらしい。

この証明のために、先に「ペズーの補題」という定理を知る必要があるらしい...が、これ以上細かく見ていくと、本題から離れすぎて何の記事だかよくわからなくなりそう。
今回は単に 「そういった定理があるから ユークリッド補題は成り立つ」とだけ覚えておいて、先に進みたい。

 

■ 証明 (素因数分解の一意性)

ある数を素因数分解した結果が、2通りになる可能性があるとする

f:id:DarkCrowCorvus:20171203152058j:plain

{\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n
\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}

ここで、片方の素因数分解p_1{\times}p_2{\cdots}」の中に含まれる、
素因数 p_1 に着目してみる。

左辺の Xp_1 を素因数にもつ。
よって p_1 の倍数であるため、
Xp_1 によって、割りきることができる \cdots

もう片方の素因数分解q_1{\times}q_2{\cdots}」は、
同じ X を成す掛け算の式である。

さきほどの「ユークリッド補題」の定理に従うならば、①によって そのもう片方の素因数分解の中に、p_1 で割り切れる素因数が存在するはずである。

f:id:DarkCrowCorvus:20171203152128j:plain

ここで、p_1 によって割り切れる素因数 q_1 が見つかったとする。

 q_1 は素因数。つまり 1 か自身と同じ数でしか割り切ることができない。そして 事前知識で述べたとおり、1 は素数に含まれないため、素因数分解の中に 1 が現れることはない

よってこの要件を満たす q_1 は「q_1=p_1」ということになる。
p_2,p_3{\cdots}」についても、同じくそれらと一致する「q_2,q_3{\cdots}」を見つけられるはず

f:id:DarkCrowCorvus:20171203152212j:plain

次に p_1{\cdots}p_n すべてに一致する  q_1{\cdots}q_n を見つけられた後、まだ片方の素因数分解の中に q_{n+1}{\cdots}q_m が残る場合があるかを考えてみる

{\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n
\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}

この式を満たすためには、片方の式に余分に存在する素因数 q_{n+1}{\cdots}q_m は全て 1 でなければならない。しかし前述のとおり、1 が素因数分解の中に含まれるのは不適である。

f:id:DarkCrowCorvus:20171203152234j:plain

よって双方の素因数の数は一致する (n=m)
どちらか一方が多かったり、少なかったりする場面は存在しない

これらを踏まえて、上記 2つの素因数分解の式は一致する。
素因数分解の結果は、その並び順を考慮しないならば一意になる。

 

関連する事実

本題の前に ある事実を紹介

■ 事実..

ある数 m と、その数の約数 n をそれぞれ素因数分解して

{\hspace{6pt}}m=(p_1)^{r_1}{\times}(p_2)^{r_2}{\times}(p_3)^{r_3}{\times}(p_4)^{r_4}{\cdots}
{\hspace{6pt}}n=(p_1)^{s_1}{\times}(p_2)^{s_2}{\times}(p_3)^{s_3}{\times}(p_4)^{s_4}{\cdots}

のように整列させた結果、
約数  n 側に出現する素因数の指数 s_i は、 m 側に出現する同じ素因数の指数 r_i と比べて、どれも小さいか または等しくなる (r_i {\geq} s_i)

■ 証明..

ある数 m と、その約数 n との関係を以下の式で示す

{\hspace{6pt}}m=nx\ {\cdots}

ある素因数 p を ① の各変数から引っ張り出して、
以下の通りに式を整理する。

{\hspace{6pt}}m'p^r=n'p^sa'p^t\ {\cdots}

f:id:DarkCrowCorvus:20171203212855j:plain
なお、変数に素因数 p が含まれていなくても
それを p^0 と表現して、強引に式を成せるものとする。

前述した 素因数分解の一意性 の定理によって、「=」で結ばれた 左辺と右辺の素因数分解の結果は一致する。故に左辺と右辺にそれぞれ含まれる素因数の種類と個数は等しくなければならない。

それを踏まえて、
② より素因数の指数 r,s,t を抜き出し、関係を以下の式で示す

{\hspace{6pt}}r=s+t\ {\cdots}

f:id:DarkCrowCorvus:20171203223135j:plain

ここに現れる数はすべて正の整数である。③ の式を満たすためには、n 側の素因数の指数 「s」が、m 側の素因数の指数「r」よりも小さいか、または等しくならなければならない。

これは m,n に含まれるすべての素因数 p_i に対して言える。
結果、約数 n に含まれる素因数の指数はすべて小さいか、または等しい。

逆に、ある数 m と、それよりも素因数の指数がどれも小さいか、または等しい数 n が、本当に約数 (倍数) の関係になりうるかを考える。

n は、それに「m と比べて足りていない素因数」を掛けてやることで m になれる。

この「足りない素因数」を

{\hspace{6pt}}x=(p_1)^{r_1-s_1}{\times}(p_2)^{r_2-s_2}{\times}(p_3)^{r_3-s_3}{\times}(p_4)^{r_4-s_4}\ {\cdots}

とすれば、この mn の関係を表す式はちょうど ① と一致する。

f:id:DarkCrowCorvus:20171203233306j:plain

結果、mn に約数 (倍数) の関係が成立する。

 

自分なりに解釈 (最大公約数)

2つの数の素因数分解の結果、素因数の指数が小さい (または等しい) ほうを集めた式から、最大公約数が求められる。

その式に含まれる素因数は、元の2つの数と比べてどれも指数が小さい、または等しくなるため、前述の 事実 に従って、その式から成る数は、2つの数にとっての約数 (公約数) になる

またその式から成る数が、2つの数の公約数であるためには、式中のどの素因数の指数もそれ以上大きくすることができない。

たとえば、今よりも大きな公約数を作ろうとする時、その数の少なくとも1つ以上の素因数の指数は、もとの公約数の同じ素因数の指数よりも大きくなる

しかし、どの素因数の指数が今より大きくなっても、もとの2つの数のうち、少なくともどちらか一方の同じ素因数の指数よりも大きくなってしまう

f:id:DarkCrowCorvus:20171205010943j:plain

前述の事実「約数なら素因数の指数がどれも小さいか等しい」を満たさなくなるため
 その一方、あるいは両方の約数になることができず、結果 公約数ではなくなる

素因数の指数が小さい (または等しい) ほうを集めた式から成る数について、結局それより大きな公約数を作ることはできないため、それが 2つの数にとっての最大公約数になる

自分なりに解釈 (最小公倍数)

2つの数の素因数分解の結果、素因数の指数が大きい (または等しい) ほうを集めた式から、最小公倍数が求められる

その式に含まれる素因数は、もとの2つの数と比べてどれも指数が大きいか、または等しい。一つ上の項で解説した 事実 に従い、もとの2つの数は その式から成る数の約数、よってその式から成る数はもとの2つの数の倍数 (公倍数) になる

またその式から成る数が、2つの数の公倍数であるためには、式中のどの素因数の指数も今より小さくすることができない。

理屈は同じく一つ上の項で説明したのと大体同じ。
今よりも小さな公倍数を作れないため、結果 それが 最小公倍数 になる

3つ以上の数の最大公約数と最小公倍数

どちらも考え方は 2つの数に対して求めた時とあまり変わらない。

3つ以上の数をそれぞれ素因数分解して、その中から各素因数の指数が一番小さいものを寄せた式から、最大公約数 を求められる

また、各素因数の指数が一番大きなものを寄せた式から、最小公倍数 を求められる

f:id:DarkCrowCorvus:20171205090754j:plain

 


参考にした書籍/サイトさん

書籍
なっとくする群・環・体 (Amazon)

 
素因数分解の一意性

素因数分解の一意性とその証明について | 高校数学の美しい物語

 
最小公倍数/最大公約数
最大公約数と最小公倍数

3つ以上の数の公倍数・公約数|算数をしよう|ACTABA

最大公約数と最小公倍数を求める ~1/3 割れるだけ割ってみる~


最大公約数と最小公倍数を求める ~1/3 割れるだけ割ってみる~  ←この記事
最大公約数と最小公倍数を求める ~2/3 素因数分解を利用する~
最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~ 

何となく読んでいた数学系の本で
最大公約数と最小公倍数という単語を見つけた。
たしかこれって習ったのは小学生のころだったはず…

ずっと使うことがなかったから アタリマエかもしれないけど、
どうやって求めればいいのか もう覚えていなかった。

なんだか悔しくなったので この際きっちり復習してみる。
完全に自分のための記事。

 


事前知識

 

倍数

ある数を2倍、3倍...のように
何倍かしてできる数を その数の倍数という

ある2つの数に共通する倍数を その2つの数の 公倍数 という
その挙げられる公倍数のうち 最も小さい数を 2つの数の 最小公倍数 という

約数

ある数が掛け算によって求められるとき、
その掛け算に使った "元の数" は約数と呼ばれる

ある2つの数に共通する約数を その2つの数の 公約数 という
その挙げられる公約数のうち 最も大きな数を 2つの数の 最大公約数 という

素数

自然数の中で、1 か自分自身の数でしか割ることができない数は素数と呼ばれる。

2 以上の数は、必ず素数1つ、もしくはいくつかの素数の掛け合わせによって表現できる。ここで この掛け合わせに使った "元の素数" は 素因数 と呼ばれる

1 は例外的に素数には含まれない。1 が素数であることを許すと、例えば素因数分解 (次の記事で紹介) の結果にいくつでも ×1 を置けてしまう不都合が生じる

 


割れるだけ割ってみる

2つの数を共通して割れそうな数 (公約数) を見つけて、
その公約数で2つの数を割る

結果からまだ公約数が見つかるなら、
その公約数でまた2つの数を割る...のように割り算を繰り返す。

f:id:DarkCrowCorvus:20171213004258j:plain

2つの数の中に、2 以上の公約数を見つけられなくなるまで割り切ったところで、それまでに出た 公約数すべての積 を求めると、それが最大公約数になる

また、公約数すべての積 (最大公約数) に、2 以上の公約数がなくなった "割り残った 2つの数" を掛けると、それが最小公倍数になる。

f:id:DarkCrowCorvus:20171213004333j:plain

小学校で習うはず…らしいのだけど、
もはやこれすら覚えていなかった

 

自分なりに解釈 (最大公約数)

2つの数をある公約数で割った結果から、まだ公約数が見つかるのであれば、その見つかった 2つの公約数の積から、より大きな公約数を作れることがある

f:id:DarkCrowCorvus:20171128002248j:plain

ただし、前述の割り算の繰り返しの結果、割り残った 2つの数には、もう 1 しか公約数が残されていない

1 をそれまでに出た公約数の積に掛けても、もうそれ以上大きな公約数を作ることはできない。

したがって、2 以上の公約数がなくなるまで 2つの数に対する割り算を繰り返した末に、その中で見つけられた公約数すべての積は 最大公約数 になる。

 

自分なりに解釈 (最小公倍数)

最大公約数に、 割り残った 2つの数を掛けた結果が、元の 2つの数の最小公倍数になる

「もとの2つの数」は、割り切られた後の2つの数に、それまでに出現した公約数を掛けていくことで復元できる

前述の手順で求められた最大公約数は、出現した公約数すべての積であるから、

「もとの2つの数」は、割り切られた後の2つの数に、その最大公約数を掛けることでも、同様に復元させることができるはず

f:id:DarkCrowCorvus:20171129004347j:plain

割り切られた後の2つの数を a,b
最大公約数を G と表現するならば
最小公倍数を求めるこの掛け算は aGb のように表現できる

「もとの2つの数」をそれぞれ A,B と表すものとして、直前の式を整理すると、

(aG)b=Ab つまりはそれが Ab
a(Gb)=aB つまりはそれが Ba 倍 

よってこれが もとの数A の倍数であり、もとの数Bの倍数。
つまりこの掛け算によって求まる数は、もとの数 A,B の公倍数になることがわかる

f:id:DarkCrowCorvus:20171129002721j:plain

また、これがきちんと最小公倍数になる。
( 以下は 先の「素因数分解を利用する」の記事を見た後の方が理解がしやすいかもしれない) 

まず、2 以上の「共通して割れる数」が見つからなくなるまで 割り切られた2つの数は、言い換えれば、互いに共通する素因数がなくなるまで割り切られた2つの数である。

先ほどの掛け算 aGb について、

aG=A である。ここでたとえば、aG 側をそのままに、b を 1ずつ減少させることによって、Aの倍数であることを維持しつつ、B の倍数にもなる より小さな公倍数

{\hspace{6pt}}aG(b-n)

を作れないかを考えてみる。

f:id:DarkCrowCorvus:20171130024249j:plain

Gb=B である。このことから、b を減少させた時に aG(b-n)B の倍数になるためには、少なくとも、その減少によって失われるであろう 「b を成すために必要な素因数」を a 側が持っていないといけない

しかし前述の通り、a,b は互いに共通する素因数がなくなるまで割られた数である。そのため b を構成するために必要な素因数は a からは一切得られない。

よって aGb において それが公倍数であるためには、今よりも b を小さくすることはできない。

f:id:DarkCrowCorvus:20171130024314j:plain

a を減少させる (a-n)Gb によってより小さい公倍数を見つけようする試みも、同様に無効である。

結果、aGb よりも小さい数は、元の2つの数 A,B のどちらか片方の倍数にはなりうるが、公倍数になることはできない。

割り切られた2つの数 a,b と 最大公約数G との積が、たしかに 最小公倍数 ということになる。

3つ以上の数の最大公約数と最小公倍数

f:id:DarkCrowCorvus:20171201001955j:plain

3つ以上の数の最大公約数を求める場合、その解き方は2つの数に対して求めた時とあまり変わらない。

3つ以上の数すべてを共通して割れる数 (公約数) を見つけては割り、また見つけては割りを繰り返す。

3つ以上の数すべてに共通する 2 以上の公約数を見つけられなくなったところで、それまでに出現した公約数すべての積を求めれば、それが その3つ以上の数に対する最大公約数になる

f:id:DarkCrowCorvus:20171201005900j:plain
3つ以上の数の最小公倍数を求める場合、その解き方は2つの数に対して求めた時と若干異なる。

3つ以上の数に対して、前述した割り算の繰り返しを行い、それらすべてに共通する公約数を見つけられなくなっても、そのうちのいずれか2つ以上の数の中に公約数を見つけられるのであれば、それらの数に対してのみ 見けられた公約数による割り算を行う

割り切られた数のどの組み合わせからも、2 以上の公約数を見つけられなくなるまで これを繰り返す。

最終的に割り切られた数すべてと、それまでに出現した公約数すべてとの積を求めれば、それが 3つ以上の数に対する最小公倍数になる

 


参考にした書籍/サイトさん

書籍
なっとくする群・環・体 (Amazon)

 
最小公倍数/最大公約数
最大公約数と最小公倍数

3つ以上の数の公倍数・公約数|算数をしよう|ACTABA

PNG イメージを自力でパースしてみる ~5/6 PNGフォーマット編~

 ここまでのあらすじ

PNG イメージを自力でパースしてみる ~1/6 予備知識編~
PNG イメージを自力でパースしてみる ~2/6 Deflateの基本と固定ハフマン編~ 
PNG イメージを自力でパースしてみる ~3/6 カスタムハフマン編~
PNG イメージを自力でパースしてみる ~4/6 非圧縮とzlib編~

 

zlibを解凍するプログラムが一通り完成した。いよいよPNGファイルのパースに挑戦してみる。

 

 


PNGフォーマット

PNGファイルの中身は、以下のような構成になっている

  • シグネチャ
  • チャンク (IHDR)
  • チャンク
     ⋮
  • チャンク (IEND)

 
チャンクは 1ファイルにつき、必要な数だけ作られる。

このチャンクのかたまりの中で、IHDRのチャンク (後述) は 必ず先頭に出現し、
IENDのチャンク (後述) は 必ず末尾に出現する。

 

シグネチャ 

ファイルの先頭に必ず出現し、このファイルがPNGファイルであることを示す 8バイト長のデータ。すべてのPNGファイルは共通して、以下の値の並びを保有する。

10進 (16進)

137 (89) 80 (50) 78 (4e) 71 (47) 13 (0d) 10 (0a) 26 (1a) 10 (0a)


PNGファイルをロードするプログラムは、まず初めにファイルの先頭 8バイトを読み出し、このシグネチャの並びと一致するかどうかで、対象が確かに PNGファイルであるかどうかをチェックする必要がある 


ちなみに この並びの中に現れる各値は、それぞれ以下のような役割を持つ

10進 16進 ASCII文字 役割
137 89 \221 ASCII文字として表現できない値。ファイルに必ず非ASCII文字を含むことで、テキストファイルとして間違えてロードされてしまう可能性を減らす。
80 50 P 自身のフォーマット名を表す
78 4e N
71 47 G
13 0d \r

"改行文字"として解釈されてしまい、システムによって勝手に「\r」や「\n」に置き換えられたりしないかを検出するために利用される

10 0a \n
26 1a \032 Control-z文字。ファイルの中身をテキストとして読み出し表示させようとしたDOSコマンドを停止させる
10 0a \n "改行文字"として解釈されてしまい、システムによって勝手に「\r」や「\r\n」に置き換えられたりしないかを検出するために利用される

 

チャンク


PNGファイル中に現れる各チャンクは、共通して以下のような構造になっている

Length 4バイト
Chunk Type 4バイト
Chunk Data Length バイト
CRC 4バイト

 

1. Length(データのサイズ)

このチャンクの Chunk Data 部のサイズ (バイト数) を表す値を ここに4バイト長で格納する。最小で「0」 最大で「2^{31}-1」までの値を収められる

 

2. Chunk Type(チャンクの種類)

このチャンクの種類を表す、アルファベット4文字のデータがここに格納される

 

3. Chunk Data(データ)

Length が「0」ではない場合、このチャンクの種類に関連したデータが、この場所に格納される。
 

4. CRC(crc32チェックサム)

CRC32チェックサムアルゴリズムを使って算出された値を、ここに4バイト長で格納する。ここの詳しい解説は、次回の記事で行うことにする。

 

なお、PNGファイル中に現れる これら多バイト長の数値データはすべて ビッグエンディアン の並びになっている。 これらの数値データを読み出す際には、その読み出したデータのバイト並びに気を付けること。

 


チャンクの種類

 

PNGで利用できるチャンクの種類 (Chunk Type) を以下にざっと書き並べてみる

Chunk Type 説明 必須
IHDR ヘッダ情報
PLTE パレット
IDAT イメージデータ
IEND 終端
tRNS 透過  
cHRM 色度と白色点  
gAMA イメージガンマ  
iCCP 埋め込みICCプロファイル  
sBIT 主要ビット  
sRGB 標準的なRGB色空間  
tEXt テキストデータ  
zTXt 圧縮テキストデータ  
iTXt 国際テキストデータ  
bKGD 背景色  
hIST 画像のヒストグラム  
pHYs ピクセル寸法  
sPLT 推奨パレット  
tIME 最終更新時刻  


これすべてに対応しようとすると、さすがに途中で心が折れそう..
今回は必須チャンクに分類されるもののうち、

  • IHDR(ヘッダ情報)
  • IDAT(イメージデータ)
  • IEND(終端)

の3つのみに対応することにしてみる。

 


IHDR (ヘッダ情報)

 

Length 4バイト
Chunk Type : "IHDR"  4バイト
Chunk Data 計 13バイト
 ・Width 4バイト
 ・Height 4バイト
 ・Bit Depth 1バイト
 ・Color Type 1バイト
 ・Compression Method 1バイト
 ・Filter Method 1バイト
 ・Interlace method 1バイト
CRC 4バイト


シグネチャを読み出した後、チャンクのかたまりの先頭に必ず現れるチャンク。
データ部は、以下の要素で構成される

 

1. Width (イメージの横幅)
2. Height(イメージの縦幅)

画像の縦横のピクセル数の値が それぞれ4バイト長で 収められる。

 

3. Bit Depth(ビット深度)

ピクセルの色要素「R」「 G」「 B」のそれぞれ、またはパレット番号 (今回は取り扱わない) が何ビット長で記録されているかを表す値が、ここに 1バイト長で収められる。

なお、後の Color Type の値によって、この場所に設定できる値が異なってくる

 

4. Color Type(カラータイプ)

PNGイメージのカラータイプを表す値が、ここに1バイト長で収められる。
ここに設定される値は、以下のビットフラグの組み合わせによって形成される

  • 1(001): パレット使用   (0なら不使用)
  • 2(010): カラー使用    (0ならグレースケール)
  • 4(100): αチャンネル使用  (0なら不使用)


ただし、このうち実際に使用することのできるフラグの組み合わせは、いくつかに限られている。使用が可能な Color Type と 対応する使用が可能な Bit Depth との一覧を以下に示す

 

Color Type Bit Depth 説明
0(000) 1, 2, 4, 8, 16 グレースケール
2(010) 8, 16 RGBカラー
3(011) 1, 2, 4, 8 インデックスカラー(要PLTEチャンク)
4(100) 8, 16 グレースケール + αチャンネル
6(110) 8, 16 RGBカラー + αチャンネル

 

5. Compression Method(圧縮方法)

画像データの圧縮のために、どのようなアルゴリズムを利用したかを表す値を、ここに 1バイト長で収める。「0」が設定されている場合、自身の画像データが、Deflate によって圧縮されたことを表す。

なお、 0以外の値は、現状扱われることがない。とりあえず今は「0を読み出せれば正しい」と覚えていれば問題ないはず

 

6. Filter Method(フィルタ方法)

圧縮前の画像データに対して、どのような事前処理を行ったかを表す値を、ここに 1バイト長で収める。「0」が設定されている場合、画像データに対して、圧縮前にフィルタリング処理 (後述) が施されることを表す。

なお、0以外の値は、現状扱われることがない。こちらもとりあえずは「0を読み出せれば正しい」と覚えておけば問題ないはず 

 

7. Interlace Method(インタレース)

画像データのピクセル要素の出現規則を表す値を、ここに 1バイト長で収める。
「0」ならインタレースなし、 「1」ならインタレースあり となる。

画像データにおける インタレース とは、画像データ中のピクセル要素を そのままの順で出現させるのではなく、飛び飛びで出現させるようにする手法のこと。

うち、インタレースありの PNGイメージは、以下の図に示す通りに処理される。

f:id:DarkCrowCorvus:20170120234812g:plain

これによる利点は、画像データを読み始めた早い段階で、おおざっぱな画像の全体像がわかるということ。初めにモザイク調で表示させ、読み込みが進み次第、徐々に鮮明になるように画像を表示させることができるようになる。


なお、今回は残念ながら 実装が面倒だったので インタレースに対応していない。
気が向いたらそのうち..

 


IDAT (イメージデータ)

 

Length 4バイト
Chunk Type : "IDAT"  4バイト
Chunk Data (画像データ) Length バイト
CRC 4バイト


実際に画像を構成するピクセル要素 または パレット番号 の連なりからなるデータが、このチャンクの中に収められる。

このとき、収められる画像データには、フィルタリング処理 (後述) と zlibによる圧縮が施される。zlibについては、前回の記事で紹介済み。

 

なお、このIDATチャンクは、ファイル中にいくつでも出現してかまわないことになっている。その場合、それらのIDATチャンクは必ず1か所に連続して出現する。

 


IEND (終端)

 

Length 4バイト
Chunk Type : "IEND"  4バイト
CRC 4バイト


チャンクのかたまりの末尾に、必ず現れるチャンク。
自身を読み出した地点がファイルが終わりであることを示す。

 

なお、IENDチャンクはデータ部を持たない。
Lengthには常に0に設定される。

  


PNGイメージのパース 

 

対応できるチャンクを IHDR, IDAT, IEND に限った場合、これから以下に示す手順で、PNGイメージから、画像を構成するピクセルデータを引っ張りだすことができる

  1. シグネチャ一致チェック
  2. チャンク読み出し
  3. IDATチャンクの zlib圧縮データを解凍
  4. 解凍したデータのフィルタリングを解く

 

1. シグネチャ一致チェック

ファイル先頭の 8バイト を読み出し、前述したシグネチャの並びと一致するかどうかをチェックする。

一致しなかった場合、そのファイルが PNGイメージではない、もしくは、ファイルを正しく読み出すことができないため、エラーとみなして、テキトウに処理を終了する。

 

2. チャンク読み出し 

以下を IEND チャンクが出現するまで繰り返す

  1.  チャンクのLength (4バイト) を読み出す
  2.  Chunk Typeの4文字 (4バイト) を読み出す
  3.  Lengthが 0 でなければ、そのバイト数分だけ Chunk Dataを読み出す
  4.  CRC (4バイト) を読み出す

 

くどいようではあるけれど、今回は IHDR, IDAT, IEND のチャンクのみに対応する。それ以外のチャンクに遭遇しても、中身を考慮せずそのまま読み飛ばすことにする。

2.1. IHDRチャンク読み出し 

シグネチャ並びの直後に出現。この場所に記録されている情報は、後に画像データを復元したり、ピクセル要素を抽出したりするために必要になる

なお、Color Typeが 「3」である場合、ファイル中に PLTEチャンクが出現し、画像データはパレット番号によって構成される。

対応チャンク 3つ縛りの制限下では、このフォーマットに対応することができない。今回に限っては、これをエラーとみなしてテキトウに処理を終了することにする。
実装はたぶん またそのうち...

 

2.2. IDATチャンクの読み出し 

前述した通り、圧縮された実画像データがここに格納されている。

なお、このチャンクが複数出現する場合は、チャンクが出現した順番にChunk Data部のデータを連結する

 

3. IDATチャンクのzlib圧縮データを解凍

IDATチャンクから得られた Chunk Data 部
またはそれら複数を結合したデータに対して、zlibによる解凍を行う。

 


フィルタリング処理


PNGファイルに収められる画像データは、zlibによって圧縮される前に、その圧縮効率を上げる目的で フィルタリング という事前処理が施される

PNGイメージをパースする際、zlib解凍を行った後 それを本来の画像データに戻すために、そのデータのフィルタリングを解く必要がある


現在、フィルタリングには、以下の 5種類 のアルゴリズムが利用されている

番号 フィルタ名 説明
0 None フィルタなし
1 Sub 隣接する左ピクセル色との差分
2 Up 隣接する上ピクセル色との差分
3 Average 左と上のピクセルの平均色との差分
4 Paeth 左、上、左上のピクセルのうち次回出現しそうな色との差分


これらの フィルタリングアルゴリズムは、画像の各水平ラインごとに行われる

 

フィルタタイプ 0:None

該当する画像の水平ラインの先頭に 「0」を表す数値を 8ビット長で付加する
先頭に 8ビット 付加する以外には、水平ラインに対して特になにも行わない。

f:id:DarkCrowCorvus:20170209000242j:plain


ちなみに、ビット深度が 8 に満たないとき (BitDepth=1,2,4) 
各水平ラインの末端がバイト境界になっていなかった場合は、次に出現するバイト境界の地点までの間にパディングが詰められるみたい

次の水平ラインの先頭ビットは必ず、その直近のバイト境界の位置から始まる

f:id:DarkCrowCorvus:20170207233748j:plain

 

フィルタタイプ 1:Sub

該当する画像の水平ラインの先頭に「1」を表す数値を 8ビット長で付加する 。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、左隣のピクセルの値との差分値になる。

f:id:DarkCrowCorvus:20170209000256j:plain

なお、差の結果は 非負の 0~255(00~FF)の範囲に収まるよう丸められる。
 ※例えば差の結果が負数の場合 [-1, -2, -3] は [255, 254, 253] のような通りになる。


また先頭のピクセルについては、左隣に参照できるピクセルがないため、左隣のピクセル値 = 0 として扱う

 

ここまでを見たとおり、フィルタリング処理自身は、データを圧縮するような作用を持っていない。しかも各水平ラインの先頭に、フィルタを識別するための 8ビットを付与するため、このままでは むしろデータサイズを増やしてしまうだけのように見える。

ただしこのフィルタリング処理には、その後に続くDeflate の、圧縮効率を底上げするという機能がある。

実際には、Noneを除く 4種類 のフィルタリングを使って、PNGイメージ中の値に偏りや同じ値並びを出現させることを行う。

このようにデータを変換することで、Deflateによるハフマン符号化、およびLZ77符号化がうまく働く機会が増えるため、データをより小さく圧縮できるようになる。

f:id:DarkCrowCorvus:20170210084353j:plain

うち「フィルタタイプ 1:Sub」は、横方向にピクセル値の変化が小さい 水平ラインに対して効果を発揮する

 

ここで、フィルタリング処理は、必ず 8ビット単位 で行われるということに注意。
このルールは他のフィルタタイプにも共通する

ビット深度が16であるPNGイメージにおいては、上位8ビット、下位8ビットの2つに分割し、別々にフィルタリング処理を施す

ビット深度が8未満のPNGイメージにNone以外のフィルタタイプを適用する場合は、事前に8ビットに伸長されるらしい...? サンプルを見つけられなかったため、ちょっと確かではないのだけど..


なお、Subフィルタリングされたピクセルは、
ピクセル値 + 左隣のピクセル の 256による剰余
によって元の値に復元できる

 

フィルタタイプ 2:Up

該当する画像の水平ラインの先頭に「2」を表す数値を 8ビット長で付加する 。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、真上のピクセルの値との差分値になる。f:id:DarkCrowCorvus:20170211232608j:plain

差の結果は 非負の 0~255(00~FF)の範囲に収まるよう丸められる。
このルールについても、差を扱うすべてのフィルタタイプに共通する


「フィルタタイプ 2:Up」は縦方向にピクセルの値の変化が小さい水平ラインに対して効果を発揮する

なお、Upフィルタリングされたピクセルは、
ピクセル値 + 真上のピクセル 256による剰余
によって元の値に復元できる

 

フィルタタイプ 3:Average

該当する画像の水平ラインの先頭に「3」を表す数値を 8ビット長で付加する 。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、左隣のピクセル値と、真上のピクセル値との平均をとった値との差分値になる。

 filtered value current - ((left + up) ÷ 2)

f:id:DarkCrowCorvus:20170212174810p:plain

差の結果は 非負の 0~255(00~FF)の範囲に収まるよう丸められる。
また先頭のピクセルについては、左隣に参照できるピクセルがないため、
左隣のピクセル値を 0 として扱い、平均を求める

平均の計算には整数徐算を利用する。
徐算の結果は、値の小さいほうの整数に丸められる(小数点以下切り捨て)


「フィルタタイプ 3:Average」は似たピクセル値が密集しているあたりの水平ラインに対して効果を発揮する

なお、Averageフィルタリングされたピクセルは、
ピクセル値 + 左隣と真上のピクセル値の平均 256による剰余
によって元の値に復元できる

 

フィルタタイプ 4:Paeth

該当する画像の水平ラインの先頭に「4」を表す数値を 8ビット長で付加する 。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、「Paeth」というアルゴリズムから得られる結果の値との差分値になる。

 filtered value = current -Paeth (left, up, upleft)

f:id:DarkCrowCorvus:20170212230424p:plain

差の結果は 非負の 0~255(00~FF)の範囲に収まるよう丸められる

 

Paethアルゴリズムは、左、上、左上の 3つの隣接するピクセル値から、「この位置に来るであろうピクセル値が、上記 3つのピクセル値のうち、どれと一番近くなりそうか」を予測するために利用される。Alan W. Paethさんが考案した

実際には以下のように求める

int PaethPredictor(int a, int b, int c)
{
    // ┏━━┳━━┓
    // ┃ c ┃ b ┃
    // ┣━━╋━━┫
    // ┃ a ┃ ?? ┃
    // ┗━━┻━━┛
    int p = a + b - c;

    // pa = |b - c|   横向きの値の変わり具合
    // pb = |a - c|   縦向きの値の変わり具合
    // pc = |b-c + a-c| ↑ふたつの合計
    int pa = abs(p - a);    
    int pb = abs(p - b);    
    int pc = abs(p - c);    

    // 横向きのほうがなだらかな値の変化 → 左
    if (pa <= pb && pa <= pc)
        return a;

    // 縦向きのほうがなだらかな値の変化 → 上
    if (pb <= pc)
        return b;
        
    // 縦横それぞれ正反対に値が変化するため中間色を選択 → 左上        
    return c;
}

なお、先頭のピクセルについては、左隣、左上の双方ともに参照できるピクセルがないため、それぞれピクセルの値を 0 として扱い 計算を行う


「フィルタタイプ 4:Paeth」はSub, Up, Averageのフィルタが有効ではない、ピクセル値がなだらかに並ぶ水平ラインに対して効果を発揮する

Paethフィルタリングされたピクセルは、
ピクセル値 + Paethアルゴリズムの結果の値 の 256による剰余
によって元の値に復元できる

 


サンプル 

 

ここまでのサンプルプログラム
VC2015でのみ動作確認済み。

 


参考にしたサイトさん

わかりやすい PNG の話 for Web

PNG を自力で読んで表示しよう その1 - 雑念日記

PNG ファイルフォーマット

PNG画像形式の概要 - ウェブで用いられる画像形式。

Portable Network Graphics (PNG) Specification (Second Edition)

PNG Specification: File Structure

Adam7 algorithm - Wikipedia

Convert, Edit, Or Compose Bitmap Images @ ImageMagick

PNG イメージを自力でパースしてみる ~4/6 非圧縮とzlib編~

ここまでのあらすじ

PNG イメージを自力でパースしてみる ~1/6 予備知識編~
PNG イメージを自力でパースしてみる ~2/6 Deflateの基本と固定ハフマン編~ 
PNG イメージを自力でパースしてみる ~3/6 カスタムハフマン編~


前回、前々回でDeflateの「固定ハフマン」と「カスタムハフマン」について触れた。ここでは残るブロックタイプの「非圧縮」と、Deflateを利用した圧縮フォーマットの「zlib」についてを紹介。

 

 


予備知識

※2017/02/14更新
追加で予備知識が必要かも

 

バイトオーダー

あたりまえとは存ずるものの...
1バイト (8ビット) 単体では、256種類までの数値を表現できる。それより広い範囲の数値を扱いたい場合には、一般的に連続した複数のバイト並びを利用することで、それを実現する

ここで、表現したい値を その連続したバイト並びに対して、
どのような順で収めるのかを、ルールとして定めたものを 
バイトオーダー または エンディアン と呼ぶ。


うち、実際によく利用されるのは以下の2つ

 

トルエンディアン

0x1234ABCD (305,441,741)
0x12 0x34 0xAB 0xCD
0xCD 0xAB 0x34 0x12

この並びの規則に従う場合、数値の下位バイトほど、先頭に出現するよう収められる。

Deflate 圧縮データ中に含まれる 多バイト長データは、このリトルエンディアンの並びの規則に従って出現する。

 

ビッグエンディアン

0x1234ABCD (305,441,741)
0x12 0x34 0xAB 0xCD
0x12 0x34 0xAB 0xCD

ネットワークバイトオーダー とも呼ばれる 。
この並びの規則に従う場合、数値の上位バイトほど、先頭に出現するよう収められる。

後に解説する zlibデータ中に含まれる多バイト長のデータは、このビッグエンディアンの並びの規則に従って出現する。

 


非圧縮 (BTYPE:00)

 

Deflate で定義されている圧縮タイプのうちの一つ。

 

このブロックに含まれるデータは圧縮されない。圧縮がむしろ逆効果になってしまうような 小さなデータに対しては、このタイプを使う。

 

非圧縮ブロック中には、以下の要素が順番に整列している。

 

  1. ヘッダー情報 (前々回の記事で紹介済み)
  2. パディング
  3. LEN:非圧縮データのバイト数 (2バイト)
  4. NLEN:LENの補数 (2バイト)
  5. 非圧縮データ (~65,535バイト?)

f:id:DarkCrowCorvus:20170108132252j:plain

 

2. パディング

メモリ上に展開されたとき、LENより以降のデータは、必ずバイト境界から始まるようになっている。パディングは、ヘッダー情報 (BFINAL、BTYPE) を読み出してから、それより後に現れる直近のバイト境界位置までの間に詰められる。

このデータにそれ以上の役割はないので、読み飛ばすか、読んでそのまま捨ててしまって構わない。

 

3. LEN:非圧縮データのバイト数

このブロックに含まれている非圧縮データの、バイト数を表す値がこの中に収められる。最大で 65,535 (0xffff) まで設定可能。
 
このデータは リトルエンディアン の並びで記録されている

4. NLEN:LENの補数

ここには LENの全ビットの0,1を反転した"補数"の値が設定される。


データが壊れていないかをチェックするためのものなんだろうか...?

  1. NLENの全ビットの0,1を反転させたものが LENと一致するか、
  2. LEN + NLEN = 0xffff になるか、

一応、このどちらかで、バイト長の値に誤りがないかをチェックできる。
同じく、リトルエンディアンの並びで格納される


このデータも リトルエンディアン の並びで記録されている

 

5. 非圧縮データ

ここに非圧縮状態のデータがそのまま収められる。データサイズはLENに設定されている通り。

 


zlib

 

 

PNGの圧縮データ部には、Deflateではなく、zlib というのを使っているそうだった。ここにきてようやく気付く。

 

実際にはそのzlibの中で、Deflateが扱われているので、「PNGはDeflate圧縮を使っている」といっても、あながち間違いではないとは思うのだけど...

 


構成

 

zlib 中には以下の要素が順番に整列している

 

  1. CMF (Compression Method and flags)
    1.1. CM:圧縮方式 (4ビット)
    1.2. CINFO :圧縮情報 (4ビット)

  2. FLG (FLaGs)
    2.1. FCHECK:CMF/FLGチェックビット (5ビット)
    2.2. FDICT: プリセット辞書の利用有無 (1ビット)
    2.3. FLEVEL: このデータの圧縮レベル (2ビット)

  3. DICTID:プリセット辞書識別ID (存在しない場合あり 4バイト)
  4. 圧縮データ
  5. Adler-32 (4バイト)

f:id:DarkCrowCorvus:20170109143630j:plain

なお、データ中の各々の要素はDeflateと同様、
アドレスの小さい順のビット番号の小さい順に並ぶ。


また、前述していたとおり、圧縮データ部を除く、zlib中の多バイトで表現される数値はすべて ビッグエンディアン の並びで記録されているということに注意すること。

 

1.1. CM:圧縮方式 
CM:Compression method

ここには、zlibがどの圧縮方式を利用しているかの情報が 4ビット長 で収められる。
CM = 8 だった場合、それがDeflate圧縮を利用したzlibであるということを示す。

なお、CM = 8 以外の値は、現状扱われていない。とりあえず今は「8を読み出せれば正しい」とだけ覚えておけば問題ないはず..

 

1.2. CINFO:圧縮情報
CINFO:Compression info

CM = 8 のとき、ここには Deflate 圧縮で使用したスライド窓のサイズを表す値が設定される。

実際にはスライド窓のサイズを n としたとき、 
log_2(n)-8 によって求まる値を、この 4ビット長 の中に収める。 

 

なお、ここに設定できる値は 0~7 の値のうちいずれかで、利用できるスライド窓のサイズは 最小で256バイト、最大で32,768バイトというのが決められている。

 

ちなみに、符号化時にどのサイズのスライド窓を利用したとしても、復号時には最大サイズ (32,768) のスライド窓が用意できれば 困ることはない。細かな実装が面倒なら CINFO ≤ 7 であるかだけをチェックすれば、後は考慮しなくてもかまわない。 

 

2.1. FCHECK:CMF/FLGチェックビット
FCHECK:Flag check bits?

1. CMF2. FRG を連結した 計16ビット長からなるデータの表す値が、31の倍数 になるよう、調節するために設定される。復号するとき、この結果が31の倍数にならない場合は、データが壊れていることを示唆する。


2.2. FDICT:プリセット辞書の利用有無
FDICT:Flag dictionaly?

このビットに「1」が設定されている場合は、プリセット辞書 (後述) を利用して解凍を行うべきであることを示す。またこれが「1」に設定されている場合は、後に 3. DICTID が出現する。


2.3. FLEVEL: このデータの圧縮レベル
FLEVEL:Flag level?

データの圧縮がどの程度の精度で行われたかを表す値が、2ビット長 で収められる。
CM = 8 の場合、以下のいずれかの値が設定される。

 

 

基本的に圧縮アルゴリズムは、圧縮が完了するまでの速さを重視すると圧縮率が落ち、逆に圧縮率を重視すると、圧縮が完了するまでに時間がかかる。

ここに設定される値は例えば、あるzlibのデータの圧縮率を上げるために、そのデータへの再圧縮を試みたいとき、それの結果、圧縮率が上がるかどうかを評価するための指標となる。

ちなみに データを解凍する上でこのデータは役に立たないため、読み飛ばしてしまっても構わない。

 

3. DICTID:プリセット辞書識別ID
DICTID:Dictionaly identifier

前述の FDICT に「1」が設定されている場合に限り、4バイトの長さで出現する。

ここには、プリセット辞書 (後述) に対してAdler-32 (後述) を施した結果、得られた値が設定される。解凍するプログラムはこれを見て、圧縮に使われたプリセット辞書を、自身が持っているかをチェックする。

 

4. 圧縮データ

CM = 8 であるとき、ここには Deflate 圧縮されたデータが収められる。解凍方法は、これまでの記事で紹介してきた通りだ。

 


プリセット辞書

 

LZ77 はその仕様により、圧縮のはじめはスライド窓の中身が空の状態である。そのため通常は、圧縮元のデータが小さかったり、または大きくても、はじめのほうに出現する羅列の圧縮には、あまり期待ができない。


しかし、特定のアプリケーションにおいて、どのような羅列が出現しやすいか 事前にわかっていたならば、あらかじめその羅列をスライド窓にセットしておけば、それらのデータを圧縮できる機会が生まれ、結果的に全体的なデータサイズを減らすことができそうだ。

 

この通り、圧縮前に事前にスライド窓へ渡されるこの羅列のことを プリセット辞書 (Preset dictionary) と呼ぶ。

 

f:id:DarkCrowCorvus:20170108215754j:plain

 

zlibの圧縮プログラムと解凍プログラムはそれぞれ、自身のアプリケーションに合った任意の数のプリセット辞書を保有する。

圧縮時にプリセット辞書を使ったならば、FDICTに「1」を設定し、DICTIDに使ったプリセット辞書を識別するためのIDを設定する。通常ここには、プリセット辞書に対して、後述のAdler-32を施した結果の値を使用する。

解凍時には、FDICTを見て「1」であるならば、後に現れるDICTIDから、使われたプリセット辞書を特定し、そのプリセット辞書を使って解凍を行う。

 


Adler-32

 

任意のデータ列を 「数値の並び」 であるとみなして これの和を求め、結果をデータ列の末尾などに付与する。そのデータを受け取った側では同じ通り、データ列から和を求め、付与されていた和の値と一致するかをチェックする

 

これによって受け取るまでの途中でデータが壊れたりしていないかを、簡易的にチェックすることができる。

この考え方をベースとしたアルゴリズム、またはそれにより求まるチェック用の値のことを チェックサム (check sum) と呼ぶ。Adler-32 はそのチェックサムアルゴリズムの一種。 Mark Adlerさんが考案した

 

Adler-32は 2つの和の値 s1(2バイト)s2(2バイト) からなる。
s1 は最初に「1」で初期化され、データ列の各値を先頭から順番に加算した結果を保持する。
s2 は最初に「0」で初期化され、s1にデータ列の値が加算されるたびに、そのs1の値を自身に加算した結果を保持する。

また双方ともに、加算されるたびに 65,521 との剰余によって上書きされ、計算の途中で桁あふれが起こらないようにされる。

 

結果的に求まる s1、s2を [s2, s1] の順番に連結することで、本来のAdler-32によるチェックサムが求まる。

 

zlibの解凍においては、4. 圧縮データ 部を使って、Adler-32 チェックサムを算出する。その直後に現れる、圧縮データに含まれる 5. Adler-32 のチェックサムと比較し、値が一致していれば、"圧縮データが壊れていない" ということを確認することができる。

 


サンプル 

 

ここまでのサンプルプログラム
VC2015でのみ動作確認済み。

 

残念ながらプリセット辞書には対応できてない。 

 


参考にしたサイトさん 

 

RFC 1950 ZLIB Compressed Data Format Specification version 3.3 日本語訳 - futomi's CGI Cafe

RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe

SWFバイナリ編集のススメ番外編 (zlib 伸張) 前編 | GREE Engineers' Blog

Improving compression with a preset DEFLATE dictionary

Adler-32 - Wikipedia

PNG イメージを自力でパースしてみる ~3/6 カスタムハフマン編~

ここまでのあらすじ

PNG イメージを自力でパースしてみる ~1/6 予備知識編~
PNG イメージを自力でパースしてみる ~2/6 Deflateの基本と固定ハフマン編~ 

 

ここでは Deflateの カスタムハフマン についてを解説

 

 


カスタムハフマン符号化 (BTYPE:10)


Deflate で定義されている圧縮タイプのうちの一つ

 

個人的に ここのブロックの圧縮ルールが結構ややこしかった。
まずはどんなふうに圧縮されているかを見てから 復号の解説を行いたいと思う 

 


圧縮

 

カスタムハフマンのブロックは、以下の手順で作成される (たぶん)

 

  1. Deflateの LZ77 でデータ圧縮
  2. カノニカル・ハフマン符号化
  3. 符号長表を符号化
  4. 配置

 

符号長表を符号化 とかいう パッと見なんかよくわからないことをしていらっしゃるけど、まずは一番上から 順を追って解説してみる

 


1. Deflateの LZ77 でデータ圧縮

 

Deflate仕様の LZ77 で元データを圧縮する。
実際の圧縮方法については、これのひとつ前の記事で解説した

 

この結果、"文字" または "一致した長さ" (それと終端符号) は 0 ~ 285  (+拡張ビット)
"距離" は 0 ~ 29  (+拡張ビット) のかたちになって出力される

 

f:id:DarkCrowCorvus:20170105224856j:plain

 


2. カノニカル・ハフマン符号化

 

  1. LZ77で置換された各値の出現回数を調べる
  2. 各値に対する 符号の長さを求め、符号長表を作成する
  3. 得られた符号長表から、カノニカル・ハフマンを使って符号表を作成する。
  4. 得られた符号表を使って、LZ77符号化されたデータをさらに符号化する

 

カノニカル・ハフマンについては、これのふたつ前の記事で解説した。これによって、圧縮後のデータに 符号長表 だけを収めれば、符号表と元データを間違いなく復元できる。

 

符号の長さを求めるときに ひとつ注意するべきことがある。Deflateのカスタムハフマンで扱うハフマン符号は、仕様により その符号長が 15 以下にならなければならない


一応、長さの制限されたハフマン符号を作成する方法が きちんとあるらしい。長くなるため こっちの記事で解説することにする
 

 

なお、文字/一致した長さの値 (0~285) の出現回数と、距離の値 (0~29) の出現回数の 2つは、それぞれ別々に統計され、それぞれ別々の符号表として作成される。

 

また、LZ77符号化されたデータは、その中に現れる値が 文字/一致した長さの値か、距離の値かによって、その都度2つの異なる符号表を使って符号化される。

 

f:id:DarkCrowCorvus:20170105224953j:plain

 


3. 符号長表を符号化

 

直前の手続きによって得られた 2つの符号長表は、表中の "符号長" を表す値の偏り具合によって、それ自体、一度ハフマン符号化される

 

まず、2つの符号長表は、値の昇順に連続して連なるリスト構造に展開されているものとする。このうち、本来出現しない値に対しては 符号長:0 が充てられる。

 

f:id:DarkCrowCorvus:20170106201614j:plain

 

符号長表中の 圧縮データ化される範囲は「可変」である。

文字/一致した長さの符号長表 の場合、利用されている一番大きな 一致した長さ の値に合わせて、0から 最小で256(257個)、最大で285(286個) までの範囲の符号長を対象とする。

 

距離の符号長表 については、最小で0のみ(1個)、最大で0~31(32個) までの範囲の符号長を対象とする。こちらも 利用されている 距離 の最大値によって、圧縮データ中に含める範囲が変化する。

 

この2つの表中の圧縮範囲に対しては、次の2つの圧縮が施される

 

3.1 ランレングス符号化

表中の符号長の値を連ねたとき、 同じ値が連続する箇所があれば、それを いくつ連続したか を表す数のデータに置き換えることで圧縮を行う。
このアプローチは通常、ランレングス符号化 と呼ばれる

 

Deflate仕様のランレングス符号化では、符号長表の圧縮範囲の値が連続する場所に対して、以下の通りに置き換えを行うものとしている

 

・ひとつ前に出現した値が 3 ~ 6 回繰り返される 16 ( 拡張ビット:2 )
・"0" が 3 ~10 回繰り返される 17 ( 拡張ビット:3 )
・"0" が 11 ~ 138 回繰り返される 18 ( 拡張ビット:7 )

 

f:id:DarkCrowCorvus:20170107163645j:plain

拡張ビットには、"どれだけ連続するか" を調整する値が設定され、
ベース値 + 拡張ビット によって本来の連続した長さを求められるようになっている

 

3.2 カノニカル・ハフマン符号化

ランレングス符号化が終わった2つの符号長表に対して、その表中の値の出現回数を調べ、符号長表を作成し、それから符号表を作成し、それから符号化を行う。

f:id:DarkCrowCorvus:20170107163725j:plain

 

値の出現回数は、表2つを合わせて集計される。

 

各値の出現回数が分かれば、次にその各値に対する符号長を求める。
ここでも求める符号長の、その長さに注意すること。LZ77符号化済みデータに対する符号長制限が 15以下 だったのに対し、こちらでは 7以下 になっていなければならない

 

得られた各値に対する符号長から 符号長表の符号長表 を作成すれば、あとはそれから、符号表を作成し、2つの符号長表を圧縮する。

 

f:id:DarkCrowCorvus:20170107163737j:plain

 

ここまでの手続きで、ひとまずカスタムハフマンブロックに含む 各データの符号化が完了する

 

4. 配置

 

最終的に カスタムハフマンブロック中には、以下の要素が順番に整列することになる

 

  1.  ヘッダー情報 (前回の記事で紹介済み)
  2.  HLIT:文字/一致長符号の個数 (5ビット)
  3.  HDIST:距離符号の個数 (5ビット)
  4.  HCLEN:符号長表の符号長表のサイズ (4ビット)
  5.  符号長表の符号長表
  6.  符号化された文字/一致長の符号長表
  7.  符号化された距離の符号長表
  8.  圧縮データ

 

2. HLIT:文字/一致長符号の個数
HLIT ...header literalの略?

ここには、文字/一致長の符号長表に含めた符号長の個数 (257 ~ 286) を表す値が設定される。実際には 個数 -257 した 0 ~ 29 までの範囲の値が 5ビット長の中に収められる

 

3. HDIST:距離符号の個数
HDIST ...header distanceの略? 

ここには、距離符号長表に含めた符号長の個数 (1 ~ 32) を表す値が設定される。実際には 個数 -1 した 0 ~ 31 までの範囲の値が 5ビット長の中に収められる

 

4. HCLEN:符号長表の符号長表のサイズ
HCLEN ...header code lengthの略?

ここには カスタムハフマンブロックに収められる 符号長表の符号長表に、符号長がいくつ含まれているか (~19) を表す値が設定される。実際には個数 -4 した 0 ~ 15 までの範囲の値が 4ビット長の中に収められる

 

5. 符号長表の符号長表

符号長表の符号長表 は、カスタムハフマンブロックに対して、以下のような変則的な並びになった状態で記録される。

 

16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15


各符号長値 (0~7) は、それぞれ3ビット長の中に収められる。
また、このうち本来出現しない値に対しては、符号長:0が充てられる


この並びの中に各符号長を収めた時、最後尾「15」の符号長が0で、なおかつそこから先頭方向に連続して0が続く場合、カスタムハフマンブロックに並びを収めるとき、その0が続く部分を省略することができる。

 

ただし省略できる符号長は15個まで。
並びの中の符号長の個数は 4未満にはならない

 

f:id:DarkCrowCorvus:20170107144210j:plain

 

この結果、並びの中に残った符号長の個数 -4 した値が、
前述の HCLEN に 実際に設定される数になる。

 

それ以降にようやく

6. 符号化された文字/一致長の符号長表
7. 符号化された距離の符号長表
8. 圧縮データ

のデータが順番に現れるようになっている

 


解凍

 

上で説明した構築の手順を逆にたどれば、カスタムハフマンブロックの解凍が行える

 

  1. ヘッダー情報を読み出す(前回の記事で紹介済み) 

  2. HLIT (5ビット) 、HDIST (5ビット) 、HCLEN (4ビット) をそれぞれ読み出す。

  3. HCLEN + 4 によって 並びの中の符号長の数 がわかれば、後に続く符号長(3ビット) をその数だけ読み出し、本来の 符号長表の符号長表 を復元する

  4. 符号長表の符号長表から、符号長表の符号表 を作成する。

  5. HLIT + 257 によって、このブロックに含まれている 文字/一致長の符号長値の数 がわかれば、先ほど作成した符号長表の符号表を使って、その数だけの符号長を読み出して復号し、本来の 文字/一致長の符号長表 を復元する

  6. HDIST + 1 によって、このブロックに含まれている 距離の符号長値の数 がわかれば、同じく符号長表の符号表を使って、その数だけの符号長を読み出して復号し、本来の距離の符号長表 を復元する

  7. 復元した2つの符号長表から 文字/一致長の符号表 と、距離の符号表 をそれぞれ作成する

  8. 作成した2つの符号表を使って、残りの圧縮データを読み出して復号する

 

なお、HLIT、HDIST、HCLEN、符号長表の符号長表、拡張ビットは "値のデータ" なので、読み出すときには その値がそれぞれ、最下位ビットから順番にパックされたビット並びになっていることに注意すること。

 


サンプル 

 

ここまでのサンプルプログラム
VC2015でのみ動作確認済み。

 


参考にしたサイトさん 

 
RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe

カスタムハフマン符号 - 七誌の開発日記(旧)

デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。

 

package-merge algorithmを勉強してみる

最大符号長の制限されたハフマン符号表を生成する方法として package-merge algorithm っていうのがあるらしい。気が向いたのでちょっと調べてみる

 

今回は以下の資料さんを参考にさせていただいた

"A Fast and Space-Economical Algorithm for Length-Limited Coding Jyrki Katajainen, Alistair Moffat, Andrew Turpin".

 

自身の理解できた範囲でそれぞれ順番に紹介してみる

 

 


package-merge algorithm

 

前述のとおり package-merge algorithm は、最大符号長の制限されたハフマン符号表を生成するために利用できる

 

ただし、符号表中の符号を ある長さまでに制限するためには、
符号表を生成する元として使う、シンボルの種類の数に制限がかかる

 

たとえば最大符号長を「2」に制限して符号表を作成した場合、
その中で同時に定義ができる接頭符号の種類は、多くて4つまで

00 01 10 11

 

最大符号長を「3」に制限した場合では、
その中で同時に定義できる接頭符号の種類は、多くて8つまでになる

000 001 010 011 100 101 110 111

 

この通り、最大符号長を L と定義した時、
表現できる符号の種類の最大は、 2^L のように表すことができる

 

シンボルの種類の数を n とするとき、

  n ≤ 2^L

を満たさなければ、最大符号長を L に制限した中で、それぞれのシンボルに対して、きちんと接頭符号を割り当てることができない。

 

package-merge algorithm  は上の制約を満たす各々のシンボルに対して、指定した符号長以下になるよう符号を割り当てて、符号表を作成するのを手助けしてくれる アルゴリズムである。

 

生成手順

 

はじめに断っておくと、package-merge algorithm 単体ではハフマン符号を生成することはできない

 

package-merge algorithm が出力できるのは、各々のシンボルを符号化したときの 符号長 までにとどまる

 

そこから実際に符号を割り当てて、符号表を求めるには、 カノニカル・ハフマン符号化 を利用する。カノニカル・ハフマン符号化については、以前別の記事で紹介した

 

 

符号化対象のデータに含まれる、各々の文字を シンボルデータ中で各々の文字が出現する回数を シンボルの重み として扱い、

 

[シンボル, 重み] のペアからなるリストと、制限したい符号の長さ情報が与えられたとき、package-merge algorithmを使って符号表を生成する手順を以下に示す

 

f:id:DarkCrowCorvus:20161224172840j:plain

 

1. ステージの初期化

制限したい符号の長さの数だけのステージを用意し、シンボルのリストの内容物によってそれぞれ初期化する。

ここであらかじめ、一番上のステージのリストはシンボルの重みの昇順にソートしておく。

 

f:id:DarkCrowCorvus:20161224191534j:plain

 

2. パッケージマージ

一番上のステージにある要素を、先頭から順番に2つずつ選び出し、そのペアからなる パッケージ をそれぞれ作成する。

その後、作成したパッケージを一つ下のステージにマージする

 

f:id:DarkCrowCorvus:20161224191941j:plain

 

ここで パッケージ はペアとなる要素それぞれへの参照と、その2つの要素の重みの合計値を自身の重みとして持つ。なお、ペアを作れなかった要素に対しては何も行わず無視する

 

マージ後、そのステージの要素を昇順に並べ替える。

またその後、そのステージで2つずつのペアを作ったとき、ペアを組めず無視されるであろう要素があれば、あらかじめそのステージから除外しておく

 

f:id:DarkCrowCorvus:20161225003416j:plain

 

ここまでのパッケージマージの流れを、今度は2番目のステージから、その下の3番目のステージに対して行い、最終的に一番下のステージにたどり着くまでこれを繰り返す

 

f:id:DarkCrowCorvus:20161225021548j:plain

 

3. 符号長を抽出

最終的に、一番下のステージに出揃った各々の要素を一つずつピックアップし、各々の要素が持つシンボル、またはその要素が参照しているシンボルの数だけ該当のシンボルの符号長をインクリメントする

 

f:id:DarkCrowCorvus:20161225115930g:plain

 

各々のシンボルの符号長は、多くてステージの数までとなり、パッケージマージの過程で、無視され除外された回数の多いシンボルほど、最終的な符号長が小さくなるという仕組みになっている

 

4. 符号表を作成

後はカノニカル・ハフマン符号化の手順に従って、各々のシンボルの符号長から 符号表を作成する

 

  1. 符号長別にグループ分けした後、その中で文字番号の小さい順に並べかえる 
  2. 符号長が短く文字番号の小さなシンボルほど小さな符号になるよう符号を割り当てる

 

f:id:DarkCrowCorvus:20161225165246j:plain

 

これで、package-merge algorithm によって最大符号長の制限された符号表が完成する

 


遅延 package-merge

 

package-merge algorithm は 一番下のステージに出揃った要素をピックアップして、各々のシンボルの符号長を求める

 

この一番下に出揃う要素について、その数に着目すると、
ステージの数にかかわらず、必ず  2n - 2 だけになる。
このあたりなんかうまくそうできてるらしい

 

f:id:DarkCrowCorvus:20161225184410j:plain

 

これから察するに、最後のステージに対して、2n-2 回だけ要素の作成を要求して、その過程で必要になり次第、上のステージの要素を作成してパッケージを貰ってくる...というアルゴリズムが組めそうだ。

 

実際に必要になるまで上のステージの要素の作成を遅らせる様子から、
このアルゴリズムのことを、
遅延 package-merge (Lazy package-merge) と呼ぶことにする。

 

生成手順

各々のステージは それぞれ以下の情報を保有する

 

  • 要素1 (先読みツリー)
  • 要素2 (先読みツリー)
  • シンボルカウンタ 

 

このうち、2つの "要素" は 自身の一つ下のステージで、次にパッケージを作成する元として使われるであろう候補の要素を事前に知っておくために保有しておく

 

冒頭で紹介した資料さんによれば、
この要素のことを 先読みツリー (lookahead tree) と呼ぶそうだ

 

なお最下段のステージは、自身の下にパッケージを提供するステージが存在しないため、先読みツリーを持たなくても構わない。

 

"シンボルカウンタ" は自身のステージで、[シンボル,重み] のリストを いくつだけ読んだかの情報を覚えておくために、その数を保持する。 

 

遅延 package-mergeを使った符号表の生成手順を以下に示す

  

1. シンボルリストをソート

[シンボル,重み] のリストを、あらかじめ重みの昇順になるように並べ替えておく

 

2. ステージの初期化

一番下のステージを除いて、各ステージ上の先読みツリー2つを、重みの昇順に並んだ [シンボル,重み] リストの上二つの要素で初期化する。

また、シンボルカウンタには、リストを "2つ" 読み出したことを記録しておく

 

f:id:DarkCrowCorvus:20161227232710j:plain

 

3. 要素を作成

これから、最下段ステージに要素を作成する次の手順を、2n-2 回だけ繰り返す

 

まず、[シンボル,重み] のリストから次に読み出せる要素の重みと、自身の一つ上の先読みツリー2つの重みの合計のどちらが小さいかを比較する。

 

リストの要素の重みのほうが小さければ 3.1 の処理、そうではない場合、またはシンボルのリストから読み出せる要素がもうない場合は  3.2 の処理へ進む

 

f:id:DarkCrowCorvus:20161229200142j:plain

 

3.1 [シンボル,重み] リストの要素を追加

[シンボル,重み] のリストから読み出した要素を自身のステージに追加する。
その後、シンボルカウンタを1つ進める。

 

f:id:DarkCrowCorvus:20161229204603j:plain

 

なお、1番目、2番目に追加される要素は必ず、[シンボル,重み] のリストの1番目、2番目の要素になるため、2. ステージの初期化 で各ステージを初期化する際に、この要素2つをあらかじめ 最下段ステージに作成しておいてもかまわない。 

 

f:id:DarkCrowCorvus:20161229205426j:plain

 

3.2 先読みツリーのパッケージを追加

一つ上のステージの先読みツリー2つからパッケージを作成し、自身のステージへ追加する。 

 

f:id:DarkCrowCorvus:20161229213605j:plain

 

一つ上の先読みツリーからパッケージが作成されるたび、ここまでの 3.要素を作成 の手順を、今度は一つ上のステージに対して2回行うことで 先読みツリー2つを更新する。

 

この過程でさらに上のステージの先読みツリーからもパッケージが作られれば、そのステージでも同じ通り、新しい要素を作成する手順を2回行う。

 

それよりさらに上のステージでも同様、最終的に更新が必要な先読みツリーすべてに対して、新しい要素が補填されるまでこの処理は繰り返される

 

なお最上段のステージは、上にパッケージを貰ってこれるステージが存在しないため、常に [シンボル,重み] リストの まだ読んでいない新しい要素 2つによって先読みツリーを更新する

 

f:id:DarkCrowCorvus:20161230172854g:plain

 

最下段のステージに 2n-2 個の要素がそろえば、あとは通常の package-merge algorithm の時と同様の手順で、各シンボルの符号長を導出し、符号表を作成できる

 

利点

早いうちに最下段ステージに要素が作成されるというのが、このアルゴリズムの特徴になる。これによる利点は、メモリ空間の再利用ができるということ

 

符号長を導出する手続きは、なにも最下段のステージに要素がすべて出揃うのを待つ必要はない。 要素が一つ新しく作成されるたびに、その要素がもつシンボル、またはその要素が参照するシンボルの符号長を更新することができる。

 

符号長の更新後、その要素とそれが参照している要素は、もう扱われることがない。そのため、それらの要素を保持するために使ったメモリ空間は、これより以降に要素を作成するために使いまわすことができる。

 

f:id:DarkCrowCorvus:20170101011731j:plain

 

要素のプールを作成してこれを実現する場合、
資料さんによれば、プールの "空き要素" は nL つだけ必要とのこと。
(資料さんに載ってるここの証明がうまく理解できなかった。悔しい)

 

※ 2017/01/07追記
たまに nL で空き要素が足りないことがあるっぽい。一番下のサンプルプログラムのほうは、ステージの数を減らしたりして ひとまず対処してみてるけど、理由はよくわかってない

 

なお、 n はシンボルの数、 L は制限したい符号の長さを表す。

 


境界 package-merge

 

package-merge algorithm で 生成した各ステージ上の要素のうち、実際にシンボルの符号長を求めるために使われた要素に対して色を付けてみる。

 

f:id:DarkCrowCorvus:20170102163345j:plain

 

最下段のステージを除いて、それより上にある各ステージはともに、ある要素を境にして、実際に符号長の導出のために使われた要素(左側) と使われなかった要素(右側)に分かれるのがわかる。

 

この色のついた左側にある要素を、以降は "アクティブな要素" と呼んで扱うことにする

 

さらにこのアクティブな要素のうち、シンボル単体からなる要素 (パッケージではない要素) に着目し、その数を数えてみる

 

f:id:DarkCrowCorvus:20170102163357j:plain

 

シンボル単体からなる要素は、各ステージともに、その重みの小さい順にもれなく出現している

 

そのため、アクティブなシンボル単体の要素の数が、その中で  であるとするならば、そこには重みの一番小さなシンボルと、2番目に小さなシンボルの 2つ が必ず現れる

 

アクティブなシンボル単体の要素の出現回数を c と定義するならば、重みの昇順に並んだ 1~ c 番目までのシンボル単体からなる要素が、そこには出現することになる

 

この通り、アクティブなシンボル単体の要素の出現回数だけを ステージごとに覚えておきさえすれば、後から実際に出現したシンボル単体の要素が何であるかを推測できる

 

出現回数から、実際に出現するシンボルが何であるかを割り出せれば、あとはそのシンボルの符号長をインクリメントする...という方法で同じ通り符号長の導出ができそうだ。

 

f:id:DarkCrowCorvus:20170103144355g:plain

 

アクティブな要素とアクティブでない要素との境界を ステージごとに形成し、それよりも左側に出現した シンボル単体の要素の数から、各シンボルの符号長を求めるこのアルゴリズム

境界 package-merge (Boundary package-merge) と呼ぶことにする。

 

生成手順

各々のステージは それぞれ以下の情報を保有する

 

  • 要素1 (先読みチェーン)
  • 要素2 (先読みチェーン)

 

また、各要素は以下の情報を保有する

 

  • 重み
  • シンボルカウンタ
  • 要素への参照

 

このうち "要素への参照" は、自身の要素が作成されたときに、一つ上のステージで、一番最後にパッケージを作成する元として使われていた要素を覚えておくために利用される。以降はこの参照を チェーン と呼ぶことにする

 

境界 package-mergeを使った符号表の生成手順を以下に示す

 

1. シンボルリストをソート

[シンボル,重み] のリストを、あらかじめ重みの昇順になるように並べ替えておく

 

2. ステージの初期化

一番下のステージを除いて、各ステージ上の先読みチェーン 2つを、重みの昇順に並んだ [シンボル,重み] リストの上二つの要素で初期化する。

 

うち、先読みチェーンの右側 (重みの大きいほう) の要素は、

  • シンボルカウンタ ⇒ 2
  • チェーン ⇒ なし  

の状態でそれぞれ設定しておく。

 

f:id:DarkCrowCorvus:20170103191631j:plain

 

なお、一番初めの先読みチェーンの左側 (重みの小さいほう) の要素については、重み以外の情報を扱うことがないため、重み以外はテキトウな設定にしておいて構わない。

 

3. 要素を作成

これから、最下段ステージに要素を作成する次の手順を、2n-2 回だけ繰り返す

 

[シンボル,重み] のリストから次に読み出せる要素の重みと、自身の一つ上の先読みチェーン2つの重みの合計のどちらが小さいかを比較する。

 

リストの要素の重みのほうが小さければ 3.1 の処理、そうではない場合、またはシンボルのリストから読み出せる要素がもうない場合は  3.2 の処理へ進む

 

3.1 [シンボル,重み] リストの要素を追加

[シンボル,重み] のリストから読み出した要素を自身のステージに追加する


要素のシンボルカウンタには、ここまでに同じステージ上で [シンボル,重み] のリストからシンボルを読んだ回数の値を設定する

要素のチェーンは、自身の一つ前の要素がチェーンを持っていれば、そのチェーンをそのまま引き継ぐ

 

f:id:DarkCrowCorvus:20170103191654j:plain

 

遅延 package-merge の時と同様、1番目、2番目に追加される要素は必ず、[シンボル,重み] のリストの1番目、2番目の要素になるため、2. ステージの初期化 で各ステージを初期化する際に、この要素2つをあらかじめ 最下段ステージに作成しておいてもかまわない。 

 

3.2 先読みチェーンのパッケージを追加

一つ上のステージの先読みチェーン2つからパッケージを作成し、自身のステージへ追加する。 

 

要素のシンボルカウンタは、自身の一つ前の要素のシンボルカウンタの値を引き継ぐ

要素のチェーンには、パッケージ作成元の先読みチェーン2つのうち、右側 (重みの大きいほう) の要素の参照を設定する。

 

f:id:DarkCrowCorvus:20170103191736j:plain

 

この後は、遅延 package-merge の時と同様。3.要素を作成 の手順を、更新が必要な先読みチェーンすべてに、新しい要素が補填されきれるまで繰り返す。

 

4. 符号長を抽出

最下段のステージに 2n-2 回、要素を作成する手続きを行ったあと、2n-2 番目に作成される要素が、最下段のステージの 境界の要素 になる。

 

また、その要素がチェーンを持っていれば、そのチェーン先の要素が 一段上のステージの境界の要素となり、それがまたチェーンを持っていれば、そのチェーン先の要素が さらに一段上のステージの境界の要素となる。

 

それぞれの境界の要素が持つ "シンボルカウンタ" には、自身を含めて 自身の左側に出現したシンボル単体の要素の数を保有するため、この数から 前述した方法で、各シンボルの符号長を求めることができる。

 

f:id:DarkCrowCorvus:20170103204520j:plain

 

各シンボルの符号長が求まれば、あとは package-merge algorithm と時と同様、カノニカル・ハフマン符号化の手順を利用して符号表を作成できる

 

利点

境界の要素 よりも左側にある各ステージ上の要素は、それが作成されても、以降扱われることはない。最下段ステージに 2n-2 の要素を作成する過程で、境界の要素が更新されるたびに、それよりも左側にある要素のメモリ空間は、ほかの要素を作成するために使いまわすことができる。

 

この通り、境界 package-merge でも 要素に使ったメモリ空間の再利用が行える。
遅延 package-merge との違いは、プールにあらかじめ確保しておくべき "空き要素" の数が L(L+1) であるということ。 遅延 package-mergeの nL よりも、その数が少なくなることを期待できる

 

※Deflateのカスタムハフマン符号 (シンボル数n=286, 制限符号長L=15) の場合を例とするならば、遅延 package-merge を利用したとき、最大で nL = 4,290 の空き要素が必要であるのに対し、境界パッケージマージを利用した時は、最大でも L(L+1) = 240 の空き要素だけ用意すれば事足りる。

 

遅延 package-merge のパッケージ要素が持つ要素への参照が2つであるのに対し、境界 package-merge の要素が持つ要素への参照 (チェーン) は1つだけ

 

これによって、要素の利用がピークになるとき、同時に生存していないといけない要素の 全体的な数を減らすことができるため、遅延 package-merge と比べて、はじめに準備しておくべき空き要素の数をその分だけ抑えられる

 


サンプル

 

 

ここまでのサンプルプログラム。VC2015でのみ動作確認済み。

 


参考にしたサイトさん

Package-merge algorithm - Wikipedia

"A Fast and Space-Economical Algorithm for Length-Limited Coding Jyrki Katajainen, Alistair Moffat, Andrew Turpin".

sfnt2woff-zopfli/katajainen.c at master · bramstein/sfnt2woff-zopfli · GitHub