CN1309173C - 压缩/解压缩结构化文档的方法 - Google Patents

Abstract

本发明涉及一种用于压缩结构化文档的方法，该结构化文档包含相互嵌套的信息元素，该结构化文档与定义文档树型结构的至少一个结构模式(1)相关，表示信息元素，该方法包括：分析(11)和编译(13)文档的结构模式以便为该模式中的每个组件获得一个可执行指令序列(5)，包括用于插入控制代码和元素代码或调用组件指令序列的指令，以及用于基于控制代码值控制指令序列的执行的展开的指令；以及解压缩(14’)以二进制流形式被压缩(10)的文档，所述步骤包括在二进制流上执行指令序列(5)，以便以原始格式还原文档。

Description

压缩/解压缩结构化文档的方法

技术领域

本发明涉及一种用于压缩和解压缩结构化文档的方法。

背景技术

本发明尤其但不唯一应用于通过数字数据传输网络传送诸如图像、视频或声音数据的文档，以及存储这些文档和存储描述这些文档的数据。

结构化文档是信息元素的集合，每个信息元素均与类型和属性相关，而且主要通过层次关系相互关联。这些文档使用诸如SGML、HTML或XML的结构语言，这种语言特别区分构成文档的不同信息子元素。与此相反，在所谓的线性文档中，定义文档内容的信息是与显示和排版信息混杂在一起的。

结构化文档包含用于文档中不同信息集合的分隔标记。在SGML、XML或HTML格式的情况下，这些标记称为“标签(tags)”，而且是以“<XXXX>”和“</XXXX>”的形式出现，第一个标签指示信息元素“<XXXX>”的开始，而第二标签指示这个集合的结束。信息元素可由若干个低层信息元素组成。由此，结构化文档具有层次结构或树型结构模式，每个节点表示一个信息元素，而且与位于高层的节点相连，高层信息元素节点是表示包含低层信息元素的信息元素。位于这个树型结构分支末端的节点表示包含预定义数据类型的信息元素，该预定义数据类型不能再分解为信息子元素。

因此，结构化文档包含以文本或二进制数据形式表示的分离标签，这些标签界定了信息元素或子元素，信息元素或子元素自身可包含由标签界定的其它信息子元素。

此外，结构化文档与结构模式相关，结构模式以规则的形式定义文档中的每个信息集合中信息的结构和类型。模式由嵌套的信息集合结构分组组成，这些分组可能为有序序列，或为有序或无序的选择元素分组，或必要元素分组。

当前存在若干数字文档压缩算法。一些压缩算法设计用于直接处理文档二进制数据，而没有考虑这些数据类型。这些算法具有能处理任何类型的文档的优点，但它们的性能对通常为声音或图像类型的大型文档不是很好(低压缩率)。

已知有其它更为有效的特别适合于数据类型(例如图像或声音数据类型)的压缩算法，以致如果在这些算法应用于不只包含它们所设计类型的数据的文档时，它们就无法使用或效率低下。因此，设计用于特定数据类型的压缩算法并不很有效，而且非常不适合处理包含不同数据类型的结构化文档。

适合于压缩XML格式的文档的压缩算法在文档SMILL：Anefficient Compressor for XML Data”by H.Liefke et.al.，SigmodRecord，Association for Computting Machinery，New York，US，Vol.29，No.2，June 2000，pages 153-l64，以及Millau：An Encoding formatfor Efficient Representation and Exchange of XML over the Web”by M.Girardot et al.Computer Network and ISDN Systems，North HollandPublishing.Amsterdam，NL，Vol.33，No.1-6，June 2000，pages 747-765中公开。

发明内容

本发明的目的是消除这些缺陷。这个目的是通过提供一种用于压缩结构化文档的方法实现的，这种结构化文档包含相互嵌套并且均与一种信息类型相关的信息元素，该结构化文档与定义文档树型结构的至少一个结构模式相关，并包含相互嵌套的结构组件，每种类型的文档信息由该模式中的一个组件定义。

根据本发明，该方法包括步骤：分析文档结构模式以便为该结构模式中的每个组件获得一个可执行指令序列，该指令序列包括用于插入控制代码和信息元素的压缩值或组件指令序列调用代码的指令，包括用于控制作为控制代码值的函数的序列的执行的指令，在结构化文档上执行指令序列以压缩结构化文档到包含文档中的信息元素的压缩值的一个二进制流中。

本方法最好还包括用于在结构化文档上执行指令序列的步骤。

根据本发明的一个特征，该文档包含不能被分解为子元素的基本元素，至少一种基本信息元素预先与适合该类型信息的压缩算法相关，该方法包括在执行指令序列期间对具有与所述算法相关的信息类型的每个信息元素的值应用压缩算法。

根据本发明另一特征，本方法包括编译为所述结构模式的每个组件获得的指令序列的步骤，以获得专用于所述结构模式，并可被计算机直接执行或解释以压缩具有该结构模式的文档的二进制编码程序。

根据本发明另一特征，本方法包括用于文档结构模式的标准化的预先步骤，以便获得该模式中组件的单个预定顺序。

根据本发明的另一特征，本方法包括优化和简化文档结构模式的预先步骤，包含减少结构组件中嵌套级别数。

该文档中的至少一个信息元素最好与所生成的二进制流中的一个信息元素代码相关，其被打上标记以便能直接访问该二进制流中的特定压缩信息元素，而不必解压缩该二进制流中即将被解压缩的元素之前的信息元素。

根据本发明的另一特征，所生成的压缩文档包括用于结构化文档中的每个信息元素的代码，用于确定与该信息元素相关的信息类型以及该信息元素的二进制值。

根据本发明的另一特征，该文档结构模式包括至少一个信息类型的子类型的定义，而且为具有n个子类型的类型的组件生成的指令序列依次包括：

插入一个子类型代码的指令，表示将应用于对应该文档的组件的元素的子类型，该指令与以比特数形式的该代码的大小有关，以及

测试该子类型代码的值的指令，每个测试指令与对应该子类型代码测试值的元素的子类型的索引相关，以及为压缩与该子类型相关的元素生成的指令序列。

最好，为对应元素集合的若干具体值(occurrences)的组件生成的二进制流包括一个预定结束代码，该组件集合由文档中的至少一个信息元素组成。

根据本发明另一特征，该结构模式的每个组件对应文档中的一个元素集合，每个元素集合至少包含一个信息元素，而且还与可能的具体值数的集合相关，指示对应这个组件的元素集合在直接高于其所属级别上一级的信息元素中可能出现的次数。

根据本发明的另一特征，为具体值数等于0或1的组件生成的指令序列依次包括：

在一个比特上插入一个出现代码的指令，指示对应该组件的元素集合是否出现在该文档中，

测试该出现代码的值的指令，以及

根据该测试指令，如果出现代码值指示在该文档中出现该元素集合，则独立于相关的具体值数为该组件生成指令序列。

根据本发明另一特征，为具体值数在n和m之间的组件生成的指令序列依次包括下述步骤：

插入具体值数代码的指令，其指示对应该压缩文档中该组件的元素集合的连续具体值数，减去最小具体值数n，该指令与如比特数的该代码的大小有关，

定义对应具体值数代码的值的迭代次数的循环指令，以及

根据该循环指令，独立于相关具体值数为该组件生成指令序列。

根据本发明另一特征，为具体值数在0和m之间的组件生成的指令序列还包括：

插入出现代码的指令，指示在该文档中是否存在至少一个对应该组件的元素集合的具体值，以及

如果出现代码值指示存在至少一个元素集合，则测试与为具体值数在1和m之间的组件生成的指令序列相关的出现代码的指令。

根据本发明的另一特征，为具体值数在n和m之间的组件生成的指令序列依次包括下述步骤：

插入单比特出现代码的指令，通知对应该文档中的组件的元素集合的具体值，该指令与以比特数形式的该代码的大小有关，

