in java

punycodeのアルゴリズム的な話。

punycodeは日本語ドメインで使われているエンコード方法です。
このエンコードはドメインという文字数が限られた環境で使われるためBase64などと比べ圧縮率の高いエンコードとなっています。
そのため周りくどい変換をしています。
自分もよく分かっていないのでこの投稿を書きながら勉強するために書いていきたいと思います。

参考資料:
Punycode: アプリケーションにおいてドメイン名国際化(IDNA)を行うためのUnicodeのBootstringエンコーディング

punycodeの基本:
1.基本文字と拡張文字を分離
2.分離した拡張文字を文字コード順にソート
3.ソートした文字コードの差分に処理順をかけて挿入位置の数字を足す

基本はデコードの処理で説明するとわかりやすいです。
参考資料でも使われている「3年B組金八先生」を簡易的にデコードしていきたいと思います。
まずpunycodeで「3年B組金八先生」は「xn--3B-ww4c5e180e575a65lsy2b」となっています。
最初のnx–はドメインでpunycodeであることを表すための接頭子でなくても構いません。
次に「3B-ww4c5e180e575a65lsy2b」の「-」で分けて、前の部分が基本文字部分、後ろの部分が拡張文字部分です。
でこの後ろの部分は数字の羅列で一般化可変長整数というものをつかっているのですが、それはまた次回にして、数字に直すと
62042,139,16683,16683,14592,42088となっています。
n = 128;
n += 62042/3;
n = 20808;
62042%3 = 2;
ここで nの20808が「先」の文字コードで「62042%3 = 2」が文字の挿入位置です。
よって出力文字列「[0]3[1]B[2]」の2の位置に先を追加して「3B先」となります。
次に

n += ((2+1)+139)/4; //ここの2は「62042%3 = 2;」の2です。1は処理上足される数字
n=20808+35
n=20843
((2+1)+139)/4 = 2;
ここで nの20843が「八」の文字コードで「((2+1)+139)/4 = 2」が文字の挿入位置です。
よって出力文字列「[0]3[1]B[2]先[3]」の2の位置に先を追加して「3B八先」となります。

これを繰り返して行くことで差分的に文字列を構築して元の文字列にデコードします。

次にエンコードしていきたいと思います。

1. コード化

文字 3 B
hex u+0033 u+5E74 U+0042 u+7D44 u+91D1 u+516B u+5148 u+751F
int 51 24180 66 32068 37329 20843 20808 29983

2. 元からドメインとして使える文字とマルチバイト文字を分けマルチバイト文字を文字コード順に
・元からドメインとして使える文字
「3B」
・マルチバイト文字
「年組金八先生」
・文字コード順

文字
hex u+5148 u+516B u+5E74 u+751F u+7D44 u+91D1
int 20808 20843 24180 29983 32068 37329

3. エンコード
この処理は少し複雑です。

ここではdelta,n,m,c,hの5変数を使っていく
・ delta:この数値を変化させ記録していく
・ n:次のソート文字選択時に前の文字を取得するために使用
・ m:ソート文字を順に入れる変数
・ c:原文文字を順に入れる変数
・ h:なん文字目の処理か

なお、nはpunycodeで初期値が定められている。
n = 128;

更にhはなん文字目かの処理で例の文字列では既に「3B」があるので
h=2;

またdeltaの初期値は0でソート文字を選択した時delta+=(m-n)*h
[原文の1文字]<[ソート文字の1文字]だったらdeltaを+1する。 [原文の1文字]=[ソート文字の1文字]だったらdeltaを記録しdeltaを0にする。 ソート文字を変更した時にdeltaを+1する。 の3つです。 これをコード化するとこのようになります。 次に処理を少し追っていきます。 n=128; h=2; delta=0; h++; delta += (m - n) * h; delta += (「先」- 128)*3; delta = 0 + (20808 - 128)*3; delta = 62040; n = 「先」+ 1; n = 20809;

文字 3 B
51 24180 66 32068 37329 20843 20808 29983
「先」 20808 20808 20808 20808 20808 20808 20808 20808
比較
delta 62041(+1) 62041 62042(+1) 62042 62042 62042 (記録:62042)0 0
h 3 3 3 3 3 3 4 4

delta ++; (delta = 1)

delta += (m – n) * h;
delta += (「八」- 20809)*4;
delta = 1 + (20843 – 20809)*4;
delta = 137;

n = 「八」+ 1;
n = 20844;

文字 3 B
51 24180 66 32068 37329 20843 20808 29983
「八」 20843 20843 20843 20843 20843 20843 20843 20843
比較
delta 138(+1) 138 139(+1) 139 139 (記録:139)0 1(+1) 1
h 4 4 4 4 4 5 5 5

同様にdeltaを計算していくと以下のようになる

文字
delta 62042 139 16683 34821 14592 42088

punycodeは最終的に
 xn--3B-ww4c5e180e575a65lsy2b
のようになります。
ですがまだ数字の状態です。
次の記事でこのpunycodeのフォーマットにしていきたいと思います。


Related Posts

Add a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

*
To prove you're a person (not a spam script), type the security word shown in the picture. Click on the picture to hear an audio file of the word.
Anti-spam image