ハフマン符号の非効率性の理論的証明とハフマン符号を超える非肥大化保証ASCII文字圧縮エンコーディング

他の圧縮エンコーディングが圧縮率が低かったり肥大化リスクがあったり辞書の共有が厄介だったりしたので非辞書式非肥大化保証ASCII文字圧縮エンコーディング(辞書の意味が多義的で扱いづらいがとりあえず辞書式のデメリットがないという意味で非辞書式と書いておく)を作ってみた。デフォルトで使ってた圧縮エンコーディングが一部の用途(KVS、RPC、IoT通信など)でデータサイズを意図せず数十％増加させてたという事態を避けるのが主な開発目的である。昨年のような革新的新アルゴリズムではないがデータベース、RPC、ログなどの値として一般的な単語、数値、識別子において現時点でASCIIコードの最高のハフマン符号実装と思われるHPACKを超える圧縮率の圧縮方式である。なおgzipなど通常の圧縮アルゴリズムは計算量と負荷が大きいため用途が異なりgzipは暗号通信が解読可能になる脆弱性もある。まずソースコードのメモをコピペ。

ASCIIコード用デルタエンコーディングアルゴリズム。
非辞書式圧縮文字エンコーディング。
定数計算量の操作のみで構成。
圧縮展開いずれも時間空間ともに線形計算量。
圧縮前よりデータサイズが増加しないことを保証。
ASCIIと完全に相互変換可能なため透過的に使用できる。

圧縮文字エンコーディングは転送または保存のために組み込み系などで使用される。
通常の圧縮アルゴリズムでは負荷が高く使用不能または肥大化する数百バイト以下の
文字列のデータサイズを平均20-30%、最大50%削減可能。
キャッシュやインメモリKVSの容量を5-10%以上拡大しRPCやIoTのトラフィックを
5-10%以上削減できる可能性がある(個別に専用のエンコーディングを適用すべき場合も多い)。
(NB-)IoTのパケットサイズは数十から数百バイト、最大512バイトのペイロード制限
がある場合もあり圧縮エンコーディングはこのレンジの文字列の圧縮に適合する。
SQL ServerではSCSUが使われている。
Protobufではsintが使われている。

他の圧縮エンコーディングとの比較

Delta ASCII:
ASCII互換。
最大50%圧縮。
非肥大化保証。
出現頻度の高い2文字を1byteに圧縮できるときのみ圧縮する。
文字ごとが望ましいが面倒なので簡易化。

ZSCII:
ASCII下位互換。
最大33%圧縮(1/3)？
ASCIIのサブセット(制御文字に制限)。
よくわからないが実装を見ると肥大化しそう。
セグメントIDとオフセットの組または連続のようだがこの方式はあまり
圧縮率が高くなかった。

Packed ASCII:
ASCII下位互換。
最大25%圧縮(1/4)。
ASCIIのサブセット(大文字＋数字＋記号)。

SCSU:
ASCII上位互換。
ASCII文字はUTF-8からは圧縮されない。

HPACK:
ASCII互換。
最大37.5%圧縮。
ハフマン符号の最も優れたASCIIコード用実装と思われるが16進数を超える
ランダム文字列以外DAより圧縮率が低い。

ANS/FSE:
理論上最適に近くともハフマン符号同様頻度分布が正しいことが前提なので同じく
単語やBase64など事前知識により部分ごとに最適な符号表を使用するほど効率的ではないと思われる。
そしてANS/FSEはそれに適したアルゴリズムではないように見える。
エンコーディングとしては状態の初期化コストも無視できないものとなる懸念がある。
また1文字など非常に短い文字列では大きく肥大化する懸念がある。
https://arxiv.org/abs/1311.2540
https://github.com/Cyan4973/FiniteStateEntropy
https://www.reddit.com/r/programming/comments/7uoqic/finite_state_entropy_made_easy/?rdt=38141

lz-string:
圧縮アルゴリズム。
ASCII上位互換。
圧縮率が非常に高いように見えるがUTF-16(全文字2バイト以上)としての圧縮率
であるためASCIIやバイナリとしては肥大化しており非効率。
数百文字以上では肥大化する以上に圧縮されるが入力に準じたサイズの辞書を
生成するため入力サイズが大きければ考慮が必要。
数文字程度の短い文字列の圧縮展開でも低速なため集中的な使用には適さない。

次に圧縮率の比較を行う。ワードは英単語使用頻度トップ5000をランダムに選択しハイフンで、テキストはZipf 1.0で選択し空白で接続している。サンプルは次の代表的なダミーテキストである。

On the other hand, we denounce with righteous indignation and dislike men who are so beguiled and demoralized by the charms of pleasure of the moment, so blinded by desire, that they cannot foresee the pain and trouble that are bound to ensue; and equal blame belongs to those who fail in their duty through weakness of will, which is the same as saying through shrinking from toil and pain. These cases are perfectly simple and easy to distinguish. In a free hour, when our power of choice is untrammelled and when nothing prevents our being able to do what we like best, every pleasure is to be welcomed and every pain avoided. But in certain circumstances and owing to the claims of duty or the obligations of business it will frequently occur that pleasures have to be repudiated and annoyances accepted. The wise man therefore always holds in these matters to this principle of selection: he rejects pleasures to secure other greater pleasures, or else he endures pains to avoid worse pains.

jsonはgoogle.comのhttpヘッダにある次のもの。基本的にURLのような断片化したテキストが少ないとDA、多いとHPACKの方が圧縮率が高くなるがHPACKは括弧により大きく肥大化するため基本的にjsonと相性が悪い。

{"group":"gws","max_age":2592000,"endpoints":[{"url":"https://csp.withgoogle.com/csp/report-to/gws/other"}]}

