4
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

Organization

Base64以外のBase〇〇系紹介

バイナリーをASCIIコードで表現可能なテキストに変換するためのエンコーディングであるBase64はインターネットの様々な箇所で使われています。

ですが、Base64以外にもBase〇〇系は数多くあることを知っている人は少ないと思います。
この記事ではあまり陽の当たらないそれらのエンコーディングを紹介します。

Base32, Base16

最初に紹介するのはBase64と同じRFCに載っているBase32とBase16です。

Base64が6ビットごとにバイナリをテキストに変換していたのに対して、これらはそれぞれ5ビット、4ビットごとに変換を行います。
Base64は6ビットを1文字のASCII(8ビット)に変換するため、変換前後でデータ量は33%増加する一方でBase32は60%の増加、Base16は100%もの増加をします。
これらはBase64と比較した場合にデータ量の増加が激しいですが、必要とされる文字数を少なくできるという利点があります。
そのため、人間が読み書きするときに判別しづらくなる文字や、一部のシステムで特殊な扱いを受ける文字(UNIXパス区切り文字である/など)を除外することができます。
実際にRFC4648ではアルファベットのI, B, Oと区別しづらい1, 8, 0の数字が除外されています。

Base32はジオコーディングのアルゴリズムであるジオハッシュで使われています。
なお、このBase32はRFC版と文字列セットが多少異なる亜種です。
RFC版とは逆にI, B, Oを除外して替わりに1, 8, 0が使われています。
https://en.wikipedia.org/wiki/Geohash#Algorithm_and_example

Base58

次に紹介するのはBase58です。
エンコーディング後の文字列が58種類になるのが特徴で、ビットコインアドレスの表記に使われています。
https://en.bitcoin.it/wiki/Base58Check_encoding#Base58_symbol_chart

Base64と比較した場合、人間が判別しずらい文字が取り除かれているという利点があります。
例えば数字の0とアルファベット大文字のOは除外されアルファベット小文字のoが採用されています。
また、Base32と比較した場合には、効率がよいという利点があります。
Base58は元のバイナリと比較して37%しかデータ量が増加しません。

ただし、Base58の欠点もあります。
文字種の数が2の累乗にならないため、エンコーディング・でコーディング処理のオーバーヘッドが大きいです。
ビットコインの参考実装ではバイナリを整数に変換してから、愚直に商と剰余を求めています。
この処理はBase64やBase32のエンコーディングと比較するとかなり大きなオーバーヘッドになります。
Base64も商と剰余を求める必要がありますが、除数が2の累乗(64=2^6)でありビット演算を使うことで効率化できていた部分が効率化できなくなったためです。
多くのCPUではビット演算よりも除算のほうがより多くのクロックサイクルを要します。
https://www.agner.org/optimize/instruction_tables.pdf

また、参考実装でのこの部分にも注意が必要です。
エンコーディングしたいデータを一旦整数に変換するため、エンコーディングしたいデータに比例するワーキングメモリが必要になります。

x = convert_bytes_to_big_integer(hash_result)

ビットコインアドレスは200ビットしかないためこれらの欠点の影響は少ないですが、大容量のデータをBase58でエンコーディングするとこの欠点は顕著になります。

Base85

最後に紹介するのはBase85です。32ビットのバイナリデータを5文字のASCIIコード文字に変換します。このエンコーディングは他ほどしっかりとした標準化がされているわけではなく、様々な亜種が存在します。特に有名な亜種であるAscii85が最もよく使われているのはPDFです。

さて、なぜ85なんて中途半端な数が使われるのでしょうか。空白や改行などの、転送途中で損失する恐れがある文字を除くと、安全に使うことができるASCIIコードの印刷可能文字は95種類あります。そして、

\log_{95}{2^{32}} = 4.87

であるため、5文字の組で32ビットのデータを十分に表現できることが分かります。では、必要十分な文字種の数はいくつになるのでしょうか。それは以下の式を満たす最大の整数 $n$ であり、答えが85でした。

\log_{n}{2^{32}} < 5

Base85の利点はやはり効率の良さです。元のバイナリと比較して25%しかデータ量が増加しません。今まで紹介した中では最良の効率です。
また、2の累乗個の文字数を使っているわけではないですが、入力は32ビットを1単位として行うことができるので、Base58にあった時間複雑度や空間複雑度の欠点もありません。

一方で、Base85の欠点は多くの文字種を入れたことにことで、 \" などのシステムによっては取り扱いに注意を要する文字が含まれることです。
そのため、Z85などの亜種では問題になりそうな記号類を取り除いた文字セットを使用しています。
https://rfc.zeromq.org/spec/32/

まとめ

さて、Base64以外のBase〇〇系を紹介しましたが、やはり一番バランスが良いのがBase64になるかと個人的には思います。
Base32とBase16はエンコーディング後のデータ量の増加という欠点があり、Base58はそれに加えてエンコーディング処理のオーバーヘッドの高さが目立ちます。
またBase85は効率を求めるあまり取り扱いに注意を要する文字が混入する確率が上がるため、汎用性に欠けます。
そのため、Base64が一番よく使われているのだと思います。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
4
Help us understand the problem. What are the problem?