只要插入的出现代码指示出现了该元素集合的一个新具体值，则执行的循环指令，

根据该循环指令，为该组件生成的指令序列，以及插入一个新的单个比特出现代码的指令，通知在该文档中的该元素集合的一个新的具体值。

根据本发明的另一个特征，该结构模式中的每个组件对应包含至少一个信息元素的元素集合，该结构化文档的结构模式包括有序组件的至少一个序列类型组件，其中该序列中的出现顺序定义了对应该序列类型分组的组件的文档中元素集合的出现顺序，并为包含n个组件的序列生成的指令序列依次包括为序列中的每个组件生成的指令序列。

根据本发明另一特征，该结构模式中的每个组件对应包含至少一个信息元素的元素集合，要压缩的文档的结构模式包括选择组件分组类型的至少一个组件，每个选择组件对应一个信息元素集合，对应选择组件所对应的文档中的一个信息集合的选择分组类型的组件，以及为一组选择组件生成的指令序列包括定义n个对应元素集合的n个组件，其依次包括下述指令：

插入一个信息元素集合数代码的指令，表示在n个元素集合中有哪些元素集合在该文档中出现，该指令与以比特数形式的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应信息元素集合的组件所生成的指令序列相关，该元素集合对应元素集合数代码的测试值。

根据本发明另一特征，该结构模式的每个组件对应包含至少一个信息元素的元素集合，而且即将压缩的文档的结构模式包括至少一个无序组件类型的分组，在该无序分组中的每个组件对应一个元素集合，而且对应该文档中一个分组的无序分组类型的分组以任意顺序包含对应无序类型分组的组件的所有元素集合，而且为无序类型分组生成的指令序列包含对应该文档中n个元素集合的n个组件，其依次包括下述指令：

插入一个元素集合数代码的指令，指示在该文档中出现的下一个元素集合，该指令与以比特数形式的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应元素集合的组件所生成的指令序列相关，该元素集合对应元素集合数代码的测试值，而且为无序类型分组生成的指令序列包括除对应该元素集合的组件之外的无序分组中的所有组件。

本发明还涉及一种用于解压缩结构化文档的方法，该结构化文档包含相互嵌套并且均与一种信息类型相关的信息元素，该结构化文档与定义文档树型结构的至少一种结构模式相关，并且包含相互嵌套的结构组件，每种类型的文档信息由该模式中的一个组件定义。

根据本发明，该方法包括分析文档结构模式以便为该结构模式中的每个组件获得一个可执行指令序列的步骤，这种序列包括用于读出二进制流中的控制代码和信息元素的压缩值或用于读出调用代码以调用组件指令序列的指令，该二进制流形成形成压缩文档，以及用于控制序列执行作为控制代码值的函数的指令，在压缩文档上执行指令序列足能以与原始文档相同格式恢复文档并且具有至少等效结构。

本方法最好还包括在形成要被解压缩的文档的二进制流上执行指令序列的步骤。

根据本发明的一个特征，该文档包含不能分解为信息子元素的基本元素以及至少一种基本元素信息类型，其与适合该信息类型的解压缩算法相关，本方法包括在形成压缩文档的二进制流之上执行指令序列期间，检测对应二进制流中所述信息类型的信息元素二进制代码，并对这种二进制代码应用该解压缩算法。

根据本发明另一特征，本方法包括编译为所述结构模式的每个组件获得的指令序列的步骤，以获得专用于所述结构模式的二进制解码程序，并可被计算机直接执行或解释以压缩具有该结构模式的文档。

根据本发明另一特征，本方法包括标准化文档结构模式的预先步骤，以便获得该模式的组件的单个预定顺序。

根据本发明的另一特征，本方法包括优化和简化文档结构模式的预先步骤，包含减少结构组件分组中分层级数。

最好，识别压缩文档的二进制流中至少一个信息元素代码，以便能直接访问这个信息元素，而不必解压缩该二进制流中该信息元素之前的信息元素。

根据本发明的另一特征，压缩文档包括用于原始文档中每个信息元素的代码，用以确定与该信息元素相关的信息类型以及所压缩信息元素的二进制值。

根据本发明的另一特征，要压缩的文档的结构模式包括至少一种信息类型的子类型的定义，而且为具有n个子类型的类型的组件生成的指令序列依次包括下述指令：

读出子类型代码的指令，表示将应用于对应该文档中的组件的元素的子类型数，该指令与如比特数的该代码的大小相关，以及

测试该子类型代码的值的指令，每个测试指令与对应所测试子类型代码值的元素的子类型的索引相关，以及为解压缩与该子类型相关的元素生成的指令序列。

最好通过一个预定的二进制代码在压缩文档的二进制流中为包含对应该模式的组件的至少一个信息元素的元素集合的一组若干具体值的结束打上标记。

根据本发明另一方面，该结构模式的每个组件对应文档的二进制流中的一个元素集合，其包含至少一个信息元素，而且还与一组多个可能的具体值相关，指示对应这个结构模式的元素集合出现在高于其所属级别一级的信息元素中的次数。

根据本发明的另一特征，为具体值数等于0或1的组件所生成的指令序列依次包括下述指令：

读出单比特出现代码的指令，指示对应该组件的元素集合是否出现在该压缩文档中，

测试该出现代码值的指令，以及

根据该测试指令，如果出现代码的值指示在该压缩文档中出现该元素集合，则独立于相关的具体值数为该组件生成的指令序列。

根据本发明另一特征，为具体值数在n和m之间的组件生成的指令序列依次包括下述指令：

读出具体值数代码的指令，其指示在对应该该组件的元素集合在压缩文档中非连续具体值数减去最小具体值数n，该指令与如比特数的该代码的大小有关，

定义对应具体值数代码的值的迭代数量的循环指令，以及

根据该循环指令，独立于相关具体值数为该组件生成的指令序列。

根据本发明另一特征，为具体值数在0和m之间的组件生成的指令序列还包括：

读出单个比特出现代码的指令，指示在该压缩文档中是否存在对应该组件的元素集合的至少一个具体值，以及

如果出现代码的值指示存在至少一个元素集合，则联系为具体值数在1和n之间的组件生成的指令序列测试出现代码的值的指令。

根据本发明的另一特征，为具体值数在n和m之间的组件生成的指令序列依次包括下述指令：

读出单个比特出现代码的指令，指示在该压缩文档中是否存在对应该组件的元素集合的一个具体值，该指令与以比特数形式的该代码的大小有关，

只要在压缩文档的二进制流中读出的出现代码指示存在该元素集合的一个新具体值就执行的循环指令，

联系该循环指令，为该组件生成的指令序列，以及插入一个新的单个比特出现代码的指令，指示在该压缩文档中是否存在该元素集合的一个新的具体值。

根据本发明的另一特征，该结构模式中的每个组件对应包含至少一个信息元素的元素集合，该压缩文档的结构模式包括至少一个有序组件序列类型组件，其中在序列中的出现顺序定义了在对应该序列类型分组的组件的文档中元素集合的出现顺序，而且为包含n个组件的序列生成的指令序列依次包括为序列中的每个组件生成的指令序列。

根据本发明另一特征，该结构模式中的每个组件对应包含至少一个信息元素的元素集合，要解压缩的文档的结构模式包括选择组件分组类型的至少一个组件，每个选择组件对应一个信息元素集合，该文档中选择组件分组类型的组件对应选择组件所对应的的一个信息集合，而且为选择组件分组生成的指令序列分别包括定义n个元素(X₁，X₂，...，X_n)集合的n个组件，其依次包括下述指令：

读出一个元素集合数代码的指令，表示在n个元素集合中出现在该文档中的元素集合，该指令与如比特数的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应元素集合数代码的测试值所对应的元素集合的组件生成的指令序列相关。

