Methods and apparatus for data compression that preserves order

Details Methods and apparatus for data compression that preserves order Methods and apparatus for data compression that preserves order

1995-08-01

1997-08-19

Loomis, John C.

Coded data generation or conversion

Digital code to digital code converters

Tree structure

395607, 341 90, G06F 500, G06F 1730

Patent

active

056597371

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.

REFERENCES:
patent: 5001477 (1991-03-01), Hicks et al.
patent: 5270712 (1993-12-01), Iyer et al.
patent: 5546080 (1996-08-01), Langdon, Jr. et al.
patent: 5585793 (1996-12-01), Antoshenkov et al.
Predictive Text Compression By Hashing, By T. Raita and J. Teuhola, Proceedings of the 10th Annual ACM SIGIR Conference on Research Development in Information Retrieval, New Orleans, Jun. 3-5, 1987, pp. 223-232.

Affiliated with

Also associated with

Rating

Methods and apparatus for data compression that preserves order does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for data compression that preserves order , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for data compression that preserves order will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1112576