一种基于XML的流式分页发布方法及系统

摘要

本发明公开了一种基于XML的流式分页发布方法及系统，方法包括以下步骤：1）对满足预先设定的分段条件的XML输入文档进行流化处理，包括分段和重构处理，选择性地进行再一次的流化处理；2）对满足预先设定的分割条件的XML输入文档进行快速分页处理，包括多轮二叉树式分割和重构处理；3）对照终端设备提供的转换样式表，将输入文档转换成其它标准格式的文档输出；4）将具有不同标准格式的文档发送给相应的终端设备。系统的组成包括以下部分：流化处理器，包括分段器和重构器；快速分页器包括分割器和重构器；XSLT转换器；发布服务器。本发明适用于XML文档特别大的场合、提高了转换的可靠性和容错性、灵活性良好、适用面较广。

说明书

技术领域

本发明涉及一种基于XML的分页发布方法及系统。

背景技术

随着信息技术的飞速发展，越来越多的企事业单位都需要操作海量数据，如 医院的医疗数据、交通局的交通数据，电业局的电力数据、规划局的规划数据， 水利局的水文、水利数据，气象局的气象数据，这些数据往往是以XML的形式 存储在服务器中，用户只需要访问服务器上的文档便可以实现数据的获取。但是， 当用户通过PC、手持设备、智能手机等不同的终端设备对服务器上的文档进行访 问时，由于终端显示格式、软件系统存储与读取格式的不同，要想正确接收并显 示数据，就必须对服务器上的文档进行格式转换。目前，XML文档格式转换工具 主要包括：DOM、SAX和XSLT，其中，XSLT作为现在最流行的XML文档格 式转换技术之一，功能十分强大，工作原理却比较简单，如图1所示。

由于在转换的过程中，首先需要将XML源文档解析成DOM树存放在内存 中，文档过大势必会造成内存的溢出。因此，用户在使用PC、手持设备、智能手 机等终端设备读取大数据的过程中，往往会因内存不足或显示屏尺寸过小而无法 正确接收和显示数据。

又因为传统的分页处理过程只是实现了分段处理器的功能，即，对输入文档 进行迭代式的分段处理，所以得到的所有小XML文档都是非“形式良好”的，使 得下一步的转换操作不具备相对独立性，可靠性和容错性也较差，另外迭代的处 理方式还大大地降低了分段处理的速度。

发明内容

为了克服已有基于XML的分页发布方法及系统的不能适用于XML文档过大， 和转换可靠性、容错性、灵活性、适用性要求较高的场合的不足,本发明提供了一 种适用于XML文档过大、转换可靠性、容错性、灵活性、适用性要求较高的场 合下的基于XML的流式分页发布方法及系统。

本发明解决其技术问题所采用的技术方案是：

一种基于XML的流式分页发布方法，所述发布方法包括以下步骤：

（1）流化处理过程：

对于每个大型的XML输入文档，流化处理器先要对其大小进行判断，如果 文档大小不超过预先设定的分段读取阈值，即T_s≤T_m，那么进入步骤（2）处理； 反之，如果文档大小超过预先设定的分段读取阈值，即T_s>T_m，那么流化处理器 将对该文档进行分段和重构处理，处理后将生成两个形式良好的XML文档，一 个大小等于T_m，另一个大小等于T_s-T_m，前者将被送入步骤（2）处理，而后者将 被送往流化处理器进行再一次地判断、分段和重构处理；

（2）快速分页处理过程：

若XML文档F_s0,1的大小远远超过终端设备的需求内存T，即T_s0,1＞＞T，则对 XML文档F_s0,1进行第一轮的分割和重构处理，生成两个“形式良好”的新XML文 档F_s1,1和F_s1,2；接下来再对新生成的两个文档F_s1,1和F_s1,2进行判断和第二轮的分割 和重构处理，即，若两个新生成的文档F_s1,1和F_s1,2仍满足分割条件：T_s1,1＞＞T且 T_s1,2＞＞T，则应同时对这两个文档进行分割和重构处理，生成四个“形式良好”文档 F_s2,1、F_s2,2、F_s2,3和F_s2,4，依此类推，反复地判断、分割和重构，直到某一轮分割 生成的所有XML文档的大小均不超过终端设备的需求内存，分割和重构处理过 程结束；

（3）XSLT转换过程：对照终端设备提供的转换样式表，将输入文档转换成其它 标准格式的文档输出；

（4）发布过程：将具有不同标准格式的文档发送给相应的终端设备。

进一步，所述步骤（1）中，流化处理过程包括分段处理过程和重构处理过程， 所述分段处理过程：

假设现在有一个XML文档F_s，大小为T_s，流化处理器可用的最大内存为T_m， 如果XML文档非常大，远远大于流化处理器可用的最大内存，即T_s＞＞T_m，或者 说，满足条件：T_s≈pT_m，p＞＞1，那么使用流化处理器中的分段器对它进行分段 处理，具体包括以下三个步骤：

第一、读取XML文档F_s；

第二、设定分段读取阈值T_d=T_m；

第三、进行分段处理，生成两个非“形式良好的”XML文档：

①F_s1，大小记为T_s1，T_s1=T_d=T_m；

②F_s2，大小记为T_s2，T_s2=T_s-T_d=T_s-T_m。

更进一步，所述重构处理过程包括初步重构和再重构两个步骤，过程如下：

1.1）读取第三步骤生成的XML文档F_s1；

1.2）将指针定位到尾部；

1.3）向前搜索结束标签的开始标记“</”，并记录其位置为L₁；

1.4）从L₁开始向后搜索相应的结束标记“>”，并记录其位置为L₂，此时会有两 种可能：

如果能够搜到结束标记“>”，那么L₂的值就是该标记的位置值；

反之，如果未能搜到结束标记“>”，这时应将指针定位到L₁处，再一次执 行步骤1.3），得到新的L₁值后，再执行步骤1.4），获取新的L₂值，这个新的L₂值 才是该情况下结束标记的真正位置；

1.5）将因分割而导致的不完整数据从F_s1的尾部移到F_s2的首部；此后将得到 已删除不完整数据的XML文档F_s1，和已添加不完整数据的XML文档F_s2；

1.6）获取因分割而缺失的所有祖先节点的标签名字：

1.6.1）设定读取标志flag=True，当读取的值的长度大小或等于0时， flag=False；

1.6.2）读取步骤1.5）生成的已删除不完整数据的XML文档F_s1，将每个 节点标签名字，空标签名字除外，添加到列表中；

1.6.3）统计列表中的不同元素及其个数，根据形式良好的XML文档的开 始标签和结束标签应配套，空标签要关闭的原理，个数为奇数的元素，第一 个元素除外，即为因分割而缺失的祖先节点标签名字，将这些标签名字放入 另一个列表中，获取这些节点标签名字时，应保持其在列表中的原有顺序不 变；

1.7）将步骤1.5）生成的两个XML文档F_s1和F_s2构造成形式良好的XML文 档：

1.7.1）把步骤1.6.3）得到的列表中的元素用作结束标签倒序地添加到已删 除不完整数据的XML文档F_s1的尾部；

1.7.2）把步骤1.6.3）得到的列表中的元素，第一个元素除外，用作开始标 签正序地添加到已添加不完整数据的XML文档F_s2的首部；

1.7.3）把步骤1.6.3）得到的列表中的第一个元素，即声明标签名字，用作 开始标签添加到步骤1.7.2）得到的XML文档F_s2的首部。

再进一步，所述步骤（2）中，假设现在有一个XML文档F_s0,1，其大小为T_s0,1，终 端设备的需求内存为T，如果XML文档非常大，远远大于终端设备的需求内存， 即T_s0,1＞＞T，或者说，满足条件：T_s0,1≈qT，q＞＞1，对这个XML文档进行第一轮 的分割和重构处理，过程如下：

2.1）读取XML文档F_s0,1；

2.2）设定一个分割阈值

2.3）进行第一轮分割处理，此轮包括一次分割处理过程，分割后得到两个非 “形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1，1=T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2=T_f0,1；

2.4）对步骤2.3）生成的两个XML文档F_s1,1和F_s1,2进行重构处理，处理后将 得到两个新的“形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1≈T_f0，1；

②F_s1,2，大小记为T_s1,2，T_s1,2≈T_f0,1；

此时第一轮的分割和重构处理过程结束，接下来我们将设定两个分割阈值 和对步骤2.4）生成的两个XML文档F_s1,1和F_s1,2进行第二轮 的分割和重构处理，处理后将得到四个“形式良好”的文档F_s2,1、F_s2,2、F_s2,3、F_s2,4， 大小分别等于T_f1,1、T_f1,1、T_f1,2、T_f1,2，依此类推，设定2^n-1个分割阈值对2^n-1个XML文档F_s(n-1),k,k=1,…,2^n-1进行第n轮的分割 和重构处理，处理后将得到2ⁿ个“形式良好”的XML文档F_sn,k,k=1,…,2ⁿ，至此， 所有文档的大小都不超过终端设备的需求内存，即T_sn,k≤T,k=1,…,2ⁿ，不再满足 分割条件，分割和重构处理结束。

一种基于XML的流式分页发布系统，所述发布系统包括：

流化处理器：对于每个大型的XML输入文档，流化处理器先要对其大小进 行判断，如果文档大小不超过预先设定的分段读取阈值，即T_s≤T_m，那么将此文 档交由快速分页器处理；反之，如果文档大小超过预先设定的分段读取阈值，即 T_s>T_m，那么流化处理器将对该文档进行分段和重构处理，处理后会生成两个形 式良好的XML文档，一个大小等于T_m，另一个大小等于T_s-T_m，前者将被送入 快速分页器处理，而后者将被送往流化处理器进行再一次地判断、分段和重构处 理；

快速分页器：若XML文档F_s0,1的大小远远超过终端设备的需求内存T，即 T_s0,1＞＞T，则对XML文档F_s0,1进行第一轮的分割和重构处理，生成两个“形式良好” 的新XML文档F_s1,1和F_s1,2；接下来再对新生成的两个文档F_s1,1和F_s1,2进行判断和第 二轮的分割和重构处理，即，若两个新生成的文档F_s1,1和F_s1,2仍满足分割条件： T_s1,1＞＞T且T_s1,2＞＞T，则应同时对这两个文档进行分割和重构处理，生成四个“形式 良好”文档F_s2,1、F_s2,2、F_s2,3和F_s2,4，依此类推，反复地判断、分割和重构，直到某 一轮分割生成的所有XML文档的大小均不超过终端设备的需求内存，分割和重 构处理过程结束；

XSLT转换器：用于对照终端设备提供的转换样式表，将输入文档转换成其 它标准格式的文档输出；

发布服务器：用于将具有不同标准格式的文档发送给相应的终端设备。

进一步，所述流化处理器包括分段器和重构器，其中，

所述分段器中，假设现在有一个XML文档F_s，大小为T_s，流化处理器可用的 最大内存为T_m，如果XML文档非常大，远远大于流化处理器可用的最大内存， 即T_s＞＞T_m，或者说，满足条件：T_s≈pT_m，p＞＞1，那么使用流化处理器中的分段 器对它进行分段处理，具体包括以下三个步骤：

第一、读取XML文档F_s；

第二、设定分段读取阈值T_d＝T_m；

第三、进行分段处理，生成两个非“形式良好的”XML文档：

①F_s1，大小记为T_s1，T_s1=T_d＝T_m；

②F_s2，大小记为T_s2，T_s2=T_s-T_d=T_s-T_m。

更进一步，所述重构器中，处理过程包括初步重构和再重构两个步骤，过程 如下：

1.1）读取第三步骤生成的XML文档F_s1；

1.2）将指针定位到尾部；

1.3）向前搜索结束标签的开始标记“</”，并记录其位置为L₁；

1.4）从L₁开始向后搜索相应的结束标记“>”，并记录其位置为L₂，此时会有两 种可能：

如果能够搜到结束标记“>”，那么L₂的值就是该标记的位置值；

反之，如果未能搜到结束标记“>”，这时应将指针定位到L₁处，再一次执 行步骤1.3），得到新的L₁值后，再执行步骤1.4），获取新的L₂值，这个新的L₂值 才是该情况下结束标记的真正位置；

1.5）将因分割而导致的不完整数据从F_s1的尾部移到F_s2的首部；此后将得到 已删除不完整数据的XML文档F_s1，和已添加不完整数据的XML文档F_s2；

1.6）获取因分割而缺失的所有祖先节点的标签名字：

1.6.1）设定读取标志flag=True，当读取的值的长度大小或等于0时， flag=False；

1.6.2）读取步骤1.5）生成的已删除不完整数据的XML文档F_s1，将每个 节点标签名字，空标签名字除外，添加到列表中；

1.6.3）统计列表中的不同元素及其个数，根据形式良好的XML文档的开 始标签和结束标签应配套，空标签要关闭的原理，个数为奇数的元素，第一 个元素除外，即为因分割而缺失的祖先节点标签名字，将这些标签名字放入 另一个列表中，获取这些节点标签名字时，应保持其在列表中的原有顺序不 变；

1.7）将步骤1.5）生成的两个XML文档F_s1和F_s2构造成形式良好的XML文 档：

1.7.1）把步骤1.6.3）得到的列表中的元素用作结束标签倒序地添加到已删 除不完整数据的XML文档F_s1的尾部；

1.7.2）把步骤1.6.3）得到的列表中的元素，第一个元素除外，用作开始标 签正序地添加到已添加不完整数据的XML文档F_s2的首部；

