[1] [DFN[[[Bootstring]]]] は、小さな (少ない) [[符号位置]]の[[集合]]によってより大きな[[集合]]の[[文字列]]を表現するための[RUBY[[[算法]]][アルゴリズム]]です [SRC[>>2]]。 [[Bootstring]] の[[引数]]を特定の値に固定した[RUBY[[[実現値]]][インスタンス]] ([[プロファイル]]) として [[Punycode]] があり、 [[IDNA]] で[[国際化ドメイン名]]のために使われています。 * 仕様書 - [2] [CITE@en[RFC 3492 - Punycode: A Bootstring encoding of Unicode for Internationalized Domain Names in Applications (IDNA)]] * 性質 [3] [[Bootstring]] は次の性質を持つように設計されています [SRC[>>2 1.1]]。 - [4] [RUBYB[[[完全性]]]@en[completeness]]: あらゆる[RUBYB[[[拡張文字列]]]@en[extended string]] (任意の[[符号位置]]の列) は、 [RUBYB[[[基本文字列]]]@en[basic string]] ([RUBYB[[[基本符号位置]]]@en[basic code point]]の列) によって表現できます。 - [5] [RUBYB[[[固有性]]]@en[uniqueness]]: ある[[拡張文字列]]を表現する[[基本文字列]]は、 高々1つしか存在しません。 - [6] [RUBYB[[[可逆性]]]@en[reversibility]]: [[拡張文字列]]を[[基本文字列]]に[[写像]]できたとすると、 その[[基本文字列]]から元の[[拡張文字列]]に再変換することができます。 - [7] [RUBYB[[[効率的符号化]]]@en[efficient encoding]]: [[基本文字列]]の長さと[[拡張文字列]]の長さの[[比]]は小さいです。 - [8] [RUBYB[[[単純性]]]@en[simplicity]]: [[符号化]]と[[復号]]の[[算法]]は十分単純です。 -- [10] [[効率性]]と[[単純性]]は必ずしも両立しませんが、 [[Bootstring]] は両者のバランスがとれたものを目指しています。 - [9] [RUBYB[[[可読性]]]@en[readability]]: [[拡張文字列]]中の[[基本符号位置]]は、 [[基本文字列]]中にそのまま出てきます。 -- [11] といってもその主目的は[[効率性]]なのですが。 * 基本符号位置分居 ** 符号化 [13] [[拡張文字列]]を [[Bootstring]] で[[符号化]]する時には、 [[基本符号位置]]はすべて元々の順序でそのまま[[基本文字列]]の先頭に含めます。 [SRC[>>2 3.1]] [14] [[基本符号位置]]を並べた後には[[区切子]]を置きます。 ([[基本符号位置]]がまったく無いときは[[区切子]]は含めません。) [[区切子]]は特定の[[基本符号位置]]とし、[[基本文字列]]のその後の部分には使わないものとします。 [SRC[>>2 3.1]] [17] これを[DFN[[RUBYB[基本符号位置分居]@en[basic code point segregation]]]]と呼びます。 ** 復号 [15] [[復号器]]は、[[基本文字列]]中の最後の[[区切子]]を探すことにより、 どこまでが[[基本符号位置]]を並べたものでどこからが非[[基本符号位置]]を表すものか判断できます。 [SRC[>>2 3.1]] ** 例 [16] [[Punycode]] での例: 「abcあいうえおxyz」は、 [PRE(code)[ abcxyz-k43eqasuw ]PRE] ... となります。[[基本符号位置]]で表せる部分が「abcxyz」で、 その後に[[区切子]]として「[CODE(char)[[[-]]]]」が挟まり、 最後に「あいうえお」を[[符号化]]した文字列が続きます。 * 挿入非整列符号化 [18] [[基本符号位置]]と [CODE(char)[[[-]]]] を取って残った部分は非[[基本符号位置]]を表しています。 これは[[一般化可変長整数]]を使った[[非負整数]]として表された[[差分]]の列となっています。 [SRC[>>2 3.2]] [19] [[復号器]]の仕事は[[基本符号位置]]の列にこの[[差分]]の列を適用して元の[[拡張文字列]]に戻すことであり、 [[符号化器]]の仕事はそうなるような[[差分]]の列を生成することとなります。 [20] この符号化の方式は[DFN[[RUBYB[[[挿入非整列符号化]]]@en[insertion unsort coding]]]]と呼ばれています。 ** 復号 [21] [[復号]]の手順をおおまかに表すと次のようになります [SRC[>>2 3.2]]。 = まず、[[基本文字列]]の最初の[[基本符号位置]]の部分を取り出します。 = 次に、[[区切子]]の後の[[差分]]の列から[[差分]]を1つずつ取出し、それを適用します。[[差分]]1つに対して1つの非[[基本符号位置]]が挿入されることになります。 =- [[差分]]の列は、「先へと進む回数を表す値」と「挿入する[[符号位置]]を表す値」が交互に繰り返される[RUBYB[[[連長符号化]]]@en[run-length encoding]]になっています。 =- [[基本符号位置]]が挿入されるとしたら、それは[[誤り]]です。 * 一般化可変長整数 [22] [[差分]]は[[整数]]の列として表されるのですが、通常の[[整数]]だと、 - 先頭に「0」を付けると同じ[[整数]]を表す別の[[文字列]]が作れてしまう - 複数の[[整数]]を並べると (1つの[[整数]]の[[桁数]]の情報が別途与えられないと) どこで区切られるかわからない ... といった問題があるため、[[Bootstring]] ではこれらの問題を解消した[DFN[[RUBYB[一般化可変長整数]@en[generalized variable-length integers]]]]を使います。 [SRC[>>2 3.3]] - [23] [[数字]]としては [CODE(math)[0]] ... [CODE(math)[[VAR@en[base]] - 1]] を使います。 [SRC[>>2 3.3]] - [24] [[閾値]] [CODE(math)[[VAR[t]] ([VAR[j]])]] を使います。 [SRC[>>2 3.3]] -- 一番上の桁が [VAR[j]] 番目とすると、その桁だけが [CODE(math)[[VAR[digit[SUB[[VAR[j]]]]]] < [VAR[t]] ([VAR[j]])]] を満たすとします。 [SRC[>>2 3.3]] --- 続きがもうない桁 [VAR[j]] では [CODE(math)[0]] ... [CODE(math)[[VAR[t]] ([VAR[j]]) - 1]] を使います。 --- 続きがまだある桁 [VAR[j]] では [CODE(math)[[VAR[t]] ([VAR[j]])]] ... [CODE(math)[[VAR@en[base]] - 1]] を使います。 - [25] この[[数字列]]によって表される値は、次の [CODE(math)[[VAR[w]] ([VAR[j]])]] を使って [CODE(math)[Σ[VAR[j]] [VAR[digit[SUB[[VAR[j]]]]]] × [VAR[w]] ([VAR[j]])]] で得られる値です。 [SRC[>>2 3.3]] -- [CODE(math)[[VAR[w]] (0) = 1]] [SRC[>>2 3.3]] --- つまり、一番下の[[桁]]については、重みは 1 であり、表される値はその[[数字]]の値と同じです。 -- [CODE(math)[[VAR[w]] ([VAR[j]]) = [VAR[w]] ([VAR[j]] - 1) × ([VAR[base]] - [VAR[t]] ([VAR[j]] - 1))]] [SRC[>>2 3.3]] --- それより上の[[桁]]については、重みは一つ下の[[桁]]の重みと一つ下の[[桁]]で続きがまだある[[桁]]に使える[[数字]]の個数の[[積]]です。 --- ここで [CODE(math)[[VAR[t]] ([VAR[j]] - 1) = 0]] だったとすると、通常の[[整数]]と同じになります。 (もちろん、その場合 >>24 の「続きがもうない桁」が該当無しになり、続きがあるかどうかは判定できなくなります。 [49] [[Bootstring]] では[[小エンディアン]]を使います [SRC[>>2 3.3]]。つまり、 一番下の[[桁]]が最初に来て、一番上の[[桁]] ([[閾値]]よりも小さな[[桁]]) が最後に来ます。 [48] [CODE(math)[[VAR[t]] ([VAR[j]])]] をどう決めても、 任意の[[非負整数]]の値について[[一般化可変長整数]]がちょうど1つだけ存在します。 [SRC[>>2 3.3]] [50] 実際には [CODE(math)[[VAR[t]] ([VAR[j]])]] は - [51] [CODE(math)[[VAR[t]] ([VAR[j]]) = [VAR[base]] × ([VAR[j]] + 1) - [VAR[bias]]]] - [52] ただし [VAR[t[SUB[min]]]] より小さな値とはしない - [53] ただし [VAR[t[SUB[max]]]] より大きな値とはしない - [54] [VAR[base]], [VAR[t[SUB[min]]]], [VAR[t[SUB[max]]]] は[[定数]] - [55] [VAR[bias]] は[[状態変数]] (>>56) ... と定義します。 [SRC[>>2 3.3]] ** 符号化 [37] [[符号化]]、つまりある値を[[一般化可変長整数]]で表現するには、次のようにします [SRC[>>2 3.3]]。 = [38] [[符号化]]する値を [VAR[N]] とします。 = [41] [VAR[t]] を [CODE(math)[[VAR[t]] (0)]] とします。 = [39] [VAR[N]] が [VAR[t]] よりも小さければ、 [VAR[N]] を表す[[数字]]を出力し、停止します。ここまでに出力した[[文字列]]が[[符号化]]した結果です。 = [42] そうでなければ、 == [43] [CODE(math)[[VAR[t]] + (([VAR[N]] - [VAR[t]]) mod ([VAR[base]] - [VAR[t]]))]] を表す[[数字]]を出力します。 == [46] [VAR[N]] を [CODE(math)[([VAR[N]] - [VAR[t]]) div ([VAR[base]] - [VAR[t]])]] とします。 == [44] [VAR[t]] を次の桁の[[閾値]]とします。 == [45] >>39 に戻ります。 [47] つまり、最後の桁では表したい値そのものに対応する[[数字]] ([[閾値]]よりも小さな値) を使って表し、それ以外の桁では[[閾値]]よりも小さな[[数字]]を除いた残った[[数字]]だけで (通常の[[整数]]のように) 表そうとしたときに使う[[数字]]を使って表す、ということになります。 ** 復号 [26] [[復号]]、つまり[[一般化可変長整数]]の表す値の計算の方法は、 >>25 から自然に定まります。 [28] [SRC[>>2 3.3]] = [27] [VAR[N]] を 0 とします。 = [29] [VAR[w]] を 1 とします。 = [40] [VAR[t]] を [CODE(math)[[VAR[t]] (0)]] とします。 = [30] [VAR[d]] を次の[[数字]]とします。 = [31] [VAR[d]] と [VAR[w]] の[[積]]を [VAR[N]] に足します。 = [32] [VAR[d]] が [VAR[t]] よりも小さければ、[[停止]]します。 [VAR[N]] が[[復号]]結果の値です。 = [33] そうでなければ、 == [34] [VAR[w]] に [VAR[base]] から [VAR[t]] を引いた値を掛けます。 == [35] [VAR[t]] を次の桁の[[閾値]]とします。 == [36] >>30 に戻ります。 * 偏差適応 [56] [VAR[bias]] (>>55) は、[DFN[[RUBYB[偏差適応]@en[bias adaptation]]]]によって、 一つ前の[[差分]]の値に依存して決定します。 具体的には、前の[[差分]]の後、次の[[差分]]の処理の前に、次のように計算します [SRC[>>2 3.4]]。 = [60] [VAR[delta]] を[[差分]]とします。 = [57] >>58 での[[桁溢れ]]を防ぐために [VAR[delta]] を[[整数除算]]します。 [SRC[>>2 3.4]] =- 最初の[[差分]]であるなら、[[定数]] [VAR[damp]] で割ります。 [SRC[>>2 3.4]] =- 2つ目以降の[[差分]]であるなら、2 で割ります。 [SRC[>>2 3.4]] =- 通常1つ目の[[差分]]よりも2つ目の[[差分]]の方が小さいため、こうしています。 [SRC[>>2 3.4]] = [58] [VAR[delta]] に、[[符号化]]または[[復号]]する[[文字列]] [WEAK[(その[[差分]]に対応する[[符号位置]]や[[基本符号位置]]もすべて含みます。)]] によって[[差分]]を[[整数除算]]した結果を足し合わせます。 [SRC[>>2 3.4]] =- 次の[[差分]]はより長い文字列に挿入されることとなるので、こうしています。 [SRC[>>2 3.4]] =- つまり、文字列の長さに対するこれまでに処理した[[差分]]までの長さの割合を [VAR[delta]] に足すことになります。 = [59] [VAR[delta]] を[[閾値]]の範囲に収まるまで割り続けます。 [SRC[>>2 3.4]] =- これは次の[[差分]]を表現するのに必要な[[数字]]の最小の個数を予想するものとなります。 [SRC[>>2 3.4]] =- 具体的には、 [CODE[while delta > ((base - tmin) * tmax) div 2 do let delta = delta div (base - tmin)]] とします。 [SRC[>>2 3.4]] =- [VAR[base]] から [VAR[t[SUB[min]]]] を引くと、続きがまだあることを表す[[数字]]が最も多いときの個数となります。 =- [VAR[t[SUB[max]]]] は続きがもうないことを表す[[数字]]が最も多いときの個数となります。 =- ループの条件部の [CODE(math)[([VAR[base]] - [VAR[t[SUB[min]]]]) × [VAR[t[SUB[max]]]])]] では、まだ続く数字の個数ともう続かない数字の個数をかけているので、ちょうど2桁で表せる最大の値を求めていることになります。 =- つまり、このループで [VAR[delta]] を[[整数除算]]した回数が、続きがまだある[[数字]]を最も多く取った時 [WEAK[([VAR[t[SUB[min]]]] を[[閾値]]としたとき)]] の桁数になります。 = [61] [VAR[bias]] は、 >>59 で除算した回数と [VAR[base]] の[[積]]に対して、 [CODE[((base - tmin + 1) * delta) div (delta + skew)]] を足した値とします。 [SRC[>>2 3.4]] =- 現在の[[差分]]は次の[[差分]]の長さのヒントであり、それによって [CODE(math)[[VAR[t]] ([VAR[j]])]] は最後になると期待される[[桁]]から上の方の[[桁]]は [VAR[t[SUB[max]]]] に、 最後になると期待される[[桁]]の前の前までの[[桁]]ほ [VAR[t[SUB[min]]]] に、 最後になると期待される[[桁]]の手前の[[桁]]はその中間となるよう、こうしています。 (最後になると期待される[[桁]]が実際には不要であるとの期待と実際にはもっと長くなる危険性とのバランスでそうしています。) [SRC[>>2 3.4]] * 引数の制約 [62] [[Bootstring]] の[[引数]]には、次の制約があります [SRC[>>2 4.]]。 - [63] [[基本符号位置]]のうちの1つは[[区切子]]とする必要があります。 - [64] [VAR@en[base]] を残った[[基本符号位置]]の数より大きくはできません。 - [65] [[区切子]]以外の[[基本符号位置]]に対して 0 ... [CODE(math)[[VAR[base]] - 1]] の[[数字]]の値を割り当てる必要があります。 -- [66] [[大文字]]と[[小文字]]のように、複数の[[符号位置]]が同じ値を持っても構いません。 -- [72] [[大文字・小文字混合注釈]]を使いたい場合、 0 ... [CODE(math)[[VAR[t[SUB[max]]]] - 1]] のすべての値について[[大文字]]と[[小文字]]が必要です。 - [67] [VAR[n]] ([[差分]]の挿入位置まで進む数) の初期値は[[拡張文字列]]に現れる非[[基本符号位置]]の数より多くはできません。 - [68] [CODE(math)[0 ≦ [VAR[t[SUB[min]]]] ≦ [VAR[t[SUB[max]]]] ≦ [VAR[base]] - 1]] - [69] [CODE(math)[1 ≦ [VAR[skew]]]] - [70] [CODE(math)[1 ≦ [VAR[damp]]]] - [71] [CODE(math)[[VAR[initial[SUB[bias]]]] mod [VAR[base]] ≦ [VAR[base]] - [VAR[t[SUB[min]]]]]] * 実装 [12] [CITE[Encode::Bootstring - search.cpan.org]]