根据本发明另一特征，该结构模式的每个组件对应包含至少一个信息元素的元素集合，而且要压缩的文档的结构模式包括无序组件类型的至少一个分组，该无序分组中每个组件对应一个元素集合，而且对应该文档中一个分组的无序分组类型的分组以任意顺序包含对应无序类型分组的组件的所有元素集合，而且为无序类型分组生成的指令序列包含对应该文档中n个元素集合的n个组件，其依次包括下述指令：

读出一个元素集合数代码的指令，指示在该文档中出现的下一元素集合，该指令与如比特数的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应该元素集合数代码的测试值所对应的元素集合的组件生成的指令序列相关，而且为无序类型分组生成的指令序列包括除对应该元素集合的组件之外的无序分组中的所有组件。

附图说明

现在参考附图描述作为非限制性实例的本发明的优选实施例，其中：

图1以框图的形式示意了根据本发明的方法中的不同步骤；

图2a、2b和2c图示了一个树型结构模式；

图3是通过给图2所示的结构模式应用根据本方面的还原法所得到的结构模式；

图4a、4b和4c是通过给图2所示的结构模式应用根据本方面的另一还原法所得到的结构模式。

具体实施方式

图1是在根据本发明的方法中的不同步骤链。

该方法设计用于处理结构化文档，结构化文档由定义文档结构的结构模式1和文档的结构信息2组成。

例如，下面示意了一种使用XML模式语言的结构模式形式：

<elementname=”C”>

  <complexType>

    <Choice>

      <element name=”A”type=”TA”minOccurs=1maxOccurs=1/>

      <element name=”B”type=”TB”minOccurs=1maxOccurs=1/>

    </Choice>

    <attribute name=”a2”required=false type=”boolean”/>

    <attribute name=”a1”required=false type=”integer”/>

  </complexType>

</element>

该模式指示名为“C”的结构组件具有一个复合结构，该复合结构由名为“a2”的第一可选布尔值型属性，总是出现在该结构中的名为“a1”的第二整数型属性，以及分别具有类型“TA”和“TB”名为“A”和“B”的一个选择组件分组(这两个组件中的一个只在该结构中出现一次)组成。

类型“TA”和“TB”在该文档结构模式中由模拟公式定义。

一般来说，称为组件分组的特定组件被用于定义文档结构。这些组件分组可以是下述类型：

SEQ，定义一个有序组件序列，其中文档的对应元素必须全部而且必须以所指示的顺序出现，

CHO，定义一组选择组件，必须出现在文档中的单个元素对应的分组中的一个组件，

AND，定义一个组件分组，其中对应元素必须全部而且以不能被修改的任意顺序出现在文档中；该分组对应XML模式标准中的“all”分组。

ANDNO，定义一个组件分组，其中对应元素必须全部而且以并不重要的任意顺序出现在文档中；该分组可用于编码在XML标准中顺序并不重要的属性，以及

ANY，包括可能在该文档中找到的所有可能元素中的任何元素。

根据本发明，在本方法的步骤11中分析和转换该表述以获得语法树4，其中每个结构组件有一个树。对应具有结构TC的组件的语法树由下述表达式表示：

TC                                                                             ->SEQ[1，1](AND_NO[1，1](a1_int[1，1]，a2_bool[0，1])，CHO[1，1]A_TA[1，1]，B_TB[1，1])

其中：

“A[x，y]”表示组件“A”对应文档中重复x至y次的元素，其可等于“*”表示一个未确定值。

该表达式可由图2c所示的树表示，包括由一组序列类型组件44的分组的单个具体值构成的根组件“TC”43。这个分组包括一个“AND”类型组件45的一个无序分组的单个具体值以及选择组件46分组的单个具体值。分组45由名为“a1”的整数和名为“a2”的布尔值的单个具体值构成，而分组46包括名为“A”的元素类型“TA”以及名为“B”的元素类型“TB”的单个具体值。

在步骤11获得的类型“TA”和“TB”可例如由下述公式给出：

TA                                                                         ->SEQ[1，1](AND[1，1](a3_int[1，1]，a4_int[0，1])，SEQ[1，1](X_TC[1，1]，Y_TC[1，1]))

TB->SEQ[1，1](a1_bool[1，1]，a5_bool[1，1])

并分别由图2a和2b所示的树表示。

类型“TA”31包括单个序列类型分组32，其分别由类型AND和SEQ的两个分组33、34构成。分组33分别包括两个名为“a3”和“a4”整数类型具体值。分组34分别包括两个名为“X”和“Y”的“TC”型具体值。

类型“TB”39由单个序列类型分组40构成，分别包括两个名为“a1”和“a5”的布尔值。

尽管在上面的描述中，在每个元素的名称和其类型之间已经作了区别，但根据本发明的方法也可应用于不作这种区别的结构语言。

此外，诸如XML模式语言的某些语言能够实现“多态(polymorphism)”或使用子类型。

这些子类型定义如下：

<complexType name=”TA1”>

  <restriction base=”TA”>

  </restriction>

</complexType>

<complexType type=”TA2”>

  <extension base=”TA”>

  </extension>

</complexType>

<element name=”X”type=”TA”/>

这种语法通过限制或扩展类型TA的信息组件X定义类型TA1和TA2作为类型TA的子类型。

具有这种结构模式的文档可包括类型TA1的元素X，可如下加入该元素：

<X xsi:type=”TA1”>

此外，通过这种方式拥有子类型的某些类型可声明为抽象，这意味着具有包含抽象类型定义的结构模式的文档中的信息元素不必包含此种类型的信息元素。抽象类型仅用于创建层次结构或类型类。在XML模式语言中如下定义抽象类型：

<complexType name=”a”type=”TA”abstract=”true”>

</complexType>

此外，结构组件必须是确定性的，换言之，它必须不能以不止一种方式解释文档中的信息元素。例如，在“CHO(a，SEQ(a，b))”模式中，如果在文档中出现“a”，则不可能知道之后是否“b”已经出现。存在用于这种目的的算法，这些算法可利用根据本发明的方法将非确定性的模式转换为确定性的模式。例如，参考文档[“Regularexpressions into finite automata”Br üggemann-Klein，Anne，ExtendedAbstract in I.Simon，Hrsg.，LATIN 1992，S.97-98.Springer-Verlag，Berlin1992.Full Version in Theoretical Computer Science 120：197-213，1993]。因此，上面讨论的模式可用“SEQ(a，b[0，1])”替换。

在根据本发明的方法的下一步骤12，接着可在转换为语法树的结构模式的组件之上执行处理，以缩减或简化它们。

例如，这种简化处理可由全局补偿(flattening)方法构成，以由所有树31、39和43生成单个语法树51，如图3所示。

该树实际上示意了在该文档中可能遇到的所有元素类型的字典，这些信息元素被集合到在文档中出现至少一次[1，*]的选择型分组52中。在该树中，复数型组件“A”、“B”、“X”和“Y”与一个“ANY”类型相关，而以不同类型出现两次(在组件“TB”和“TC”中)的组件；“a1”根据XML语言与缺省“pcdata”类型相关，或与原始文档中的元素类型(例如文本)相关。相同的信息元素实际上也可以不同方式表示；例如，二进制序列也可认为是字符串或整数。

作为变型，这种简化处理包括局部补偿语法树以获得如在图4a到4c中表示为31’、39’和43’的语法树。

在每个附图中，分组32～34(图2a)、40(图2b)以及44～46(图2c)已经被至少出现一次[1，*]的选择型分组53、54和55替代。

还可进一步处理树“TA”、“TB”和“TC”以消除出现在结构模式中的多义性。

在一些情况下，也可在改进所能生成的二进制代码的紧密度的同时非破坏性地简化语法树。

在包含最小具体值数n_x等于0或1的单个组件X的一个组件分组具有下述形式的情况下，也可进行这种简化：