1.7.3）把步骤1.6.3）得到的列表中的第一个元素，即声明标签名字，用作 开始标签添加到步骤1.7.2）得到的XML文档F_s2的首部。

再进一步，所述快速分页器包括分割器和重构器，其中，

所述分割器中，假设现在有一个XML文档F_s0,1，其大小为T_s0,1，终端设备的 需求内存为T，如果XML文档非常大，远远大于终端设备的需求内存，即T_s0,1＞＞T， 或者说，满足条件：T_s0,1≈qT，q＞＞1，对这个XML文档进行第一轮的分割和重 构处理，过程如下：

2.1）读取XML文档F_s0,1；

2.2）设定一个分割阈值

2.3）进行第一轮分割处理，此轮包括一次分割处理过程，分割后得到两个非 “形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1=T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2=T_f0,1；

2.4）对步骤2.3）生成的两个XML文档F_s1,1和F_s1,2在所述重构器中进行重构 处理，处理后将得到两个新的“形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1≈T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2≈T_f0,1；

此时第一轮的分割和重构处理过程结束，接下来我们将设定两个分割阈值 和对步骤2.4）生成的两个XML文档F_s1,2和F_s1,2进行第二轮 的分割和重构处理，处理后将得到四个“形式良好”的文档F_s2,1、F_s2,2、F_s2,3、F_s2,4， 大小分别等于T_f1,1、T_f1,1、T_f1,2、T_f1,2，依此类推，设定2^n-1个分割阈值对2^n-1个XML文档F_s(m-1),k,k=1,…,2^n-1进行第n轮的分割 和重构处理，处理后将得到2ⁿ个“形式良好”的XML文档F_sn,k，k=1,…,2ⁿ，至此， 所有文档的大小都不超过终端设备的需求内存，即T_sn,k≤T,k=1,…,2ⁿ，不再满足 分割条件，分割和重构处理结束。

本发明的技术构思为：使用流化处理器和快速分页器，将这个大型XML文 档分成多个不超过终端设备内存限制的小XML文档，然后再通过XSLT转换器 完成转换工作。经过上述分析与研究，我们可以绘出分页读取大数据的过程图， 如图2所示。

由上图可知，该过程是在XML文件服务器、流式分页服务器和发布服务器 三者的共同作用下完成的，其中XML文件服务器用来存储并发送异构的XML文 档；流式分页服务器负责完成XML文档的分割、重构和转换功能；发布服务器 的用途是向PC、手持设备、智能手机等终端设备发送相应标准格式的小XML文 档，只要这些终端设备向XSLT转换器提出交换数据的请求，并提供自身的转换 样式表。

本发明的有益效果主要表现在：（1）该系统使用流式分页服务器对数据进行 了分页处理，使得数据能够以“页”的形式被发送到终端设备上，解决了终端用户 设备因其内存、显示屏尺寸和规格等限制而无法正确获取或显示数据的问题；

（2）该系统可以满足多个用户，即多种不同终端或多个具有不同格式标准的 同种终端，同时请求访问文件服务器上的XML文档的要求，灵活性高、适用面 广。

（3）该系统可以使用流式分页服务器将任意大小的XML文档分页转换成终 端设备可接收和显示的格式和大小，即，系统可应用于任意大小的XML文档， 具有普遍适用性。

（4）相较于传统的只是实现了分段处理器功能的分页发布系统，该系统不仅增加了重构 器，使得输出的XML文档都是“形式良好”的，提高了解析和转换的可靠性和容 错性；还增加了快速分页器，使得分页处理更加快速、高效。

本系统却在此基础上增加了重构器，目的是为了将这些非“形式良好”小XML 文档全部转换成“形式良好”的小XML文档，使得下一步的解析和转换成为可能；

本系统还增加了快速分页器，它采用的是一种基于二叉树的分割算法，可以 对上述所有“形式良好”的小XML文档进行快速的分割和重构处理，总体上加快 了分页处理速度，即能够更加快速地达到预期的分页效果。

（5）系统中的任意一个环节，包括流化处理器、快速分页器和XSLT转换器，输 出的所有XML文档都是“形式良好”的，可以独立地进行解析和格式转换。其中， 任何一个文档发生处理或传输错误不会影响其它文档的正确解析和格式转换，即， 有效地将错误隔绝在相应的错误文档中，而不会扩散到其它正确的文档中；一旦 文档的错误更正，就可以结合其它正确文档形成一份完整的文档，有效地提高了 解析、格式转换的容错性。

（6）由于终端用户设备接收到的所有XML文档也是“形式良好”的，因此，它可 以对这些文档进行快速的拆分、解析和组装。

附图说明

图1是XSLT转换原理图。

图2是大数据的分页读取过程图。

图3是流式分页发布系统框图。

图4是流化处理器的组成框图。

图5是快速分页器的组成框图。

图6是流化处理示意图，其中，（a）表示文档大小不超过预先设定的分段读 取阈值时的情况，（b）表示文档大小超过预先设定的分段读取阈值时的情况。

图7是F_s1和F_s2的重构处理过程的流程图。

图8是基于二叉树的快速分页算法的示意图，其中，每个椭圆节点代表相应 轮次处理使用的一份XML文档。

图9是基于二叉树的快速分页过程的流程图。

图10是快速分页处理流程图。

图11是第一轮分割和重构处理流程图。

具体实施方式

下面结合附图对本发明作进一步描述。

实施例1

参照图1～图11，一种基于XML的流式分页发布方法，所述发布方法包括以 下步骤：

（1）流化处理过程：

对于每个大型的XML输入文档，流化处理器先要对其大小进行判断，如果 文档大小不超过预先设定的分段读取阈值，即T_s≤T_m，那么进入步骤（2）处理； 反之，如果文档大小超过预先设定的分段读取阈值，即T_s>T_m，那么流化处理器 将对该文档进行分段和重构处理，处理后将生成两个形式良好的XML文档，一 个大小等于T_m，另一个大小等于T_s-T_m，前者将被送入步骤（2）处理，而后者将 被送往流化处理器进行再一次地判断、分段和重构处理；

（2）快速分页处理过程：

若XML文档F_s0,1的大小远远超过终端设备的需求内存T，即T_s0,1＞＞T，则对 XML文档F_s0,1进行第一轮的分割和重构处理，生成两个“形式良好”的新XML文 档F_s1,1和F_s1,1；接下来再对新生成的两个文档F_s1,1和F_s1,2进行判断和第二轮的分割 和重构处理，即，若两个新生成的文档F_s1,1和F_s1,2仍满足分割条件：T_s1,1＞＞T且 T_s1,2＞＞T，则应同时对这两个文档进行分割和重构处理，生成四个“形式良好”文档 F_s2,1、F_s2,2、F_s2,3和F_s2,4，依此类推，反复地判断、分割和重构，直到某一轮分割 生成的所有XML文档的大小均不超过终端设备的需求内存，分割和重构处理过 程结束；

（3）XSLT转换过程：对照终端设备提供的转换样式表，将输入文档转换成其它 标准格式的文档输出；

（4）发布过程：将具有不同标准格式的文档发送给相应的终端设备。

进一步，所述步骤（1）中，流化处理过程包括分段处理过程和重构处理过程， 所述分段处理过程：

假设现在有一个XML文档F_s，大小为T_s，流化处理器可用的最大内存为T_m， 如果XML文档非常大，远远大于流化处理器可用的最大内存，即T_s＞＞T_m，或者 说，满足条件：T_s≈pT_m，p＞＞1，那么使用流化处理器中的分段器对它进行分段 处理，具体包括以下三个步骤：

第一、读取XML文档F_s；

第二、设定分段读取阈值T_d=T_m；

第三、进行分段处理，生成两个非“形式良好的”XML文档：

①F_s1，大小记为T_s1，T_s1=T_d=T_m；

②F_s2，大小记为T_s2，T_s2=T_s-T_d=T_s-T_m。

更进一步，所述重构处理过程包括初步重构和再重构两个步骤，过程如下：

1.1）读取第三步骤生成的XML文档F_s1；

1.2）将指针定位到尾部；

1.3）向前搜索结束标签的开始标记“</”，并记录其位置为L₁；

1.4）从L₁开始向后搜索相应的结束标记“>”，并记录其位置为L₂，此时会有两 种可能：

如果能够搜到结束标记“>”，那么L₂的值就是该标记的位置值；

反之，如果未能搜到结束标记“>”，这时应将指针定位到L₁处，再一次执 行步骤1.3），得到新的L₁值后，再执行步骤1.4），获取新的L₂值，这个新的L₂值 才是该情况下结束标记的真正位置；

1.5）将因分割而导致的不完整数据从F_s1的尾部移到F_s2的首部；此后将得到 已删除不完整数据的XML文档F_s1，和已添加不完整数据的XML文档F_s2；

1.6）获取因分割而缺失的所有祖先节点的标签名字：

1.6.1）设定读取标志flag=True，当读取的值的长度大小或等于0时， flag=False；