DA(Delta ASCII)は文字テーブルをセグメント化しセグメント内の出現頻度の高い組み合わせを圧縮しているが平均的にはより圧縮率の高い素朴なデルタエンコーディングもあるためこのシミュレーション結果と比較する。Hはヘッダー、Eはエスケープ、Sはシフトで続く数字はそのためのビット数である。HPACKはHPACKの辞書によるハフマン符号化である(このためヘッダとしての構造的圧縮とは異なる)。左の数値は減少したサイズの比率(1 - after / before)で右は圧縮アルゴリズムにおける圧縮率(before / after)である。ここではわかりやすく左を圧縮率とする。圧縮率がマイナスのものは肥大化している。

'Delta   comp. ratio random number', 0.422590625, 1.7318735082886383
'HPACK   comp. ratio random number', 0.27509062500000003, 1.3794827801751082
'SimH2E5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH3E5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH2S5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH3S5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH2S0 comp. ratio random number', 0.46875, 1.8823529411764706

'Delta   comp. ratio random hex', 0.304153125, 1.4370977810312076
'HPACK   comp. ratio random hex', 0.25192812499999995, 1.3367699460696876
'SimH2E5 comp. ratio random hex', 0.019862500000000005, 1.0202650138373444
'SimH3E5 comp. ratio random hex', -0.040043749999999934, 0.961498013905665
'SimH2S5 comp. ratio random hex', 0.14002812499999995, 1.1628287262301455
'SimH3S5 comp. ratio random hex', 0.14002812499999995, 1.1628287262301455
'SimH2S0 comp. ratio random hex', 0.18818437499999996, 1.2318067911048152

'Delta   comp. ratio random 36', 0.06517968750000003, 1.0697242952773345
'HPACK   comp. ratio random 36', 0.25349999999999995, 1.3395847287340925
'SimH2E5 comp. ratio random 36', 0.05402343750000005, 1.0571086426890202
'SimH3E5 comp. ratio random 36', 0.0036562500000000275, 1.0036696672207759
'SimH2S5 comp. ratio random 36', 0.15463281250000005, 1.1829179258273494
'SimH3S5 comp. ratio random 36', 0.15463281250000005, 1.1829179258273494
'SimH2S0 comp. ratio random 36', 0.1783828125, 1.2171118316582197

'Delta   comp. ratio random 64', 0.17917968750000002, 1.2182934373958978
'HPACK   comp. ratio random 64', 0.188125, 1.2317167051578137
'SimH2E5 comp. ratio random 64', -0.17171874999999992, 0.8534471262835045
'SimH3E5 comp. ratio random 64', -0.25217187499999993, 0.7986124109359987
'SimH2S5 comp. ratio random 64', -0.010890625000000043, 0.9892267029383125
'SimH3S5 comp. ratio random 64', -0.010890625000000043, 0.9892267029383125
'SimH2S0 comp. ratio random 64', 0.09820312499999995, 1.1088971671142684

'Delta   comp. ratio word 3-6', 0.2918974981659963, 1.412224921406116
'HPACK   comp. ratio word 3-6', 0.21294680124459286, 1.2705621444412303
'SimH2E5 comp. ratio word 3-6', 0.2741392830942805, 1.3776747752143306
'SimH3E5 comp. ratio word 3-6', 0.2741139864916142, 1.377626764244642
'SimH2S5 comp. ratio word 3-6', 0.2740128000809491, 1.3774347538241751
'SimH3S5 comp. ratio word 3-6', 0.2740128000809491, 1.3774347538241751
'SimH2S0 comp. ratio word 3-6', 0.14601199058966385, 1.1709766284546343

'Delta   comp. ratio word 5-10', 0.3177409624576546, 1.4657189498027479
'HPACK   comp. ratio word 5-10', 0.2369947561371757, 1.3106069821189636
'SimH2E5 comp. ratio word 5-10', 0.28957260197688983, 1.4076033705663336
'SimH3E5 comp. ratio word 5-10', 0.28955713335498945, 1.4075727225222088
'SimH2S5 comp. ratio word 5-10', 0.2894333843797856, 1.4073275862068966
'SimH3S5 comp. ratio word 5-10', 0.2894333843797856, 1.4073275862068966
'SimH2S0 comp. ratio word 5-10', 0.22670812257335993, 1.2931727710987977

'Delta   comp. ratio word 1', 0.32395864291188936, 1.479199444701527
'HPACK   comp. ratio word 1', 0.2422142622514899, 1.3196342319283325
'SimH2E5 comp. ratio word 1', 0.3017002706042452, 1.4320498174405842
'SimH3E5 comp. ratio word 1', 0.3017002706042452, 1.4320498174405842
'SimH2S5 comp. ratio word 1', 0.3012935821432482, 1.4312162797465804
'SimH3S5 comp. ratio word 1', 0.3012935821432482, 1.4312162797465804
'SimH2S0 comp. ratio word 1', 0.2352223490951182, 1.3075695907389606

'Delta   comp. ratio word 2', 0.2984751349197725, 1.4254662233328514
'HPACK   comp. ratio word 2', 0.2732514759679815, 1.375991786611379
'SimH2E5 comp. ratio word 2', 0.3424173276830019, 1.5207213360359566
'SimH3E5 comp. ratio word 2', 0.34238835162447023, 1.5206543291473893
'SimH2S5 comp. ratio word 2', 0.2520337571081893, 1.3369587324339245
'SimH3S5 comp. ratio word 2', 0.2520337571081893, 1.3369587324339245
'SimH2S0 comp. ratio word 2', 0.3073345648158209, 1.4436984281366674

'Delta   comp. ratio word 4', 0.3330567982133731, 1.4993780539649715
'HPACK   comp. ratio word 4', 0.28805858344009694, 1.4046099534874574
'SimH2E5 comp. ratio word 4', 0.35931713327592607, 1.560834621835884
'SimH3E5 comp. ratio word 4', 0.3592751279412485, 1.5607322949503117
'SimH2S5 comp. ratio word 4', 0.22777392728876567, 1.2949575718015667
'SimH3S5 comp. ratio word 4', 0.22777392728876567, 1.2949575718015667
'SimH2S0 comp. ratio word 4', 0.3419794313877863, 1.519709333872392

