[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]] は[[状態変数]] ... と定義します。 [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 に戻ります。 * 実装 [12] [CITE[Encode::Bootstring - search.cpan.org]]