GROUP[n_G,m_G](X[n_x,m_x])

其中GROUP可以是SEQ、CHO或AND类型分组。分组可以用下面的组件替代：

X[n_G.n_x0.m_G.m_x]

在选择组件CHO分组包括最小具体值数等于0的至少一个组件的情况下，可能出现另一种非破坏简化的情况。因此分组：

CHO[0,m_c](X1[n_x1,m_x1],X2[1,m_x2],X3[n_x3,m_x3])

可用下述替代：

CHO[n_c,m_c](X1[n_x1,m_x1],X2[0,m_x2],X3[n_x3,m_x3])

类似地，具有单个CHO类型具体值，尤其包含单个CHO类型具体值的分组CHO[1，1](...，CHO[1，1](...)，...)可通过用包含在两个CHO类型分组中的所有组件的CHO类型分组的单个CHO[1，1](...)分组替代以简化。

在步骤12，树“TA”、“TB”和“TC”也可经历规范化处理，其包含重新排序模式以便获得该模式中的单个组件顺序。该处理接着为由之前的处理获得的语法树的不同节点赋值一个二进制数。该数将在压缩对应的信息元素期间使用。

特别地，规范化处理包括为每个分组加一个签名，其是通过连接分组名与该分组中之前排序的所有组件的签名生成的。因此，图4中的分组53与“CHO.a3.a4.X.Y”签名相关。

在这个处理中，认为有序分组(SEQ)已经被规范化。因此，要规范化的分组为选择型分组(”CHO”)和”AND”及”AND_NO”分组。这个处理对由定义文档中对应元素的子分组g_i和组件e_i构成的每个分组G包括下述步骤：

如果有的话，在规范化分组G之前规范化分组G中的子分组g_i，这种规范化算法是递归的，

如果有的话，在子分组g_i之前存储分组G中的组件e_i，

以一个预定顺序存储组件e_i，

以一个预定顺序存储子分组g_i，以及

确定分组G的签名，这是通过以在经上述步骤后产生的顺序连接其组件(和子分组)的所有签名给出的。

存储分组组件的预定顺序可以是它们对应的签名的字母数字顺序，或它们的最小具体值数的降序，而且在此情况下，具有相同的最小具体值数的组件是以字母数字顺序存储的。

应指出，对于根据本发明的方法来说这种规范化处理不是必要的。可以保存组件在模式中出现的顺序。

本方法的下一步骤13包括生成描述一个二进制流的指令序列5，也称为“二进制语法”。这种处理包括为结构模式中的每个语法树或复数类型生成指令序列，其以文档树型结构模式中位于语法树最低级别的节点或组件开始。由此为最低级节点生成的二进制语法的调用指令接着被插入到用于出现低级组件的高级节点的二进制语法中。该结果是为整个文档结构模式获得二进制语法，其以如同包含调用子程序的主程序的软件的相同方式为低级组件调用二进制语法，其接着能调用其它子程序，等等。

表示类型TX的元素X的组件的二进制语法为下述形式：

X

TX

其中“X”表示插入或读出元素X的值或调用对应元素X的指令序列的指令，而“TX”表示对元素X的类型的引用。

如果类型TX具有一个或若干个子类型，这表示存在多态现象。在此情况下，其与下述的二进制语法相关：

X

TX_poly

如果类型TX包括子类型S₁，S₂，...，S_n，根据缺省类型TX是否为抽象必须考虑两种不同情形。

如果缺省类型TX是抽象的，则“TX_poly”二进制语法依次包括下述指令：

插入或读出子类型“flagPoly”的代码的指令，其表示将应用于元素X的子类型数，该指令与如比特数的该代码的大小有关，以及

测试子类型代码的值的指令，每个测试指令与插入或读出元素X的值的指令相关，或与调用对应元素X的指令序列相关，元素X与对应子类型代码测试值的元素X的子类型的索引相关。

在这个操作之前，子类型S₁，S₂，...，S_n以它们的签名顺序排列：

例如，这种类型的二进制语法可为下述形式：

表1

flagPoly	E(log2(n))bits
		if(flagPoly=0){
X	S1
		}
else if(flagPoly=1){
		X	S2
}
		...
else if(flagPoly=k){
		X	Sk+1
}
		...
else if(flagPoly=n-1){
		X	Sn

}

其中E()为四舍五入到下一个较大整数的函数，而“flagPoly”包含将应用到元素X的子类型的数码，而“X”指示用于元素X的代码必须插入的位置。

如果 $2^{E\left({\log }_2^{\left(n\right)}\right)}>n,$ 则可在二进制序列的最后添加下述行以检测故障：

Else	SpecificProcess

其中“SpecificProcess”是设计用于通知在“flagPoly”的值不对应TX的子类型的情况下处理错误的过程。

如果缺省类型TX不是抽象的，则通过插入之前的二进制语法到依次包括下述指令的二进制语法中获得TX_poly的二进制语法：

插入或读出单比特“typInfoFlag”子类型出现代码的指令，指示该元素类型是缺省类型还是这个缺省类型的子类型，以及

测试子类型出现代码的值的指令，以及

联系该测试指令，如果子类型出现代码的值指示该元素类型为子类型，则为定义类似表1中所指示的多态现象的指令序列，否则为插入或读出元素X的值的指令，该值与元素X的缺省类型的索引相关。

例如，这种类型的二进制语法可为下述形式：

表2