'Delta   comp. ratio word 6', 0.3441845670148005, 1.524819255088448
'HPACK   comp. ratio word 6', 0.2926721326212379, 1.4137715281964383
'SimH2E5 comp. ratio word 6', 0.3644755979780424, 1.5735037031126458
'SimH3E5 comp. ratio word 6', 0.3644087525960211, 1.5733382171079593
'SimH2S5 comp. ratio word 6', 0.22031315908970417, 1.282566214446412
'SimH3S5 comp. ratio word 6', 0.22031315908970417, 1.282566214446412
'SimH2S0 comp. ratio word 6', 0.353072697810468, 1.5457687387987644

'Delta   comp. ratio word 8', 0.34956916567772556, 1.5374424877042678
'HPACK   comp. ratio word 8', 0.2947749514128958, 1.417987069522655
'SimH2E5 comp. ratio word 8', 0.3670570833978295, 1.579921306913905
'SimH3E5 comp. ratio word 8', 0.3670072063705003, 1.5797968161155957
'SimH2S5 comp. ratio word 8', 0.21643878024869723, 1.2762244669502574
'SimH3S5 comp. ratio word 8', 0.21643878024869723, 1.2762244669502574
'SimH2S0 comp. ratio word 8', 0.3583647214626008, 1.558517795778763

'Delta   comp. ratio word 1 upper', 0.2063318265004458, 1.2599724083563264
'HPACK   comp. ratio word 1 upper', 0.0559196633870892, 1.0592318907813638
'SimH2E5 comp. ratio word 1 upper', 0.17357776352630183, 1.2100352046030964
'SimH3E5 comp. ratio word 1 upper', 0.1453285573508939, 1.170040263543192
'SimH2S5 comp. ratio word 1 upper', 0.20617540786160082, 1.2597241379310344
'SimH3S5 comp. ratio word 1 upper', 0.20617540786160082, 1.2597241379310344
'SimH2S0 comp. ratio word 1 upper', 0.17534529414525035, 1.2126287437643444

'Delta   comp. ratio word 1 camel', 0.2663183744975052, 1.3629890203603028
'HPACK   comp. ratio word 1 camel', 0.21825092678043512, 1.279182840449798
'SimH2E5 comp. ratio word 1 camel', 0.026825796561918303, 1.0275652565256526
'SimH3E5 comp. ratio word 1 camel', -0.010949304719150232, 0.9891692840896783
'SimH2S5 comp. ratio word 1 camel', 0.1149989832788475, 1.129942204704926
'SimH3S5 comp. ratio word 1 camel', 0.1149989832788475, 1.129942204704926
'SimH2S0 comp. ratio word 1 camel', 0.12571366003973028, 1.143790031130354

'Delta   comp. ratio text 100', 0.35245982450951396, 1.544305724725944
'HPACK   comp. ratio text 100', 0.2929113674455289, 1.414249860568879
'SimH2E5 comp. ratio text 100', 0.3682342502218279, 1.5828651685393258
'SimH3E5 comp. ratio text 100', 0.36793847973972194, 1.582124473561067
'SimH2S5 comp. ratio text 100', 0.3692201518288475, 1.5853391684901532
'SimH3S5 comp. ratio text 100', 0.3692201518288475, 1.5853391684901532
'SimH2S0 comp. ratio text 100', 0.3615301192940944, 1.5662445954292774

'Delta   comp. ratio text 500', 0.35289073250503555, 1.5453340729783038
'HPACK   comp. ratio text 500', 0.2964122609337295, 1.4212868480725624
'SimH2E5 comp. ratio text 500', 0.3719960911792274, 1.5923467767545252
'SimH3E5 comp. ratio text 500', 0.37159723191671823, 1.591336083782926
'SimH2S5 comp. ratio text 500', 0.3724148934048621, 1.5934093870157933
'SimH3S5 comp. ratio text 500', 0.3724148934048621, 1.5934093870157933
'SimH2S0 comp. ratio text 500', 0.3686855593004008, 1.5839967146828406

'Delta   comp. ratio text 1000', 0.35317733768762916, 1.5460188058733615
'HPACK   comp. ratio text 1000', 0.29711078487181797, 1.422699308051889
'SimH2E5 comp. ratio text 1000', 0.3723522185936423, 1.5932502744761086
'SimH3E5 comp. ratio text 1000', 0.37209255874804004, 1.5925914144386302
'SimH2S5 comp. ratio text 1000', 0.37293145978767817, 1.5947220054468139
'SimH3S5 comp. ratio text 1000', 0.37293145978767817, 1.5947220054468139
'SimH2S0 comp. ratio text 1000', 0.3689866275179515, 1.5847524689794885

'Delta   comp. ratio country', 0.30586832061068703, 1.4406488418448002
'HPACK   comp. ratio country', 0.23847805343511452, 1.3131597907464838
'SimH2E5 comp. ratio country', 0.05405534351145036, 1.0571442981792505
'SimH3E5 comp. ratio country', -0.002934160305343436, 0.9970744238042004
'SimH2S5 comp. ratio country', 0.13188215648854962, 1.151917343335669
'SimH3S5 comp. ratio country', 0.13188215648854962, 1.151917343335669
'SimH2S0 comp. ratio country', 0.130462786259542, 1.1500370360209597

