Data compression system and method

Abstract

The invention provides a method of compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, the method including the steps of: retrieving the data file from a secondary storage device; storing the data file in direct access memory; calculating the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; on the sub-sequence having a frequency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique values within the sub-sequence; creating an output data file, the data file having a file type identifier, and adding the index to the output data file.

What is claimed: 
     
       1. A method of compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, the method including the steps of:
 retrieving the data file from a secondary storage device; 
 storing the data file in direct access memory; 
 calculating the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; 
 creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 creating an output data file, the output data file having a file type identifier; and 
 adding the index to the output data file. 
 
     
     
       2. A method of compressing a data file as claimed in  claim 1  wherein the step of applying a data transformation to the sub-sequence further includes the steps of:
 maintaining in computer memory a plurality of transformation data sets, the data sets having a sequence of byte values and identified by a transformation data set identifier; 
 retrieving one of the transformation data sets from computer memory, the retrieved transformation data set having a length substantially equal to the length of the sub-sequence of the data file; and 
 applying a data transformation to respective byte values in the sub-sequence based on corresponding byte values in the retrieved data set. 
 
     
     
       3. A method of compressing a data file as claimed in  claim 2  wherein the sub-sequence following data transformation based on at least one of the retrieved transformation data set sets is substantially identical to the sub-sequence prior to the data transformation. 
     
     
       4. A method of compressing a data file as claimed in  claim 2  wherein at least one of the transformation data sets comprises a randomly generated sequence of byte rates. 
     
     
       5. A method of compressing a data file as claimed in  claim 2  wherein at least one of the transformation data sets comprises a predefined sequence of byte rates. 
     
     
       6. A method of compressing a data file as claimed in  claim 2  wherein at least one of the transformation data sets comprises a sequence of byte values derived from a portion of the data file other than the sub-sequence of the data file. 
     
     
       7. A method of compressing a data file as claimed in  claim 2  further comprising the step of adding to the index the transformation data set identifier of the data transformation data set applied to the sub-sequence. 
     
     
       8. A method of compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, the method including the steps of:
 retrieving the data file from a secondary storage device; 
 storing the data file in direct access memory; 
 calculating the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; 
 calculating the position of the one or more unique byte values within the sub-sequence; 
 creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 creating an output data file, the output data file having a file type identifier; and 
 adding the index to the output data file. 
 
     
     
       9. A method of compressing a data file as claimed in  claim 8  wherein the step of calculating the position of the one or more unique byte values within the sub-sequence further comprises the steps of:
 creating a temporary position index in computer memory; 
 retrieving successive byte values from the sub-sequence; 
 on retrieving each byte value, determining whether the retrieved byte value is a unique byte value or a repeated value; 
 on detection of a unique byte value, adding one of two bit values to the temporary position index, and otherwise adding the other of the two bit values to the temporary position index; 
 creating a position index representing the position of the one or more unique byte values from the temporary position index; and 
 calculating the data value representing the position of the one or more unique byte values at least partly from the position index. 
 
     
     
       10. A method of compressing a data file as claimed in  claim 9  wherein the number of bytes in the sub-sequence is substantially equal to the number of bits in the temporary position index. 
     
     
       11. A method of compressing a data file as claimed in  claim 9  wherein the size of the position index is less than the size of the temporary position index. 
     
     
       12. A method of compressing a data file as claimed in  claim 9  further comprising the steps of:
 creating a permutation index representing the order of unique byte values within the sub-sequence; and 
 calculating the data value representing the position of the one or more unique byte values both from the position index and the permutation index. 
 
     
     
       13. A method of compressing a data file as claimed in  claim 12  comprising the step of concatenating the position index and the permutation index to form the data value representing the position of the one or more unique byte values. 
     
     
       14. A system for compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, where the system is configured to:
 retrieve the data file from a secondary storage device; 
 store the data file in direct access memory; 
 calculate the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; 
 create an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, apply a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and add to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, add to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 create an output data file, the output data file having a file type identifier; and 
 add the index to the output data file. 
 
     
     
       15. A system for compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, where the system is configured to:
 retrieve the data file from a secondary storage device; 
 store the data file in direct access memory; 
 calculate the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; and 
 calculate the position of the one or more unique byte values within the sub-sequence; 
 create an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, apply a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and add to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, add to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 create an output data file, the outout data file having a file type identifier; and add the index to the output data file. 
 
     
     
       16. A computer program stored on tangible storage medium comprising executable instructions for performing a method of compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, the method comprising:
 retrieving the data file from a secondary storage device; 
 storing the data file in direct access memory; 
 calculating the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; 
 creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 creating an output data file, the output data file having a file type identifier; and
 adding the index to the output data file. 
 
 
     
     
       17. A computer program stored on tangible storage medium comprising executable instructions for performing a method of compressing a data file comprising a sequence of bytes of a length greater than or equal to a predefined length, the method comprising:
 retrieving the data file from a secondary storage device; 
 storing the data file in direct access memory; 
 calculating the frequency of unique byte values within a sub-sequence of the data file, the sub-sequence having a length not exceeding the predefined length; and 
 calculating the position of the one or more unique values within the sub-sequence; 
 creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 creating an output data file, the output data file having a file type identifier; and 
 adding the index to the output data file. 
 
     
     
       18. A method of modifying a data file prior to compression, comprising the steps of:
 (a) reading the data file into a sequence of multiple-byte data groups;   (b) arranging the bytes of each data group in ascending byte value order;   (c) writing an index into a first file that represents the original position of the bytes in each data group relative to their rearranged order;   (d) writing the first byte value from each of the rearranged data groups into a second file;   (e) writing calculated difference byte values representing the respective differences between each pair of consecutive byte values in each rearranged data group into a third file; and   (f) outputting the first, second and third files for compression.   
     
     
       19. A method according to claim 18 wherein step (c) comprises creating an index using Huffman structures. 
     
     
       20. A method according to claim 18 comprising writing the index into the first file after step (b) has been completed for all data groups in the data file. 
     
     
       21. A method according to claim 18 wherein step (d) comprises writing the first byte values of each rearranged data group into the second file in sequential order according to each values' respective data group position in the data file. 
     
     
       22. A method according to claim 18 wherein step (e) comprises writing the calculated difference byte values for each rearranged data group into the third file in sequential order according to the order of the pair of byte values in the rearranged data group from which each difference byte value was derived. 
     
     
       23. A method according to claim 18 wherein the data file is a three-byte structured data file and step (a) comprises reading the data file into a sequence of multiple-byte data groups that each comprise three consecutive bytes of the data file. 
     
     
       24. A method according to claim 23 wherein step (e) comprises writing a first calculated difference byte value representing the second byte value minus the first byte value and a second calculated difference byte value representing the third byte value minus the second byte value for each of the rearranged data groups into the third file. 
     
     
       25. A method according to claim 24 wherein step (e) comprises writing the first calculated difference byte value into the third file for a rearranged data group and immediately following that the second calculated difference byte value for that rearranged data group, and continuing this process for each subsequent rearranged data group in the data file. 
     
     
       26. A method according to claim 18 wherein the data file is an image file. 
     
     
       27. A method according to claim 26 wherein the image file is a 24-bit bitmap image file. 
     
     
       28. A method according to claim 26 wherein the image file is a 30-bit bitmap image file. 
     
     
       29. A method according to claim 18 wherein step (f) comprises outputting the first, second and third files to a lossless compression algorithm for compression into a single file. 
     
     
       30. A method according to claim 29 wherein the lossless compression algorithm is WinZip. 
     
     
       31. A method of modifying a data file prior to compression, the data file having a sequence of byte values and each byte value having an associated decimal order value representing its position in the sequence of the byte values of the data file, the method comprising the steps of:
 (a) writing the byte values having an even order value into a first file;   (b) writing the byte values having an odd order value into a second file; and   (c) outputting the first and second files to a lossless compression algorithm for compression into a single file.   
     
     
       32. A method according to claim 31 wherein step (a) comprises writing the byte values into the first file in sequential order relative to their position in the data file. 
     
     
       33. A method according to claim 31 wherein step (b) comprises writing the byte values into the second file in sequential order relative to their position in the data file. 
     
     
       34. A method according to claim 31 wherein the data file is a 2-byte structured data file. 
     
     
       35. A method according to claim 31 wherein the data file is an audio file. 
     
     
       36. A method according to claim 35 wherein the audio file is a Wave file having an audio sample size of 16 bits. 
     
     
       37. A method according to claim 31 wherein lossless compression algorithm is WinZip. 
     
     
       38. A method according to claim 1 wherein the output data file at the completion of compression further comprises:
 a header comprising information indicative of a file type identifier of the original data file; and   an index representing the compressed sub-seiuences of the original data file.   
     
     
       39. A method according to claim 38 wherein the header further comprises a data value indicative of the number of iterations the compression method of claim 1 was applied to the original data file during compression. 
     
     
       40. A method according to claim 38 wherein the index representing the compressed sub-sequences comprises a series of indices, each index representing a sub-sequence of the original data file and comprising:
 a data value representing the calculated frequency of unique byte values within the sub-sequence;   a data value representing a transformation data set identifier of the transformation data set applied to the sub-sequence;   a position index representing the position of the unique values in the sub-sequence; and   a permutation index representing the order of the unique byte values within the sub-sequence.   
     
     
       41. A method according to claim 8 wherein the output data file at the completion of compression further comprises:
 a header comprising information indicative of a file type identifier of the original data file; and   an index representing the compressed sub-sequences of the original data file.   
     
     
       42. A method according to claim 41 wherein the header further comprises a data value indicative of the number of iterations the compression method of claim 8 was applied to the original data file during compression. 
     
     
       43. A method according to claim 41 wherein the index representing the compressed sub-sequences comprises a series of indices, each index representing a sub-sequence of the original data file and comprising:
 a data value representing the calculated frequency of unique byte values within the sub-sequence;   a data value representing a transformation data set identifier of the transformation data set applied to the sub-sequence;   a position index representing the position of the unique values in the sub-sequence; and   a permutation index representing the order of the unique byte values within the sub-sequence.   
     
     
       44. A method for decompressing a data file, comprising:
 receiving a data file comprising a compressed original data file, the original data file comprising a sequence of bytes of a length greater than or equal to a predefined length and having been compressed by a compression process comprising:
 retrieving the original data file from a secondary storage device; 
 storing the original data file in direct access memory; 
 calculating the frequency of unique byte values within a sub-sequence of the original data file, the sub-sequence having a length not exceeding the predefined length; 
 creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; 
 on the sub-sequence having a freuency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique byte values within the sub-sequence; 
 creating an output data file, the output data file having a file type identifier; and 
 adding the index to the output data file; and 
   reversing the compression process to reconstruct the original data file.   
     
     
       45. A method according to claim 44 wherein said reversing the compression process comprises reversing the compression process for each index representing a sub-sequence of the original data file. 
     
     
       46. A method according to claim 45 wherein said reversing the compression process further comprises concurrently processing multiple indices representing multiple sub-sequences of the original data file. 
     
     
       47. A method for decompressing a data file, comprising:
 receiving a data file comprising a compressed original data file, the original data file comprising a sequence of bytes of a length greater than or equal to a predefined length and having been compressed by a compression process comprising:
 retrieving the original data file from a secondary storage device; 
 storing the original data file in direct access memory; 
 calculating the frequency of unique byte values within a sub-sequence of the original data file, the sub-sequence having a length not exceeding the predefined length; 
 calculating the position of the one or more unique values within the sub-sequence; 
 creating an index for the sub-sequence, the index including a data value representing the calculated frequency of unique byte values within the sub-sequence; and 
 on the sub-sequence having a frequency of unique byte values below a predetermined threshold, applying a data transformation to the sub-sequence to increase the frequency of unique byte values in the sub-sequence and adding to the index a data value representing the data transformation; 
 on the sub-sequence having a frequency of unique byte values above a predefined threshold, adding to the index a data value representing the position of one or more unique values within the sub-sequence; 
 creating an output data file, the data file having a file type identifier; and 
 adding the index to the output data file; and 
   reversing the compression process to reconstruct the original data file.   
     
     
       48. A method according to claim 47 wherein said reversing the compression process further comprises reversing the compression process for each index representing a sub-sequence of the original data file. 
     
     
       49. A method according to claim 48 wherein said reversing the compression process further comprises concurrently processing multiple indices representing multiple sub-sequences of the original data file. 
     
     
       50. A method for reconstructing an original data file, comprising:
 receiving a data file comprising a modified original data file having been modified by a modification process comprising:
 (a) reading the original data file into a sequence of multiple-byte data groups; 
 (b) arranging the bytes of each data group in ascending byte value order; 
 (c) writing an index into a first file that represents the original position of the bytes in each data group relative to their rearranged order; 
 (d) writing the first byte value from each of the rearranged data groups into a second file; 
 (e) writing calculated difference byte values representing the respective differences between each pair of consecutive byte values in each rearranged data group into a third file; and 
 (f) outputting the first, second and third files for compression; and 
   reversing the modification process to reconstruct the original data file.   
     
     
       51. A method according to claim 50, wherein said reversing the modification process further comprises:
 calculating the ascending byte values for each rearranged data group based on the first byte values from the second file and the difference byte values from the third file;   re-ordering the position of the calculated ascending byte values of each rearranged data group back into their original position in the data group based on the index of the first file; and   assembling the original data file from the re-ordered data groups.   
     
     
       52. A method for reconstructing an original data file, comprising:
 receiving a data file comprising a modified original data file, the original data file having a sequence of byte values and each byte value having an associated decimal order value representing its position in the sequence of the byte values of the original data file, the modified original data file having been modified by a modification process comprising:
 (a) writing the byte values having an even order value into a first file; 
 (b) writing the byte values having an odd order value into a second file; and 
 (c) outputting the first and second files for compression to a lossless compression algorithm for compression into a single file; and 
   reversing the modification process to reconstruct the original data file.   
     
     
       53. A method of according to claim 52 wherein said reversing the modification process further comprises recombining the byte values from the first and second files into their original order relative to each other. 
     
     
       54. A method according to claim 53 wherein said recombining the byte values from the first and second files further comprises inserting the byte values from the second file between their associated respective adjacent byte values in the first file.