System and method for data compression and decompression

• US 20040111427A1
• Filed: 12/24/2002
• Published: 06/10/2004
• Est. Priority Date: 12/06/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng
• Granted Patent: US 7,099,884 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A data compressor is provided which performs substitution-based data encoding. The compressor identifies repetitive data of an input file and writes meta-data representative of the repetitive data to a first buffer using a triple structure. The triple structure includes information of a length of non-repetitive data preceding repetitive data, an offset between like groups of repetitive data, and a length of the repetitive data. Non-repetitive data is written to a second buffer. The compressor concatenates the first and second buffers along with information of the length of the input file and the length of the first buffer to form a compressed file. A corresponding decompressor parses the compressed file and quickly computes the original file using a pre-allocated memory area.

Claims

1. A processing system comprising:

a data compressor coupled to a memory including first and second buffers;

the data compressor identifying repetitive data strings of an input file and writing meta data representative of each of the repetitive data strings to data structures in the first buffer, wherein the meta data includes information of a length of non-repetitive data preceding the repetitive data strings, an offset between the repetitive data strings, and a length of the repetitive data strings;

the data compressor writing the non-repetitive data to a second buffer; and

the data compressor generating a compressed file by concatenating the first buffer and the second buffer, wherein the compressed file is a compressed version of the input file.

2. The processing system of claim 1, wherein the writing of meta data representative of the repetitive data strings by the data compressor comprises:

setting a current location and a sliding window in the input file, wherein the current location is a data location of the input file currently under evaluation, wherein the sliding window includes at most n data locations of the input file before the current location, wherein n is a size of the sliding window;

searching data in the sliding window for repetitive data strings, wherein repetitive data strings include longest occurrences of data in the sliding window matching future data beyond the sliding window;

writing the meta data representative of the repetitive data strings to the data structures in the first buffer when a length of the repetitive data strings is at least as large as a threshold value;

updating the current location and refreshing the sliding window; and

searching data in the refreshed sliding window when data remains in the input file.

3. The processing system of claim 1, wherein the writing of non-repetitive data by the data compressor further comprises:

setting the current location and the sliding window in the input file;

searching data in the sliding window for the repetitive data strings;

writing data of the current location to the second buffer when a length of the repetitive data strings is less than the threshold value;

updating the current location and refreshing the sliding window; and

searching data in the refreshed sliding window when data remains in the input file.

4. The processing system of claim 1, wherein generating a compressed file further comprises concatenating a length of the input file and the first buffer.

5. The processing system of claim 1, wherein the data compressor is at least one component of a first device.

6. The processing system of claim 1, further comprising a data decompressor coupled to another memory including an output buffer, the data decompressor:

receiving the compressed file;

parsing the data structures of the first buffer;

writing data to the output buffer using information of the data structures of the first buffer and data of the second buffer; and

generating an output file using information of the output buffer, wherein the output file is a reconstructed version of the input file.

7. The processing system of claim 6, wherein the writing of data to an output buffer by the data decompressor further comprises:

reading the length of non-repetitive data preceding the repetitive data string from the data structures;

when the length of non-repetitive data is greater than zero, writing data of the second buffer corresponding to the non-repetitive data preceding the repetitive data string to the output buffer; and

updating the current location and a data buffer pointer.

8. The processing system of claim 6, wherein the writing of data to an output buffer by the data decompressor further comprises:

reading the offset between the repetitive data strings from the data structures and identifying data locations in the output buffer for the repetitive data strings;

reading the length of the repetitive data strings from the data structures;

writing the repetitive data strings to the identified data locations in the output buffer using the length of the repetitive data strings; and

updating the current location.

9. The processing system of claim 6, wherein the data decompressor is at least one component of a second device, wherein the second device is coupled to a first device including the data compressor.

10. The processing system of claim 9, wherein the coupling is selected from among wireless connections, wired connections, hybrid wireless and wired connections, and connections with at least one network including local area networks, metropolitan area networks, and wide area networks.

11. The processing system of claim 9, wherein the second device is a portable communication device selected from among personal computers, cellular telephones, personal digital assistants, portable computing devices, and portable communication devices.

12. The processing system of claim 1, wherein the processing system is a component of a communication system.

13. A data compressor performing substitution-based data encoding, comprising:

receiving an input file;

identifying repetitive data of the input file;

writing meta-data representative of the repetitive data to a first buffer using a triple structure, wherein the triple structure includes information of a length of non-repetitive data preceding repetitive data, an offset between like groups of repetitive data, and a length of the repetitive data;

writing non-repetitive data to a second buffer; and

concatenating the first and second buffers along with information of a length of the input file and a length of the first buffer to form a compressed file.

14. A communication system comprising a first device including a data compressor coupled to a memory including first and second buffers, wherein the data compressor identifies repetitive data strings of an input file and writes meta data representative of each of the repetitive data strings to data structures in the first buffer, wherein the meta data includes information of a length of non-repetitive data preceding the repetitive data strings, an offset between the repetitive data strings, and a length of the repetitive data strings, wherein the data compressor writes the non-repetitive data to a second buffer, and wherein the data compressor generates a compressed file by concatenating the first buffer and the second buffer, wherein the compressed file is a compressed version of the input file.