'Delta   comp. ratio sample', 0.3544176706827309, 1.5489891135303266
'HPACK   comp. ratio sample', 0.29518072289156627, 1.4188034188034189
'SimH2E5 comp. ratio sample', 0.3644578313253012, 1.5734597156398105
'SimH3E5 comp. ratio sample', 0.3624497991967871, 1.568503937007874
'SimH2S5 comp. ratio sample', 0.3654618473895582, 1.5759493670886076
'SimH3S5 comp. ratio sample', 0.3654618473895582, 1.5759493670886076
'SimH2S0 comp. ratio sample', 0.35843373493975905, 1.5586854460093897

'Delta   comp. ratio json', 0.17592592592592593, 1.2134831460674158
'HPACK   comp. ratio json', 0.16666666666666663, 1.2
'SimH2E5 comp. ratio json', 0.15740740740740744, 1.1868131868131868
'SimH3E5 comp. ratio json', 0.12962962962962965, 1.148936170212766
'SimH2S5 comp. ratio json', 0.2129629629629629, 1.2705882352941176
'SimH3S5 comp. ratio json', 0.2129629629629629, 1.2705882352941176
'SimH2S0 comp. ratio json', 0.18518518518518523, 1.2272727272727273

見ての通りDAは特に数値と1語においてハフマン符号のHPACKより圧縮率が高くHEXの圧縮率も高い。これは主に通常の圧縮エンコーディングでは圧縮してもバイト単位で溢れたビットが1バイトに切り上げられてしまうのに対してDAが常にビットを溢れさせず圧縮するからである(文字列が長くなると素の圧縮率の高さが主となり上記の数値となる)。HPACKと違い大文字でも圧縮率が高いので大文字コマンドの圧縮にも優れている。その他でも16進数を超えるランダム文字列(以下ランダム文字列。識別子は一般的にHEXなので問題ない。トークンやセッションIDは一般的に64進数なので問題あるがKVS、RPC、IoT通信においてこれを含む用途の比率は小さいと思われる。32進数はマイナーだし未対応)以外すべてにおいてHPACKを超える圧縮率となっており値として使用される単純なASCII文字列の圧縮エンコーディングとして一般的に優れている(httpヘッダのように断片的で複雑な文字列が多いデータには向かない)。一方HPACKは一部の記号を多用すると2倍以上、制御文字では3倍以上に肥大化する可能性があり断片化によるものも含めランダム性のある文字列の比率が高い場合にDAより高圧縮率となる。HPACKはhttpヘッダ頻出文字に最適化したせいか疑似テキストでもサンプルテキストでも最も圧縮率が低いがDAも非常に最適化が不足している状態であるため偏りをなくしたとしてもハフマン符号よりDAの方が一般的に圧縮率が高くなる可能性が高い(大文字小文字数字の各文字列すべてでDAより圧縮率が高くなるよう短いハフマン符号を割り当てることは困難であり後述するように方式としては理論的に不可能である。また英数字62文字のみの符号化に必要な最小平均ビット数はぎりぎり6ビットでありこれらを踏まえるとHPACKの英数字のハフマン符号はすでに最適に近いと思われる。HPACKの最小ビット数である5ビット符号をすべて小文字に集めて頻度順に割り当て小文字のみおよび小文字主体で比較してもDAとの圧縮率の差は1/3-1/4程度しか縮まらないことからさらに最適化を進めても一般的な文字列の圧縮率でDAに追いつけるほどの向上は難しいだろう)。DAはノーリスクゆえデフォルトで使用できることを目的に作られているが単語、数値、識別子のような単純な文字列またはその組み合わせであれば多くの用途においてハフマン符号より優れた最適な圧縮エンコーディングとしてそのまま使い続けられるだろう(要するにずぼらエンコーディングということである。汎用エンコーディングなので特定領域に特化(ランレングスなど)または独自に符号化したもの(Protobufのフィールド番号など)には当然DAもハフマン符号も敵わない)。メモリフットプリントも約1KBと小さい。(その後改良によりすべての圧縮率が20%以上となり欠点のない万能の汎用圧縮エンコーディングとなった)

理論的観点から見ると汎用的な静的テーブルを使用するハフマン符号はランダム文字列も圧縮できるほど全体的かつ平均的に圧縮率を高めたことで反面最も圧縮頻度の高い単語、数値、識別子(HEX)などの部分的な圧縮率が低下していると考えられる(万能を追求しすぎて器用貧乏化した。そのうえ肥大化リスクもあるので逆に汎用エンコーディングとしてはバランスが悪く使いにくいものとなった。ハフマン符号は個別の符号化では最適に近くとも個別の偏りの情報を持たない汎用的な非個別的符号化では個別の偏りに動的に適応するアルゴリズムより圧縮率が低くなりうることは自明である。DAは次の部分文字列と文字の2つの頻度情報を持つがハフマン符号は一般的かつ全体的な頻度情報しか持たないため基本的に部分文字列の規則性が高いほどDAに有利となる)。これは文字レベルの最適化と文字列レベルの最適化の違いと考えられハフマン符号は文字レベルの圧縮エンコーディング、DAは文字列レベルの圧縮エンコーディングと言える。上記圧縮率の比較は規則性の高い部分文字列の多い文字列の圧縮には文字列レベルのエンコーディングの方が文字レベルのエンコーディングより適していることを示している。DAが最終的に単語や数値等の部分文字列の多い文字列においてもハフマン符号の圧縮率を超えられなかったとしても部分文字列によってはランレングスや独自符号などハフマン符号より優れた圧縮方式が存在することから部分文字列ごとに最適な圧縮方式を適用し全体として複数の圧縮方式を組み合わせる複合方式の圧縮率がハフマン符号より高くなりうることは自明である。DAはこれを可能にする効率的な合成方法を開発したものでもある。複合方式は少なくとも大文字小文字の各文字列両方の圧縮において非常に短い文字列を除いてハフマン符号より理論的に優れていることを容易に証明できる。すべての大文字小文字に5ビットの符号を割り当てることは単一の符号表しか持たないハフマン符号では不可能だが複数の符号表を複合できる複合方式では容易である。符号表が2つあれば符号表自体が1ビットの情報となるため符号のビット数を平均1ビット削減できる。この差は文字数に比例して拡大することはあっても縮小することはない。従ってこの場合に単一の静的テーブルを使用するハフマン符号より複合方式の方が効率的で圧縮率が高いことが理論的に証明される。程度の差はあれど識別可能なすべての規則的文字列に同じことが当てはまり理想的なハフマン符号であってもこの理論的非効率性を免れることはない。これはハフマン符号に限らず算術符号や範囲符号においても同じである。なお文字列内での符号表の変更はヘッダや文字数などのオーバーヘッドなしで可能である。