typeInfoFlag	1bit
		if(typeInfoFlag){
Binary syntax of polymorphism
		else
X	TX

其中“typeInfoFlag”为指示X的类型是TX还是TX的一个子类型的代码。

下一步骤为确定已经确定了二进制语法的每个元素或元素集合X的具体值数[n，m]的二进制语法。之后，一个元素可表示一个元素集合。

在用于这种目的的三种情形之间进行区别。在第一种情形下，m和n均等于1，换言之，元素X与具体值数[1，1]相关。所产生的二进制语法对应为元素X生成的二进制语法。

在第二种情形下，n＝0且m＝1，所生成的二进制语法依次包括下述指令：

插入或读出单比特出现代码“flagX”的指令，其指示在压缩文档中是否出现元素X，该指令与如比特数的该代码的大小有关，

测试出现代码的值的指令，以及

联系该测试指令的指令，如果出现代码的值指示在该文档中出现元素X，则该指令插入或读出元素X的值或调用对应元素X的指令序列。

例如，这种类型的二进制语法可为下述形式：

表3

FlagX	1bit
		if(flag X){
binary synatax of X
		}

其中flagX为指示在文档中是否出现X的单比特代码。如果指示符flagX的值等于“true”，则这个二进制语法类似于其中插入了X的编程指令序列。

在第三种情形下，m-n小于预定的阈值常量，例如2¹⁶(＝65536)，其意味着具体值数可以无符号的16位整数的形式编码。在此情况下，元素X[n，m]的二进制语法连续包括下述指令：

-插入或读出多个具体值代码“loopflagX”的指令，其指示压缩文档中元素X的连续具体值数，减去元素X的最小具体值数n，该指令与如比特数的该代码的大小有关，

-定义对应具体值数代码的值的迭代数的循环指令，以及

-联系该循环指令，插入或读出元素X的值或调用对应元素X的指令序列的指令。

例如，这种类型的二进制语法可为下述形式：

表4

loopflagX	E(log2(m-n+1))bits
		for(k=0;k＜loopFlagX+n;k++){
binary syntax of X
		}

其中，“loopflagX”是文档中X的连续具体值数的代码，减去X的最小具体值数n，而E()是四舍五入到下一个较大整数的函数。

这个语法指示“loopflagX”被编码到E(log₂(m-n+1))位上，而且X必须被插入(loopFlagX+n)次。

在第四种情形下，m没有界限，或m-n大于预定的阈值常量。所生成的二进制语法类似于第三种情形下的二进制语法，除了“loopflagX”没有被编码到E(log₂(m-n+1))位上，但它以可编码任意整数的另一格式被编码。

例如，这种格式可以是“UNIT_VLC”格式，其由预定数量的位集合构成，例如5位，每个集合的第一位指示该集合是否为该整数代码中的最后一个集合，而该集合接下来的四位用于编码该整数。

在第三和第四种情形下，如果最小具体值数n为0，则优选添加的二进制语法还包括：

插入或读出单比特“shuntflagX”出现代码的指令，以指示在该压缩文档中是否出现至少一个元素X，以及

如果出现代码的值指示出现至少一个元素X则测试出现代码的值的指令，该指令与为具体值数在1和m之间的元素X所生成的指令序列相关。

例如，这种类型的二进制语法可为下述形式：

表5

shuntFlagX	1bit
		if(shuntFlag X){
binary syntax of X[n,m]
		}

其中“shuntFlag”表示指示具体值数是否为0的单比特代码，而行“binary syntax of X[n，m]”是对应第三或第四种情形的具体值数X的二进制语法。

作为变型，也可选择另一种编码，其中无需输入结构模式的元素的具体值数。这种类型的编码使用连续包含下述指令的二进制语法：

插入或读出单比特“flagX”出现代码的指令，其指示文档中是否存在元素X的具体值，该指令与如比特数的该代码的大小有关，

只要插入或读出的出现代码指示出现元素X的一个新具体值就执行的循环指令，

联系该循环指令，插入或读出元素X的值或调用对应元素X的指令序列的指令，以及插入或读出指示文档中是否存在元素X的新具体值的新的单比特“flagX”出现代码的指令。

例如，这种二进制语法可为下述形式：

表6

FlagX	1bit
		while(flag X){

binary syntax of X
		FlagX	1bit
}

这种解决方案的优点是无需分析文档的整体结构模式以确定该结构中每个元素的最小和最大具体值数。

序列类型分组SEQ(X1，X2，...，Xn)的二进制语法对序列类型分组组件包括连续生成的指令序列，或调用这些指令序列。

例如，这种类型的语法可为下述形式：

表7

binary syntax of X1
	binary syntax of X2
...
	binary syntax of Xn

选择分组CHO(X1，X2，...，Xn)的二进制语法依次包括下述指令：

插入或读出组件编号代码“flagChoX”的指令，其表示组件编号Xi(i＝1...n)，而且表示在该压缩文档中将被插入或读出的分组中的下一个元素Xi，该指令与如比特数的该代码的大小有关，以及

测试元素编号代码的值的指令，每个测试指令与一个插入或读出元素Xi的值或调用对应组件代码的测试值所对应的元素Xi的指令序列的指令相关。

例如，这种类型的二进制语法可为下述形式；

表8

flagChoX	E(log2n))bits
		if(flagCho=0){
binaru syntax of X1
		}
elseif(flagCho=1){

binaru syntax of X2
		}
...
		elseif(flagCho=n-1){
binaru syntax of Xn
		}

其中n为分组中的组件编号，而“flagCho”为将在CHO分组中选择的组件代码。

如上所述，如果 $2^{E\left({\log }_2^{\left(n\right)}\right)}>n,$ 则可在二进制语法的最后添加下述行以检测故障：

Else	SpecificProcess

如果指示符“flagCho”的值不对应在CHO分组中预期的一个组件，则这个指令调用错误通知过程。

如果没有编码具体值数，也可使用“flagCho”的一个未用值(如果 $2^{E\left({\log }_2^{\left(n\right)}\right)}>n$ )以标记分组CHO的最后一个具体值：

表9

flagCho	E(log2(n))bits
		while(flagCho!=n){
if(flagCho=0){
		binary syntax of X1
}
		elseif(flagCho=1){
binary syntax of X2
		}

...
		elseif(flagCho=n-1){
binary syntax of Xn
		}
flagCho
		}

AND分组的二进制语法是由递归过程生成的。其包括嵌套CHO类型分组，每个分组确定哪个元素出现在说明中。

准确地说，这种类型的二进制语法是通过区别两种情形生成的，在第一种情形中分组仅包含一个组件，而在第二种情形中分组包含若干个组件。如果分组仅包含一个组件，这种分组的二进制语法与具有单个组件的序列类型分组的二进制语法相同。

如果分组包含n个组件，则可以AND(X₁，X₂，...，X_n)形式书写。这种分组的二进制语法依次包括下述指令：

插入或读出组件编号代码“flagChoX”的指令，其表示分组的组件编号Xi，而且表示在压缩文档中将被插入或读出的分组的下一个元素Xi，该指令与如比特数的该代码的大小有关，以及

测试元素编号代码的值的指令，每个测试指令与插入或读出元素Xi的值或调用对应组件代码的测试值所对应的元素Xi所对应的指令序列的指令相关，以及为包含分组中除组件Xi外的所有组件X1，..，Xn的 “无序分组”类型分组生成的指令序列。

例如，这种类型的二进制语法可为下述形式：

表10

FlagChoX	E(log2(n))bits
		if(flagCho=0){
binary syntax of X1
		binary syntax of AND(X2,...,Xn)

}
		Elseif(flagCho=1){
binary syntax of X2
		binary syntax of AND(X1,X3,...,Xn)
}
		...
Elseif(flagCho=k-1){
		binary syntax of Xk
binary syntax of AND(X1,...,Xk-1,Xk+1,...,Xn)
		}
		Elseif(flagCho=n-1){
binarV svntax of Xn
		binary syntax of AND(X1,X2,...,Xn-1)
}

这种二进制语法是由CHO(X₁，X₂，...，X_n)的二进制语法开始获得的，其中已从分组AND(X₁，...，X_k+1，...，X_n)的二进制中删除了组件X_k，在该二进制语法后已经添加了该分组中每个组件X_k(k在1和n之间)的二进制语法。因此这种二进制语法是递归的。

AND_NO类型分组的二进制语法与SEQ分组的二进制语法相同，其中也可通过在分组中采用适当的组件顺序优化编码。

下一步骤14包括读出文档2，通过执行在该文档上生成的二进制语法压缩其内包含的数据以便获得包含一个二进制代码序列的二进制流，其中文档的每个元素或基本信息元素的压缩值被定位。

准确地说，其目标是从文档的内容开始，并确定由二进制序列定义的不同“typeInfoFlag”，“flagX”，“loopflagX”，...代码的值，以插入到二进制流中。

根据第一种编码类型，该二进制流对每个元素e为(K.N.V₁..V_N)_e形式，其中N为元素e的具体值数，或对应元素e的连续信息元素的个数，K为用于确定元素e的代码，而V₁..V_N为元素e的N个具体值的可能已压缩的对应值。如果e为一组元素，其值V被分解为许多二进制序列(K.N.V)，因为其中包含元素。然而，在某些情况下可以省略N，特别是当该数为固定时。对于K也是一样的，例如在序列类型分组的情况下。

作为比较，考虑由标准ISO 8601定义的扩展持续时间表示格式：

sPnYnMnDTnHnMnS

其中s为“+”或“-”符号，nY表示年数(不定整数)，nM为月数(不定整数)，nD为天数(不定整数)，“T”为日期和时间之间的分隔符，nH为小时数(不定整数)，nM为分钟数(不定整数)，而nS为秒数(十进制)，所有这些元素都是可选的。

这种格式对应的一个结构模式可如下表示：

(\+|\-)P(\d+Y)?(\d+M)?(\d+D)?(T(\d+H)?(\d+M)?(\d+(\,\d+)?S)?)?

其中“\+”指示插入“+”字符，“(x|y)”指示插入元素x或v，“？”指示插入前一元素是可选的，而“\d+”表示任意位数的二进制数。

下面示意了这种类型的二进制语法的结构实例：

表11

