[1] Bootstring は、小さな (少ない) 符号位置の集合によってより大きな集合の文字列を表現するための算法アルゴリズムです >>2。 Bootstring の引数を特定の値に固定した実現値インスタンス (プロファイル) として Punycode があり、 IDNA で国際化ドメイン名のために使われています。

仕様書

性質

[3] Bootstring は次の性質を持つように設計されています >>2 1.1。

構成要素

[302] Bootstring では、

... といった手法を組み合わせて使っています。

基本符号位置分居

符号化

[13] 拡張文字列を Bootstring で符号化する時には、 基本符号位置はすべて元々の順序でそのまま基本文字列の先頭に含めます。 >>2 3.1

[14] 基本符号位置を並べた後には区切子を置きます。 (基本符号位置がまったく無いときは区切子は含めません。) 区切子は特定の基本符号位置とし、基本文字列のその後の部分には使わないものとします。 >>2 3.1

[17] これを基本符号位置分居basic code point segregationと呼びます。

復号

[15] 復号器は、基本文字列中の最後の区切子を探すことにより、 どこまでが基本符号位置を並べたものでどこからが非基本符号位置を表すものか判断できます。 >>2 3.1

例

[16] Punycode での例: 「abcあいうえおxyz」は、

abcxyz-k43eqasuw
... となります。基本符号位置で表せる部分が「abcxyz」で、 その後に区切子として「-」が挟まり、 最後に「あいうえお」を符号化した文字列が続きます。

挿入非整列符号化

[18] 基本符号位置と - を取って残った部分は非基本符号位置を表しています。 これは一般化可変長整数を使った非負整数として表された差分の列となっています。 >>2 3.2

[19] 復号器の仕事は基本符号位置の列にこの差分の列を適用して元の拡張文字列に戻すことであり、 符号化器の仕事はそうなるような差分の列を生成することとなります。

[20] この符号化の方式は挿入非整列符号化insertion unsort codingと呼ばれています。

復号

[21] 復号の手順をおおまかに表すと次のようになります >>2 3.2。

  1. まず、基本文字列の最初の基本符号位置の部分を取り出します。
  2. 次に、区切子の後の差分の列から差分を1つずつ取出し、それを適用します。差分1つに対して1つの非基本符号位置が挿入されることになります。
    • 差分の列は、「先へと進む回数を表す値」と「挿入する符号位置を表す値」が交互に繰り返される連長符号化run-length encodingになっています。
    • 基本符号位置が挿入されるとしたら、それは誤りです。

一般化可変長整数

[22] 差分は整数の列として表されるのですが、通常の整数だと、

  • 先頭に「0」を付けると同じ整数を表す別の文字列が作れてしまう
  • 複数の整数を並べると (1つの整数の桁数の情報が別途与えられないと) どこで区切られるかわからない
... といった問題があるため、Bootstring ではこれらの問題を解消した一般化可変長整数generalized variable-length integersを使います。 >>2 3.3

[49] Bootstring では小エンディアンを使います >>2 3.3。つまり、 一番下の桁が最初に来て、一番上の桁 (閾値よりも小さな桁) が最後に来ます。

[48] t (j) をどう決めても、 任意の非負整数の値について一般化可変長整数がちょうど1つだけ存在します。 >>2 3.3

[50] 実際には t (j) は

  • [51] t (j) = base × (j + 1) - bias
  • [52] ただし tmin より小さな値とはしない
  • [53] ただし tmax より大きな値とはしない
  • [54] base, tmin, tmax は定数
  • [55] bias は状態変数 (>>56)
... と定義します。 >>2 3.3

符号化

[37] 符号化、つまりある値を一般化可変長整数で表現するには、次のようにします >>2 3.3。

  1. [38] 符号化する値を N とします。
  2. [41] t を t (0) とします。
  3. [39] N が t よりも小さければ、 N を表す数字を出力し、停止します。ここまでに出力した文字列が符号化した結果です。
  4. [42] そうでなければ、
    1. [43] t + ((N - t) mod (base - t)) を表す数字を出力します。
    2. [46] N を (N - t) div (base - t) とします。
    3. [44] t を次の桁の閾値とします。
    4. [45] >>39 に戻ります。

[47] つまり、最後の桁では表したい値そのものに対応する数字 (閾値よりも小さな値) を使って表し、それ以外の桁では閾値よりも小さな数字を除いた残った数字だけで (通常の整数のように) 表そうとしたときに使う数字を使って表す、ということになります。

復号

[26] 復号、つまり一般化可変長整数の表す値の計算の方法は、 >>25 から自然に定まります。

[28] 一般化可変長整数の復号 >>2 3.3
  1. [27] N を 0 とします。
  2. [29] w を 1 とします。
  3. [40] t を t (0) とします。
  4. [30] d を次の数字とします。
  5. [31] d と w の積を N に足します。
  6. [32] d が t よりも小さければ、停止します。 N が復号結果の値です。
  7. [33] そうでなければ、
    1. [34] w に base から t を引いた値を掛けます。
    2. [35] t を次の桁の閾値とします。
    3. [36] >>30 に戻ります。

偏差適応

[56] bias (>>55) は、偏差適応bias adaptationによって、 一つ前の差分の値に依存して決定します。 具体的には、前の差分の後、次の差分の処理の前に、次のように計算します >>2 3.4。

  1. [60] delta を差分とします。
  2. [57] >>58 での桁溢れを防ぐために delta を整数除算します。 >>2 3.4
    • 最初の差分であるなら、定数 damp で割ります。 >>2 3.4
    • 2つ目以降の差分であるなら、2 で割ります。 >>2 3.4
    • 通常1つ目の差分よりも2つ目の差分の方が小さいため、こうしています。 >>2 3.4
  3. [58] delta に、そこまでに符号化または復号する文字列 (その差分に対応する符号位置や基本符号位置もすべて含みます。) の長さによって差分を整数除算した結果を足し合わせます。 >>2 3.4
    • 次の差分はより長い文字列に挿入されることとなるので、こうしています。 >>2 3.4
    • つまり、文字列の長さに対する差分の長さの割合を delta に足すことになります。
  4. [59] delta を閾値の範囲に収まるまで割り続けます。 >>2 3.4
    • これは次の差分を表現するのに必要な数字の最小の個数を予想するものとなります。 >>2 3.4
    • 具体的には、 while delta > ((base - tmin) * tmax) div 2 do let delta = delta div (base - tmin) とします。 >>2 3.4
    • base から tmin を引くと、続きがまだあることを表す数字が最も多いときの個数となります。
    • tmax は続きがもうないことを表す数字が最も多いときの個数となります。
    • ループの条件部の (base - tmin) × tmax) では、まだ続く数字の個数ともう続かない数字の個数をかけているので、ちょうど2桁で表せる最大の値を求めていることになります。
    • つまり、このループで delta を整数除算した回数が、続きがまだある数字を最も多く取った時 (tmin を閾値としたとき) の桁数になります。
  5. [61] bias は、 >>59 で除算した回数と base の積に対して、 ((base - tmin + 1) * delta) div (delta + skew) を足した値とします。 >>2 3.4
    • 現在の差分は次の差分の長さのヒントであり、それによって t (j) は最後になると期待される桁から上の方の桁は tmax に、 最後になると期待される桁の前の前までの桁ほ tmin に、 最後になると期待される桁の手前の桁はその中間となるよう、こうしています。 (最後になると期待される桁が実際には不要であるとの期待と実際にはもっと長くなる危険性とのバランスでそうしています。) >>2 3.4

擬似コード

[195] 次の擬似コードは、 >>2 6.1 に注釈を入れたものです。

[196] 

 function adapt(delta,numpoints,firsttime):
     if firsttime then let delta = delta div damp
     else let delta = delta div 2

  • [199] 初回実行であれば引数の damp を、そうでなければ 2 を使って delta を割ります。
    • [200] これは桁溢れを防止するためです。 (>>56)
    • [209] 1つ目の符号位置は最初の n (Punycode では 0x80) からの差分が delta に反映されているので、通常は大きな値になります。2つ目以降では (同じ書字方式の文字は近い符号位置を持つ可能性が高いという性質を仮定すると) 小さな値となります。

[198] 

     let delta = delta + (delta div numpoints)

  • [210] numpoints は処理済みの符号位置の数です。 delta は前の符号位置から今回の符号位置までの値の差に処理済みの符号位置の数を掛けている (>>78) ので、ここで足している値はその値の差を何分の一かにしたもの (>>199) といえます。
    • [211] 符号位置は後から出てくるものほど文字列のより後ろの方へと挿入されて delta が大きくなる傾向にあるので (>>128 参照)、その補正のために足しています。

[201] 

     let k = 0
     while delta > ((base - tmin) * tmax) div 2 do begin
       let delta = delta div (base - tmin)
       let k = k + base
     end

  • [213] delta をできるだけ割ります。
  • [214] base から tmin を引いた数は、閾値 t をもっとも小さくし、できるだけ次の桁に続くことを意味する数字を増やした時の次に続く数字の個数を表しています。
  • [215] そのたびに k に base を足していっているので、 k は数字の述べ個数になります。
    • [216] このあたりは >>157 のループに対応しています。
  • [217] ループ条件にある (base - tmin) × tmax は、
    • [218] 前半は >>214 と同じです。
    • [219] tmax は閾値 t をもっとも大きくし、できるだけ次の桁に続かないことを意味する数字を増やしたときの次に続かない数字の個数を表しています。
    • [220] それらの積ですから、この桁はまだ続き、次の桁で最後であるとしたときに表せる値の個数になります。

[212] 

     return k + (((base - tmin + 1) * delta) div (delta + skew))

  • [221] >>201 で delta を何度も割っているので、ここでの delta は最後の2桁相当の値になっています。