1.6.2）读取步骤1.5）生成的已删除不完整数据的XML文档F_s1，将每个 节点标签名字，空标签名字除外，添加到列表中；

1.6.3）统计列表中的不同元素及其个数，根据形式良好的XML文档的开 始标签和结束标签应配套，空标签要关闭的原理，个数为奇数的元素，第一 个元素除外，即为因分割而缺失的祖先节点标签名字，将这些标签名字放入 另一个列表中，获取这些节点标签名字时，应保持其在列表中的原有顺序不 变；

1.7）将步骤1.5）生成的两个XML文档F_s1和F_s2构造成形式良好的XML文 档：

1.7.1）把步骤1.6.3）得到的列表中的元素用作结束标签倒序地添加到已删 除不完整数据的XML文档F_s1的尾部；

1.7.2）把步骤1.6.3）得到的列表中的元素，第一个元素除外，用作开始标 签正序地添加到已添加不完整数据的XML文档F_s2的首部；

1.7.3）把步骤1.6.3）得到的列表中的第一个元素，即声明标签名字，用作 开始标签添加到步骤1.7.2）得到的XML文档F_s2的首部。

再进一步，所述步骤（2）中，假设现在有一个XML文档F_s0,1，其大小为T_s0,1，终 端设备的需求内存为T，如果XML文档非常大，远远大于终端设备的需求内存， 即T_s0,1＞＞T，或者说，满足条件：T_s0,1≈qT，q＞＞1，对这个XML文档进行第一轮 的分割和重构处理，过程如下：

2.1）读取XML文档F_s0,1；

2.2）设定一个分割阈值

2.3）进行第一轮分割处理，此轮包括一次分割处理过程，分割后得到两个非 “形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1=T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2=T_f0,1；

2.4）对步骤2.3）生成的两个XML文档F_s1,1和F_s1,2进行重构处理，处理后将 得到两个新的“形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1≈T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2≈T_f0,1；

此时第一轮的分割和重构处理过程结束，接下来我们将设定两个分割阈值 和对步骤2.4）生成的两个XML文档F_s1,1和F_s1,2进行第二轮 的分割和重构处理，处理后将得到四个“形式良好”的文档F_s2,1、F_s2,2、F_s2,3、F_s2,4， 大小分别等于T_f1,1、T_f1,1、T_f1,2、T_f1,2，依此类推，设定2^n-1个分割阈值对2^n-1个XML文档F_s(n-1),k,k=1,…,2^n-1进行第n轮的分割 和重构处理，处理后将得到2ⁿ个“形式良好”的XML文档F_sn,k,k=1,…,2ⁿ，至此， 所有文档的大小都不超过终端设备的需求内存，即T_sn,k≤T,k=1,…,2ⁿ，不再满足 分割条件，分割和重构处理结束。

实施例2

参照图1～图11，一种基于XML的流式分页发布系统，所述发布系统包括：

流化处理器：对于每个大型的XML输入文档，流化处理器先要对其大小进 行判断，如果文档大小不超过预先设定的分段读取阈值，即T_s≤T_m，那么将此文 档交由快速分页器处理；反之，如果文档大小超过预先设定的分段读取阈值，即 T_s>T_m，那么流化处理器将对该文档进行分段和重构处理，处理后会生成两个形 式良好的XML文档，一个大小等于T_m，另一个大小等于T_s-T_m，前者将被送入 快速分页器处理，而后者将被送往流化处理器进行再一次地判断、分段和重构处 理；

快速分页器：若XML文档F_s0,1的大小远远超过终端设备的需求内存T，即 T_s0,1＞＞T，则对XML文档F_s0,1进行第一轮的分割和重构处理，生成两个“形式良好” 的新XML文档F_s1,1和F_s1,2；接下来再对新生成的两个文档F_s1,1和F_s1,2进行判断和第 二轮的分割和重构处理，即，若两个新生成的文档F_s1,1和F_s1,2仍满足分割条件： T_s1,1＞＞T且T_s1,2＞＞T，则应同时对这两个文档进行分割和重构处理，生成四个“形式 良好”文档F_s2,1、F_s2,2、F_s2,3和F_s2,4，依此类推，反复地判断、分割和重构，直到某 一轮分割生成的所有XML文档的大小均不超过终端设备的需求内存，分割和重 构处理过程结束；

XSLT转换器：用于对照终端设备提供的转换样式表，将输入文档转换成其 它标准格式的文档输出；

发布服务器，用于将具有不同标准格式的文档发送给相应的终端设备。

