Method and system for improving data transmission and storage of markup language documents

Abstract

A method and system are provided for improving the transmission and storage of documents utilizing markup languages. The system converts the markup language tags to tokens and combines the tokens with the content information to create a token stream. The token stream is further compressed and stored on a device or transmitted over a communications network. The compressed token stream may then be decompressed and de-tokenized to return the markup language document to its original content form. The method may be performed on a computing device or over the transmission network.

Claims

What is claimed is:

1. A method in a computer system for improving data transmission of markup language documents, wherein the markup language documents include markup tags and information characters, the method comprising:

parsing a document to recognize the markup tags;

accessing a substantially markup-tag-specific table of tags, wherein the table lists the markup tags and assigns them tokens;

converting the markup tags in the document to tokens which are adapted to be readily recognizable by a compression algorithm without the transmission of dictionary information;

creating a token stream;

compressing the token stream using said compression algorithm;

decompressing the token stream using the compression algorithm; and

recreating the markup tags from the token stream.

2. The method as recited in claim 1, wherein converting markup tags to tokens includes:

parsing the document to recognize the tags;

accessing a table of tags, wherein the table lists the tags and their associated tokens; and

replacing the tags with the tokens.

3. The method as recited in claim 2, wherein parsing is performed by a recursive-descent parser.

4. The method as recited in claim 2, wherein the table of tags is extensible.

5. The method as recited in claim 1, wherein the markup tags are hypertext markup language tags.

6. The method as recited in claim 1, wherein the markup tags are extensible markup language tags.

7. The method as recited in claim 1, wherein the token stream includes the converted markup tags.

8. The method as recited in claim 1, wherein the token stream includes one or more information characters.

9. The method as recited in claim 8, wherein each of the information characters are tokens.

10. The method as recited in claim 1, wherein compressing the token stream includes encoding the token stream using Huffman coding.

11. The method as recited in claim 1, wherein compressing the token stream includes encoding the token stream using arithmetic coding.

12. The method as recited in claim 1, wherein compressing the token stream includes encoding the token stream using LZ77 coding.

13. The method as recited in claim 1, wherein compressing the token stream includes encoding the token stream using LZ78 coding.

14. The method as recited in claim 1, wherein compressing the token stream includes encoding the token stream using LZW coding.

15. The method as recited in claim 1, wherein converting the markup tags, creating a token stream and compressing the token stream are performed on a computer sending the markup language document.

16. The method as recited in claim 1, wherein converting the markup tags, creating a token stream and compressing the token stream are performed on a web browser.

17. The method as recited in claim 1, wherein converting the markup tags, creating a token stream and compressing the token stream are performed on a transmission network.

18. The method as recited in claim 1, wherein decompressing the token stream and recreating the markup tags are performed on a computer receiving the markup language document.

19. The method as recited in claim 1, wherein decompressing the token stream and recreating the markup tags are performed on a web browser.

20. The method as recited in claim 1, wherein decompressing the token stream and recreating the markup tags are performed on a transmission network.

21. A method in a computer system for improving data transmission of markup language documents, the method comprising:

parsing the document to distinctly recognize a plurality of redundant markup tags;

accessing a markup-specific table of tags, wherein the table lists the markup tags and a plurality of associated tokens;

converting said markup tags into said tokens which are adapted to be readily recognizeable by a compression algorithm without the transmission of dictionary information; and

creating a token stream using said compression algorithm.

22. The method as recited in claim 21, wherein parsing is performed by a recursive-descent parser.

23. The method as recited in claim 21, wherein the table of tags is extensible.

24. The method as recited in claim 21, wherein the markup tags are hypertext markup language tags.

25. The method as recited in claim 21, wherein the markup tags are extensible markup language tags.

26. The method as recited in claim 21, wherein the token stream includes the converted markup tags.

27. The method as recited in claim 21, wherein the token stream includes one or more information characters.

28. The method as recited in claim 27, wherein each of the information characters are tokens.

29. The method as recited in claim 21 further comprising compressing the token stream.

30. The method as recited in claim 29, wherein compressing the token stream includes encoding the token stream using Huffman coding.

31. The method as recited in claim 29, wherein compressing the token stream includes encoding the token stream using arithmetic coding.

32. The method as recited in claim 29, wherein compressing the token stream includes encoding the token stream using LZ77 coding.

