Unicode双向算法(bidi算法)详解（一）

脚本之家

你与百万开发者在一起

第1节 理解字符

一、字体的设计原理(字符集、编码、字体三者的关系)

1、字符集：就是各种字符的集合，比如Unicode就是一个字符集，它使用2个字节(即最多65535个)来表示所有的字符。

2、编码：一个字符要能被计算机所接受，需要进行两次编码，因为计算机只能表示二进制，对于人们常使用的10进制来讲不是很方便，因此字符的第一次编码就是把相应的字符使用一个整数值与其相对应，比如ASCII码字符集把字符'a'编码为10进制的61，就是一次编码，Unicode字符集也是一次编码。为了能让计算机的二进制识别，需要把第一次编码后的整数值再次编码为二进制值，比如使用一个字节来表示字符'a'一次编码后的整数值61，再如中文汉字使用两个字节进行表示，再如对于Unicode字符集有3种不同的二次编码方案，分别是UTF-8，UTF-16和UTF-32，目前使用较多的是使用UTF-8来存储的Unicode字符集。

3、字形(glyph)：用于表示字符的外形，比如字母a的ASCII码为61，但这个字母可以以多种外形对其进行书写，再如中文字符中的每一笔画都是一个字形。注：glyph也翻译为图元，图像。其实对象的外形都是使用图元进行描述的。

4、字形与字符的关系：一个字形可以用于表示多个字符，一个字符也可以由多个字形组成，比如中文字符，就经常共享字形，而且是由多个字形组成的。字符的衬线、粗细等都是字形设计的元素。

5、字体：是一个拥有相同设计风格的字形及从字符到字形映射关系的集合，字体使字符能被显示出来，字体是计算机显示文字的一种方式，比如早期电报就把字符表示为一长串数字，这一长串数字就相当于是字符集，当接收到电报后，是使用宋体、草书或者其他形式显示出来，就需要使用字体了，每种字体都有一个相应的名字，比如“Times New Roman”、“宋体”等，相同的字体显示的字符具有相似的风格，比如以宋体显示的字体，其风格都是相似的。另外，字体名通常有版权，是受到法律保护的。

6、计算机显示字符的原理简述：当计算机接收到一串二进制之后，表示的具体是什么字符，需要由字符集来决定，然后字符需要被显示出来(即字体以什么外观进行显示)，这时就需要寻找相应的字体，若字库中没有相应字符的字体，则可能会被显示为乱码，所以要让计算机正确显示文字，不仅编码应正确，还要有相应的字体才行。

1、用户感知字符(user-perceived character)与字形族 (grapheme cluster)

用户感知字符就是指的人们认为的一个字符，字形族是用于近似表示用户感知字符的。计算机中的一个“字符”通常就是一个Unicode代码值，但是，现实中人们认为的一个“字符”，可能并不是由一个Unicode代码值组成，而是由多个Unicode代码值组成的。比如   

2、字符的成形 (shaping)   

3、对字符的处理

由以上可知，用户感知字符与计算机理解的字符是不同的，而人们通常是以用户感知字符对字符进行理解的，因此，就有很多问题需要处理，比如，一个字符串中有多少个用户感知字符(即，怎样确定一个用户感知字符的边界)，怎样对用户感知字符断行，怎样显示等，Unicode标准对这些方面都有详细的描述，有兴趣的读者可参阅Unicode有关这些方面的内容，本文重点介绍Unicode双向排序算法(bidi算法)，bidi算法影响各个Unicode字符的排序顺序，至于字符能否最终成形为用户感知字符、怎样断行等内容不属于bidi算法的范围。

第2节 Unicode字符的分类与定向格式化字符

Unicode为字符定义了很多属性，以用于描述该字符，比如Bidi_Paired_Bracket_Type属性用于描述该字符是开括号(值为open)还是闭括号(值为close)，再如General_Category描述了该字符的通用类别，比如若该字符是行分隔符，则值为Line_Separator，是控制符，则值为Control等。

3、定向格式化字符的分类

