Punycode

新しい方式に改定されているのでRFC 5891などを読む。Punycodeの前に行う。

IDNAとの違い?

正規化、ASCII文字の制限がない

Punycodeでは大文字・小文字を区別することができる

ACEプレフィックス xn-- はつけない

basic code point (ASCIIっぽい範囲 0 - 127)

Basic string

Extended string

1. Basic code point の文字を抜き出して先頭にまとめる

2. Basic code point がある場合は delimiter で分ける

3. Extended string をコード順に差し込んでいく手順を符号化する

コード dnsで大文字小文字を区別しないので a-z 0-9 の36文字と delimiter で '-'

変換テストっぽい

なども参考に実装してみたらこんな感じ

RFC 3492 一部訳

2. 用語

コードポイントとは、コード化された文字セット内の文字に関連付けられた整数値です。

演算子 div と mod は整数の除算を実行します。 (x div y) は x を y で割った商で、余りは切り捨てられます。(x mod y) は余りなので、(x div y) * y + (x mod y) == x となります。Bootstring ではこれらの演算子は非負のオペランドに対してのみ使用されるため、商と余りは常に非負になります。

break 文は最も内側のループから抜け出します（C 言語と同様）。

オーバーフローとは、整数変数の最大値を超える値を計算しようとすることです。

3. Bootstring の説明

Bootstring は、任意のコードポイントのシーケンス（「拡張文字列」）を基本コードポイントのシーケンス（「基本文字列」）として表現します。このセクションでは、その表現について説明します。セクション 6「Bootstring アルゴリズム」では、アルゴリズムを擬似コードとして示します。セクション 7.1「デコードトレース」とセクション 7.2「エンコーディングトレース」では、サンプル入力に対するアルゴリズムのトレースを示します。

以下のセクションでは、Bootstring で使用される 4 つの手法について説明します。「基本コードポイント分離」は、拡張文字列に含まれる基本コードポイントを単純にすべて一度にコピーする、非常に単純かつ効率的なエンコードです。「挿入非ソートコーディング」は、基本コードポイント以外のコードを差分としてエンコードし、出現順ではなく数値順に処理します。これにより、通常は差分が小さくなります。差分は「一般化可変長整数」として表現され、基本コードポイントを使用して非負整数を表します。この整数表現のパラメータは、「バイアス適応」を使用して動的に調整され、連続するデルタが同様の大きさを持つ場合の効率が向上します。

3.1. 基本コードポイントの分離 Basic code point segregation

拡張文字列に出現するすべての基本コードポイントは、基本文字列の先頭に元の順序でリテラル表現され、基本コードポイントの数が0以外の場合（かつその場合のみ）、その後に区切り文字が続きます。区切り文字は特定の基本コードポイントであり、基本文字列の残りの部分には出現しません。したがって、デコーダーは最後の区切り文字をスキャンすることで、リテラル部分（存在する場合）の終了を見つけることができます。

3.2 挿入非ソート符号化 Insertion unsort coding

基本文字列の残りの部分（最後の区切り文字が存在する場合はその後ろの部分）は、セクション3.3で説明されている一般化可変長整数として、非負整数デルタのシーケンスを表します。デルタの意味は、デコーダーの観点から理解するのが最も適切です。

デコーダーは拡張文字列を段階的に構築します。当初、拡張文字列は基本文字列のリテラル部分（最後の区切り文字を除く）のコピーです。デコーダーは、各デルタごとに1つずつ、非基本コードポイントを拡張文字列に挿入し、最終的にデコードされた文字列を生成します。

このプロセスの中心となるのは、インデックス i とカウンター n という2つの状態変数を持つステートマシンです。インデックス i は拡張文字列内の位置を指し、0（先頭位置）から拡張文字列の現在の長さ（現在の終端を超える位置）までの範囲をとります。現在の状態が <n,i> の場合、次の状態は、i が拡張文字列の長さより短い場合は <n,i+1>、i が拡張文字列の長さに等しい場合は <n+1,0> になります。つまり、状態が変化するたびに i が増加し、必要に応じて 0 にラップアラウンドします。n はラップアラウンドの回数をカウントします。