Duration	Number of bits
		Sign	1

YearDefined	1
		if(YearDefined)
YearS	UINT_VLC
		MonthDefined	1
if(MonthDefined)
		Month	UINT_VLC
DayDeflined	1
		if(DayDefined)
Day	UINT_VLC
		HoursDefined	1
if(HoursDefined)
		Hours	UINT_VLC
MinutesDefined	1
		if(MinutesDefined)
Minutes	UINT_VLC
		SecondsDefined	1
if(SecondsDefined)
		Seconds	UINT_VLC，UINT_VLC

其中值Sign等于0表示“+”号，等于1表示“-”号。

因此，持续时间“+P1347Y”被编码如下：

+	+1347Y	M	D	H	M	S
							0	1101010010000011	0	0	0	0	0

这种编码系统需要22位，而常规编码需要48位。持续时间“-P1Y2MT2H”被编码如下：

-

1Y

2M

D

2H

M

S

1

100001

10010

0

10010

0

0

也就是说需要22位，而不是常规编码所必需的72位。

在此之前，可为压缩文档产生一个通用信头，其包含对文档说明有用的若干编码参数。因此，这种信头可包含所用的结构模式的签名，以及定义所用的编码的参数集合，例如如下：

指示编码每个元素的长度是必需的还是任选的，或其是否不在文档中出现的参数，

指示元素是否可以是子类型的参数，换言之，与比它们的基本类型更精确的类型相关，以及

指示用于具体值数的编码类型的参数。

文档中的每个信息元素也可与一个信头相关，其的出现及其特征在文档信头中被指定。

元素的信头也可包括元素的编码长度，以便能访问特定元素，同时不用解压缩文档中所有之前出现的元素就能解压缩文档。元素信头被插入到文档中，例如就在编码元素的值之前。

一般来说，通过在顺序读出压缩文档获得的二进制流之上执行由模式生成的二进制语法，解压缩文档包括顺序读出已压缩的文档。这种处理还提供一种方法检验压缩文档的结构是否对应以二进制语法编译的模式。

当结构模式中元素的具体值数未被编码时，元素编码的形式简单地为KV，以K_csc位终止的相同类型的每个元素集合的编码等于0。

这种编码只对编码复合形式，以及对没有最大具体值数或最小具体值数为0的元素有用。特别地，其对编码所包含的元素个数不等于2^p的选择类型分组很理想，其中p为一个整数。

这种类型的编码可与前一类型组合。在此情况下，所必要的就是将其包含在压缩文档的信头中，以及为必须定位若干具体值的编码位置分配一个比特。

根据本发明，该文档至少一种基本类型的信息元素与外部压缩模块16有关。通过这种方式，在读出文档时分析所遇到的信息元素的对应类型，以及当信息类型与外部压缩模块16有关时，其被应用到信息元素的内容中而且压缩的结果被插入到压缩文档中作为对应的信息元素的值。

例如，外部压缩模块针对声音信息可使用“mp3”标准，或对图像使用“jpeg”标准，对视频类型数据使用“MPEG1”或“MPEG2”标准，或对实数型值使用IEEE 754标准，或对字符串使用UTF8标准。

如果没有一种压缩模块与信息类型关联，则可使用缺省压缩模块，或可以它们在原始文档中出现的相同方式恢复这种类型的信息元素。

例如，编码CHO[0，*](a1，a2，a3)结构模式产生下述二进制语法：

表12

loopflagCho	UNIT_VLC bits
		for(k=0;k＜loopFlagCho;k++){
flagCho	2bits
		if(flagCho=0){
value Va1 of a1
		}
elseif(flagCho=1){
		value Va2 of a2
}
		elseif(flagCho=2){
value Va3 of a3
		}
}

如果我们现在想利用这种结构编码具体值“a₂ a₃ a₁ a₁a₃”，如果具体值数被编码，则编码结果如下：

00101 01 V_a2 10 V_a3 00 V_a1 00 V_a1 10 V_a3

其中“00101”表示具体值数的二进制值，在“UINT_VLC”格式中其等于5，而V_a1、V_a2和V_a3分别为a₁、a₂和a₃的具体值。

如果具体值数未被编码，则编码如下：

01 V_a2 10 V_a3 00 V_a1 00 V_a1 10 V_a3 11

“11”是具体值数的结束码，其在此情况下被结合到CHO分组的选择代码中。

在第一种情形中，结果是元素值编码不超过15位，而第二种情形更为紧凑，其编码为12位。

对具体值“b₂ b₁ a₁”的编码处理的结构如下：

SEQ[0，*](a₁[0，*]，CHO[0，*](b₁，b₂))

给定下述二进制语法：

表13

