Method and apparatus for sending and receiving a data structure in a constituting element occurrence frequency based compressed form

• US 7,054,953 B1
• Filed: 11/07/2000
• Issued: 05/30/2006
• Est. Priority Date: 11/07/2000
• Status: Expired due to Fees

• Current Assignee: Xevo, Inc. (Lear Corporation)
• Original Assignee: UI Evolution Incorporated
• Inventors: Nakajima, Satoshi
• Primary Examiner(s): Tran, Philip B.
• Application Number:
  US09/708,179
• Time in Patent Office: 2,030 Days
• Field of Search: 709/246, 709/247, 709/201, 709/238, 707/101, 710/68, 341/51
• US Class Current: 709/246
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

In accordance with a first aspect of the present invention, a digital device is provided with a data transmitter designed to receive constituting elements of a data structure, determine occurrence frequency of each unique constituting element in the data structure, assign a cookie representation to each of the unique constituting elements based at least in part on the occurrence frequencies of the unique constituting elements, and transmit the data structure implicitly in a substantively equivalent form that allows a receiver of the data structure in the substantively equivalent form to be able to reconstitute the data structure using the occurrence frequency based cookie representations. In accordance with another aspect of the present invention, a digital device is provided with a data receiver designed to receive unique constituting elements of a data structure transmitted in a pre-determined manner, infer corresponding cookie representations for the received unique constituting elements in accordance with their manner of transmissions under the pre-determined manner of transmission, and receive the constituting elements of the data structure in a representative form. In one embodiment, the data receiver is further designed to reconstitute the constituting elements of the data structure, received in the representative form, based on the inferred cookie representations.

Claims

1. A method comprising:

receiving a plurality of constituting elements of a data structure;

determining occurrence frequency of each unique constituting element in said data structure;

assigning a cookie representation to each of said unique constituting elements based at least in part on the occurrence frequencies of said unique constituting elements;

transmitting a list of said unique constituting elements in the order of their occurrence frequencies to allow a receiver of said list of said unique constituting elements to infer the corresponding cookie representations of the unique constituting elements; and

transmitting said data structure in a representative form encoded with said cookie representations.

2. The method of claim 1, wherein said determining and assigning comprises assigning an initial cookie representation to each unique constituting element as the constituting elements are received, and tracking occurrence frequencies of the unique constituting elements, and upon receipt of all constituting elements of the data structure, re-assigning a final cookie representation for each of the unique constituting elements based on the occurrence frequencies of the unique constituting elements.

3. The method of claim 2, wherein the method further comprises ordering said unique constituting elements based on their occurrence frequencies.

4. The method of claim 2, wherein the method further comprises storing said constituting elements of the data structure as they are received, using said initial cookie representations, and subsequently replacing the stored initial cookie representations with the final cookie representations, and said transmitting comprises transmitting said constituting elements of said data structure using said final cookie representations.

5. The method of claim 1, wherein the cookie representations are numeric in form, with the cookie representations of the 128 most frequently occurred unique constituting elements having a size of one byte each, and the cookie representations of the next 32,640 most frequently occurred unique constituting elements having a size of two bytes each.

6. The method of claim 1, wherein said data structure is an XML data structure, and said constituting elements comprise tag names, attribute names and attribute values.

7. A method comprising:

receiving a plurality of unique constituting elements of a data structure transmitted in a pre-determined order based at least in part on the occurrence frequencies of said unique constituting elements;

inferring a plurality of corresponding cookie representations for the received unique constituting elements in accordance with their manner of transmissions under the pre-determined order of transmission, the plurality of corresponding cookie representations not having been received together with said received unique constituting elements; and

receiving the constituting elements of the data structure in a representative form encoded with cookie representations.

8. The method of claim 7, wherein said inferring comprises inferring a unique one-byte numeric representation for each of the first 128 unique constituting elements transmitted, and a unique two-bytes representation for each of the next 32,460 unique constituting elements transmitted.

9. The method of claim 7, wherein the method further comprises reconstituting the constituting elements of the data structure, received in said representative form, based on the inferred cookie representations.

10. The method of claim 7, wherein said data structure is an XML data structure, and said constituting elements comprises tag names, attribute names and attribute values.

11. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to receive a plurality of constituting elements of a data structure, determine occurrence frequency of each unique constituting element in said data structure, assign a cookie representation to each of said unique constituting elements based at least in part on the occurrence frequencies of said unique constituting elements, transmit a list of said unique constituting elements in the order of their occurrence frequencies to allow a receiving of said list of said unique constituting elements to infer the corresponding cookie representations of the unique constituting elements, and transmit said data structure in a representative form encoded with said cookie representations; and

at least one processor coupled to the storage medium to execute the programming instructions.

12. The apparatus of claim 11, wherein said programming instructions are designed to perform said determining and assigning by assigning an initial cookie representation to each unique constituting element as the constituting elements are received, and tracking occurrence frequencies of the unique constituting elements, and upon receipt of all constituting elements of the data structure, re-assigning a final cookie representation for each of the unique constituting elements based on the occurrence frequencies of the unique constituting elements.

13. The apparatus of claim 12, wherein the programming instructions are further designed to order said unique constituting elements based on their occurrence frequencies.

14. The apparatus of claim 12, wherein the programming instructions are further designed to store said constituting elements of the data structure as they are received, using said initial cookie representations, and subsequently replace the stored initial cookie representations with the final cookie representations, and said programming instructions perform said transmitting by transmitting said constituting elements of said data structure using said final cookie representations.

15. The apparatus of claim 11, wherein the programming instructions are deigned to employ cookie representations in numeric form, with the cookie representations of the 128 most frequently occurred unique constituting elements having a size of one byte each, and the cookie representations of the next 32,640 most frequently occurred unique constituting elements having a size of two bytes each.

16. The apparatus of claim 11, wherein said programming instructions are designed to perform said receive, determine, assign and transmit for an XML data structure, said constituting elements comprising tag names, attribute names and attribute values.

17. The apparatus of claim 11, wherein said apparatus is a selected one of a wireless mobile phone, a palm sized personal digital assistant, a notebook sized computer, a desktop computer, a set top box and a server.

18. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to receive a plurality of unique constituting elements of a data structure transmitted in a pre-determined order based at least in part on the occurrence frequencies of said unique constituting elements, to infer a plurality of corresponding cookie representations for the received unique constituting elements in accordance with their manner of transmissions under the predetermined order of transmission, the plurality of corresponding cookie representations not having been received together with said received unique constituting elements, and to receive the constituting elements of the data structure in a representative form encoded with cookie representations; and

at least one processor coupled to the storage medium to execute the programming instructions.

19. The apparatus of claim 18, wherein said programming instructions are designed to infer a unique one-byte numeric representation for each of the first 128 unique constituting elements transmitted, and a unique two-bytes representation for each of the next 32,460 unique constituting elements transmitted.

20. The apparatus of claim 18, wherein said programming instructions are further designed to reconstitute the constituting elements of the data structure, received in said representative form, based on the inferred cookie representations.

21. The apparatus of claim 18, wherein said programming instructions are designed to perform said receive, infer, receive, and re-constitute for a XML data structure, said constituting elements comprising tag names, attribute names and attribute values.

22. The apparatus of claim 18, wherein said apparatus is a selected one of a wireless mobile phone, a palm sized personal digital assistant, a notebook sized computer, a desktop computer, a set top box and a server.