状態は常に単調に進むことに注意してください（デコーダーが以前の状態に戻ることはできません）。各状態において、挿入が行われるか行われないかのどちらかです。特定の状態では、最大で1回の挿入が行われます。挿入は、拡張文字列の位置 i に n の値を挿入します。デルタは、この一連のイベントのランレングス符号化です。つまり、挿入状態の前にある非挿入状態の連続の長さです。したがって、デコーダーは各デルタに対して、デルタ状態の変化、挿入、そしてさらにもう1つの状態の変化を実行します。（実装では各状態の変化を個別に実行する必要はなく、代わりに除算と剰余の計算を使用して次の挿入状態を直接計算できます。）挿入されたコードポイントが基本コードポイントである場合はエラーとなります（基本コードポイントは、セクション3.1で説明したように分離されていると想定されているため）。

エンコーダーの主なタスクは、デコーダーが目的の文字列を構築するために必要なデルタのシーケンスを導出することです。これは、デコーダーが挿入する必要がある次のコードポイントを拡張文字列内で繰り返しスキャンし、デコーダーが実行する必要がある状態変化の回数をカウントすることで実現できます。ただし、デコーダーの拡張文字列には、既に挿入されているコードポイントのみが含まれることに留意してください。セクション 6.3「エンコード手順」では正確なアルゴリズムが説明されています。

3.3 一般化可変長整数 Generalized variable-length integers

従来の整数表現では、基数(base)は桁を表す異なる記号の数であり、その値は0からbase-1までです。最下位桁(the least significant digit)をdigit_0、次の下位桁をdigit_1、以下同様に表します。表現される値は、digit_j * w(j) のjに対する和です。ここで、w(j) = base^j は位置jの重み（スケール係数）です。例えば、基数8の整数437の場合、桁は7、3、4で、重みは1、8、64なので、値は7 + 3*8 + 4*64 = 287となります。この表現には2つの欠点があります。1つは、各値に複数のエンコードが存在することです（最上位桁に余分なゼロが存在する可能性があるため）。これは、一意のエンコードが必要な場合に不便です。

第二に、整数は自己境界を持たないため、複数の整数を連結すると、それらの境界が失われます。

一般化可変長表現は、これら2つの問題を解決します。桁の値は依然として0からbase-1までですが、今度は整数が閾値( thresholds) t(j)によって自己境界を持つようになります。閾値t(j)はそれぞれ0からbase-1までの範囲にあります。最上位桁である1桁だけが、digit_j < t(j)を満たします。したがって、複数の整数を連結した場合、リトルエンディアン（最下位桁が先頭）の場合は最初の桁から、ビッグエンディアン（最上位桁が先頭）の場合は最後の桁から、簡単に分離できます。前と同様に、値は j について digit_j * w(j) の合計ですが、重みが異なります。

w(0) = 1

w(j) = w(j-1) * (base - t(j-1)) (j > 0 の場合)

例えば、8 進数のリトルエンディアンシーケンス 734251... を考えます。しきい値が 2、3、5、5、5、5... だとします。これは、重みが 1、1*(8-2) = 6、6*(8-3) = 30、30*(8-5) = 90、90*(8-5) = 270 などであることを意味します。7 は 2 以上、3 は 3 以上ですが、4 は 5 未満なので、4 が最後の桁になります。 734 の値は 7*1 + 3*6 + 4*30 = 145 です。次の整数は 251 で、その値は 2*1 + 5*6 + 1*30 = 62 です。この表現のデコードは、従来の整数のデコードと非常に似ています。まず、現在の値 N = 0、重み w = 1 から始めます。次の桁 d を取得し、N を d * w だけ増加させます。d が現在のしきい値 (t) より小さい場合は停止し、それ以外の場合は w を (base - t) 倍して、次の位置に合わせて t を更新し、これを繰り返します。

この表現のエンコードは、従来の整数のエンコードと似ています。N < t の場合は N の桁を 1 つ出力して停止し、それ以外の場合は t + ((N - t) mod (base - t)) の桁を出力し、N を (N - t) div (base - t) で置き換え、次の位置に合わせて t を更新し、これを繰り返します。

t(j) の任意の値集合に対して、各非負整数値には、正確に1つの一般化された可変長表現が存在します。

ブートストリングは、最初の値からデルタを分離できるように、リトルエンディアン順序を使用します。t(j) の値は、定数 base、tmin、tmax、および状態変数bias によって定義されます。