ここまで読めば複合方式のハフマン符号の圧縮率を知りたいと思っただろう。これはヘッダや文字数などのオーバーヘッドなしで合成できることもあり確かにDAとHPACKより圧縮率が高いことも多い。次は圧縮率の完全な比較である。

'Huffman comp. ratio random number', 0.46875, 1.8823529411764706
'Delta   comp. ratio random number', 0.422590625, 1.7318735082886383
'HPACK   comp. ratio random number', 0.27509062500000003, 1.3794827801751082
'SimH2E5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH3E5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH2S5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH3S5 comp. ratio random number', 0.46875, 1.8823529411764706
'SimH2S0 comp. ratio random number', 0.46875, 1.8823529411764706

'Huffman comp. ratio random hex', 0.421784375, 1.7294586254046662
'Delta   comp. ratio random hex', 0.304153125, 1.4370977810312076
'HPACK   comp. ratio random hex', 0.25192812499999995, 1.3367699460696876
'SimH2E5 comp. ratio random hex', 0.019862500000000005, 1.0202650138373444
'SimH3E5 comp. ratio random hex', -0.040043749999999934, 0.961498013905665
'SimH2S5 comp. ratio random hex', 0.14002812499999995, 1.1628287262301455
'SimH3S5 comp. ratio random hex', 0.14002812499999995, 1.1628287262301455
'SimH2S0 comp. ratio random hex', 0.18818437499999996, 1.2318067911048152

'Huffman comp. ratio random 36', 0.09043749999999995, 1.0994296708582423
'Delta   comp. ratio random 36', 0.06517968750000003, 1.0697242952773345
'HPACK   comp. ratio random 36', 0.25349999999999995, 1.3395847287340925
'SimH2E5 comp. ratio random 36', 0.05402343750000005, 1.0571086426890202
'SimH3E5 comp. ratio random 36', 0.0036562500000000275, 1.0036696672207759
'SimH2S5 comp. ratio random 36', 0.15463281250000005, 1.1829179258273494
'SimH3S5 comp. ratio random 36', 0.15463281250000005, 1.1829179258273494
'SimH2S0 comp. ratio random 36', 0.1783828125, 1.2171118316582197

'Huffman comp. ratio random 64', 0.22778906249999997, 1.2949829527634733
'Delta   comp. ratio random 64', 0.17917968750000002, 1.2182934373958978
'HPACK   comp. ratio random 64', 0.188125, 1.2317167051578137
'SimH2E5 comp. ratio random 64', -0.17171874999999992, 0.8534471262835045
'SimH3E5 comp. ratio random 64', -0.25217187499999993, 0.7986124109359987
'SimH2S5 comp. ratio random 64', -0.010890625000000043, 0.9892267029383125
'SimH3S5 comp. ratio random 64', -0.010890625000000043, 0.9892267029383125
'SimH2S0 comp. ratio random 64', 0.09820312499999995, 1.1088971671142684

'Huffman comp. ratio word 3-6', 0.27659305355290786, 1.3823477987201456
'Delta   comp. ratio word 3-6', 0.2918974981659963, 1.412224921406116
'HPACK   comp. ratio word 3-6', 0.21294680124459286, 1.2705621444412303
'SimH2E5 comp. ratio word 3-6', 0.2741392830942805, 1.3776747752143306
'SimH3E5 comp. ratio word 3-6', 0.2741139864916142, 1.377626764244642
'SimH2S5 comp. ratio word 3-6', 0.2740128000809491, 1.3774347538241751
'SimH3S5 comp. ratio word 3-6', 0.2740128000809491, 1.3774347538241751
'SimH2S0 comp. ratio word 3-6', 0.14601199058966385, 1.1709766284546343

'Huffman comp. ratio word 5-10', 0.2896344764644918, 1.4077259760904122
'Delta   comp. ratio word 5-10', 0.3177409624576546, 1.4657189498027479
'HPACK   comp. ratio word 5-10', 0.2369947561371757, 1.3106069821189636
'SimH2E5 comp. ratio word 5-10', 0.28957260197688983, 1.4076033705663336
'SimH3E5 comp. ratio word 5-10', 0.28955713335498945, 1.4075727225222088
'SimH2S5 comp. ratio word 5-10', 0.2894333843797856, 1.4073275862068966
'SimH3S5 comp. ratio word 5-10', 0.2894333843797856, 1.4073275862068966
'SimH2S0 comp. ratio word 5-10', 0.22670812257335993, 1.2931727710987977

'Huffman comp. ratio word 1', 0.3017784799236677, 1.4322102244724226
'Delta   comp. ratio word 1', 0.32395864291188936, 1.479199444701527
'HPACK   comp. ratio word 1', 0.2422142622514899, 1.3196342319283325
'SimH2E5 comp. ratio word 1', 0.3017002706042452, 1.4320498174405842
'SimH3E5 comp. ratio word 1', 0.3017002706042452, 1.4320498174405842
'SimH2S5 comp. ratio word 1', 0.3012935821432482, 1.4312162797465804
'SimH3S5 comp. ratio word 1', 0.3012935821432482, 1.4312162797465804
'SimH2S0 comp. ratio word 1', 0.2352223490951182, 1.3075695907389606

