US5629695A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Order preserving run length encoding with compression codeword extraction for comparisons
Assignee: International Business Machines Corp
•
Filing: 1995-06-06
•
Granted: 1997-05-13
•
Expires: 2015-06-06
Abstract
Abstract The present invention provides a system and method for the dictionary ordering of keys after expansion, compression and concatenation of their key parts. After each key part has been expanded through padding, each substring of identical characters of length greater than or equal to three is compressed through run-length encoding algorithm. The substring is replaced by the sequence character, a compression identifying character and a number identifying the number of characters being replaced. After compression and the subsequent concatenation, the keys are compared character by character. At the first instance of a miscomparison, the comparison scheme performs a normal dictionary ordering if neither of the characters are part of a compression sequence. If a character at the point of miscomparison is part of a compression sequence then an ordering decision is made based on the compression character, the length of the compressed substring and the character following the compressed substring.
Inventors
- 👤 Steven J. Watts
- 👤 Balakrishna R. Iyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 17:40
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99937
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
89 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for comparing character strings that are compressed through run length encoding, said method steps comprising: (a) comparing the compressed character strings to identify a point of miscomparison; and (b) ordering said compressed character strings based on characters at the point of miscomparison, characters at the two character positions prior to said point of miscomparison and characters at the two character positions after said point of miscomparison.
Claim 2
Dependent Claim
89 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for comparing character strings that are compressed through run length encoding, said method steps comprising: (a) comparing the compressed character strings to identify a point of miscomparison; and (b) ordering said compressed character strings based on characters at the point of miscomparison, characters at the two character positions prior to said point of miscomparison and characters at the two character positions after said point of miscomparison.
Claim 3
Dependent Claim
49 words
The program storage device of claim 1, further including the performance of the step of replacing a substring of identical characters within the character string with a run-length encoded codeword comprising a compressed character, a compression identifying character and a number identifying the number of characters that are replaced.
Claim 4
Dependent Claim
23 words
The program storage device of claim 2, wherein said compression identifying character is a character in the character set that is infrequently used.
Claim 5
Dependent Claim
27 words
The program storage device of claim 3, wherein an n-length substring (n≧1) of said compression identifying characters is always compressed to represent a substring of length n.
Claim 6
Dependent Claim
36 words
The program storage device of claim 4, further including the performance of the step of identifying whether the character at the point of miscomparison is part of a codeword representing a substring of compression identifying characters.
Claim 7
Dependent Claim
99 words
The program storage device of claim 5, wherein the performance of the step of ordering further comprises the steps of: (1) identifying whether the character at the point of miscomparison is pan of a run-length encoded codeword; (2) identifying said compressed character of said compressed substring; (3) identifying a count value representing the number of compressed characters that follows said point of miscomparison; (4) identifying the next character following said run-length encoded codeword; and (5) comparing said compressed character of the key with a higher count value to the next character of the key with a lower count value.
Claim 8
Dependent Claim
112 words
A computer program product, comprising: a computer usable medium having computer readable program code means embodied in said medium for comparing character strings that are compressed through run length encoding, said computer readable program code means comprising: computer readable program code means for causing a computer to effect a comparison of the compressed character strings to identify a point of miscomparison; and computer readable program code means for causing a computer to effect an ordering of the compressed character strings based on characters at the point of miscomparison, characters at the two character positions prior to said point of miscomparison and characters at the two character positions after said point of miscomparison.
Claim 9
Dependent Claim
112 words
A computer program product, comprising: a computer usable medium having computer readable program code means embodied in said medium for comparing character strings that are compressed through run length encoding, said computer readable program code means comprising: computer readable program code means for causing a computer to effect a comparison of the compressed character strings to identify a point of miscomparison; and computer readable program code means for causing a computer to effect an ordering of the compressed character strings based on characters at the point of miscomparison, characters at the two character positions prior to said point of miscomparison and characters at the two character positions after said point of miscomparison.
Claim 10
Dependent Claim
42 words
The computer program product of claim 7, wherein a substring of identical characters within the character string is replaced with a run-length encoded codeword comprising a compressed character, a compression identifying character and a number identifying the number of characters being replaced.
Claim 11
Dependent Claim
23 words
The computer program product of claim 8, wherein said compression identifying character is a character in the character set that is infrequently used.
Claim 12
Dependent Claim
27 words
The computer program product of claim 9, wherein an n-length substring (n≧1) of said compression identifying character is always compressed to represent a substring of length n.
Claim 13
Dependent Claim
43 words
The computer program product of claim 10, further comprising computer readable program code means for causing a computer to effect an identification of whether the character at the point of miscomparison is part of a codeword representing a substring of compression identifying characters.
Claim 14
Dependent Claim
137 words
The computer program product of claim 11, wherein the computer readable program code means for causing a computer to effect an ordering further comprises: computer readable program code means for causing a computer to effect an identification of whether the character at the point of miscomparison is part of a run-length encoded codeword; computer readable program code means for causing a computer to effect an identification of said compressed character of said compressed substring, a count value representing the number of compressed characters that would follow said point of miscomparison, and the next character following said run-length encoded codeword; and computer readable program code means for causing a computer to effect a comparison of said compressed character of the key with a higher count value to the next character of the key with a lower count value.
Claim 15
Dependent Claim
122 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for comparing character strings that are compressed through run length encoding, wherein a string of identical characters is replaced with a compressed character, a compression identifying character and a number identifying the number of characters that are replaced, said method steps comprising: (a) comparing the compressed character strings to identify a point of miscomparison; (b) identifying for each character string whether a character at said point of miscomparison is part of a run-length encoded codeword; (c) identifying the compressed character for each run length encoded codeword; and (d) ordering the compressed character strings based on the compressed character value.
Claim 16
Dependent Claim
122 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for comparing character strings that are compressed through run length encoding, wherein a string of identical characters is replaced with a compressed character, a compression identifying character and a number identifying the number of characters that are replaced, said method steps comprising: (a) comparing the compressed character strings to identify a point of miscomparison; (b) identifying for each character string whether a character at said point of miscomparison is part of a run-length encoded codeword; (c) identifying the compressed character for each run length encoded codeword; and (d) ordering the compressed character strings based on the compressed character value.
Claim 17
Dependent Claim
27 words
The program storage device of claim 13, wherein an n-length substring (n≧1) of said compression identifying characters is always compressed to represent a substring of length n.
Claim 18
Dependent Claim
38 words
The program storage device of claim 14, further including the performance of the step of identifying whether the character at said point of miscomparison is the start of a codeword representing a substring of said compression identifying character.
Claim 19
Dependent Claim
57 words
The program storage device of claim 13, wherein the performance of the step of identifying whether a character at said point of miscomparison is part of a run-length encoded codeword further comprises the step of identifying whether the compression identifying character is at said point of miscomparison or at the position previous to said point of miscomparison.
Claim 20
Dependent Claim
68 words
The program storage device of claim 13, further including the performance of the steps of: (e) identifying a count value representing the number of compressed characters that follows said point of miscomparison; (f) identifying the next character following said run-length encoded codeword; and (g) comparing the compressed character of the key with a higher count value to the next character of the key with a lower count value.
Claim 21
Dependent Claim
171 words
A computer program product, comprising: a computer usable medium having computer readable program code means embodied in said medium for causing a comparison of character strings that are compressed through run length encoding, wherein a string of identical characters is replaced with a compressed character, a compression identifying character and a number identifying the number of characters that are replaced, said computer readable program code means comprising: computer readable program code means for causing a computer to effect a comparison of the compressed character strings to identify a point of miscomparison; computer readable program code means for causing a computer to effect an identification for each character string whether a character at said point of miscomparison is part of a run-length encoded codeword; computer readable program code means for causing a computer to effect an identification of the compressed character for each run length encoded codeword; and computer readable program code means for causing a computer to effect an ordering of the compressed character strings based on the compressed character value.
Claim 22
Dependent Claim
171 words
A computer program product, comprising: a computer usable medium having computer readable program code means embodied in said medium for causing a comparison of character strings that are compressed through run length encoding, wherein a string of identical characters is replaced with a compressed character, a compression identifying character and a number identifying the number of characters that are replaced, said computer readable program code means comprising: computer readable program code means for causing a computer to effect a comparison of the compressed character strings to identify a point of miscomparison; computer readable program code means for causing a computer to effect an identification for each character string whether a character at said point of miscomparison is part of a run-length encoded codeword; computer readable program code means for causing a computer to effect an identification of the compressed character for each run length encoded codeword; and computer readable program code means for causing a computer to effect an ordering of the compressed character strings based on the compressed character value.
Claim 23
Dependent Claim
45 words
The computer program product of claim 18, further comprising computer readable program code means for causing a computer to effect an identification of whether the character at said point of miscomparison is the start of a codeword representing a substring of said compression identifying character.
Claim 24
Dependent Claim
98 words
The computer program product of claim 18, further comprising: computer readable program code means for causing a computer to effect an identification of a count value representing the number of compressed characters that follows said point of miscomparison; computer readable program code means for causing a computer to effect an identification of the next character following said run-length encoded codeword; and computer readable program code means for causing a computer to effect a comparison of the compressed character of the key with a higher count value to the next character of the key with a lower count value.
References Cited (Backward Citations)
US4464650A
Cited
US5153591A
Cited
US5463390A
Cited
US5532694A
Cited
US5298895A
Cited
US5270712A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |