Methods and apparatus for data compression that preserves order by using

Abstract

A compressor receives a plurality of characters in a character string, and encodes the input character string to generate an encoded string. The encoding preserves the original binary order of the input character strings in the encoded strings. A predicted character is generated for each character based on prior character sequences in the character string. In one embodiment, a hash based predictive technique is used to generate the predicted characters. A correct order indicating token is generated for an input character if a predicted character, corresponding to the input character, is the input character. The compressor stores the order indicating token in the encoded string to represent the character. However, if an input character has a binary representation greater than a binary representation of a corresponding predicted character, then a failure greater than token and the input character are stored in the encoded string to represent the input character. A failure less than token and an input character are stored for an input character in the encoded string if the input character has a binary representation less than a binary representation of the predicted character. Thus, binary order is preserved in the encoded string. With the binary order preserving compression technique, data may be sorted while the data are still compressed. Prefix bits compression and dynamic token generation are also disclosed.