'Huffman comp. ratio word 2', 0.340729472273534, 1.5168280060213826
'Delta   comp. ratio word 2', 0.2984751349197725, 1.4254662233328514
'HPACK   comp. ratio word 2', 0.2732514759679815, 1.375991786611379
'SimH2E5 comp. ratio word 2', 0.3424173276830019, 1.5207213360359566
'SimH3E5 comp. ratio word 2', 0.34238835162447023, 1.5206543291473893
'SimH2S5 comp. ratio word 2', 0.2520337571081893, 1.3369587324339245
'SimH3S5 comp. ratio word 2', 0.2520337571081893, 1.3369587324339245
'SimH2S0 comp. ratio word 2', 0.3073345648158209, 1.4436984281366674

'Huffman comp. ratio word 4', 0.3570663474261231, 1.5553704429635438
'Delta   comp. ratio word 4', 0.3330567982133731, 1.4993780539649715
'HPACK   comp. ratio word 4', 0.28805858344009694, 1.4046099534874574
'SimH2E5 comp. ratio word 4', 0.35931713327592607, 1.560834621835884
'SimH3E5 comp. ratio word 4', 0.3592751279412485, 1.5607322949503117
'SimH2S5 comp. ratio word 4', 0.22777392728876567, 1.2949575718015667
'SimH3S5 comp. ratio word 4', 0.22777392728876567, 1.2949575718015667
'SimH2S0 comp. ratio word 4', 0.3419794313877863, 1.519709333872392

'Huffman comp. ratio word 6', 0.3620691642252736, 1.567568055846624
'Delta   comp. ratio word 6', 0.3441845670148005, 1.524819255088448
'HPACK   comp. ratio word 6', 0.2926721326212379, 1.4137715281964383
'SimH2E5 comp. ratio word 6', 0.3644755979780424, 1.5735037031126458
'SimH3E5 comp. ratio word 6', 0.3644087525960211, 1.5733382171079593
'SimH2S5 comp. ratio word 6', 0.22031315908970417, 1.282566214446412
'SimH3S5 comp. ratio word 6', 0.22031315908970417, 1.282566214446412
'SimH2S0 comp. ratio word 6', 0.353072697810468, 1.5457687387987644

'Huffman comp. ratio word 8', 0.3644927162341125, 1.5735460875825096
'Delta   comp. ratio word 8', 0.34956916567772556, 1.5374424877042678
'HPACK   comp. ratio word 8', 0.2947749514128958, 1.417987069522655
'SimH2E5 comp. ratio word 8', 0.3670570833978295, 1.579921306913905
'SimH3E5 comp. ratio word 8', 0.3670072063705003, 1.5797968161155957
'SimH2S5 comp. ratio word 8', 0.21643878024869723, 1.2762244669502574
'SimH3S5 comp. ratio word 8', 0.21643878024869723, 1.2762244669502574
'SimH2S0 comp. ratio word 8', 0.3583647214626008, 1.558517795778763

'Huffman comp. ratio word 1 upper', -0.006710359606450611, 0.9933343691733997
'Delta   comp. ratio word 1 upper', 0.2063318265004458, 1.2599724083563264
'HPACK   comp. ratio word 1 upper', 0.0559196633870892, 1.0592318907813638
'SimH2E5 comp. ratio word 1 upper', 0.17357776352630183, 1.2100352046030964
'SimH3E5 comp. ratio word 1 upper', 0.1453285573508939, 1.170040263543192
'SimH2S5 comp. ratio word 1 upper', 0.20617540786160082, 1.2597241379310344
'SimH3S5 comp. ratio word 1 upper', 0.20617540786160082, 1.2597241379310344
'SimH2S0 comp. ratio word 1 upper', 0.17534529414525035, 1.2126287437643444

'Huffman comp. ratio word 1 camel', 0.18318186795138514, 1.2242627345844503
'Delta   comp. ratio word 1 camel', 0.2663183744975052, 1.3629890203603028
'HPACK   comp. ratio word 1 camel', 0.21825092678043512, 1.279182840449798
'SimH2E5 comp. ratio word 1 camel', 0.026825796561918303, 1.0275652565256526
'SimH3E5 comp. ratio word 1 camel', -0.010949304719150232, 0.9891692840896783
'SimH2S5 comp. ratio word 1 camel', 0.1149989832788475, 1.129942204704926
'SimH3S5 comp. ratio word 1 camel', 0.1149989832788475, 1.129942204704926
'SimH2S0 comp. ratio word 1 camel', 0.12571366003973028, 1.143790031130354

'Huffman comp. ratio text 100', 0.36971310263235724, 1.5865790708587517
'Delta   comp. ratio text 100', 0.35245982450951396, 1.544305724725944
'HPACK   comp. ratio text 100', 0.2929113674455289, 1.414249860568879
'SimH2E5 comp. ratio text 100', 0.3682342502218279, 1.5828651685393258
'SimH3E5 comp. ratio text 100', 0.36793847973972194, 1.582124473561067
'SimH2S5 comp. ratio text 100', 0.3692201518288475, 1.5853391684901532
'SimH3S5 comp. ratio text 100', 0.3692201518288475, 1.5853391684901532
'SimH2S0 comp. ratio text 100', 0.3615301192940944, 1.5662445954292774

'Huffman comp. ratio text 500', 0.3732724408192569, 1.5955896391522943
'Delta   comp. ratio text 500', 0.35289073250503555, 1.5453340729783038
'HPACK   comp. ratio text 500', 0.2964122609337295, 1.4212868480725624
'SimH2E5 comp. ratio text 500', 0.3719960911792274, 1.5923467767545252
'SimH3E5 comp. ratio text 500', 0.37159723191671823, 1.591336083782926
'SimH2S5 comp. ratio text 500', 0.3724148934048621, 1.5934093870157933
'SimH3S5 comp. ratio text 500', 0.3724148934048621, 1.5934093870157933
'SimH2S0 comp. ratio text 500', 0.3686855593004008, 1.5839967146828406