字向格式化字符分为隐式定向格式化字符和显示定向格式化字符两大类，显示定向格式化字符又分为显示定向嵌入格式化字符、显示定向重写格式化字符、显示定向隔离格式化字符，分别简称为嵌入格式化字符、重写格式化字符、隔离格式化字符。其中隔离格式化字符是在Unicode 6.3中引入的。具体的分类规则详见表2

4、组合字符

1)、组合字符(Combining character)是指General_Category属性的值为Mc (Spacing Combining Mark，间距组合标记)、Mn (Nonspacing Mark，无间距标记)、Me(Enclosing Mark，嵌入标记)的所有字符。

2)、组合字符通常用于与它的基本字符组合为一个字符，比如

以上字符由字符g (u+0067)和 (U+0308)组合而成，其中字符g就是基本字符，而U+0308就是组合字符。

3)、无间距标记(Mn)通常不单独占据空间位置，其占据的位置取决于它的基本字符。

5、零宽度字符 ( LRM、RLM、ALM )

表2中的LRM、RLM、ALM是一种零宽度字符，可将其理解为在该处插入了一个相应方向的强字符，但该字符是不可见的(宽度为零所以不可见)。比如aLRMb，相当于在a和b之间插入了一个从左向右的强字符，但该字符宽度为零且不可见(即不会被显示)。

6、与定向格式化字符对应的HTML5元素和CSS等效项

1)、HTML5没有提供对LRE、RLE、LRO、RLO的精确等效项，可使用CSS来获取LRE、RLE、LRO、RLO、LRI、RLI、FSI的精确等效项。表3为HTML和CSS与bidi算法的等效情形。由表3可见，在HTML5中，bdi元素更多用于对字符的隔离，以避免文本被周围字符方向性所影响，或避免隔离的文本影响周围字符的方向性，而bdo元素主要用于强制改变文本的方向性。

2)、注意：HTML5与HTML4.0不同，早期版本的bdi元素与隔离(LRI、RLI)相对应，bdo元素与重写(LRO、RLO)相对应。

7、以Unicode代码(即数字)的形式输入字符

1)、注意：定向格式化字符是Unicode字符集中的一个字符，只是不会被显示出来，每个定向格式化字符都有其对应的Unicode代码，比如RLO的Unicode代码为U+202E

2)、Unicode字符可在Word、浏览器、记事本等应用上以Unicode代码的形式输入，定向格式化字符同样可以被输入，但是不会被显示

3)、HTML的格式如下：

&#x+mmmm;(16进制)，或   &#+mmmm;(10进制) 注意：末尾有个分号

      示例：a表示字符a

4)、CSS的格式为：+mmmm(16进制)

      示例：0061表示字符a

• 方法1：输入相应的Unicode代码，然后选中该代码或在该代码末尾按下ALT+x，这时会把相应代码转换为字符，同时在Word中还可使用ALT+x把相应的字符转换为相应的Unicode代码。

• 方法2：按住ALT键不放，然后以10进制的形式输入Unicode代码，然后释放ALT键，便会产生相应的字符，比如，按住ALT键，同时输入97，然后释放ALT时便会产生字符a。

• 方法3：选择【插入】---【符号】---【其他符号】，弹出一个对话框，在该对话框中插入Unicode字符，其界面和使用方法如下图所示

第3节 运行等级与隔离运行序列

1)、含有隔离启动器时：除最后一个运行等级外，隔离运行序列中运行等级的最后一个字符是隔离启动器，与该隔离启动器匹配的PDI是序列中下一个运行等级的第一个字符，也就是说，序列中的运行等级是以隔离启动器结束的(最后一个运行等级除外)，以PDI开始的(除第一个运行等级外)。

1)、每个运行等级只属于一个隔离运行序列，也就是说，不存一个运行等级属于两个序列的情形。

2)、在同一个隔离运行序列中所有的运行等级具有相同的嵌入等级，因为隔离运行序列是以隔离启动器开始一个运行等级，又以与其匹配的PDI开始另一个运行等级，很明显，这两个运行等级具有相同的嵌入等级。

3)、紧随着隔离启动器之后的运行等级会开启一个新的隔离运行序列，与之匹配的PDI之前的运行等级会结束它的隔离运行序列。