本实施例中，流式分页发布系统由流式分页服务器，包括流化处理器、快速 分页器、XSLT转换器，和发布服务器两个部分组成，如图3所示，其工作原理 是首先通过流式分页服务器对大型XML文档进行分割、重构和转换处理，生成 多个“形式良好”的小XML目标文档，这些文档的大小和数据格式分别取决于终 端设备提供的可用内存和转换样式表，然后再通过发布服务器将这些小XML文 档以“页”的形式发送到相应的终端设备。

流化处理器由分段器和重构器组成，如图4所示，工作的基本思想是先对输 入的XML文档的大小进行判断，如果文档不满足预先设定的分段条件，就不做 任何处理地将其送往快速分页器；反之，如果文档满足预先设定的分段条件，就 对该文档进行分段读取，确保读入数据的大小不超过预先设定的分段读取阈值， 然后再使用重构器对存储着上述数据的新XML文档进行重构处理，使得流化处 理器输出的每一个XML文档都是形式良好的。

快速分页器由分割器和重构器组成，如图5所示，工作的基本思想是先对输 入的XML文档的大小进行判断，如果文档满足预先设定的分割条件，就对该文 档进行二叉树式分割处理，然后再对此次分割处理生成的所有新XML文档进行 重构处理。需要强调的是，此处的重构处理过程与流化处理器中的相同。

XSLT转换器的功能是对照终端设备提供的转换样式表，将输入文档转换成 其它标准格式的文档输出；发布服务器的功能是将具有不同标准格式的文档发送 给相应的终端设备。

流化处理过程是利用流化处理器来实现的，对于每个大型的XML输入文档， 流化处理器都先要对其大小进行判断。如果文档大小不超过预先设定的分段读取 阈值，即T_s≤T_m，那么流化处理器将不做任何处理地将该文档输出到快速分页器， 如图6a所示。反之，如果文档大小超过预先设定的分段读取阈值，即T_s>T_m，那 么流化处理器将对该文档进行分段和重构处理，处理后将生成两个形式良好的 XML文档，一个大小约等于T_m，另一个大小约等于T_s-T_m，前者将被送到快速分 页器，而后者将被送往流化处理器进行再一次地判断、分段和重构处理，如图6b 所示。

分段处理过程：假设现在有一个XML文档F_s，大小为T_s，流化处理器可用的 最大内存为T_m，如果XML文档非常大，远远大于流化处理器可用的最大内存， 即T_s＞＞T_m，或者说，满足条件：T_s≈pT_m，p＞＞1，那么我们将使用流化处理器中 的分段器对它进行分段处理，具体包括以下三个步骤：

第一、读取XML文档F_s。

第二、设定分段读取阈值T_d=T_m。

第三、进行分段处理，生成两个非“形式良好的”XML文档：

①F_s1，大小记为T_s1，T_s1=T_d=T_m；

②F_s2，大小记为T_s2，T_s2=T_s-T_d=T_s-T_m。

重构处理过程比较复杂，它包括初步重构和再重构两个步骤，其实现流程如 图7所示，具体实施方式如下：

1.1）读取第三步骤生成的XML文档F_s1。

1.2）将指针定位到尾部。

1.3）向前搜索结束标签的开始标记“</”，并记录其位置为L₁。

1.4）从L₁开始向后搜索相应的结束标记“>”，并记录其位置为L₂。此时会有两 种可能：

如果能够搜到结束标记“>”，那么L₂的值就是该标记的位置值；

反之，如果未能搜到结束标记“>”，这时应将指针定位到L₁处，再一次执

行步骤1.3），得到新的L₁值后，再执行步骤1.4），获取新的L₂值，这个新的L₂值

才是该情况下结束标记的真正位置。

1.5）将因分割而导致的不完整数据从F_s1的尾部移到F_s2的首部。此后将得到 已删除不完整数据的XML文档F_s1，和已添加不完整数据的XML文档F_s2。

1.6）获取因分割而缺失的所有祖先节点的标签名字：

1.6.1）设定读取标志flag=True，当读取的值的长度大小或等于0时， flag=False；

1.6.2）读取步骤1.5）生成的已删除不完整数据的XML文档F_s1，将每个 节点标签名字，空标签名字除外，添加到列表中；

1.6.3）统计列表中的不同元素及其个数，根据形式良好的XML文档的开 始标签和结束标签应配套，空标签要关闭的原理，个数为奇数的元素，第一 个元素除外，即为因分割而缺失的祖先节点标签名字，将这些标签名字放入 另一个列表中。值得注意的是，获取这些节点标签名字时，应保持其在列表 中的原有顺序不变。

1.7）将步骤1.5）生成的两个XML文档F_s1和F_s2构造成形式良好的XML文 档：