大文字・小文字混合注釈

[322] Bootstring の実質唯一の具象化であるところの Punycode の主用途たる IDNA は大文字・小文字を区別しないことになっており、 Punycode 化の前に正規化されます。しかし、 表示用などで大文字と小文字の区別を保存しておきたいことがあります。 そのため、 Bootstring で符号化した基本文字列には大文字・小文字混合注釈mixed-case annotationを埋め込むことができます RFC 3492 A.。

[327] 大文字・小文字混合注釈はオプションの機能であり、Punycode や Bootstring の実装はこれに対応する必要はありません RFC 3492 A.。

[328] 大文字・小文字混合注釈を使うためには基本符号位置の選定に一定の制約があります (>>72)。

引数

[303] Bootstring にはいくつかの引数があります。この引数を特定の値に固定することにより、 具体的な算法が定まります。 (その一例が Punycode です。)

[62] Bootstring の引数には、次の制約があります >>2 4.。

符号化

[73] 次に示すのは、 >>2 6.3 に示された擬似コードによる Bootstring の符号化の実装に適宜注釈を入れたものです。

[110] 

   let n = initial_n

[109] 

   let delta = 0

[140] 

   let bias = initial_bias

[177] 

   let h = b = the number of basic code points in the input

[98] 

   copy them to the output in order, followed by a delimiter if b > 0

[74] 

   {if the input contains a non-basic code point < n then fail}

[75] 

   while h < length(input) do begin

[94] 

     let m = the minimum {non-basic} code point >= n in the input

[78] 

     let delta = delta + (m - n) * (h + 1), fail on overflow

[88] 

     let n = m

[120] 

     for each code point c in the input (in order) do begin

[128] 

       if c < n {or c is basic} then increment delta, fail on overflow

[80] 

       if c == n then begin

[124] 

         let q = delta

[157] 

         for k = base to infinity in steps of base do begin

[153] 

           let t = tmin if k <= bias {+ tmin}, or
                   tmax if k >= bias + tmax, or k - bias otherwise

[154] 

           if q < t then break

[161] 

           output the code point for digit t + ((q - t) mod (base - t))

[171] 

           let q = (q - t) div (base - t)

[172] 

         end

[163] 

         output the code point for digit q

[104] 

         let bias = adapt(delta, h + 1, test h equals b?)

[117] 

         let delta = 0

[118] 

         increment h

[182] 

       end

[183] 

     end

[119] 

     increment delta and n

[90] 

   end

復号

[222] 次に示すのは、 RFC 3492 6.2 に示された Bootstring の復号の擬似コードに注釈を加えたものです。

[223] 

   let n = initial_n

[270] 

   let i = 0

[271] 

   let bias = initial_bias
   let output = an empty string indexed from 0

[248] 

   consume all code points before the last delimiter (if there is one)
     and copy them to output, fail on any non-basic code point

[242] 

   if more than zero code points were consumed then consume one more
     (which will be the last delimiter)

[246] 

   while the input is not exhausted do begin

[250] 

     let oldi = i

[256] 

     let w = 1

[257] 

     for k = base to infinity in steps of base do begin

[260] 

       consume a code point, or fail if there was none to consume
       let digit = the code point's digit-value, fail if it has none

[267] 

       let i = i + digit * w, fail on overflow

[228] 

       let t = tmin if k <= bias {+ tmin}, or
               tmax if k >= bias + tmax, or k - bias otherwise

[229] 

       if digit < t then break

[279] 

       let w = w * (base - t), fail on overflow

[263] 

     end

[264] 

     let bias = adapt(i - oldi, length(output) + 1, test oldi is 0?)

[287] 

     let n = n + i div (length(output) + 1), fail on overflow

[292] 

     let i = i mod (length(output) + 1)

[224] 

     {if n is a basic code point then fail}

[225] 

     insert n into output at position i

[299] 

     increment i

[252] 

   end

桁溢れの処理

[304] 符号化と復号の算法中に現れている通り、桁溢れの処理が必要となります。 Punycode を IDNA で使う場合は26ビットの符号無し整数があれば十分です RFC 3492 6.4。 (Punycode の項を参照。) それ以外の場合はより大きな整数が必要になることもあるでしょう。

[305] 桁溢れの処理方法は何通りか考えられ、どれが簡便であるかはプログラミング言語にも依存します。

実装

[329] RFC 3492 には C言語による実装例があります。 Punycode 用ではありますが、容易に他の Bootstring にも拡張できます。 http://tools.ietf.org/html/rfc3492#appendix-B

[330] 大文字・小文字混合注釈には対応していません。

[12] Encode::Bootstring - search.cpan.org http://search.cpan.org/dist/Encode-Bootstring/lib/Encode/Bootstring.pm

[331] >>12 はちょっと物足りない感じでした。 Punycode を実装できない。