• 以下示例的“文本”表示实际输入的内容，其中的符号“⋄”不属于文本的内容，该符号只是为了提高示例的清晰度，以方便阅读。
• 以下示例均假设分段的嵌入等级为0

示例1(含隔离启动器)： 

分析如下文本的运行等级和隔离运行序列

文本1 ⋄ RLI ⋄ 文本2 ⋄ PDI ⋄ 文本3 ⋄ RLI ⋄ 文本4 ⋄ PDI ⋄ RLI⋄ 文本5 ⋄ PDI ⋄ 文本6 

1、运行等级的分析方法：

• |文本1 ⋄ RLI |构成一个动行等级，因为在RLI之后的 |文本2 | 与 |文本1 ⋄ RLI | 的嵌入等级不相同，|文本1 ⋄ RLI |的嵌入等级为0，而 |文本2 | 的嵌入等级为1，因此 |文本1 ⋄ RLI | 构成一个运行等级，其等级为0。此处应用了规则：RLI和与之匹配的PDI的嵌入等级是提升之前的嵌入等级。
• |文本2 | 构成一个运行等级，因为在 |文本2 | 之前的RLI和之后的PDI与 |文本2 | 的嵌入等级不相同，|文本2 | 之前的RLI和之后的PDI的嵌入等级都为0，而 |文本2 | 的嵌入等级为1，因此，|文本2 | 构成一个运行等级。
• 其余运行等级的分析方法与以上类似，不再重述。

• |文本1 ⋄ RLI | 为隔离运行序列中的一个运行等级(以RLI结束)，与该RLI匹配的PDI，即 |文本2 | 之后的PDI是该序列中的下一个运行等级的开始，因此 | PDI ⋄ 文本3 ⋄ RLI | 是该隔序运行序列中的下一个运行等级(以RLI结束)，同理，|文本4 | 之后的   | PDI ⋄ RLI | 是该序列中的再下一个运行等级，| PDI ⋄ 文本6 | 是该序列中的最后一个运行等级，因此，第一个隔离运行序列中的运行等级包含 |文本1 ⋄ RLI | 、| PDI ⋄ 文本3 ⋄ RLI |、 | PDI ⋄ RLI | 、| PDI ⋄ 文本6 | 四个运行等级。

• |文本2 | 独自构成一个隔离运行序列，因为，紧随着隔离启动器之后的运行等级会开启一个新的隔离运行序列，与之匹配的PDI之前的运行等级会结束它的隔离运行序列。|文本2 | 位于 |文本1 ⋄ RLI | 中的RLI之后，同时位于 | PDI ⋄ 文本3 ⋄ RLI | 中的PDI之前，因此 |文本2 | 独自构成一个隔离运行序列。

• 其余隔离运行序列的分析方法与以上相同，不再重述。

3、最终的运行等级和隔离运行序列如下所示：

l 运行等级(共有7个)：

|文本1 ⋄ RLI |  → 等级0

|文本2 | → 等级1

| PDI ⋄ 文本3 ⋄ RLI | → 等级0

|文本4 | → 等级1

| PDI ⋄ RLI | → 等级0

|文本5 | → 等级1

| PDI ⋄ 文本6 | → 等级0

l 隔离运行序列(共有4个)

|文本1 ⋄ RLI | | PDI ⋄ 文本3 ⋄ RLI | | PDI ⋄ RLI | | PDI ⋄ 文本6 | → 等级0

|文本2 | → 等级1

|文本4 | → 等级1

|文本5 | → 等级1

4、图形法表示运行等级和隔离运行序列

示例2(不含隔离启动器)： 

分析如下文本的运行等级和隔离运行序列，本示例主要是要明白以下分段1的文本与分段2和分段3的文本的隔离运行序列的区别

分段1：文本1 ⋄ RLE ⋄ 文本2 ⋄ PDF ⋄ RLE ⋄ 文本3 ⋄ PDF ⋄ 文本4    

分段2：文本1 ⋄ RLE ⋄ 文本2 ⋄ PDF ⋄ 文本3 ⋄ RLE ⋄ 文本4 ⋄ PDF ⋄ 文本5    

分段3：文本1 ⋄ RLI ⋄ 文本2 ⋄ PDI ⋄ RLI ⋄ 文本3 ⋄ PDI ⋄ 文本4    

