[1] Bootstring は、小さな (少ない) 符号位置の集合によってより大きな集合の文字列を表現するための算法です >>2。 Bootstring の引数を特定の値に固定した実現値 (プロファイル) として Punycode があり、 IDNA で国際化ドメイン名のために使われています。
[3] Bootstring は次の性質を持つように設計されています >>2 1.1。
[302] Bootstring では、
[13] 拡張文字列を Bootstring で符号化する時には、 基本符号位置はすべて元々の順序でそのまま基本文字列の先頭に含めます。 >>2 3.1
[14] 基本符号位置を並べた後には区切子を置きます。 (基本符号位置がまったく無いときは区切子は含めません。) 区切子は特定の基本符号位置とし、基本文字列のその後の部分には使わないものとします。 >>2 3.1
[17] これを基本符号位置分居と呼びます。
[15] 復号器は、基本文字列中の最後の区切子を探すことにより、 どこまでが基本符号位置を並べたものでどこからが非基本符号位置を表すものか判断できます。 >>2 3.1
[16] Punycode での例: 「abcあいうえおxyz」は、
abcxyz-k43eqasuw... となります。基本符号位置で表せる部分が「abcxyz」で、 その後に区切子として「
-」が挟まり、
最後に「あいうえお」を符号化した文字列が続きます。[18] 基本符号位置と - を取って残った部分は非基本符号位置を表しています。
これは一般化可変長整数を使った非負整数として表された差分の列となっています。
>>2 3.2
[19] 復号器の仕事は基本符号位置の列にこの差分の列を適用して元の拡張文字列に戻すことであり、 符号化器の仕事はそうなるような差分の列を生成することとなります。
[20] この符号化の方式は挿入非整列符号化と呼ばれています。
[22] 差分は整数の列として表されるのですが、通常の整数だと、
0 ... base - 1 を使います。 >>2 3.3t (j) を使います。 >>2 3.3w (j) を使って Σj digitj × w (j) で得られる値です。 >>2 3.3[49] Bootstring では小エンディアンを使います >>2 3.3。つまり、 一番下の桁が最初に来て、一番上の桁 (閾値よりも小さな桁) が最後に来ます。
[48] t (j) をどう決めても、
任意の非負整数の値について一般化可変長整数がちょうど1つだけ存在します。
>>2 3.3
[50] 実際には t (j) は
[37] 符号化、つまりある値を一般化可変長整数で表現するには、次のようにします >>2 3.3。
[47] つまり、最後の桁では表したい値そのものに対応する数字 (閾値よりも小さな値) を使って表し、それ以外の桁では閾値よりも小さな数字を除いた残った数字だけで (通常の整数のように) 表そうとしたときに使う数字を使って表す、ということになります。
[26] 復号、つまり一般化可変長整数の表す値の計算の方法は、 >>25 から自然に定まります。
[56] bias (>>55) は、偏差適応によって、 一つ前の差分の値に依存して決定します。 具体的には、前の差分の後、次の差分の処理の前に、次のように計算します >>2 3.4。
while delta > ((base - tmin) * tmax) div 2 do let delta = delta div (base - tmin) とします。 >>2 3.4(base - tmin) × tmax) では、まだ続く数字の個数ともう続かない数字の個数をかけているので、ちょうど2桁で表せる最大の値を求めていることになります。((base - tmin + 1) * delta) div (delta + skew) を足した値とします。 >>2 3.4[195] 次の擬似コードは、 >>2 6.1 に注釈を入れたものです。
function adapt(delta,numpoints,firsttime):
if firsttime then let delta = delta div damp
else let delta = delta div 2let delta = delta + (delta div numpoints)
let k = 0
while delta > ((base - tmin) * tmax) div 2 do begin
let delta = delta div (base - tmin)
let k = k + base
end(base - tmin) × tmax は、return k + (((base - tmin + 1) * delta) div (delta + skew))
[322] Bootstring の実質唯一の具象化であるところの Punycode の主用途たる IDNA は大文字・小文字を区別しないことになっており、 Punycode 化の前に正規化されます。しかし、 表示用などで大文字と小文字の区別を保存しておきたいことがあります。 そのため、 Bootstring で符号化した基本文字列には大文字・小文字混合注釈を埋め込むことができます RFC 3492 A.。
[327] 大文字・小文字混合注釈はオプションの機能であり、Punycode や Bootstring の実装はこれに対応する必要はありません RFC 3492 A.。
[328] 大文字・小文字混合注釈を使うためには基本符号位置の選定に一定の制約があります (>>72)。
[303] Bootstring にはいくつかの引数があります。この引数を特定の値に固定することにより、 具体的な算法が定まります。 (その一例が Punycode です。)
[62] Bootstring の引数には、次の制約があります >>2 4.。
base - 1 の数字の値を割り当てる必要があります。 >>2 4.0 ≦ tmin ≦ tmax ≦ base - 1 >>2 4.1 ≦ skew >>2 4.1 ≦ damp >>2 4.initialbias mod base ≦ base - tmin >>2 4.[73] 次に示すのは、 >>2 6.3 に示された擬似コードによる Bootstring の符号化の実装に適宜注釈を入れたものです。
let n = initial_n
let delta = 0
let bias = initial_bias
let h = b = the number of basic code points in the input
copy them to the output in order, followed by a delimiter if b > 0
{if the input contains a non-basic code point < n then fail}while h < length(input) do begin
let m = the minimum {non-basic} code point >= n in the inputlet delta = delta + (m - n) * (h + 1), fail on overflow
h + 1 進数で、一番下の桁が直前の非基本符号位置からの位置の差 (元の delta)、それより上の桁が直前の非基本符号位置の次の符号位置から実際の符号位置までの値の差 (m - n) を表しています。m - n は、 >>94 より、ここで処理され得る最小の符号位置 (n) と実際に input に含まれていた最小の符号位置 (m) との差となります。m - n は、 delta が h + 1 よりも必ず小さくなるので、 m - n に h + 1 を掛けて足せば一つの値にできます。let n = m
for each code point c in the input (in order) do begin
if c < n {or c is basic} then increment delta, fail on overflowc < n が成立しますから、チェックを省略できます。 >>2 6.3if c == n then begin
let q = delta
for k = base to infinity in steps of base do begin
let t = tmin if k <= bias {+ tmin}, or
tmax if k >= bias + tmax, or k - bias otherwiseif q < t then break
output the code point for digit t + ((q - t) mod (base - t))
let q = (q - t) div (base - t)
end
output the code point for digit q
let bias = adapt(delta, h + 1, test h equals b?)
let delta = 0
increment h
end
end
increment delta and n
end
[222] 次に示すのは、 RFC 3492 6.2 に示された Bootstring の復号の擬似コードに注釈を加えたものです。
let n = initial_n
let i = 0
let bias = initial_bias let output = an empty string indexed from 0
consume all code points before the last delimiter (if there is one)
and copy them to output, fail on any non-basic code point if more than zero code points were consumed then consume one more
(which will be the last delimiter)while the input is not exhausted do begin
let oldi = i
let w = 1
for k = base to infinity in steps of base do begin
consume a code point, or fail if there was none to consume
let digit = the code point's digit-value, fail if it has nonelet i = i + digit * w, fail on overflow
let t = tmin if k <= bias {+ tmin}, or
tmax if k >= bias + tmax, or k - bias otherwiseif digit < t then break
let w = w * (base - t), fail on overflow
end
let bias = adapt(i - oldi, length(output) + 1, test oldi is 0?)
let n = n + i div (length(output) + 1), fail on overflow
let i = i mod (length(output) + 1)
{if n is a basic code point then fail}insert n into output at position i
increment i
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>
[12] Encode::Bootstring - search.cpan.org <http://search.cpan.org/dist/Encode-Bootstring/lib/Encode/Bootstring.pm>