t(j) = base * (j + 1) -bias

tmin から tmax の範囲にクランプされます。

クランプとは、式の結果が tmin より小さい値または tmax より大きい値である場合、それぞれ t(j) = tmin または tmax となることを意味します。(セクション 6「ブートストリングアルゴリズム」の擬似コードでは、パフォーマンス上の理由から、式 base * (j + 1) を k で表しています。) これらの t(j) 値により、表現はバイアスによって決定される特定の範囲内の整数を優先します。

3.4 バイアス適応 Bias adaptation

各デルタがエンコードまたはデコードされた後、次のデルタのバイアスは以下のように設定されます。

1. 次のステップでオーバーフローが発生しないように、デルタはスケーリングされます。

let delta = delta div 2

ただし、これが最初のデルタの場合、除数は2ではなく、dampと呼ばれる定数です。これは、2番目のデルタが通常1番目のデルタよりもはるかに小さいことを補正します。

2. 次のデルタがより長い文字列に挿入されることを補正するために、デルタが増加します。

let delta = delta + (delta div numpoints)

numpointsは、これまでにエンコード/デコードされたコードポイントの総数です（このデルタ自体に対応するコードポイントと基本コードポイントを含みます）。

3. デルタは閾値内に収まるまで繰り返し除算され、次のデルタを表すために必要な最小桁数を予測します。

while delta > ((base - tmin) * tmax) div 2

do let delta = delta div (base - tmin)

4. バイアスを設定します。

let bias =

(base * 手順3で実行された除算回数) +

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

この手順の目的は、現在のデルタが次のデルタの大きさの目安となることです。そのため、t(j) は、最後になると予想される桁から上位桁までは tmax に設定され、下位桁からは最後から3番目になると予想される桁まで tmin に設定され、最後から2番目になると予想される桁までは tmin と tmax の間のどこかに設定されます。

