Patent US5659737A successfully refreshed from Google Patents.
US5659737A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for data compression that preserves order by using failure greater than and failure less than tokens
Assignee: Oracle International Corp
•
Filing: 1995-08-01
•
Granted: 1997-08-19
•
Expires: 2015-08-01
Abstract
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.
Inventors
- 👤 Yasuhiro Matsuda
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 04:48
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
153 words
A method for compressing a plurality of characters in a character string, said method comprising the steps of: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding, for an input character, a failure greater than token and said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding, for an input character, a failure less than token and said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said .character string.
Claim 2
Independent Claim
153 words
A method for compressing a plurality of characters in a character string, said method comprising the steps of: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding, for an input character, a failure greater than token and said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding, for an input character, a failure less than token and said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said .character string.
Claim 3
Dependent Claim
36 words
The method as set forth in claim 1, wherein: said correct predicted token equals a binary 1,0; said failure greater than token equals a binary 1,1; and said failure less than token equals a binary 0.
Claim 4
Dependent Claim
104 words
The method as set forth in claim 1, further comprising the steps of: eliminating one or more significant bits of an input character if said one or more significant bits of a corresponding predicted character are set to zero and if said input character has a binary representation less than a binary representation of said corresponding predicted character; and eliminating one or more significant bits of an input character if said one or more significant bits of a corresponding predicted character are set to one and if said input character has a binary representation greater than a binary representation of said corresponding predicted character.
Claim 5
Independent Claim
188 words
A method for compressing a plurality of characters in a character string, said method comprising the steps of: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a binary "10" token for said input character if a most significant bit of a corresponding predicted character is not set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "01" token for said input character if a most significant bit of a corresponding predicted character is set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "1" token and an input character for said, input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding a binary "0" token and an input character for said input character if said input character has a binary representation less than a binary representation of a corresponding predicted character.
Claim 6
Independent Claim
188 words
A method for compressing a plurality of characters in a character string, said method comprising the steps of: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a binary "10" token for said input character if a most significant bit of a corresponding predicted character is not set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "01" token for said input character if a most significant bit of a corresponding predicted character is set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "1" token and an input character for said, input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding a binary "0" token and an input character for said input character if said input character has a binary representation less than a binary representation of a corresponding predicted character.
Claim 7
Independent Claim
168 words
A method for sorting a plurality of records comprising a plurality of characters, said method comprising the steps of: generating a plurality of compressed records from said records including the steps of: generating a predicted character for each of said characters in said records based on prior character sequences in said records; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding a failure greater than token and said input character for said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; encoding a failure less than token and said input character for said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said records; and sorting said compressed records.
Claim 8
Independent Claim
168 words
A method for sorting a plurality of records comprising a plurality of characters, said method comprising the steps of: generating a plurality of compressed records from said records including the steps of: generating a predicted character for each of said characters in said records based on prior character sequences in said records; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding a failure greater than token and said input character for said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; encoding a failure less than token and said input character for said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said records; and sorting said compressed records.
Claim 9
Dependent Claim
146 words
A computer readable medium comprising a plurality of program instructions for: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding, for an input character, a failure greater than token and said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding, for an input character, a failure less than token and said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said character string.
Claim 10
Dependent Claim
146 words
A computer readable medium comprising a plurality of program instructions for: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding, for an input character, a failure greater than token and said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding, for an input character, a failure less than token and said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said character string.
Claim 11
Dependent Claim
36 words
The computer readable medium as set forth in claim 6, wherein: said correctly predicted token equals a binary 1,0; said greater than token equals a binary 1,1; and said less than token equals a binary 0.
Claim 12
Dependent Claim
106 words
The computer readable medium as set forth in claim 6, comprising further program instructions for: eliminating one or more significant bits of an input character if said one or more significant bits of a corresponding predicted character are set to zero and if said input character has a binary representation less than a binary representation of said corresponding predicted character; and eliminating one or more significant bits of an input character if said one or more significant bits of a corresponding predicted character are set to one and if said input character has a binary representation greater than a binary representation of said corresponding predicted character.
Claim 13
Dependent Claim
181 words
A computer readable medium comprising a plurality of program instructions for: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a binary "10" token for said input character if a most significant bit of a corresponding predicted character is not set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "01" token for said input character if a most significant bit of a corresponding predicted character is set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "1" token and an input character for said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding a binary "0" token and an input character for said input character if said input character has a binary representation less than a binary representation of a corresponding predicted character.
Claim 14
Dependent Claim
181 words
A computer readable medium comprising a plurality of program instructions for: generating a predicted character for each of said characters in said character string based on prior character sequences in said character string; encoding a binary "10" token for said input character if a most significant bit of a corresponding predicted character is not set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "01" token for said input character if a most significant bit of a corresponding predicted character is set to zero and if said input character has a binary representation equal to a binary representation of said corresponding predicted character; encoding a binary "1" token and an input character for said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; and encoding a binary "0" token and an input character for said input character if said input character has a binary representation less than a binary representation of a corresponding predicted character.
Claim 15
Dependent Claim
202 words
A computer system comprising: a processing unit; a storage device coupled to said processor unit for storing records; main memory, coupled to said processor unit, for storing a plurality of instructions for execution in said processor unit, said instructions for generating a plurality of compressed records from said records including instructions for: generating a predicted character for each of said characters in said records based on prior character sequences in said records; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding a failure greater than token and said input character for said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; encoding a failure less than token and said input character for said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said records; and sorting said compressed records that comprise a plurality of characters including utilizing said storage device for temporary storage.
Claim 16
Dependent Claim
202 words
A computer system comprising: a processing unit; a storage device coupled to said processor unit for storing records; main memory, coupled to said processor unit, for storing a plurality of instructions for execution in said processor unit, said instructions for generating a plurality of compressed records from said records including instructions for: generating a predicted character for each of said characters in said records based on prior character sequences in said records; encoding a correct order indicating token for an input character if a predicted character, corresponding to said input character, is said input character; encoding a failure greater than token and said input character for said input character if said input character has a binary representation greater than a binary representation of a corresponding predicted character; encoding a failure less than token and said input character for said input character if said input character has a binary representation less than a binary representation of said predicted character, wherein said correct order indicating token, said failure greater than token, and said failure less than token result in preserving binary order of said records; and sorting said compressed records that comprise a plurality of characters including utilizing said storage device for temporary storage.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-18 | 2001-02-17 | 2001-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-18 | 2005-02-17 | 2005-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-18 | 2009-02-17 | 2009-08-19 | $7700.00 | Window Closed / Lapsed |