Order preserving run length encoding with compression codeword extraction for comparisons
First Claim
1. 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.
0 Assignments
0 Petitions
Accused Products
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.
22 Citations
20 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. 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. - View Dependent Claims (14, 15, 16, 17)
-
-
18. 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. - View Dependent Claims (19, 20)
-
Specification