33. The method as recited in claim 29, wherein compressing the token stream includes encoding the token stream using LZ78 coding.

34. The method as recited in claim 29, wherein compressing the token stream includes encoding the token stream using LZW coding.

35. The method as recited in claim 29, wherein converting the markup tags, creating a token stream and compressing the token stream are performed on a computer sending the markup language document.

36. The method as recited in claim 29, wherein converting the markup tags, creating a token stream and compressing the token stream are performed on a web browser.

37. The method as recited in claim 29, wherein converting the markup tags, creating a token stream and compressing the token stream are performed on a transmission network.

38. The method as recited in claim 29 further comprising decompressing the token stream.

39. The method as recited in claim 38, wherein decompressing the token stream is performed on a computer receiving the markup language document.

40. The method as recited in claim 38, wherein decompressing the token stream is performed on a web browser.

41. The method as recited in claim 38, wherein decompressing the token stream is performed on a transmission network.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

Not Applicable.

BRIEF DESCRIPTION OF THE DRAWINGS

The objectives and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description of the drawings, in which:

FIG. 1 is a block diagram illustrating a computing environment for implementing the present invention;

FIG. 2 is a block diagram illustrating a network environment for implementing the present invention;

FIG. 3 is a block diagram further illustrating network environment in FIG. 2 for practicing the present invention; and

FIG. 4 is a flow diagram illustrating a preferred method for improving data transmission and storage of markup language documents in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides a method and system for improving the transmission and storage of documents utilizing markup languages. FIG. 1 is a block diagram illustrating a typical computing device 10 in which invention may be implemented. The computing device 10 is an example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the present invention. The present invention is operational with numerous general purpose or special purpose computer systems. Examples of well known computing systems that are suitable for use with the present invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programable consumer electronics, network PCs, mini computers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

The invention may be described in the general context of computer-executable instructions such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components and data structures, that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

Referring back to FIG. 1, computing device 10 typically includes memory 12, processor 14, and input/output interface 16. Input/output interface 16 may include a number of input devices such as a keyboard, mouse, pen, voice input devices or touch input devices. The input/output interface 16 may also include various output devices including a display, speakers, or a printer. The input/output interface 16 also includes communications connections that allow the computing device to communicate with other devices. The communication connections may include numerous communication media. Communication media may include, but are not limited to, wired media such as a wire network or direct wire connection, and wireless media such as acoustic, RF, infrared and other wireless media.

As described in greater detail below, the present invention may be implemented in a single computing device or across multiple computing devices through a computer network. As shown in FIG. 2, a block diagram illustrates multiple devices 18 in communication with one another either through a network 20 or through a direct communication link between the devices 18. The devices 18 may be personal computers, servers, routers, network PCs, peer devices, or common network nodes, and they typically include many or all of the elements described above relative to the computing device 10 in FIG. 1. The present invention may be performed using a preferred method that is described in greater detail below using one device or across multiple devices within a network. FIG. 3 is a block diagram illustrating a preferred network embodiment for practicing the method of the present invention. As devices 18 (FIG. 2) are coupled with a network 20, the network 20 may include servers 22 that are in communication with one another. The communication may be implemented through a series of wired connections 24 or may be a wireless type connection through a satellite network 26. As would be understood, devices 18 (FIG. 2) may also be in direct communication with the satellite network 26 to facilitate direct communication between two or more devices 18. Alternatively, devices 18 may be in communication directly with a satellite network 26 to communicate with a server 22 that in turn communicates with another device 18. Combinations of the above are all included within the scope of the present invention.

FIG. 4 is a flow diagram illustrating a preferred method for improving data transmission and storage of markup language documents. At step 30, the system converts the tags within the markup language document to tokens. As mentioned above, two types of information are typically included in markup language documents. First, content information that includes the readable information characters that the user sees and secondly, the markup instructions or tags that tell the displaying program how to visually represent the content information characters. The content information characters within the document may be considered to already each be a single token. Converting the tags to tokens is accomplished by parsing the document, according to well known techniques, to recognize the markup language tags. A lookup table is then utilized by the system to match the markup language tags to an appropriate token.

