System for exchanging compressed data according to predetermined dictionary codes

• US 6,088,699 A
• Filed: 04/22/1998
• Issued: 07/11/2000
• Est. Priority Date: 04/22/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gampper, James Michael, Wolfe, Daniel Charles
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M
• Application Number:
  US09/064,883
• Time in Patent Office: 811 Days
• Field of Search: 341/20-35, 341/173-192, 341/106, 341/107, 341/67, 341/87, 709/200-253, 707/10, 707/1, 707/3, 707/227
• US Class Current: 1/1
• 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
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Messages containing non-dictionary and dictionary data objects are quickly exchanged between sending and receiving devices. Data stores of the devices contain a common dictionary cross-referencing each of multiple data objects with a different dictionary index code. Data objects in the dictionary are likely to be frequently exchanged. Prior to transmission of data objects, the sending device searches its dictionary for each data object. Each data object may include text, graphics, program segments, or another type of data object. If the data object appears in the dictionary, the sending device obtains its dictionary index code. Next, the sending device transmits a message representing the data objects to the receiving device. The message includes multiple subparts each corresponding to a different data object. If a data object is not present in the dictionary, its subpart comprises the content of the data object without any dictionary encoding. If a data object is represented in the dictionary, its subpart comprises the data object'"'"'s index code from the dictionary. Flags included in the message distinguish between dictionary and non-dictionary subparts. The receiving device interprets received messages, reviewing flags in the message to determine which subparts comprise dictionary index codes. Each index code is cross-referenced in the receiving device'"'"'s dictionary to obtain the unencoded data object, which is provided as an output. Each non-dictionary data object is provided as an output directly.

Claims

1. A method for exchanging data between a sending device and a receiving device, each device including a processor coupled to a digital data store, the method comprising:

the sending and receiving devices maintaining respective dictionaries in their respective digital data stores, each dictionary containing multiple data objects each cross-referenced to a different dictionary index code, where the data objects include data objects having one of the following types;

a binary graphics file, or a binary executable program;

in response to the sending device receiving multiple data objects for transmittal to the receiving device, the sending device;

searching for each of the received data objects in the dictionary contained in the sending device'"'"'s store;

for each data object present in the dictionary, obtaining a representative index code cross-referenced to the data object in the dictionary;

the sending device composing a message for transmittal to the receiving device, the message including multiple subparts each subpart corresponding to a different one of the received data objects, each subpart comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

where the composed message further includes one or more flags distinguishing between index codes and non-dictionary data objects in the message;

the sending device transmitting the composed message to the receiving device; and

the receiving device receiving the transmitted message, and in response the receiving device performing operations to process the the message comprising;

reviewing the flags in the received message to identify subparts of the message as index codes or non-dictionary data objects;

for each subpart identified as an index code, cross-referencing the index code in the dictionary contained in the receiving device'"'"'s store to obtain the cross-referenced data object, and

for each obtained data object that is a binary graphics file, operating the receiving device'"'"'s processor to display an image represented by said binary graphics file;

for each obtained data object that is a binary executable program, operating the receiving device'"'"'s processor to execute said program; and

for each subpart identified as a non-dictionary data object, providing an output of that data object.

2. The method of claim 1, where the data object types further include textual data objects.

3. The method of claim 2, where each dictionary includes multiple sub-dictionaries each sub-dictionary exclusively containing dictionary index codes of a single type of data object.

4. The method of claim 3, the flags further including one or more sub-dictionary identifiers identifying sub-dictionaries containing the dictionary index codes in the composed message.

5. The method of claim 1, the method further comprising constructing the dictionaries and storing the constructed dictionaries in the digital stores, the constructing including forming the dictionary index codes by compressing the cross-referenced data objects according to a predefined compression process.

6. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for transmitting data from a sending device to a receiving device, each device including a processor coupled to a digital data store, the method comprising:

the sending device maintaining a dictionary in its digital data store, the dictionary containing multiple data objects each cross-referenced to a different dictionary index code, where the data objects include data objects having one of the following types;

a binary graphics file, or a binary executable program;

in response to the sending device receiving multiple data objects for transmittal to the receiving device,

searching for each of the received data objects in the dictionary contained in the sending device'"'"'s store;

for each data object present in the dictionary, obtaining a representative index code cross-referenced to the data object in the dictionary; and

the sending device composing a message to the receiving device, the message including multiple subparts each subpart corresponding to a different one of the received data objects, each subpart comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

where the composed message further includes one or more flags distinguishing between index codes and non-dictionary data objects in the message.

7. The medium of claim 6, where the data object types further include textual data objects.

8. The medium of claim 7, where each dictionary includes multiple sub-dictionaries each sub-dictionary exclusively containing dictionary index codes of a single type of data object.

9. The medium of claim 8, the flags further including one or more sub-dictionary identifiers identifying sub-dictionaries containing the dictionary index codes in the composed message.

10. The medium of claim 6, the method further comprising constructing the dictionary of the sending device and storing the constructed dictionary in the digital store of the sending device, the constructing including forming the dictionary index codes by compressing the cross-referenced data objects according to a predefined compression process.

11. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for a receiving device to receive data from a sending device, each device including a processor coupled to a digital data store, the method comprising:

the receiving device maintaining a dictionary in the digital store, the dictionary containing multiple data objects each cross-referenced to a different dictionary index code, where the data objects include data objects having one of the following types;

a binary graphics file, or a binary executable program;

the receiving device receiving a message including multiple subparts each subpart corresponding to a different data object and comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

the message further including one or more flags distinguishing between dictionary index codes and non-dictionary data objects; and

in response to receiving the message, the receiving device performing operations to process the message comprising;

reviewing the flags in the received message to distinguish between dictionary index codes and non-dictionary data objects;

for each subpart comprising an index code, cross-referencing the index code in the dictionary contained in the receiving device'"'"'s store to obtain the cross-referenced data object, and

for each obtained data object that is a binary graphics file, operating the receiving device'"'"'s processor to display an image represented by said binary graphics file;

for each obtained data object that is a binary executable program, operating the receiving device'"'"'s processor to execute said program; and

for each subpart comprising a non-dictionary data object, providing an output of the non-dictionary data object.

12. The medium of claim 11, where the data object types further include textual data objects.

13. The medium of claim 12, where each dictionary includes multiple sub-dictionaries each sub-dictionary exclusively containing dictionary index codes of a single type of data object.

14. The medium of claim 13, the flags including one or more sub-dictionary identifiers identifying sub-dictionaries containing the dictionary index codes in the composed message.

15. The medium of claim 12, the method further comprising constructing the dictionary of the receiving device and storing the constructed dictionary in the digital store of the receiving device, the constructing including forming the dictionary index codes by compressing the cross-referenced data objects according to a predefined compression process.

16. A data exchange system including multiple devices, each device including a processor coupled to a digital data store, the devices'"'"' processors being programmed to perform the a method for exchanging data, the method comprising:

designating a sending device and a receiving device;

the sending and receiving devices maintaining respective dictionaries in their respective digital data stores, each dictionary containing multiple data objects each cross-referenced to a different dictionary index code, where the data objects include data objects having one of the following types;

a binary graphics file, or a binary executable program;

in response to the sending device receiving multiple data objects for transmittal to the receiving device, the sending device;

searching for each of the received data objects in the dictionary contained in the sending device'"'"'s store;

for each data object present in the dictionary, obtaining a representative index code cross-referenced to the data object in the dictionary;

the sending device composing a message for transmittal to the receiving device, the message including multiple subparts each subpart corresponding to a different one of the received data objects, each subpart comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

where the composed message further includes one or more flags distinguishing between index codes and non-dictionary data objects in the message;

the sending device transmitting the composed message to the receiving device; and

the receiving device receiving the transmitted message, and in response the receiving device performing operations to process the message comprising;

reviewing the flags in the received message to identify subparts of the message as index codes or non-dictionary data objects;

for each subpart identified as an index code, cross-referencing the index code in the dictionary contained in the receiving device'"'"'s store to obtain the cross-referenced data object, and

for each obtained data object that is a binary graphics file, operating the receiving device'"'"'s processor to display an image represented by said binary graphics file;

for each obtained data object that is a binary executable program, operating the receiving device'"'"'s processor to execute said program; and

for each subpart identified as a non-dictionary data object, providing an output of that data object.

17. The system of claim 16, where the data object types further include textual data objects.

18. The system of claim 17, where each dictionary includes multiple sub-dictionaries each sub-dictionary exclusively containing dictionary index codes of a single type of data object.

19. The system of claim 18, the flags including one or more sub-dictionary identifiers identifying sub-dictionaries containing the dictionary index codes in the composed message.

20. The system of claim 16, the method further comprising constructing the dictionaries and storing the constructed dictionaries in the digital stores, the constructing including forming the dictionary index codes by compressing the cross-referenced data objects according to a predefined compression process.

21. A data sending device, comprising:

a digital data store, containing a dictionary containing multiple data objects and cross-referencing each of the data objects with a different dictionary index code, the data objects including data objects having one of the following types;

a binary graphics file, or a binary executable program; and

a processor, coupled to the store, and programmed to perform a method for transmitting data to a receiving device, the method comprising;

in response to the sending device receiving multiple data objects for transmittal to the receiving device, the sending device;

searching for each of the received data objects in the dictionary contained in the sending device'"'"'s store;

for each data object present in the dictionary, obtaining a representative index code cross-referenced to the data object in the dictionary; and

the sending device composing a message to the receiving device, the message including multiple subparts each subpart corresponding to a different one of the received data objects, each subpart comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

where the composed message further includes one or more flags distinguishing between index codes and non-dictionary data objects in the message.

22. The device of claim 21, where the data object types further include textual data objects.

23. The device of claim 22, where each dictionary includes multiple sub-dictionaries each sub-dictionary exclusively containing dictionary index codes of a different type of data object.

24. The device of claim 23, the flags further including one or more sub-dictionary identifiers identifying sub-dictionaries containing the dictionary index codes in the composed message.