'Huffman comp. ratio text 1000', 0.3735506486502681, 1.5962982447749774
'Delta   comp. ratio text 1000', 0.35317733768762916, 1.5460188058733615
'HPACK   comp. ratio text 1000', 0.29711078487181797, 1.422699308051889
'SimH2E5 comp. ratio text 1000', 0.3723522185936423, 1.5932502744761086
'SimH3E5 comp. ratio text 1000', 0.37209255874804004, 1.5925914144386302
'SimH2S5 comp. ratio text 1000', 0.37293145978767817, 1.5947220054468139
'SimH3S5 comp. ratio text 1000', 0.37293145978767817, 1.5947220054468139
'SimH2S0 comp. ratio text 1000', 0.3689866275179515, 1.5847524689794885

'Huffman comp. ratio country', 0.208587786259542, 1.2635640221847118
'Delta   comp. ratio country', 0.30586832061068703, 1.4406488418448002
'HPACK   comp. ratio country', 0.23847805343511452, 1.3131597907464838
'SimH2E5 comp. ratio country', 0.05405534351145036, 1.0571442981792505
'SimH3E5 comp. ratio country', -0.002934160305343436, 0.9970744238042004
'SimH2S5 comp. ratio country', 0.13188215648854962, 1.151917343335669
'SimH3S5 comp. ratio country', 0.13188215648854962, 1.151917343335669
'SimH2S0 comp. ratio country', 0.130462786259542, 1.1500370360209597

'Huffman comp. ratio sample', 0.36345381526104414, 1.5709779179810726
'Delta   comp. ratio sample', 0.3544176706827309, 1.5489891135303266
'HPACK   comp. ratio sample', 0.29518072289156627, 1.4188034188034189
'SimH2E5 comp. ratio sample', 0.3644578313253012, 1.5734597156398105
'SimH3E5 comp. ratio sample', 0.3624497991967871, 1.568503937007874
'SimH2S5 comp. ratio sample', 0.3654618473895582, 1.5759493670886076
'SimH3S5 comp. ratio sample', 0.3654618473895582, 1.5759493670886076
'SimH2S0 comp. ratio sample', 0.35843373493975905, 1.5586854460093897

'Huffman comp. ratio json', 0.2314814814814815, 1.3012048192771084
'Delta   comp. ratio json', 0.17592592592592593, 1.2134831460674158
'HPACK   comp. ratio json', 0.16666666666666663, 1.2
'SimH2E5 comp. ratio json', 0.15740740740740744, 1.1868131868131868
'SimH3E5 comp. ratio json', 0.12962962962962965, 1.148936170212766
'SimH2S5 comp. ratio json', 0.2129629629629629, 1.2705882352941176
'SimH3S5 comp. ratio json', 0.2129629629629629, 1.2705882352941176
'SimH2S0 comp. ratio json', 0.18518518518518523, 1.2272727272727273

かなり大雑把な符号化しかしてないため圧縮率が低いものも適切に符号化すればいくつかは有意に改善できるだろう。しかし文字列レベルの圧縮エンコーディングに近づいたことでhttpヘッダに多い断片的文字列の圧縮に不利になったため最終的にHPACKの上位互換にもなるかは厳しいところである。DAに対してもハフマン符号の性質として短文字列の圧縮率が低い傾向が残り大文字小文字の圧縮率の両立も依然として難しい。そしてこのような一長一短に近い性能が複数のハフマン符号の使用により10−20倍に増加したフットプリント10-20KBに釣り合うかも微妙なところである。以上のことからDAは単純ながらバランスがよく一般にハフマン符号より優れた圧縮エンコーディングとして選択できる。ただし実装としては実験的に作っただけで安定性は全く保証していないので永続化や通信に使うならバージョンを固定して使う必要がある。揮発性データなら整合性を考慮しなくてよいので問題ない。

さて最後に前述の理論でHPACKの上位互換エンコーディングを作れることを実証しよう。大文字小文字トークンの3種類のハフマン符号表を複合するだけである。フットプリントもたぶん素朴に作っても3-4倍程度でそう大きくないし最適化すればたぶん一つの符号表の補正として残りの符号表を表現して2倍以下に抑えられる。サンプルはgoogle.comのhttpヘッダである。

'XPACK   comp. ratio request', 0.2533415841584158, 1.3393005138405436
'HPACK   comp. ratio request', 0.2471534653465347, 1.3282919612033537
'Delta   comp. ratio request', 0.19801980198019797, 1.2469135802469136
0, 'accept'
0, 'text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7'
0, 'accept-encoding'
0, 'gzip, deflate, br'
0, 'accept-language'
0, 'ja,en-US;q=0.9,en;q=0.8'
0, 'cache-control'
0, 'max-age=0'
0, 'dnt'
0, '1'
0, 'sec-ch-ua'
-1, '"Google Chrome";v="117", "Not;A=Brand";v="8", "Chromium";v="117"'
0, 'sec-ch-ua-arch'
0, '"x86"'
0, 'sec-ch-ua-bitness'
0, '"64"'
0, 'sec-ch-ua-full-version'
0, '"117.0.5938.89"'
0, 'sec-ch-ua-full-version-list'
-1, '"Google Chrome";v="117.0.5938.89", "Not;A=Brand";v="8.0.0.0", "Chromium";v="117.0.5938.89"'
0, 'sec-ch-ua-mobile'
0, '?0'
0, 'sec-ch-ua-model'
0, '""'
0, 'sec-ch-ua-platform'
0, '"Windows"'
0, 'sec-ch-ua-platform-version'
0, '"10.0.0"'
0, 'sec-ch-ua-wow64'
0, '?0'
0, 'sec-fetch-dest'
0, 'document'
0, 'sec-fetch-mode'
0, 'navigate'
0, 'sec-fetch-site'
0, 'same-origin'
0, 'sec-fetch-user'
0, '?1'
0, 'sec-gpc'
0, '1'
0, 'upgrade-insecure-requests'
0, '1'
0, 'user-agent'
-3, 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36'
0, 'x-client-data'
-45, 'CKa1yQEIj7bJAQiltskBCKmdygEI5tTKAQieicsBCJahywEIhaDNAQjwsc0BCNy9zQEI38TNAQi1xc0BCLnKzQEI1dDNAQiR0s0BCIrTzQEIwtTNAQjJ1s0BCPnA1BUYwcvMARi4v80B'