At step 32, the system creates a token stream from the converted markup tags and the non-tag characters. The token stream is placed into another document. At step 34, the token stream is compressed by encoding the sequence of tokens into transmittable symbols. Each symbol is a unique sequence of binary bits. The symbol sequences are not all the same size and are carefully chosen so that those symbols that appear most frequently are encoded with the fewest bits. Furthermore, the bit streams are such that no concatenation of valid strings can be confused with some other string and that no initial substring of a valid string is equal to a shorter valid string. A variety of well known compression algorithms may be employed to compress the token stream. Huffman coding is a preferred compression technique. A slight improvement may be realized by using a similar technique, arithmetic coding, to compress the token stream. Additional compression encoding methods include substitution codes such as LZ77, LZ78, and LZW.

At this point, the compressed string of binary information is ready for transmission. Systems receiving this binary representation decompress the binary stream and recreate the markup language document at the receiving system.

At step 36, the token stream is decompressed at the receiving system by performing the same encoding algorithm used in the compression at step 34. At step 38, the markup tags are recreated utilizing the same table used to create the original token stream resulting in a markup language document having tags and content character information. Markup languages are not case sensitive and are not sensitive to placement of spaces within the tags. As such, the case and precise spacing of information within the tag is discarded when creating the token stream at step 32. This may result in a reproduced document, at step 38, that differs in these attributes from the original document. However, the reproduced document has the exact same semantic meaning and produces the same display representation for the user.

In another embodiment, the markup recreation at step 38 may not be needed. As a first step in creating or converting the markup tags to tokens, the document must be parsed to recognize the tag information and create a document containing the resulting tokens. A markup language viewing or printing program may be programmed to recognize the token stream instead of the markup language tags. In other words, the displaying of the content information is driven by the token stream and not the markup tags. However, most viewing and printing programs must have the capability of displaying documents using markup tags and thus will have to retain the ability to parse the token stream to recreate the markup tags.

As mentioned above, a table is utilized to assign the markup language tags to tokens. This token look-up table assigns token values to each sequence of characters representing a tag. For example, HTML tags include a start tag, an end tag, and HTML attributes that are each assigned to a particular token. Further, this token look-up table is extensible to include XML tags and their corresponding attributes created by users. Additionally, the extensible nature of this table allows for future expansion of new HTML tags and other unforeseen markup language tags and attributes. That is, the extensible nature of the token look-up table allows users to expand the table. A preferred embodiment does this by reserving a number of token codes for definition by the tag to token converter. Table A provided below illustrates a preferred token look-up table. The table assigns content characters, tag, and attribute names to token values. No particular sequence of assignments is optimal, and thus, the table is completely arbitrary and one assignment is as good as any.

Table B provided below illustrates a token compression table utilized by the compression algorithm created by the compression algorithm as described above at step 34. This table takes the token stream and creates an appropriate Huffman code. The assignment of the variable length bit strings to token values is critical to the performance of a preferred method. The assignments in the compression table are chosen based upon the statistical frequencies of the various tokens encountered in an actual sample of HTML and XML coded documents.

In operation, a user creates a HTML or XML document that is placed on the internet or the World Wide Web. The document is made available on the web and the markup language tags within the document are converted to tokens utilizing the algorithm stated above. The converted tags are combined with the character information to create a token stream. This token stream is further compressed using a of substitution code, preferably Huffman coding. The document is now compressed to the point where limited bandwidth applications may be able to transmit and receive the document. One such example of a narrow bandwidth application is transmitting documents via a satellite network. Users receiving the document then decompress the document using the same Huffman code. Then, the markup tags are recreated using the same algorithm to create the tokens. The document is now ready for display at the receiving units or receiving device location.

The present invention provides a number of advantages. Tokenizing the HTML code extracted from the World Wide Web has measured a 25% compression improvement over standard compression methods alone. When tested with a sample of 500 HTML and XML files extracted from the World Wide Web, the tokenizing process on average, converted each 1000 characters of HTML source code to 832 tokens. Thus, the tokenizing step alone can compress the size of the document's binary representation. Further converting the markup language tags to tokens gives the tag information the same semantic weight as the character content information. Thus, the same document can be compressed to a higher degree resulting in a smaller file and faster transmission.

Although the invention has been described with reference to a preferred embodiment as illustrated in the attached drawing figures, it is noted that substitutions may be made and equivalents employed herein without departing from the scope of the invention as recited in the claims.