15. The communication system of claim 14, further comprising a portable communication device coupled to the first device via at least one coupling, the portable communication device including a data decompressor coupled to a device memory including an output buffer, wherein the data decompressor receives the compressed file via the at least one coupling, parses the data structures of the first buffer, writes data to the output buffer using information of the data structures of the first buffer and data of the second buffer, and generates an output file using information of the output buffer, wherein the output file is a reconstructed version of the input file.

16. The communication system of claim 15, wherein the portable communication device is at least one device selected from among cellular telephones, personal digital assistants, portable communication devices, personal computers, and portable computing devices.

17. A method for manipulating data files, comprising:

receiving an input file and identifying repetitive data strings of the input file;

writing meta data representative of each of the repetitive data strings to data structures in a first buffer, wherein the meta data includes information of a length of non-repetitive data preceding the repetitive data strings, an offset between the repetitive data strings, and a length of the repetitive data strings;

writing the non-repetitive data to a second buffer; and

generating a compressed file by concatenating the first buffer and the second buffer, wherein the compressed file is a compressed version of the input file.

18. The method of claim 17, wherein writing meta data representative of the repetitive data strings further comprises:

setting a current location and a sliding window in the input file, wherein the current location is a data location of the input file currently under evaluation, wherein the sliding window includes at most n data locations of the input file before the current location, wherein n is a size of the sliding window;

searching data in the sliding window for repetitive data strings, wherein repetitive data strings include longest occurrences of data in the sliding window matching future data beyond the sliding window;

writing the meta data representative of the repetitive data strings to the data structures in the first buffer when a length of the repetitive data strings is at least as large as a threshold value;

updating the current location and refreshing the sliding window; and

searching data in the refreshed sliding window when data remains in the input file.

19. The method of claim 17, wherein writing non-repetitive data further comprises:

setting the current location and the sliding window in the input file;

searching data in the sliding window for the repetitive data strings;

writing data of the current location to the second buffer when a length of the repetitive data strings is less than the threshold value;

updating the current location and refreshing the sliding window; and

searching data in the refreshed sliding window when data remains in the input file.

20. The method of claim 17, wherein generating a compressed file further comprises concatenating a length of the input file and a length of the first buffer.

21. The method of claim 17, further comprising verifying integration of the generated compressed file.

22. The method of claim 18, wherein data of the sliding window is a compression dictionary.

23. The method of claim 18, wherein the threshold value is approximately three bytes.

24. The method of claim 17, further comprising:

receiving the compressed file;

parsing the data structures of the first buffer;

writing data to an output buffer using information of the data structures of the first buffer and data of the second buffer; and

generating an output file using information of the output buffer, wherein the output file is a reconstructed version of the input file.

25. The method of claim 24, wherein writing data to an output buffer further comprises:

reading the length of non-repetitive data preceding the repetitive data string from the data structures;

when the length of non-repetitive data is greater than zero, writing data of the second buffer corresponding to the non-repetitive data preceding the repetitive data string to the output buffer; and

updating the current location and a data buffer pointer.

26. The method of claim 24, wherein writing data to an output buffer further comprises:

reading the offset between the repetitive data strings from the data structures and identifying data locations in the output buffer for the repetitive data strings;

reading the length of the repetitive data strings from the data structures;

writing the repetitive data strings to the identified data locations in the output buffer using the length of the repetitive data strings; and

updating the current location.

27. The method of claim 24, further comprising verifying integration of the received compressed file.

28. A method for transferring data files, comprising:

receiving an input file;

identifying repetitive data patterns of the input file;

generating meta data representative of the repetitive data patterns and writing the meta data to a first buffer;

writing non-repetitive data to a second buffer; and

generating a compressed file by concatenating the first buffer, the second buffer, and information of a length of the input file and a length of the first buffer.

29. A processing system comprising:

means for receiving an input file and identifying repetitive data strings of the input file;

means for writing meta data representative of each of the repetitive data strings to data structures in a first buffer, wherein the meta data includes information of a length of non-repetitive data preceding the repetitive data strings, an offset between the repetitive data strings, and a length of the repetitive data strings;

means for writing the non-repetitive data to a second buffer; and

means for generating a compressed file by concatenating the first buffer and the second buffer, wherein the compressed file is a compressed version of the input file.

30. A computer readable medium including executable instructions which, when executed in a processing system, processes data files by:

receiving an input file and identifying repetitive data strings of the input file;

writing meta data representative of each of the repetitive data strings to data structures in a first buffer, wherein the meta data includes information of a length of non-repetitive data preceding the repetitive data strings, an offset between the repetitive data strings, and a length of the repetitive data strings;

writing the non-repetitive data to a second buffer; and

generating a compressed file by concatenating the first buffer and the second buffer, wherein the compressed file is a compressed version of the input file.