\( \def\vector#1{\boldsymbol{#1}} \)

基数変換

Takami Torao #Base64
  • このエントリーをはてなブックマークに追加

基数 \(r_a\) で表される \(n_a\) 個の数列 \(\vector{A} = a_0, a_1, \ldots, a_{n_a-1}\) (\(0 \le a_i \lt r_a\)) を基数 \(r_b\) の数列 \(\vector{B}\) に変換する操作について考える。ここで数列の要素 \(a_i\) は \(i\) が小さい方が下の桁を表す (つまり \(a_0, a_1, \ldots\) の並びは little endian での表現である)。なお \(i \ge n_a\) の領域において \(a_i=0\) と考える事もできるが、ここでは有限なメモリを持つコンピュータ上での処理を目的としているため有限の桁数とする。

表現上の数列 \(\vector{A}\) と \(\vector{B}\) は本来的な数値を介して以下のように表すことができる。\[ N = \sum_{i=0}^{n_a-1} a_i r_a^i = \sum_{i=0}^{n_b-1} b_i r_b^i \]

一般的に基数変換は \(\vector{A}\) から \(N\) を求め \(\vector{B}\) に変換する。

def convert(a:Array[Int], r_a:Int, r_b:Int):Array[Int] = {
  val n = a.foldRight(BigInt(0)) { case (a_i, sigma) => sigma * r_a + a_i }
  var remaining = n
  val b = Buffer[Int]()
  while(remaining != 0){
    b.append((remaining % r_b).toInt)
    remaining /= r_b
  }
  b.toArray
}

\(r_a\), \(r_b\) が 2 のべき乗であればシフト演算とビット演算を使用して

\(\vector{A}\) を基数 \(r_b\) で表すために十分かつ最も小さい桁数 \(n_b\) を求める。まず、\(r\), \(n\) が決定している場合に取り得る最大値 \(N_{\rm max}\) は基数 \(r\) の桁数 \(n\) によるべき乗より 1 つ小さい値であることから、それぞれの最大値は以下のように表される。\[ \left\{ \begin{array}{lcl} N_{{\rm max} \ a} & = & r_a^{n_a} - 1 \\ N_{{\rm max} \ b} & = & r_b^{n_b} - 1 \end{array} \right. \] 基数 \(r_b\) の表現において桁数 \(n_b\) を用いて \(N_{{\rm max}\ a}\) を表すことができるためには: \[ N_{{\rm max}\ a} \le N_{{\rm max}\ b}\\ r_a^{n_a} - 1 \le r_b^{n_b} - 1 \\ n_b \ge \frac{\log r_a}{\log r_b} n_a \] \(n_b\) は上記の条件を満たす最も小さい整数であるため以下の式で求めることができる。\[ n_b = \left\lceil \frac{\log r_a}{\log r_b} n_a \right\rceil \] しかし、実際のプログラミングでの ceil() は浮動小数点演算の誤差に非常に敏感であり、log() も誤差の大きな演算である。例えば: \(r_a=3\), \(n_a=5\) での最大値 \(N_{{\rm max}\ a} = [2,2,2,2,2]\) に対して \(r_b=243\) では \(\vector{B}=[242]\), \(n_b=1\) だが、演算の誤差により 2 となる。

scala> math.log(3) * 5 / math.log(243)
res31: Double = 1.0000000000000002

特に \(r_a\), \(r_b\) が 2 のべき乗で決定しているのであれば対数を使用せずに計算した方が良い。

Base64 とその派生符号化変換

Base64 はバイナリを 64 種類の文字を使用した文字列に変換する。これは、基数 256 の数列を基数 64 の数列に変換し、それぞれの桁を文字にマッピングすることと等価である。Base58 のような 64 以外の符号化についても、対象とする基数が異なるだけで同じ処理となることが分かるだろう。2 のべき乗となる基数に対しては余剰演算の代わりにシフト演算とビット操作が使用できるため効率が良い。

参照