(予想される最後の桁が不要であること (それが不十分になる危険性があるため)。

4. Bootsrtingパラメータ Bootstring parameter

基本コードポイントの集合が与えられた場合、そのうちの1つを区切り文字として指定する必要があります。baseは、残りの識別可能な基本コードポイントの数よりも大きくすることはできません。0からbase - 1までの範囲の数字値は、区切り文字以外の個別の基本コードポイントに関連付ける必要があります。場合によっては、複数のコードポイントが同じ数字値を持つ必要があります。例えば、基本文字列が大文字と小文字を区別しない場合、同じ文字の大文字と小文字は等価である必要があります。

nの初期値は、拡張文字列に出現する可能性のある最小の非基本コードポイントよりも大きくすることはできません。

残りの5つのパラメータ（tmin、tmax、skew、damp、およびbiasの初期値）は、以下の制約を満たす必要があります。

0 <= tmin <= tmax <= base-1

skew >= 1

damp >= 2

initial_bias mod base <= base - tmin

制約が満たされている場合、これらの5つのパラメータは効率には影響しますが、正確性には影響しません。これらは経験的に選択するのが最適です。

大文字と小文字が混在するアノテーションのサポートが必要な場合（付録Aを参照）、0からtmax-1に対応するコードポイントがすべて大文字と小文字の両方であることを確認してください。

5. Punycode のパラメータ値 Parameter values for Punycode

Punycode は以下の Bootstring パラメータ値を使用します。

base = 36、tmin = 1、tmax = 26、skew = 38、damp = 700、initial_bias = 72、initial_n = 128 = 0x80

table:code point

コードポイント 数字値

------------ ----------------------

41..5A (A～Z) = それぞれ0～25

61..7A (a～z) = それぞれ0～25

30..39 (0～9) = それぞれ26～35

デコーダーは、大文字と小文字の両方（両方の混在を含む）の文字を認識する必要があります。エンコーダーは、大文字と小文字の混合注釈（付録 A を参照）を使用しない限り、大文字のみ、または小文字のみを出力するべきです（SHOULD）。

おそらくほとんどのユーザーは、エンコードされた文字列を手動で入力したり（カットアンドペーストではなく）入力したりすることはないでしょう。しかし、そうするユーザーは、以下の文字セットの間に視覚的な曖昧さが生じる可能性があることに注意する必要があります。

G 6 I l 1 O 0 S 5 U V Z 2

このような曖昧さは通常、文脈によって解決されますが、Punycode でエンコードされた文字列では、人間には文脈が分かりません。

6. ブートストリングアルゴリズム

パラメータが特定の条件（Punycode が満たす条件）を満たす場合、擬似コードの一部を省略できます。これらの部分は{括弧}で囲まれており、擬似コードの直後の注記で省略可能な条件が説明されています。

形式的には、コードポイントは整数であるため、擬似コードではコードポイントに対して直接算術演算を実行できるものと想定しています。一部のプログラミング言語では、コードポイントと整数間の明示的な変換が必要になる場合があります。

6.1 バイアス適応関数

code:adapt

function adapt(delta,numpoints,firsttime):

if firsttime then let delta = delta div dump

else let delta = delta div 2

let 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

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

adapt() 内での delta と k への変更が、エンコード/デコード手順内の同名の変数に影響を与えるかどうかは問題ではありません。なぜなら、adapt() を呼び出した後、呼び出し元はそれらの変数を上書きする前に読み込まないからです。

6.2 デコード手順

code:doceding

let n = initial_n

let i = 0

let bias = initial_bias

let output = 0 から始まるインデックスの空文字列

最後の区切り文字（もしあれば）の前のすべてのコードポイントを消費する

そしてそれらを output にコピーする。基本コードポイント以外のコードポイントがあれば失敗する

消費されたコードポイントが 0 個を超える場合は、さらに 1 個消費する

（これが最後の区切り文字となる）

while 入力が尽きるまでは、do begin とする

let oldi = i

let w = 1

for k = base to 無限大まで、base の刻みで do begin

コードポイントを 1 個消費する。消費するコードポイントがない場合は失敗する

let digit = コードポイントの数字値とする。数字がない場合は失敗する

let i = i + digit * w とする。オーバーフローの場合は失敗する

let t = tmin if k <= bias {+ tmin}, または

tmax if k >= bias + tmax, それ以外の場合は k - bias とする

if digit < t then break

let w = w * (base - t) とする。オーバーフローで失敗

end

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

let n = n + i div (length(output) + 1), オーバーフローで失敗

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

{n が基本コードポイントの場合、失敗}

output の i 番地に n を挿入

increment i

end

中括弧で囲まれた文全体（n が基本コードポイントであるかどうかのチェック）は、initial_n がすべての基本コードポイントを超える場合（Punycode ではこれが当てはまります）、n が initial_n より小さくなることはないため省略できます。

t の代入において、t が tmin から tmax の範囲にクランプされる場合、「+ tmin」は常に省略できます。これにより、bias < k <bias + tmin の場合にクランプ計算が不正確になりますが、bias の計算方法とパラメータの制約により、これは発生しません。

デコーダーの状態は単調にしか進むことができず、デルタの表現は1つしかないため、与えられた整数列を表現できるエンコードされた文字列は1つしかありません。エラー条件は、無効なコードポイント、予期しない入力の終了、オーバーフロー、そしてリテラルではなくデルタを使用してエンコードされた基本コードポイントのみです。上記のようにデコーダーがこれらのエラーで失敗した場合、2つの異なる入力に対して同じ出力を生成することはできません。この特性がなければ、エンコードの一意性を保証するために、出力を再エンコードし、入力と一致することを確認する必要があったでしょう。

(略)

RFC 訳　おわり

-------

例

Punycodeの前の正規化を省略

Punicodeだけだと大文字・小文字を区別する

語

基本文字列 128未満で表現したPunycode文字列

拡張文字列 Unicodeで表現した全体の文字列

文字単位で処理するのでコード系はUCS-4 (UTF-32)のcode pointで扱う

UTF-16ではサロゲートペアでいろいろ駄目になる

圧縮しやすいように非ASCII文字はUnicode順(昇順)に追加するという形式になっている

Bootstringという手法でASCII(基本文字列)と非ASCII部分のような分け方になるが、Bootstringでは分ける基準は特定のコードではないのでASCIIと非ASCIIという分け方ではなくてもいいPunicodeの基準が128というだけ。

1. コード分離

RFC 3942

3.1. 基本コードポイントの分離 Basic code point segregation

3.2. 挿入非ソート符号化

最初に基本文字列(<128)とそれ以外の文字だけの拡張文字列に分ける、拡張文字列側はUnicodeの昇順にASCII側に1文字ずつ挿入していくとUnicodeに復元できるという順にする

分離する場合は逆に後方のUnicodeの大きい方からコードと位置を記録しながら消していくと基本コードポイントの分離も完了する

3年B組金八先生

基本文字列

3B

拡張文字列 コード順

先八年生組金

3B

2文字で挿入箇所は3箇所 0, 1, 2番目

%u5148 先 2

3B先

挿入箇所は4箇所 0, 1, 2, 3番目

%u516B 八 2

3B八先

%u5E74 年 1

3年B八先

%u751F 生 5

3年B八先生

%u7D44 組 3

3年B組八先生

%u91D1 金 4

3年B組金八先生

同じ文字があるときは先頭から並べる

順番と位置を都合よく残したいのでUnicodeの大きい方から分離していくと楽かも

code pointと位置を合わせて(n, i) という1つのコードにしながらその差分をとっていく

nがcode point, i が位置

差分なので0相当の基準もあり、code point 128 の位置 0 という情報が最小なのでそこが基準になる

位置は上限があり、code point は上限はあるがいつ拡張されるかもわからないので上限がないようなもの

ということでcode point * 位置の候補数 + 位置 という重み付けになる

ラベルの長さが63文字くらいなので0x10ffff文字なcode point とあわせても32bitに収まる

最初の文字

これを差分で計算するともっと小さくできるので、

ASCII以外で最初に挿入できる文字は0x80で位置が0というところを基準として差分をとる

基準 (0x80, 0) 0x80 * 3 + 0 = 0x180

0xF3DA - 0x180 で 0xF25A (62042)が最初の差分的コード

1文字追加すると候補数も1増えるので

文字が変わっても、位置が変わっても、code point * 位置の候補数 + 位置 の順番が変わることはない

次の基準

同じ文字が続くこともあるので次に挿入可能な (0x5148,3) が新しい基準になる。位置の候補数(挿入可能な場所)は4箇所に増えている。

基準 0x5148 * 4 + 3 = 0x14523

0xF3DA に 0x5148 + 1 を足してもいい

0x145AE - 0x14523 = 0x8B (139) ということで次の差分は小さくなったがあんまり小さくなることはないかもしれない

table:deltaっぽい

code code 基準base base 差16進 10進

先 (0x5148,2) 0x5148 * 3 + 2 0xF3DA - (0x80,0) 0x80 * 3 + 0 0x180 0xF25A 62042

八 (0x516B,2) 0x516B * 4 + 2 0x145AE - (0x5148,3) 0x5148 * 4 + 3 0x14523 0x8B 139

年 (0x5E74,1) 0x5E74 * 5 + 1 0x1D845 - (0x516B,3) 0x516B * 5 + 3 0x1971A 0x412B 16683

生 (0x751F,5) 0x751F * 6 + 5 0x2BEBF - (0x5E74,2) 0x5E74 * 6 + 2 0x236BA 0x8805 34821

組 (0x7D44,3) 0x7D44 * 7 + 3 0x36CDF - (0x751F,6) 0x751F * 7 + 6 0x333DF 0x3900 14592

金 (0x91D1,4) 0x91D1 * 8 + 4 0x48E8C - (0x7D44,4) 0x7D44 * 8 + 4 0x3EA24 0xA468 42088

ASCIIな文字に変換するので使える文字はa-zと0-9で36文字

3.3. の t(i) から

t(0) は1

t(0) <= n なので

n - t

(基本と拡張の分離)

ASCII文字と圧縮コードの堺目にデリミタとか呼ばれる'-'を入れる。(ASCII文字があるとき)

基本文字列(ASCII文字)しかなければここで終了 Punycodeでなければ最後の - を取る?

あとで頭にxn-- を付けてASCIIのラベルと区別するのでASCIIがなければデリミタを省略する?

3B-

DNSのラベルでは最初と最後に - を使えないのでどちらかのみで追加すると使えない

最後の-がデリミタなのでラベル中の-とも区別可能

変な符号

xn---

xn----

3.3. 一般化可変長整数 Generalized variable-length integers

次は漢字を圧縮変換的なことをしていく

ステートマシンという考え方らしいよ