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

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

 

一、基本名词1、嵌入等级(或嵌入水平) ((level，可翻译为：等级、水平、级别)：表示字符的嵌入层次，数字越大嵌入得越深，需要注意的是，在bidi算法中，字符串中的每个字符都有一个嵌入等级。2、基础方向(base direction)：分段的方向被称为基础方向，基础方向决定了该段文本从浏览器的左侧还是右侧开始书写。3、隔离启动器：是对LRI、RLI、FSI的统称，注意：隔离启动器不包括PDI4、嵌入启动器：是对LRE、RLE、LRO、RLO的统称，注意：嵌入启动器不包括PDF二、运行等级和隔离运行序列1、运行等级(level run)：也称为定向运行(directional run)，是指具有相同嵌入等级的字符所形成的最大子串，该子串与其直接接触的前后字符的嵌入等级不相同，比如ab cd RLE ef gh PDF kk mm，假设分段的嵌入等级为0，则字符a、b、c、d(含其中的空格)的嵌入等级都为0，字符e、f、g、h的嵌入等级都为1，字符k、k、m、m的嵌入等级为0，因此，该字符串共有3个运行等级，分别是子串ab cd，子串ef gh，子串kk mm。2、隔离运行序列(简称为运行序列或序列)：是由一系列运行等级组成的序列，其规则如下：

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

2)、无隔离启动器时：此时每个运行等级构成一个独立的隔离运行序列。3、隔离运行序列具有如下特点：

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

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

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

4、隔离启动器的重要规则：隔离启动器和与其匹配的PDI拥有的嵌入等级是提升之前的原始嵌入等级，而不是提升之后的嵌入等级。5、示例

• 以下示例的“文本”表示实际输入的内容，其中的符号“⋄”不属于文本的内容，该符号只是为了提高示例的清晰度，以方便阅读。
• 以下示例均假设分段的嵌入等级为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 | 构成一个运行等级。
• 其余运行等级的分析方法与以上类似，不再重述。

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、图形法表示运行等级和隔离运行序列

图1为运行等级和隔离运行序列的图形表示法，等级=0的隔离运行序列由4个运行等级组成(虚线上方对应的运行等级)，小括号范围内的运行等级不属于该隔离运行序列，等级=1的隔离运行序列虽然是画在同一行上的，但表示的是3个等级=1的隔离运行序列而不是一个由多个运行等级组成的等级=1的隔离运行序列，等级=0的隔离运行序列才表示的是一个由多个运行等级组成的隔离运行序列。

示例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的运行等级如下所示

|文本1 | → 等级0|文本2 | → 等级1|文本3 | → 等级0|文本4 | → 等级1|文本5 | → 等级0

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

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

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

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

序列1：|文本1 | → 等级0序列2：|文本2 | |文本3 | → 等级1序列3：|文本4 | → 等级0

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

序列1：|文本1 | → 等级0序列2：|文本2 | → 等级1序列3：|文本3 | → 等级0序列4：|文本4 | → 等级1序列5：||文本5 | → 等级0分段3：因含有隔离启动器(其分析方法见示例1)，其隔离运行序列如下(共有3个)序列1：|文本1 ⋄ RLI | | PDI ⋄ RLI | | PDI ⋄ 文本4 | → 等级0序列2：|文本2 | → 等级1序列3：|文本3| → 等级1

 

第4节 bidi算法总览

 

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

一、bidi算法基本规则及思想1、再次提醒：在bidi算法中定向格式化字符是作为一个字符处理的，比如a LRE b，这里共有3个字符，分别是a、LRE、b。2、强字符的方向是确定的，要么为从左向右(称为L类型)，要么为从右向左(称为R类型)，其中AL类型视为R类型。3、最终类型(在不引起混淆的情况下，本文有时会将其简称为类型)：bidi算法会把每个字符(包括定向格式化字符)都转换为L、R、EN、AN四种类型之一，因此，最终类型是指字符的L、R、EN、AN类型。4、bidi算法规定(这是强制规定)：L类型字符的嵌入等级必须是偶数，R类型字符的嵌入等级必须是奇数，若不满足以上要求，需对字符的嵌入等级进行调整(调整规则见I1~I2算法)或作硬性规定，此规则，通常可以反过来理解(注：字符串含有EN、AN时就不能这样理解了)，即，最终的嵌入等级若是奇数，则该字符是R类型，若是偶数，则该字符是L类型。同理，运行等级，分段的嵌入等级也需要满足此规定。5、bidi算法的一个基本思想是，首先确定各个字符的嵌入等级，然后，把所有字符都调整为L、R、EN、AN四种类型之一，并根据字符的这些类型调整字符的嵌入等级为偶数或奇数，然后对调整后具有相同嵌入等级组成的子串进行重排序并显示。也就是说，所有的字符类型，比如ON、LRI、WS、NSM等最后都会被调整为L、R、EN、AN四种类型之一。6、总体来讲，bidi算法分为4大步，即，

• 初次确定各字符的嵌入等级(P、X系列算法)
  
• 调整字符为L、R、EN、AN四种类型之一(W、N系列算法)，即，把字符的类型调整为最终类型
  
• 调整嵌入等级 ( I系列算法)，调整后的嵌入等级为最终嵌入等级
  
• 重排序(L系列算法)。
  