1.7.1）把步骤1.6.3）得到的列表中的元素用作结束标签倒序地添加到已删 除不完整数据的XML文档F_s1的尾部；

1.7.2）把步骤1.6.3）得到的列表中的元素，第一个元素除外，用作开始标 签正序地添加到已添加不完整数据的XML文档F_s2的首部；

1.7.3）把步骤1.6.3）得到的列表中的第一个元素，即声明标签名字，用作 开始标签添加到步骤1.7.2）得到的XML文档F_s2的首部。

快速分页处理过程是利用快速分页器来实现的，它的核心是二叉树式分割算 法，一种特殊的并行分割算法，其相对于传统的迭代分割算法，具有更加快速、 高效的优点。

基于二叉树的快速分页算法：基于二叉树的快速分页算法的基本原理是先将 一个XML文档分割并重构成两个新文档，然后再将这两个新XML文档各自分割 并重构成另外两个文档，即共得到四个XML文档，依此类推，当得到的所有文 档不再满足分割条件时，分割结束。下面我们将用一个简图来说明上述算法的基 本原理，如图8所示。

为了进一步解释基于二叉树的快速分页算法的基本原理，我们可以把图8转 换成图9所示的文档变化图，并将文档命名为F_sn,k，其中下小标n代表分割和重 构处理的轮次，如n=1说明文档是在第一轮分割和重构处理中生成的；下小标k 代表每一轮分割和重构处理后生成的文档的序号，它的取值范围取决于轮次n， 即k=1,…,2ⁿ，例如当n=1时，k的取值为1和2，F_s1,1代表第一轮分割和重构处 理后生成的第一个文档，F_s1,2代表第一轮分割和重构处理后生成的第二个文档。

通过对图9的研究与分析，我们可以绘出快速分页处理的整体流程，如图10 所示。由于XML文档F_s0,1的大小远远超过终端设备的需求内存T，即T_s0,1＞＞T，因 此我们需要对它进行第一轮的分割和重构处理，生成两个“形式良好”的新XML 文档F_s1,1和F_s1,2。接下来我们需要对新生成的两个文档F_s1,1和F_s1,2进行判断和第二 轮的分割和重构处理，即，若两个新生成的文档F_s1,1和F_s1,2仍满足分割条件： T_s1,1＞＞T且T_s1,2＞＞T，则应同时对这两个文档进行分割和重构处理，生成四个“形式 良好”文档F_s2,1、F_s2,2、F_s2,3和F_s2,4，依此类推，反复地判断、分割和重构，直到某 一轮分割生成的所有XML文档的大小均不超过终端设备的需求内存，分割和重 构处理过程结束。

二叉树式分割及重构处理过程：假设现在有一个XML文档F_s0,1，其大小为T_s0,1， 终端设备的需求内存为T，如果XML文档非常大，远远大于终端设备的需求内存， 即T_s0,1＞＞T，或者说，满足条件：T_s0,1≈qT，q＞＞1，那么我们将使用快速分页器， 包括分割器和重构器，对这个XML文档进行第一轮的分割和重构处理，该处理 的流程如图11所示，具体包括以下四个步骤：

2.1）读取XML文档F_s0,1；

2.2）设定一个分割阈值

2.3）进行第一轮分割处理，此轮包括一次分割处理过程，分割后得到两个非 “形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1=T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2=T_f0,1；

2.4）对步骤2.3）生成的两个XML文档F_s1,1和F_s1,2进行重构处理，处理后将 得到两个新的“形式良好”的XML文档：

①F_s1,1，大小记为T_s1,1，T_s1,1≈T_f0,1；

②F_s1,2，大小记为T_s1,2，T_s1,2≈T_f0,1；

此时第一轮的分割和重构处理过程结束。接下来我们将设定两个分割阈值 和对步骤4）生成的两个XML文档F_s1,1和F_s1,2进行第二轮的 分割和重构处理，处理后将得到四个“形式良好”的文档F_s2,1、F_s2,2、F_s2,3、F_s2,4， 大小分别约等于T_f1,1、T_f1,1、T_f1,2、T_f1,2。依此类推，设定2^n-1个分割阈值 对2^n-1个XML文档F_s(n-1),k,k=1,…,2^n-1进行第n 轮的分割和重构处理，处理后将得到2ⁿ个“形式良好”的XML文档F_sn,k,k=1,…,2ⁿ。 至此，所有文档的大小都不超过终端设备的需求内存，即T_sn,k≤T,k=1,…,2ⁿ，不 再满足分割条件，分割和重构处理结束。