1、各分段的图形表示法分别如图2、图3、图4所示：

2、运行等级的分析方法：

• 注：根据bidi的算法，字符RLE、LRE、PDF会被移除，因此，分析时可忽略。但是，RLI、LRI、FSI、PDI不会被移除，因此，分析时不可忽略。

• 分段1：很明显文本1、文本4的嵌入等级为0，文本2和文本3的嵌入等级1，因此，分段1共有3个运行等级，如下所示

|文本1 | → 等级0

|文本2 | |文本3 | → 等级1

|文本4 | → 等级0

• 分段2：文本1、文本3、文本5的嵌入等级0，文本2和文本4的嵌入等级都为1，因此，分段2的运行等级如下所示

• 分段3：文本1 ⋄ RLI、PDI ⋄ RLI、PDI ⋄ 文本4的嵌入等级为0，文本2和文本4的嵌入等级为1，因此，分段3的运行等级如下所示

3、隔离运行序列的分析方法：

• 分段1：没有隔离启动器，因此每个运行等级构成一个隔离运行序列，因此，其隔离运行序列共有3个，如下：

分段2：与分段1相同，每个运行等级构成一个隔离运行序列，因此，分段2共有5个隔离运行序列，如下：

第4节 bidi算法总览

对Unicode算法的完整测试，建议在以下由Unicode推荐的网站进行https://www.unicode.org/cldr/utility/bidic.jsp?

• 初次确定各字符的嵌入等级(P、X系列算法)

• 调整字符为L、R、EN、AN四种类型之一(W、N系列算法)，即，把字符的类型调整为最终类型

• 调整嵌入等级 ( I系列算法)，调整后的嵌入等级为最终嵌入等级

• 重排序(L系列算法)。

• P系列算法用于解析分段的嵌入等级
• X系列算法用于解析分段中各个字符的嵌入等级，此步骤解析出的字符并不一定满足L类型的嵌入等级为偶数，R类型为奇数的规则，需在I系列进行调整。
• W系列算法用于解析弱字符的类型，即调整弱字符的类型为最终类型
• N系列算法用于中性和隔离格式化字符的类型为最终类型
• I系列算法用于调整各字符的嵌入等级为奇数或偶数。
• L系列算法用于重排序

• RLE、LRE、RLI、LRI、FSI、LRO、RLO会提升之后的字符的嵌入等级，具体怎样提升的，详见下一小节对X系列算法的讲解。

• PDF、PDI会把之后字符的嵌入等级还原到之前的嵌入等级。

• 算法X9规定，RLE、LRE、RLO、LRO、PDF、BN会被移除，移除后这些了符只会作为占位符，在之后的分析中，这些字符表现得就像不存在一样，但是FSI、LRI、RLI、PDI不会被移除，由于对嵌入等级和字符类型的调整都是在该步骤之后，所以RLE、LRE、RLO、LRO、PDF、BN这些字符对整个字符排序的影响可忽略，其嵌入等级可不考虑，当使用图形法分析时，这些字符的嵌入等级使用x代替

• 控制字符RLE和PDF不会被显示

• 基础方向假设为L，即分段的嵌入等级为0

• 第11和12的个字符是希伯来文(控制字符RLE和PDF分别算一个字符)

• 注意：因字符串中包含有从右向左的希伯来文，字处理软件(比如word)显示这些字符串的顺序可能与这些字符的顺序不一致，为避免显示上的混乱，上面的字符串是以图片形式给出的。

• 以下解题步骤中的Unicode代码为16进制，嵌入等级中的x表示该字符的嵌入等级不会被考虑，由算法调整后的选项以粗体加灰色背景显示。

• 本示例暂不讲解空格的处理方法，

3、步骤3和步骤4：解析弱字符、中性字符、隔离格式化字符

4、步骤5：调整各字符的嵌入等级

 5、步骤6：反转各子串

• 反转等级2：

• 反转等级1，即，在上步基础上的第7~11(含空格，不含控制符)的个字符，该次反转是最终显示顺序，结果为：

参考文献：http://www.unicode.org/reports/tr9/