'XPACK   comp. ratio response', 0.25389886578449905, 1.340300870942201
'HPACK   comp. ratio response', 0.24155245746691867, 1.3184827478775605
'Delta   comp. ratio response', 0.20510396975425327, 1.258026159334126
0, 'accept-ch'
-2, 'Sec-CH-UA-Arch'
0, 'accept-ch'
-2, 'Sec-CH-UA-Bitness'
0, 'accept-ch'
-2, 'Sec-CH-UA-Full-Version'
0, 'accept-ch'
-2, 'Sec-CH-UA-Full-Version-List'
0, 'accept-ch'
-2, 'Sec-CH-UA-Model'
0, 'accept-ch'
-2, 'Sec-CH-UA-Platform'
0, 'accept-ch'
-2, 'Sec-CH-UA-Platform-Version'
0, 'accept-ch'
-1, 'Sec-CH-UA-WoW64'
0, 'alt-svc'
0, 'h3=":443"; ma=2592000,h3-29=":443"; ma=2592000'
0, 'cache-control'
0, 'private, max-age=0'
0, 'content-encoding'
0, 'br'
0, 'content-length'
0, '54188'
0, 'content-security-policy-report-only'
-2, 'object-src 'none';base-uri 'self';script-src 'nonce-OqX2tRcsQ42YI77KwfGMfg' 'strict-dynamic' 'report-sample' 'unsafe-eval' 'unsafe-inline' https'
0, 'http:;report-uri https://csp.withgoogle.com/csp/gws/other-hp'
0, 'content-type'
-1, 'text/html; charset=UTF-8'
0, 'cross-origin-opener-policy'
0, 'same-origin-allow-popups; report-to="gws"'
0, 'date'
-2, 'Wed, 22 Nov 2023 18:46:19 GMT'
0, 'expires'
0, '-1'
0, 'origin-trial'
-50, 'Ap+qNlnLzJDKSmEHjzM5ilaa908GuehlLqGb6ezME5lkhelj20qVzfv06zPmQ3LodoeujZuphAolrnhnPA8w4AIAAABfeyJvcmlnaW4iOiJodHRwczovL3d3dy5nb29nbGUuY29tOjQ0MyIsImZlYXR1cmUiOiJQZXJtaXNzaW9uc1BvbGljeVVubG9hZCIsImV4cGlyeSI6MTY4NTY2Mzk5OX0='
0, 'origin-trial'
-83, 'AvudrjMZqL7335p1KLV2lHo1kxdMeIN0dUI15d0CPz9dovVLCcXk8OAqjho1DX4s6NbHbA/AGobuGvcZv0drGgQAAAB9eyJvcmlnaW4iOiJodHRwczovL3d3dy5nb29nbGUuY29tOjQ0MyIsImZlYXR1cmUiOiJCYWNrRm9yd2FyZENhY2hlTm90UmVzdG9yZWRSZWFzb25zIiwiZXhwaXJ5IjoxNjkxNTM5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZX0='
0, 'p3p'
-2, 'CP="This is not a P3P policy! See g.co/p3phelp for more info."'
0, 'permissions-policy'
0, 'unload=()'
0, 'report-to'
0, '{"group":"gws","max_age":2592000,"endpoints":[{"url":"https://csp.withgoogle.com/csp/report-to/gws/other"}]}'   
0, 'server'
0, 'gws'
0, 'set-cookie'
0, '1P_JAR=2023-11-22-18; expires=Fri, 22-Dec-2023 18:46:19 GMT; path=/; domain=.google.com; Secure; SameSite=none' 
0, 'set-cookie'
-23, 'AEC=Ackid1QH6gVXB6Rn68KWRmRtOGSW1unAfUHYsxuZh3Zs8cyWCZdKy8vrhQ; expires=Mon, 20-May-2024 18:46:19 GMT; path=/; domain=.google.com; Secure; HttpOnly; SameSite=lax'
0, 'set-cookie'
-19, 'NID=511=fx_DiN-XffVTX7QHZe7UgP5GQd0mx2HY9B0Hz6MgzEpOESnD8DldcSLyj-U6AHIo8t4-dcOKelciAyOK2j03GJE1r_31zKvXnECnKWvOQiFPO6mtTTaCZWqtn2x8m5lnzbB_CyUA-HzXz-Vw3TXC0eeW_AQlcu8CybBgyxtW5Kc; expires=Thu, 23-May-2024 18:46:19 GMT; path=/; domain=.google.com; Secure; HttpOnly; SameSite=none'
0, 'strict-transport-security'
0, 'max-age=31536000'
0, 'x-frame-options'
-12, 'SAMEORIGIN'
0, 'x-xss-protection'
0, '0'

理論的に肥大化する可能性がないではないが全体として肥大化する可能性は低くこのサンプルではフィールド単位でもまったく肥大化していない。約1%圧縮率が向上しているがトークンの圧縮効果が大きいためログインしてトークンが増えるほどさらに圧縮率が上がる。セキュリティ上の必要性からトークンによりヘッダサイズが増大しがちな昨今の需要に応える圧縮エンコーディングである。

github.com