Punycode编码.doc

一 Punycode 基于的思想1.1 可变长整数引入的原因Punycode是基于36进制数的编码格式，由a.z0.9表示0-35的可变长整数。而由于普通的可变长整数连接在一起无法区分各个整数的界限如，734651，无法区分是，7,34651这两个整数，或者是734,651这两个数于是，punycode在每一位引入阈值，t(j)（从低位到高位）每一位有对应的权重和权值。恰好只有一个权值最大的digit_j2,3=3,2 (base - tmin) * tmax) / 2; k += base) delta /= base - tmin; 4.得到bias 的值 k + (base - tmin + 1) * delta / (delta + skew);以上过程被封装在下面这个函数中static punycode_uint adapt (punycode_uint delta, punycode_uint numpoints, int firsttime)权重权重的计算公式如下W(0) = 1 W (j) = w( j-1 ) * (base - t(j-1) ) 当j0时因而，一个数的值等于其权值乘以对应的权重之和。二Punycode 编码过程2.1 流程图h=b=outh是输出中的序号b是输入中的序号对应代码中delta= (m-n)*(h+1)找出剩余字Unicode最小值【1】，用当前最小值减去前一个最小值乘以序号加一得到待编码项delta记录当前文字序号。（punycode编码是根据Unicode差值以及序号进行的）扫描整个输入，将ASII码部分按照原来的次序保存在前面的部分，用-符号分隔。输出流序号递增。根据delta，h，b，即增量【2】，排序后序号，起始序号。计算出每一位对应的阈值，权值，再将每一位权值编码成36进制数【3】跳入下一个字操作，处理所有增量【1】 这里对应的代码是for (m = maxint, j = 0; j = n & inputj = max_out) return punycode_big_output; t = k = bias + tmax ? tmax : k - bias; if (q t) break; outputout+ = encode_digit (t + (q - t) % (base - t), 0); q = (q - t) / (base - t); outputout+ = encode_digit (q, case_flags & case_flagsj); bias = adapt (delta, h + 1, h = b); delta = 0; +h;三，关于每个字的编码位数由于，被编码的数是Unicode的差值以及位置改变数的积，因此，当相邻的两个字一样的话，则，Unicode差值为0，则对应的编码为a（36进制中表示0），故，最少有一位。而，punycode编码的权重中，达到第四位时，w(4) =w (3)*(base-t(j-1),可知，w（4）的最小值约为35 3=42875，乘以权值，完全足以表示Unicode间的差值，因而，最大位数为4位。四，编码示例4.1 最简单的情况，仅有一个汉字如字符串为“中”“中”对应的Unicode值为 20013，则当前最小m = 20013 ，而前一个最小值n为初始值initial_n = 128,”中”所在的位置h= 0，所以，delta=(20013-128)*(0+1) = 19885接下来对19885编码成36进制数。根据第一节中的公式，可以得出，t(0) = 1 对应的权值为 5 ，编码为f ，权重为 1t(1) = 1 对应的权值为 8 ，编码为I ，权重为1*（36-1）=35t(2) = 26 对应的权值为 16，编码为q ，权重为 35*（36-1）= 352 = 1225可以验算5*1 + 8 *35 + 16 *1225 =19885 = delta所以，“中“字的编码为xnfiq4.2 汉字和一个字符如字符“中a“首先，会扫描字符串，发现有ASCII字符a，因而，会将a放在前半部分，并与后部分以分隔符-分割“中”对应的Unicode值为 20013，则当前最小m = 20013 ，而前一个最小值n为初始值initial_n = 128,”中”所在的位置h= 1，所以，delta=(20013-128)*(1+1) = 39770接下来对39770编码成36进制数。根据第一节中的公式，可以得出，t(0) = 1 对应的权值为 10 ，编码为k ，权重为 1t(1) = 1 对应的权值为 16 ，编码为 q ，权重为1*（36-1）=35t(2) = 26 对应的权值为 32，编码为6 ，权重为 35*（36-1）= 352 = 1225t(3) = 26 对应的权值为 0，编码为a ，权重为 1225*（36-1）= 352 = 42875可以验算10*1 + 16 *35 + 32 *1225 + 0* 42875 =39770 = delta所以，“中“字的编码为xna-kq6a4.3 两个相同的汉字如字符“中中“中”对应的Unicode值为 20013，则当前最小m = 20013 ，而前一个最小值n为初始值initial_n = 128,”中”所在的位置h= 0，所以，delta1=(20013-128)*(0+1) = 19885接下来对19885编码成36进制数。根据第一节中的公式，可以得出，t(0) = 1 对应的权值为 5 ，编码为f ，权重为 1t(1) = 1 对应的权值为 8 ，编码为 i ，权重为1*（36-1）=35t(2) = 26 对应的权值为 16，编码为q ，权重为 35*（36-1）= 352 = 1225可以验算5*1 + 8 *35 + 16 *1225 =19885 = delta1到处理第二个字时：delta2 =(m-n)*(h+1) =(20013-20013)*(1+1)=0t(0) = 15 对应的权值为 0，编码为a ，权重为 10*1= 0=delta所以，“中“字的编码为xnfiqa4.4 两个不同的汉字如字符“中国“中”对应的Unicode值为 20013，则当前最小m = 20013 ，而前一个最小值n为初始值initial_n = 128,”中”所在的位置h= 0，所以，delta1=(20013-128)*(0+1) = 19885n=m = 20013接下来对19885编码成36进制数。根据第一节中的公式，可以得出，t(0) = 1 对应的权值为 5 ，编码为f ，权重为 1t(1) = 1 对应的权值为 8 ，编码为 i ，权重为1*（36-1）=35t(2) = 26 对应的权值为 16，编码为q ，权重为 35*（36-1）= 352 = 1225可以验算5*1 + 8 *35 + 16 *1225 =19885 = delta1到处理第二个字时：“国”对应的Unicode值为 22269，则当前最小m = 22269 ，而前一个最小值n为20013,”国”所在的位置h= 1，所以，delta2=(22269-20013)*(1+1) = 4512t(0) = 15 对应的权值为 18 ，编码为s ，权重为 1t(1) = 26 对应的权值为 34 ，编码为 8 ，权重为1*（36-15）=21t(2) = 26 对应的权值为 18，编码为s ，权重为 21*（36-26）= 210可以验算18*1 + 34 *21 + 18 *210 =4512 = delta2所以，“中“字的编码为xnfiqs8s关于punycode编码后长度问题有关带有ASCII字符的讨论由于punycode的每一位编码长度主要由delta决定，delta = （m-n）* （h+1）。考虑要使得delta最大，则要求m与n的差距最大，同时，这个m所代表的汉子所在的位置h，必须在后方，因此，考虑极限情况让字符串前方都是最小字母 a，汉字取Unicode值最大的龥，同时有111个aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa龥编码后的字符串为：xnaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa-n8838a 可以看到，龥字被编码成了六位字符串，然而，由于ASCII字符的存在，编码扩展比接近为1有关不带有ASCII字符的讨论在汉字中，Unicode值最大的汉字是龥，最小的汉字是怑，这两个汉字不同顺序的编码分别为：怑龥：xn-97t482l龥怑：xn-97t382l前三位一样，是因为，在编码过程中，对所有字的Unicode进行了排序，从而，两字Unicode之