shuntFlagSeq	1bit
		if(shuntFlagSeq){
loopfalgSeq	UINT_VLCbits
		for((k=0;k＜loopFlagSeq;k++){
shuntFlaga1	1bit
		if(shuntFlaga1){
loopflaga1	UINT_VLCbits

for((k=0;k＜loopFlaga1;k++){
		value code Va1 of a1
}
		}
shuntFlagCho	1bit
		if(shuntFlagCho){
loopflagCho	UINT_VLCbits
		for((k=0;k＜loopFlagCho;k++){
flagCho	1bit
		if(flagCho=0){
value code Vb1 of b1
		}
elseif(flagCho=1){
		value code Vb2 of b2
}
		}
}
		}
}

对这种二进制语法的编码如下：

1      不等于0的序列的具体值数

000010 该序列的具体值数(在此情况下两次)

0      a＝0的具体值数

1      不等于0的CHO的具体值数

00010  CHO的具体值数(两次)

1      b₂的选择代码

V_b2      b₂的编码值

0         b₁的选择代码

V_b1      b₁的编码值

1         a＝0的具体值数

0000      1 a₁的具体值数(一次)

V_a1      a₁的编码值

0         CHO＝0的具体值数

如果属性的顺序无效(如同在XML语言中一样)，则可进行编码以预定顺序重新排序元素的属性，例如以字母数字顺序，接着取决于它们是否要求。这种排序相对减小了压缩说明的大小。

如果文档信头包括对长度编码是任选还是必须的指示，则元素与压缩文档中的信头相关，其包含如比特数的元素值的长度。这个特征使得能直接访问压缩文档中的元素，而无需使用二进制语法解压缩文档中在其之前的元素，以只读出所搜索的这些元素的对应长度。

元素的长度可如下编码。

如果文档信头包括编码元素长度是必须的指示，则利用下述公式计算如比特数的元素的长度L：

L＝8*p+h

其中p表示字节数(以ANSI编码或使用用于编码该数的每个字节的高位比特)，用于编码元素长度，而h为具有这个长度的剩余比特(h＜8)。

应指出，被调用用于编码元素的值的外部压缩模块16反过来可提供这个长度。

如果编码元素的长度不是必须的，则对应该元素的值的第一个比特的值指示下一个比特是否表示该元素的长度。

解压缩通过这种方式压缩的文档是通过下述步骤执行的：在文档结构模式之上执行步骤11～14以获得文档结构模式的结构组件的二进制语法，接着执行步骤14’以解码或解压缩文档，这个步骤包括浏览整个压缩文档执行通过步骤11～14获得的二进制语法以便能确定在文档中发现的压缩信息元素的类型和名称。利用外部压缩模块16获得的元素的值是使用对应的解压缩模块16’解压缩的。

应指出，如果必须处理(压缩或解压缩)具有相同结构模式的若干文档，则步骤11～13只执行一次，而且只需对要处理的每个文档应用步骤14和16(或14’和16’)。

此外，利用适当的转换处理可编辑类似于常规编程语言的结构模式的二进制语法17、17，，以生成二进制代码，用于可直接被计算机处理器执行或解释的压缩或解压缩程序6、6’。因此，根据本发明的方法能自动生成专用于给定结构模式的可执行并由此非常快速的压缩和解压缩程序。

Claims (36)

1.一种用于压缩结构化文档的方法，该结构化文档包含相互嵌套并且均与一种信息类型相关的信息元素，该结构化文档(2)与定义文档树型结构的至少一个结构模式(1；31，39，43)相关，并包含相互嵌套的结构组件(a3，a4，X，Y，a1，a5，a1，a2，A，B，32，33，34，40，44，45，46)，每种类型的文档信息由该模式中的一个组件定义，

其特征在于，该方法包括步骤：分析(11，13)文档结构模式(1)以便为该结构模式中的每个组件获得一个可执行指令序列(5)，该指令序列包括用于插入控制代码和信息元素的压缩值或组件指令序列调用代码到一个二进制流中的指令、用于控制作为控制代码值的函数的序列的执行的指令，在该结构化文档(2)上执行指令序列以压缩(14)该结构化文档(2)到包含文档中的信息元素的压缩值的一个二进制流(10)中。

2.根据权利要求1的用于压缩结构化文档的方法，其特征在于，其还包括在结构化文档(2)之上执行指令序列的步骤。

3.根据权利要求1或2的用于压缩结构化文档的方法，其特征在于，该文档包含不能被分解为子元素的基本元素，而且至少一种基本信息元素预先与适合该类型信息的压缩算法(16)相关，该方法包括在执行指令序列期间(5)对具有与所述算法相关的信息类型的每个信息元素的值应用压缩算法(16)。

4.根据权利要求1的用于压缩结构化文档的方法，其特征在于，本方法包括编译(17)所述结构模式的每个组件所获得的指令序列(5)的步骤，以获得专用于所述结构模式，并可被计算机直接执行或解释以压缩具有该结构模式(1)的文档(2)的二进制编码程序(6)。

5.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该方法包括标准化(12)文档结构模式(5)的预先步骤(12)，以便获得该模式中组件的单个预定顺序。

6.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该方法包括用于优化和简化文档结构模式的预先步骤(12)，其中包括减少结构组件中嵌套级别数。

7.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该文档(2)中的至少一个信息元素与所生成的二进制流(10)中的一个信息元素代码相关，其被打上标记以便能直接访问该二进制流中的特定压缩信息元素，而不必解压缩该二进制流中即将被解压缩的元素之前的信息元素。

8.根据权利要求1的用于压缩结构化文档的方法，其特征在于，所生成的压缩文档(10)包括用于结构化文档(2)中的每个信息元素的代码，其中该代码用以确定与该信息元素相关的信息类型以及该信息元素的二进制值。

9.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该文档(2)的结构模式(1)包括至少一个信息类型的子类型的定义，而且为具有n个子类型(S₁，S₂，...，S_n)的类型(TX)的组件生成的指令序列依次包括：

插入一个子类型代码(″flagPoly″)的指令，表示将应用于对应该文档的组件的元素(X)的子类型，该指令与以比特数形式的该代码的大小有关，以及

测试该子类型代码的值的指令，每个测试指令与对应该子类型代码测试值的元素的子类型(S₁，S₂，...，S_n)的索引相关，以及为压缩与该子类型相关的元素(X)生成的指令序列。

10.根据权利要求1的用于压缩结构化文档的方法，其特征在于，为对应元素集合的多个具体值的组件生成的二进制流包括一个预定结束代码，其中该组件集合由文档(2)中的至少一个信息元素组成。

11.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该结构模式(1)的每个组件对应于文档(2)中的一个元素集合，每个元素集合至少包含一个信息元素，而且每个组件还与可能的具体值数的集合相关，用以指示对应于这个组件的元素集合在直接高于其所属级别上一级的信息元素中可能出现的次数。

12.根据权利要求11的用于压缩结构化文档的方法，其特征在于，为具体值数等于0或1的组件生成的指令序列依次包括：

在一个比特上插入一个出现代码(″falgX″)的指令，指示对应于该组件的元素(X)集合是否出现在该文档(2)中，

测试该出现代码的值的指令，以及

根据该测试指令，如果出现代码值指示在该文档中出现该元素集合(X)，则独立于相关的具体值数为该组件生成指令序列。

13.根据权利要求11或12的用于压缩结构化文档的方法，其特征在于，为具体值数在n和m之间的组件生成的指令序列依次包括下述步骤：

插入具体值数代码(″loopflagX″)的指令，其指示对应于该压缩文档中该组件的元素集合(X)的连续具体值数减去最小具体值数n，该指令与以比特数形式的该代码的大小有关，

定义对应于具体值数代码的值的迭代次数的循环指令，以及

根据该循环指令，独立于相关具体值数为该组件生成指令序列。

14.根据权利要求13的用于压缩结构化文档的方法，其特征在于，为具体值数在0和m之间的组件生成的指令序列还包括：

插入出现代码(″shuntflagX″)的指令，用以指示在该文档中是否存在至少一个对应于该组件的元素集合(X)的具体值，以及

如果出现代码值指示存在至少一个元素集合，则测试与为具体值数在1和m之间的组件所生成的指令序列相关的出现代码的指令。

15.根据权利要求11的用于压缩结构化文档的方法，其特征在于，为具体值数在n和m之间的组件生成的指令序列依次包括下述步骤：

插入单比特出现代码(″flagX″)的指令，用以通知对应该文档中的组件的元素集合(X)的具体值，该指令与以比特数形式的该代码的大小有关，

只要插入的出现代码指示出现了该元素(X)集合的一个新具体值，则执行的循环指令，

根据该循环指令，为该组件生成的指令序列，以及插入一个新的单个比特出现代码(″flagX″)的指令，通知在该文档中的该元素集合(X)的一个新的具体值。

16.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该结构模式(1)中的每个组件对应包含至少一个信息元素的元素集合，该结构化文档(2)的结构模式(1)包括有序组件的至少一个序列类型组件，其中该序列中的出现顺序定义了对应该序列类型分组的组件的文档中元素集合的出现顺序，并为包含n个组件(X1，X2，...，Xn)的序列生成的指令序列依次包括为序列中的每个组件生成的指令序列。

17.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该结构模式(1)中的每个组件对应包含至少一个信息元素的元素集合，要压缩的文档的结构模式(1)包括：选择组件分组类型的至少一个组件，每个选择组件对应于一个信息元素集合；对应选择组件所对应的文档中的一个信息集合的选择分组类型的组件；以及为一组选择组件生成的指令序列包括定义n个对应元素集合(X1，X2，...，Xn)的n个组件；其依次包括下述指令：

插入一个信息元素集合数代码(″flagChoX″)的指令，表示在n个元素集合(X1，X2，...，Xn)中有哪些元素集合在该文档(2)中出现，该指令与以比特数形式的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应信息元素集合(Xi)的组件所生成的指令序列相关，该元素集合(Xi)对应元素集合数代码的测试值。

18.根据权利要求1的用于压缩结构化文档的方法，其特征在于，该结构模式(1)的每个组件对应包含至少一个信息元素的元素集合，将被压缩的文档的结构模式(1)包括至少一个无序组件类型的分组，在该无序分组中的每个组件对应一个元素集合，而且对应该文档中一个分组的无序分组类型的分组以任意顺序包含对应无序类型分组的组件的所有元素集合，而且为无序类型分组生成的指令序列包含对应该文档中n个元素集合(X1，X2，...，Xn)的n个组件，其依次包括下述指令：

插入一个元素集合(Xi)数代码(″flagChoX″)的指令，指示在该文档(2)中出现的下一个元素集合，该指令与以比特数形式的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应元素集合(Xi)的组件所生成的指令序列相关，该元素集合对应元素集合数代码的测试值，而且为无序类型分组生成的指令序列包括除对应该元素集合(Xi)的组件之外的无序分组中的所有组件(X1，...，Xn)。

19.一种用于解压缩结构化文档的方法，该结构化文档包含相互嵌套并且均与一种信息类型相关的信息元素，该结构化文档(2)与定义文档树型结构的至少一种结构模式(1；31，39，43)相关，并且包含相互嵌套的结构组件(a3，a4，X，Y，a1，a5，a1，a2，A，B，32，33，34，40，44，45，46)，每种类型的文档信息由该模式中的一个组件定义。

其特征在于，其包括分析(11，13)文档结构模式(1)以便为该结构模式中的每个组件获得一个可执行指令序列(5)的步骤，该序列包括用于读出二进制流中的控制代码和信息元素的压缩值或用于读出调用代码以调用组件指令序列的指令，该二进制流形成压缩文档(10)，以及用于控制序列的执行作为控制代码值的函数的指令，其中在压缩文档(10)上执行指令序列以与原始文档(2)相同格式恢复文档(2′)并且具有至少等效结构。

20.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，其还包括在形成要被解压缩(10)的文档的二进制流上执行指令序列(5)的步骤。

21.根据权利要求19或20的用于解压缩结构化文档的方法，其特征在于，该结构化文档(2)包含不能分解为信息子元素的基本元素，以及至少一种基本元素信息类型，该基本元素信息类型与适合该信息类型的解压缩算法相关(16′)，本方法包括在形成压缩文档(10)的二进制流之上执行指令序列(5)期间，检测对应二进制流中所述信息类型的信息元素二进制代码，并对这种二进制代码应用该解压缩算法。

22.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，其包括编译所述结构模式(1)的每个组件所获得的指令序列(5)的步骤，以获得专用于所述结构模式的二进制解码程序(6)，并可被计算机直接执行或解释以压缩具有该结构模式的文档(10)。

23.根据权利要求19至22任何一项的用于解压缩结构化文档的方法，其特征在于，其包括用于标准化(12)文档结构模式(5)的预先步骤，以便获得该模式的组件的单个预定顺序。

24.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，其包括用于优化和简化文档结构模式的预先步骤(12)，其中包含减少结构组件分组中分层级数。

25.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，识别压缩文档(10)的二进制流中至少一个信息元素代码，以便能直接访问这个信息元素，而不必解压缩该二进制流中该信息元素之前的信息元素。

26.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，压缩文档(10)包括用于原始文档中每个信息元素的代码，用以确定与该信息元素相关的信息类型以及所压缩信息元素的二进制值。

27.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，将被压缩的文档(10)的结构模式(1)包括至少一种信息类型(TX)的子类型的定义，而且为具有n个子类型(S₁，S₂，...，S_n)的类型(TX)的组件生成的指令序列(5)依次包括下述指令：

读出子类型代码(″flagPoly″)的指令，表示将应用于对应该文档中的组件的元素(X)的子类型数，该指令与以比特数形式的该代码的大小相关，以及

测试该子类型代码的值的指令，每个测试指令与对应所测试子类型代码值的元素(X)的子类型(S₁，S₂，...，S_n)的索引相关，以及为解压缩与该子类型相关的元素(X)生成的指令序列。

28.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，通过一个预定的二进制代码，在压缩文档(10)的二进制流中，为包含对应该模式(1)的组件的至少一个信息元素的元素集合的一组若干具体值的结束打上标记。

29.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，该结构模式(1)中的每个组件对应文档(10)的二进制流中的一个元素集合，其包含至少一个信息元素，而且还与一组多个可能的具体值相关，用以指示对应这个结构模式的元素集合出现在高于其所属级别一级的信息元素中的次数。

30.根据权利要求29的用于解压缩结构化文档的方法，其特征在于，为具体值数等于0或1的组件所生成的指令序列依次包括下述指令：

读出单比特出现代码(″flagX″)的指令，用以指示对应该组件的元素集合(X)是否出现在该压缩文档中，

测试该出现代码值的指令，以及

根据该测试指令，如果出现代码的值指示在该压缩文档中出现该元素集合(X)，则独立于相关的具体值数为该组件生成的指令序列。

31.根据权利要求29或30的用于解压缩结构化文档的方法，其特征在于，为具体值数在n和m之间的组件生成的指令序列依次包括下述指令：

读出具体值数代码(″loopflagX″)的指令，其指示在对应该该组件的元素集合(X)在压缩文档中的连续具体值数减去最小具体值数n，该指令与以比特数形式的该代码的大小有关，

定义对应具体值数代码的值的迭代数量的循环指令，以及

根据该循环指令，独立于相关具体值数为该组件生成的指令序列。

32.根据权利要求31的用于解压缩结构化文档的方法，其特征在于，为具体值数在0和m之间的组件生成的指令序列还包括：

读出单个比特出现代码(″shuntflagX″)的指令，用以指示在该压缩文档中是否存在对应该组件的元素集合(X)的至少一个具体值，以及

如果出现代码的值指示存在至少一个元素集合，则根据为具体值数在1和n之间的组件生成的指令序列测试出现代码的值的指令。

33.根据权利要求29的用于解压缩结构化文档的方法，其特征在于，为具体值数在n和m之间的组件生成的指令序列依次包括下述指令：

读出单个比特出现代码(″flagX″)的指令，用以指示在该压缩文档(10)中是否存在对应该组件的元素集合(X)的一个具体值，该指令与以比特数形式的该代码的大小有关，

只要在压缩文档的二进制流中读出的出现代码指示存在该元素集合(X)的一个新具体值就执行的循环指令，

根据该循环指令，为该组件生成的指令序列，以及插入一个新的单个比特出现代码(″flagX″)的指令，用以指示在该压缩文档(10)中是否存在该元素集合(X)的一个新的具体值。

34.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，该结构模式(1)中的每个组件对应包含至少一个信息元素的元素集合，该压缩文档(10)的结构模式(1)包括至少一个有序组件序列类型组件，其中在序列中的出现顺序定义了在对应该序列类型分组的组件的文档中元素集合的出现顺序，而且为包含n个组件(X1，X2，...，Xn)的序列生成的指令序列依次包括为序列中的每个组件生成的指令序列。

35.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，该结构模式(1)中的每个组件对应包含至少一个信息元素的元素集合，要解压缩的文档的结构模式(1)包括选择组件分组类型的至少一个组件，每个选择组件对应一个信息元素集合，该文档中选择组件分组类型的组件对应选择组件所对应的的一个信息集合，而且为选择组件分组生成的指令序列分别包括定义n个元素集合的n个组件(X₁，X₂，...，X_n)，其依次包括下述指令：

读出一个元素集合数代码(″flagChoX″)的指令，表示在n个元素集合(X1，X2，...，Xn)中出现在该文档中的元素集合，该指令与以比特数形式的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应元素集合数代码的测试值所对应的元素集合(Xi)的组件生成的指令序列相关。

36.根据权利要求19的用于解压缩结构化文档的方法，其特征在于，该结构模式(1)的每个组件对应包含至少一个信息元素的元素集合，而且要压缩的文档的结构模式(1)包括无序组件类型的至少一个分组，该无序分组中每个组件对应一个元素集合，而且对应该文档中一个分组的无序分组类型的分组以任意顺序包含对应无序类型分组的组件的所有元素集合，而且为无序类型分组生成的指令序列包含对应该文档中n个元素集合(X₁，X₂，...，X_n)的n个组件，其依次包括下述指令：

读出一个元素集合(Xi)数代码的指令，用以指示在该文档(10)中出现的下一元素集合，该指令与以比特数形式的该代码的大小有关，以及

测试元素集合数代码的值的指令，每个测试指令与为对应该元素集合数代码的测试值所对应的元素集合(Xi)的组件生成的指令序列相关，而且为无序类型分组生成的指令序列包括除对应该元素集合(Xi)的组件之外的无序分组中的所有组件(X₁，...，X_n)。

Images