25. The device of claim 21, the method further comprising constructing the dictionary of the sending device and storing the constructed dictionary in the digital store of the sending device, the constructing including forming the dictionary index codes by compressing the cross-referenced data objects according to a predefined compression process.

26. A data receiving device, comprising:

a digital data store containing a dictionary containing multiple data objects and cross-referencing each of the data objects with a different dictionary index code, where the data objects include data objects with one of the following types;

a binary graphics file, or a binary executable program; and

a processor, coupled to the store, and programmed to perform a method for receiving data from a sending device, the method comprising;

the receiving device receiving a message including multiple subparts each subpart corresponding to a different data object and comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

the message further including one or more flags distinguishing between dictionary index codes and non-dictionary data objects; and

in response to receiving the message, the receiving device performing operations to process the message comprising;

reviewing the flags in the received message to distinguish between dictionary index codes and non-dictionary data objects;

for each subpart comprising an index code, cross-referencing the index code in the dictionary contained in the receiving device'"'"'s store to obtain the cross-referenced data object, and

for each obtained data object that is a binary graphics file, operating the receiving device'"'"'s processor to display an image represented by said binary graphics file;

for each obtained data object that is a binary executable program, operating the receiving device'"'"'s processor to execute said program; and

for each subpart comprising a non-dictionary data object, providing an output of the non-dictionary data object.

27. The device of claim 26, where the data object types further include textual data objects.

28. The device of claim 27, where each dictionary includes multiple sub-dictionaries each sub-dictionary exclusively containing dictionary index codes of a different type of data object.

29. The device of claim 28, the flags further including one or more sub-dictionary identifiers identifying sub-dictionaries containing the dictionary index codes in the composed message.

30. The device of claim 26, the method further comprising constructing the dictionary of the receiving device and storing the constructed dictionary in the digital store of the receiving device, the constructing including forming the dictionary index codes by compressing the cross-referenced data objects according to a predefined compression process.

31. A data sending device, comprising:

first means for storing digital data, the first means containing a dictionary containing multiple data objects and cross-referencing each of the data objects with a different dictionary index code, the data objects including data objects with one of the following types;

a binary graphics file, or a binary executable program; and

second means, coupled to the store, for transmitting data to a receiving device, by;

in response to the receiving multiple data objects for transmittal to the receiving device,

searching for each of the received data objects in the dictionary contained in the first means;

for each data object present in the dictionary, obtaining a representative index code cross-referenced to the data object in the dictionary; and

composing a message to the receiving device, the message including multiple subparts each subpart corresponding to a different one of the received data objects, each subpart comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

where the composed message further includes one or more flags distinguishing between index codes and non-dictionary data objects in the message.

32. A data receiving device, comprising:

first means for storing digital data, the first means containing a dictionary containing multiple data objects and cross-referencing each of the data objects with a different dictionary index code, where the data objects include data objects with one of the following types;

a binary graphics file, or a binary executable program; and

second means, coupled to the store, for receiving data from a sending device by;

receiving a message including multiple subparts each subpart corresponding to a different data object and comprising;

if the corresponding data object is not present in the dictionary, the content of the data object; and

if the corresponding data object is present in the dictionary, the index code cross-referenced to the data object;

the message further including one or more flags distinguishing between dictionary index codes and non-dictionary data objects; and

in response to receiving the message, the second means performing operations to process the message comprising;

reviewing the flags in the received message to distinguish between dictionary index codes and non-dictionary data objects;

for each subpart comprising an index code, cross-referencing the index code in the dictionary contained in the receiving device'"'"'s store to obtain the cross-referenced data object, and

for each obtained data object that is a binary graphics file, operating the receiving device'"'"'s processor to display an image represented by said binary graphics file;

for each obtained data object that is a binary executable program, operating the receiving device'"'"'s processor to execute said program; and

for each subpart comprising a non-dictionary data object, providing an output of the non-dictionary data object.

33. A method for conducting communications between first and second computing machines, the computing machines including respective copies of a common dictionary, the method comprising operations of:

at the first computing machine,

designating multiple data objects for transmission to the second computing machine, where the data objects include some data objects with one of the following types;

a binary graphics file readable by a processor to display a represented data object, or a binary instruction sequence executable by a processor to run a program;

determining whether each designated data object is present in the first computing machine'"'"'s dictionary, and

if the data object is present in the dictionary, obtaining a representative index code cross-referenced to the data object in the dictionary, and preparing a transmission that substitutes the index code for the data object;

otherwise, if the data object is not present in the dictionary, preparing a transmission that includes a non-dictionary representation of the data object;

sending the transmission to the second computing machine;

at the second computing machine,

receiving transmissions from the first computing machine;

for each transmission,

analyzing contents of the transmission to determine whether the transmission includes an index code;

if the transmission includes an index code, cross-referencing the index code in the second computing machine'"'"'s dictionary to obtain the data object;

determining the data object'"'"'s type, and

if the data object is a graphics file, operating the second computing machine to read the graphics file and display the image represented thereby;

if the data object is an instruction sequence, operating the second computing machine to execute the program.

34. The method of claim 33, where the data object types further include text.