Method and system for compressing data which allows access to data without full uncompression

• US 6,438,556 B1
• Filed: 12/11/1998
• Issued: 08/20/2002
• Est. Priority Date: 12/11/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Malik, Nadeem, Baumgartner, Jason Raymond, Roberts, Steven Leonard
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/210,503
• Time in Patent Office: 1,348 Days
• Field of Search: 707/100, 707/101, 707/6, 348/419.1, 348/384.1, 386/109, 386/111, 386/112, 386/27, 386/33
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method for compressing data on a computer system is disclosed. The method and system include separating the data into a plurality of segments. The plurality of segments includes a plurality of unique segments. The method and system also include providing a plurality of code words. Each of the plurality of code words corresponds to a unique segment of the plurality of unique segments. The method and system also include providing a representation of the data. The representation includes the plurality of code words for the plurality of segments. The plurality of code words in the representation replaces the plurality of segments. As a result, the data in the representation could be accessed randomly.

Claims

1. A method for compressing and accessing data on a computer system, the method comprising the steps of:

(a) separating the data into a plurality of segments, the plurality of segments including a plurality of unique segments;

(b) providing a plurality of code words, each of the plurality of code words corresponding to a unique segment of the plurality of unique segments;

(c) providing a representation of the data the representation including the plurality of code words;

wherein the plurality of code words replace the plurality of segments; and

(d) decompressing a only portion of the representation of the data to allow a user access to a desired data set, the portion of the representation of the data including only a portion of the plurality of code words corresponding to at least one segment including the desired data set.

2. The method of claim 1 wherein the plurality of segments have an order and wherein the representation providing step (c) further includes the step of:

(c1) saving the code word for each of the plurality of segments in the order.

3. The method of claim 1 wherein the data includes a data file.

4. The method of claim 1 wherein the plurality of segments have a fixed length.

5. The method of claim 1 wherein the data includes a portion of a data file.

6. The method of claim 1 wherein the code word representing a particular segment of the plurality of segments can be randomly accessed.

7. The method of claim 1 wherein a portion of the representation of the data can be used without completely uncompressing the representation of the data.

8. The method of claim 1 further wherein the plurality of code word providing step further includes the step of:

(b1) providing a dictionary indicating a correspondence between the plurality of code words and the plurality of unique segments.

9. A method for compressing data on a computer system, the data including a portion of a data file, the data file being divided into a plurality of super-segments, the portion of the data file further including a super-segment of the plurality of super-segments, the method comprising the steps of:

(a) separating the data into a plurality of segments, the plurality of segments including a plurality of unique segments;

(b) providing a plurality of code words, each of the plurality of code words corresponding to a unique segment of the plurality of unique segments;

(c) providing a representation of the data, the representation including the plurality of code words;

wherein the plurality of code words replace the plurality of segments; and

(d) decompressing a only portion of the representation of the data to allow a user access to a desired data set the portion to the representation of the data including only a portion of the plurality of code words corresponding to at least one segment including the desired data set.

10. A method for compressing data on a computer system, the method comprising the steps of:

(a) separating the data into a plurality of segments, the plurality of segments being adjacent;

(b) separating each of the plurality of segments into a plurality of subsegments, the plurality of subsegments being adjacent;

(c) providing a plurality of code words, each of the plurality of code words corresponding to a unique subsegment of the plurality of unique subsegments;

(d) providing compressed data including a representation of each segment, the representation including a portion of the plurality of code words;

wherein the portion of the plurality of code words replaces the plurality of subsegments in each of the plurality of segments, the representation of a particular segment being saved before a subsequent representation of a subsequent segment of the plurality of segments;

wherein a portion of the data represented by a portion of the compressed data may be accessed without uncompressing all of the compressed data.

11. A computer system for compressing data and accessing the data, comprising;

a processor;

a memory coupled with the processor;

means coupled with the processor for compressing data including

means for separating the data into a plurality of segments, the plurality of segments including a plurality of unique segments;

means coupled with the separating means for providing a plurality of code words, each of the plurality of code words corresponding to a unique segment of the plurality of unique segments; and

means, coupled with the plurality of code word providing means, for providing a representation of the data, the representation including the plurality of code words; and

means for decompressing a only portion of the representation of the data to allow a user access to a desired data set, the portion of the representation of the data including only a portion of the plurality of code words corresponding to at least one segment including the desired data set;

wherein the plurality of code words replace the plurality of segments.

12. The system of claim 11 wherein the plurality of segments have an order and wherein the representation providing means further includes:

means for saving the code word for each of the plurality of segments in the order.

13. The system of claim 11 wherein the data includes a data file.

14. The system of claim 11 wherein the data includes a portion of a data file.

15. The system of claim 11 wherein the code word representing a particular segment of the plurality of segments can be randomly accessed.

16. The system of claim 11 wherein the plurality of code word providing means further include:

means for providing a dictionary indicating a correspondence between the plurality of code words and the plurality of unique code words.

17. The system of claim 11 wherein a portion of the representation of the data can be used without completely uncompressing the representation of the data.

18. A system for compressing data on a computer system, the data including a portion of a data file, the data file being divided into a plurality of super-segments, and the portion of the data file further including a super-segment of the plurality of super-segments, the system comprising:

a processor;

a memory coupled with the processor; and

means coupled with the processor for compressing data including

means for separating the data into a plurality of segments, the plurality of segments including a plurality of unique segments;

means coupled with the separating means for providing a plurality of code words, each of the plurality of code words corresponding to a unique segment of the plurality of unique segments;

means, coupled with the plurality of code word providing means, for providing a representation of the data, the representation including the plurality of code words;

wherein the plurality of code words replace the plurality of segments; and

(d) means for decompressing a only portion of the representation of the data to allow a user access to a desired data set, the portion of the representation of the data including only a portion of the plurality of code words corresponding to at least one segment including the desired data set.

19. A computer-readable medium including a program for compressing accessing data on a computer system, the program including instructions for:

(a) separating the data into a plurality of segments, the plurality of segments including a plurality of unique segments;

(b) providing a plurality of code words, each of the plurality of code words corresponding to a unique segment of the plurality of unique segments; and

(c) providing a representation of the data, the representation including the plurality of code words;

(d) decompressing a only portion of the representation of the data to allow a user access to a desired data set, the portion of the representation of the data including only a portion of the plurality of code words corresponding to at least one segment including the desired data set;

wherein the plurality of code words replace the plurality of segments.

20. A computer-readable medium containing a program for compressing data on a computer system, the program including instructions for:

(a) separating the data into a plurality of segments, the plurality of segments being adjacent;

(b) separating each of the plurality of segments into a plurality of subsegments, the plurality of subsegments being adjacent;

(c) providing a plurality of code words, each of the plurality of code words corresponding to a unique subsegment of the plurality of unique subsegments;

(d) providing compressed data including a representation of each of the plurality of segments, the representation including a portion of the plurality of code words;

wherein the portion of the plurality code words replace the plurality of subsegments of each of the plurality of segments;

wherein a portion of the data represented by a portion of the compressed data may be accessed without uncompressing all of the compressed data.