Method and system for encoding a mark-up language document

• US 7,669,120 B2
• Filed: 06/21/2002
• Issued: 02/23/2010
• Est. Priority Date: 06/21/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Qian, Liao, Hongbin, Zhu, Wenwu
• Primary Examiner(s): Stevens; Robert
• Application Number:
  US10/177,830
• Publication Number:
  US 20040003343A1
• Time in Patent Office: 2,804 Days
• Field of Search: 715/523, 715/513, 715/501.1, 715/205, 715/234.242, 715/249, 715/234, 715/239, 715/242, 701/101
• US Class Current: 715/242
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

A method and system for encoding a mark-up language document is provided, in which, the structure of the mark-up language document is condensed by removing those parts of the structure that are fixed, and by expressing the variable parts of the structure in terms of whether or how often they occur. A template that specifies which parts of the structure are fixed and which parts are variable may be provided to both the device that is transmitting the mark-up language document and the device that is receiving the mark-up language document.

Claims

1. A method implemented by a sending computer, the method comprising:

identifying a template that defines a structure for a block of mark-up language wherein the block of mark-up language has an associated document type and wherein the block of mark-up language comprises;

a plurality of elements;

a plurality of sets of tags; and

a plurality of data items;

wherein individual ones of the plurality of elements each comprise;

a particular set of tags from the sets of tags; and

a particular data item from the plurality of data items;

parsing the template to build a first logical tree that represents a structure of the plurality of sets of tags in the block of mark-up language, wherein the structure defines;

relative locations of sets of tags of fixed elements, which are present and occur a fixed number of times in the block of mark-up language;

relative locations of sets of tags of optional elements, which may or may not be present, and if present, occur only one time in the block of mark-up language;

relative locations of sets of tags of variable elements, which are present and may occur any number of times in the block of mark-up language; and

relative locations of sets of tags of variably optional elements, which may or may not be present, and if present, may occur any number of times in the block of mark-up language;

sending the template to a receiving computer, thereby enabling the receiving computer to build a second logical tree that is identical to the first logical tree;

identifying a document block having the document type, such that;

the document block comprises;

a plurality of document elements;

a plurality of sets of document tags; and

a plurality of document data items;

wherein individual ones of the plurality of document elements each comprise;

a particular set of document tags from the plurality of sets of document tags; and

a particular document data item from the plurality of document data items;

a structure of the plurality of sets of document tags in the document block is represented by the first logical tree such that each individual document element of the plurality of document elements is one of;

a fixed document element corresponding to a fixed element, as defined by the first logical tree;

an optional document element corresponding to an optional element, as defined by the first logical tree;

a variable document element corresponding to a variable element, as defined by the first logical tree;

or

a variably optional document element corresponding to a variably optional element, as defined by the first logical tree,

encoding the document block using the first logical tree by;

for each document element in the document block, separating the set of document tags of the document element from the document data item of the document element, resulting in a structure component of the document block and a data component of the document block, wherein the structure component of the document block is distinct from the data component of the document block;

for each fixed document element in the document block, removing from the structure component of the document block, the set of document tags of the fixed document element;

for each optional document element in the document block, replacing in the structure component of the document block, the set of document tags of the optional document element with an indicator that the optional document element is present;

for each optional element indicated in the first logical tree, but not present in the document block, adding to the structure component of the document block, an indicator that the optional element is not present;

for each variable document element in the document block;

determining a number of times that the variable document element appears in the document block;

adding to the structure component of the document block, an indicator of the number of times that the variable document element appears in the document block; and

removing from the structure component of the document block, the set of document tags associated with each occurrence of the variable document element;

for each variably optional document element in the document block;

determining a number of times that the variably optional document element appears in the document block;

adding to the structure component of the document block, an indicator of the number of times that the variably optional document element appears in the document block; and

removing from the structure component of the document block, the set of document tags associated with each occurrence of the variably optional document element; and

for each variably optional element indicated in the first logical tree, but not present in the document block, adding to the structure component of the document block, an indicator that the variably optional element is not present,

such that the structure component of the document block, when fully encoded, does not include any sets of document tags, does not include any representation of fixed elements, and comprises;

indicators of the number of times that variable document elements appear in the document block;

indicators of the number of times that variably optional elements appear in the document block; and

indicators of variably optional elements that are not present in the document block; and

sending the encoded structure component of the document block and the data component of the document block from the sending computer to the receiving computer with an indication of the document type, thereby enabling the receiving computer to use the second logical tree to decode the encoded document block.

2. A computer-readable storage medium having stored thereon computer-executable instructions for performing the method of claim 1.

3. A system for transferring a mark-up language document, the mark-up language having a plurality of elements, each element comprising a data item and a set of tags bounding the data item, the system comprising:

a sending device comprising;

a processor;

a memory;

a component for determining, based on a mark-up language template, which elements appear in the mark-up language document a fixed number of times;

a component for removing from the mark-up language document, the tags that correspond to those elements determined to appear a fixed number of times;

a component for determining, based on the mark-up language template, which elements of the mark-up language document appear in the mark-up language document a variable number of times;

a component for removing from the mark-up language document, the tags that correspond to those elements determined to appear a variable number of times;

a component for creating a message, separate from the mark-up language document, that contains numerical values that correspond to the number of times that those elements that are determined to appear in the mark-up language document a variable number of times appear, but does not contain information regarding those elements that are determined to appear in the mark-up language document a fixed number of times; and

a component for transmitting the message and the mark-up language document sans tags to a receiving device, wherein the receiving device is configured to;

receive the message and the mark-up language document sans tags;

determine which elements appear in the mark-up language document a fixed number of times;

determine which elements of the mark-up language document appear in the mark-up language document a variable number of times; and

recreate the mark-up language document with tags.

4. A computer-implemented method for transferring a mark-up language document, the mark-up language having a plurality of elements, each element comprising a data item and a set of tags bounding the data item, the computer-implemented method comprising:

determining, based on a mark-up language template, which elements appear in the mark-up language document a fixed number of times;

removing from the mark-up language document, the tags that correspond to those elements determined to appear a fixed number of times;

determining, based on the mark-up language template, which elements of the mark-up language document appear in the mark-up language document a variable number of times;

removing from the mark-up language document, the tags that correspond to those elements determined to appear a variable number of times;

creating a message, separate from the mark-up language document, that contains numerical values that correspond to the number of times that those elements that are determined to appear in the mark-up language document a variable number of times appear, but does not contain information regarding those elements that are determined to appear in the mark-up language document a fixed number of times; and

storing the message in computer storage media; and

transmitting the message and the mark-up language document sans tags to a receiving device, wherein the receiving device is configured to;

receive the message and the mark-up language document sans tags;

determine which elements appear in the mark-up language document a fixed number of times;

determine which elements of the mark-up language document appear in the mark-up language document a variable number of times; and

recreate the mark-up language document with tags.

5. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 4.