二、周围字符的类型对字符最终类型的影响及bidi调整字符类型的方法1、bidi算法调整字符类型的方法是根据该字符周围字符的类型对该字符的类型进行调整，也就是说，周围字符的类型会对该字符的最终类型产生影响，具体的调整算法详见W和N系列算法。2、强字符、弱字符、中性字符对周围字符的影响1)、强字符会对其前后的中性字符的最终类型产生影响，除L类型的强字符会对之后的EN字符(欧洲数字，弱类型)的最终类型产生影响外，强字符不会对弱字符的最终类型产生影响。从表1可见，大部分的字符都是强字符，比如，阿拉伯字符(从右到左)，汉字(从左到右)、英文字符(从左向右)等。2)、中性字符不会影响周围文本的最终类型，大部分的标点符号和空格都是中性字符，比如符号“;”，“[”，“)”等都是中性字符3)、弱字符不会对其前后字符的最终类型产生影响，数字就是弱字符。3、定向格式化字符对周围字符的影响1)、隔离(LRI、RSI、FSI)范围内的字符不会影响到外部字符的排序，反之亦然。隔离范围内的字符作为一个整体对周围字符的影响与中性字符相同。2)、嵌入(LRE、RLE)范围内的字符会影响到外部字符的排序，反之亦然。嵌入内的字符作为一个整体对周围字符的影响与强字符相同。由于嵌入会对周围字符产生很强的影响从而导致新的问题，因此在支持隔离的平台上，建议使用隔离而不是嵌入。3)、重写格式化字符可以强制改变文本的书写方向，因此存在着安全问题，除非特殊情况，否则不应使用重写格式化字符RLO、LRO。重写范围内的字符作为一个整体对周围字符的影响与强字符相同。三、bidi算法总体概述(详细规则见下一节)1、bidi算法由多个算法组成，每个算法都有一个名称，每个算法又包含多个子算法或步骤，比如P系列算法，共有P1、P2、P3三个步骤，P系列算法是解析字符顺序时的第一步。下面为bidi的各种算法及其作用：

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

2、以下为使用bidi算法的步骤，及各系列算法的主要规则(详细规则见下一节)1)、步骤1：算法编号P1~P3把文本分成段，然后以段为作用域进行后续算法的处理。若段的方向为从左向右(即L)，则分段的嵌入等级为0(偶数)，若段的方向为从右向左(即R)，则分段的嵌入等级为1(奇数)。通常，在分段的嵌入等级确定后，还需要解析出各字符在调整之前的bidi类型2)、步骤2：算法编号X1~X10计算出各字符原始的、调整之前的嵌入等级，在该系列算法中，还会确定出运行等级和隔离运行序列，该步骤的几种基本规则如下：

• 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代替
  

   3)、步骤3：算法编号W1~W7把弱字符调整为L、EN、AN、ON四种类型之一   4)、步骤4：算法编号N0~N2把中性和隔离格式化字符调整为L或R类型   5)、步骤5：算法编号I1~I2根据各个字符的L或R类型调整各字符的嵌入等级，在此步骤之前确定的字符的L类型不一定是偶数，同理R类型也不一定是奇数，该步骤的主要作用是把L类型的嵌入等级调整为偶数，R类型的嵌入等级调整为奇数，其方法比较简单，就是把不符合要求的字符的嵌入等级加1即可。该步骤的调整并不会影响之前确定的运行等级   5)、步骤6：算法编号L1~L4重排序具有相同嵌入等级的子串，并显示。该步骤的主要算法为：从嵌入层次最深的子串开始将所有字符进行反转(即，所有字符按从右向左排序输出)，嵌入多少层就重复多少次该操作，比如，"ab cd ef"嵌入的层次为3层(即嵌入等级为3)，则第1次反转为fe dc ab，第2次在第1次反转后的结果上反转为ab cd ef，第3次在第2次的基础上反转为fe dc ba，最后显示为fe dc ba3、总结：bidi算法需要对各字符的bidi类型、嵌入等级进行调整，但运行等级、隔离运行序列是不会被调整的，一旦确定会保持不变，因此，bidi算法的关键是要正确的调整各字符的bidi类型和嵌入等级，最后再进行反转。 示例3：分析如下字符串的显示顺序，

说明：

• 控制字符RLE和PDF不会被显示
  
• 基础方向假设为L，即分段的嵌入等级为0
  
• 第11和12的个字符是希伯来文(控制字符RLE和PDF分别算一个字符)
  
• 注意：因字符串中包含有从右向左的希伯来文，字处理软件(比如word)显示这些字符串的顺序可能与这些字符的顺序不一致，为避免显示上的混乱，上面的字符串是以图片形式给出的。
  
• 以下解题步骤中的Unicode代码为16进制，嵌入等级中的x表示该字符的嵌入等级不会被考虑，由算法调整后的选项以粗体加灰色背景显示。
  
• 本示例暂不讲解空格的处理方法，
  

1、步骤1：处理分段：由题知基础方向为L，即分段的嵌入等级为0。2、步骤2(X1~X10)：分析各字符bidi类型、计算嵌入等级、运行等级及隔离运行序列(以下简称为序列)

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

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

 5、步骤6：反转各子串

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

 

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

本文作者：黄邦勇帅（原名：黄勇）

声明：本文为 脚本之家专栏作者 投稿，未经允许请勿转载。