US3593309A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and means for generating compressed keys
Assignee: International Business Machines Corp
•
Filing: 1969-01-03
•
Granted: 1971-07-13
•
Expires: 1989-01-03
Abstract
Abstract Electronically compressing a sorted sequence of uncompressed keys, each having an associated pointer address for accessing the information represented by the key. Compression is by electronic transfer of the remaining part of any key after removing some or all of (1) high-order ''''factored'''' bytes, and (2) low-order ''''noise'''' bytes. The transferred parts of a key are delineated using an electronic device for comparing like-ordered bytes in their sorting order in adjacent uncompressed keys. The comparing device determines a difference-byte position as the highestordered unequal byte position in every pair of adjacent keys. The ''''noise'''' bytes are electronically sensed as the bytes having a lower-order than the difference byte. The ''''factored'''' bytes are electronically sensed at higher-order positions than the difference-byte; and they are vicariously represented in prior compressed keys due to the sorted nature of the key sequence. In some cases, the ''''factored'''' bytes include the difference byte; and in other cases the ''''factored'''' bytes do not include all bytes having a higher-order than the difference-byte position. The pointer with each uncompressed key is associated with a related compressed key. A count field is generated with each compressed key to indicate the size of the factor field and number of transferred key bytes.
Inventors
- 👤 William A Clark
- 👤 Kent A Salmond
- 👤 Thomas S Stafford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 15:51
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9017; G06F16/902
Claims Analysis
Total Claims: 125
Claim 1
Independent Claim
77 words
A compressed key generation method using machine-readable keys in a source index representing different items of information comprising the following steps: machine-accessing in a sorted sequence each key and its next key to obtain a pair of keys, machine-sensing a highest-order unequal bytes position, said position having unequal bytes in the pair, machine-generating a code representing said position, and machine-registering said code as a component of a compressed key representing one of the keys in said pair.
Claim 2
Dependent Claim
77 words
A compressed key generation method using machine-readable keys in a source index representing different items of information comprising the following steps: machine-accessing in a sorted sequence each key and its next key to obtain a pair of keys, machine-sensing a highest-order unequal bytes position, said position having unequal bytes in the pair, machine-generating a code representing said position, and machine-registering said code as a component of a compressed key representing one of the keys in said pair.
Claim 3
Dependent Claim
51 words
A compressed key generation method as defined in claim 1 further including the step of: machine-counting the number of bytes from said position to the highest-order byte position in said pair to perform said machine-generating step, and machine-registering the output of the machine-counting step as said code within said compressed key.
Claim 4
Dependent Claim
47 words
A compressed key generation method as defined in claim 1 further comprising: machine-demarcing bytes of one of the keys in said pair located from said position through the highest-order byte position, whereby key bytes for the compressed key are selectable from bytes defined by said machine-demarcing step.
Claim 5
Dependent Claim
23 words
A compressed key generation method as defined in claim 3 further comprising machine-recording any selected key bytes from said key in said pair.
Claim 6
Dependent Claim
65 words
A compressed key generation method as defined in claim 3 further including the steps of: machine-inhibiting the selection of bytes having a lower-order than said position in the next key of said pair of key bytes for the compressed key, whereby compressed key bytes are selectable from remaining bytes in said next key, and said bytes demarced by said machine-inhibiting step are search noise bytes.
Claim 7
Dependent Claim
45 words
A compressed key generation method as defined in claim 3 in which each key has an associated address for retrieving its represented item of information, further comprising the step of machine-recording with said compressed key the address associated with the next key in said pair.
Claim 8
Dependent Claim
57 words
A compressed key generation method as defined in claim 3 in which said pair is the first pair of keys in the sorted sequence, further including the steps of machine-transferring all bytes in said next key between said position and the highest-order byte position to form key bytes within the first compressed key in a compressed index.
Claim 9
Dependent Claim
32 words
A compressed key generation method as defined in claim 7 further including the step of machine-transferring with the first compressed key a pointer associated with the first key in the source index.
Claim 10
Dependent Claim
37 words
A compressed key generation method as defined in claim 1 further including the step of machine-storing the code of said machine-generating step at least until after the machine-generating step outputs a next code for the next pair.
Claim 11
Dependent Claim
50 words
A compressed key generation method as defined in claim 1 applied to two sequential pairs of keys, further including the steps of machine-comparing the codes for the two sequential pairs and outputting a comparison signal, and machine-generating a compressed key from the next pair in relation to said comparison signal.
Claim 12
Dependent Claim
52 words
A compressed key generation method as defined in claim 10, including the steps, machine-detecting said comparison signal and signalling that the code for a second pair of the two sequential pairs is greater than the code for the first pair, and machine-generating a compressed key from a key in the second pair.
Claim 13
Dependent Claim
29 words
A compressed key generation method as defined in claim 11, in which said machine-generating step includes the substep machine-selecting key bytes from the second key of said second pair.
Claim 14
Dependent Claim
55 words
A compressed key generation method as defined in claim 10 including the steps machine-detecting said comparison signal and signalling that the code for a second pair of the two sequential pairs is equal to or less than the code for the first pair, and machine-generating a compressed key from a key in the second pair.
Claim 15
Dependent Claim
33 words
A compressed key generation method as defined in claim 13 in which said machine-generating method includes the substep machine-selecting not more than one key byte from the second key of said second pair.
Claim 16
Dependent Claim
56 words
A compressed key generation method as defined in claim 3 comprising the steps of: machine-selecting said bytes from a first key in said pair, machine-changing the lowest-order byte of said bytes to its next byte in a collating sequence being used, and recording the bytes selected by said machine-selecting step as modified by said changing step.
Claim 17
Dependent Claim
89 words
A compressed key generation method as defined in claim 15 comprising the steps of: comparing said changed lowest-order byte with the byte in the same location in the next key of the pair, and if equal performing the following step: restoring the changed byte to its original form for said recording step, machine-selecting the adjacent next lower-order byte of said first key, increasing it to its next byte in the collating sequence, and recording the last selected byte with the byte in the corresponding byte-position in the next key.
Claim 18
Dependent Claim
108 words
A compressed key generation method using machine-readable keys in a source index comprising the steps: machine-accessing a pair of keys sequentially in the sorted order of the keys in said index, positioning a second key of one pair as a first key of the next pair, machine-comparing like-ordered bytes in a current pair of equality and inequality from a highest-ordered byte position to at least a highest-order unequal byte position, machine-counting the equal bytes of said current pair duriNg said machine-comparing step until said highest-order unequal byte position is sensed, and registering a count output signal from said machine counting step as a component of a compressed key.
Claim 19
Dependent Claim
108 words
A compressed key generation method using machine-readable keys in a source index comprising the steps: machine-accessing a pair of keys sequentially in the sorted order of the keys in said index, positioning a second key of one pair as a first key of the next pair, machine-comparing like-ordered bytes in a current pair of equality and inequality from a highest-ordered byte position to at least a highest-order unequal byte position, machine-counting the equal bytes of said current pair duriNg said machine-comparing step until said highest-order unequal byte position is sensed, and registering a count output signal from said machine counting step as a component of a compressed key.
Claim 20
Dependent Claim
34 words
A compressed key generation method as defined in claim 17, further comprising the step of: storing the count output signal from said machine-counting step at least through the machine-counting step for the next pair.
Claim 21
Dependent Claim
68 words
A compressed key generation method as defined in claim 18, including the further steps of changing the status of the next pair and current pair, to the current pair and prior pair respectively, machine-comparing the count output signals for said next pair against the count output signal for said prior pair to generate a shift-type signal, and generating a current compressed key in response to said shift-type signal.
Claim 22
Dependent Claim
90 words
A compressed key generation method as defined in claim 19, in which said shift-type signal indicates the count output signal for the current pair is greater than the count output signal for the prior pair, said generating step including the substep of machine-copying to a current compressed key recording area those bytes in one of the keys in the current pair from a byte position determined by the count output signal for said prior pair to a lower-order byte position determined by the count output signal for said current pair.
Claim 23
Dependent Claim
88 words
A compressed key generation method as defined in claim 20, in which said generating step includes the substeps of: machine-generating a factor byte-count code from a byte count in the range from the count output signal of said prior pair to one byte greater than said signal, machine-generating a key-byte count code equal to the number of bytes transferred to the compressed key recording area by said machine-copying step, and machine-copying the factor byte-count code and the key-byte count code as fields within the current compressed key area.
Claim 24
Dependent Claim
54 words
A compressed key generation method as defined in claim 20, further including the steps of: machine-inhibiting the selection in said one of the keys of its bytes having a higher-order than a byte position determined by the count output signal for said prior pair, whereby factor bytes are not included as compressed key bytes.
Claim 25
Dependent Claim
78 words
A compressed key generation method as defined in claim 19, in which said shift-type signal indicates the count output signal for the current pair is less than or equal to the count output signal for the prior pair, said generating step including the substep of: machine-copying to a current compressed key recording area not more than one byte derived from one of the keys in the current pair at the highest-order unequal byte position for the current pair.
Claim 26
Dependent Claim
94 words
A compressed key generation method as defined in claim 23, in which said generating step includes the substeps of: machine-generating a factor byte-count code from a byte count in the range from the count output signal of said prior pair through the count output signal of the current pair increased by one byte, machine-generating a key-byte count code equal to the number of bytes transferred to the compressed key recording area by said machine-copying step, and machine-recording the factor byte-count code and the key-byte count code as fields within the current compressed key area.
Claim 27
Dependent Claim
34 words
A compressed key generation method as defined in claim 21 in which said machine-copying step includes the substep of: machine-recording both of said codes in a single byte of said current compressed key area.
Claim 28
Dependent Claim
32 words
A compressed key generation method as defined in claim 5, in which the machine-recording substep includes the substep of machine-recording said single byte at the beginning of said current compressed key area.
Claim 29
Dependent Claim
57 words
A compressed key generation method as defined in claim 25, in which said machine-recording substep includes the substeps of: machine-generating an extender code when the factoR byte-count code exceeds an allocated area for said byte-count code in said single byte, and machine-recording the factor byte-count code in another predetermined byte location in the current compressed key field.
Claim 30
Dependent Claim
57 words
A compressed key generation method as defined in claim 25, in which said machine-recording substep includes the substeps of: machine-generating an extender code when the key byte-count code exceeds an allocated area for said byte-count code in said single byte, and machine-recording the key byte-count code in another predetermined byte location in the current compressed key field.
Claim 31
Dependent Claim
40 words
A compressed key generation method as defined in claim 27, in which said machine-recording substep includes the substeps of: machine-recording the factor byte count code and the key byte-count code in different predetermined bytes in the current compressed key area.
Claim 32
Dependent Claim
34 words
A compressed key generation method as defined in claim 27, in which said machine-recording substep includes the substep of: machine-recording each of said codes before the key bytes in the current compressed key area.
Claim 33
Dependent Claim
63 words
A compressed key generation method as defined in claim 19, in which said shift-type signal indicates said count output signal for the current pair is equal to the count output signal for the prior pair, said generating step including the substep of machine-copying to a current compressed key recording area a byte from one of said keys at its highest-order unequal byte position.
Claim 34
Dependent Claim
169 words
A compressed key generation method as defined in claim 19, in which said shift-type signal indicates said count output signal for the current pair is equal to the count output signal for the prior pair, said generating step including the substeps of machine-sensing the existence of nonexistence of any key byte for the prior compressed key to generate a prior key-byte existence signal, for controlling the following substeps: machine-copying to a current compressed key recording area from one of the keys in a current pair its byte at the highest-order unequal byte position, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, and bypassing the machine-copying step, in response to said prior key-byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby alternation in the existence and nonexistence of key bytes occurs among a succession of compressed keys resulting from a succession of pairs of keys providing equal shift-type signals.
Claim 35
Dependent Claim
56 words
A compressed key generation method as defined in claim 19, in which said shift-type signal indicates the count output signal for said current pair is less than the count output signal for said prior pair, said generating step including the substep of machine-inhibiting the copying of any key byte to a current compressed key recording area.
Claim 36
Dependent Claim
211 words
A compressed key generation method as defined in claim 19, in which said shift-type signal indicates the count output signal for the current pair is greater than the count output signal for the prior pair, said generating step including the substeps of machine-sensing the existence of nonexistence of any key byte for the prior compressed key to provide a prior key-byte existence signal, for controlling the following substeps: machine-copying to a current compressed key recording area those bytes in one of the keys in a current pair from a byte position specified by the count output signal or said prior pair through a lower-order byte position specified by the count output signal for said current pair, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, machine-copying to a current compressed key recording area those bytes in one of the keys in the current pair from a lower-order byte position next to that specified by the count output signal for said prior pair through a lower-order byte position specified by the count output signal for said current pair, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key.
Claim 37
Dependent Claim
65 words
A compressed key generation method as defined in claim 32, in which said shift-type signal indicates the count output signal for said current pair is less than the count output signal for said prior pair, said generating step including the substeps of: machine-generating a null factor signal, machine-recording a null code in the current compressed key recording area in response to said null factor signal.
Claim 38
Dependent Claim
40 words
A compressed key generation method as defined in claim 20, including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 39
Dependent Claim
68 words
A compressed key generation method as defined in claim 20, in which the generation step includes the substeps of machine-copying bytes only from the second key in said pair from byte locations defined by the respective preceding machine-copying step, and machine-recording a pointer address to information identified by said first key in said pair, whereby the current compressed key recording area receives the output of said machine-copying steps.
Claim 40
Dependent Claim
58 words
A compressed key generation method as defined in claim 23, including the additional steps: machine-generating a factor signal indicating not less than the value of said count output signal for the current pair increased by one, and storing said factor signal into the current compressed key area, whereby a minimum factor field is available for left-shift-type compressed keys.
Claim 41
Dependent Claim
47 words
A compressed key generation method as defined in claim 33, including the additional steps of: machine-generating a factor signal indicating not over the value of said count output signal for the prior pair increased by one, and storing said factor signal into the current compressed key area.
Claim 42
Dependent Claim
140 words
A compressed key generation method as defined in claim 39, in which said machine-generating step includes the substeps of: machine-sensing the existence or nonexistence of any key byte for the prior compressed key to provide a prior key-byte existence signal, for controlling the following substeps: machine-generating a factor signal specifying not over the value represented by said count output signal for the prior pair, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, machine-generating a factor signal specifying not over the value represented by said count output signal for the prior pair increased by one, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby a maximum factor field is available for left-shift-type compressed keys.
Claim 43
Dependent Claim
133 words
A compressed key generation method as defined in claim 16, including the additional steps of: machine-sensing the existence of nonexistence of any key byte for the prior compressed key, to provide a prior key-byte existence signal, for controlling the following substeps: machine-generating a factor signal specifying the value of the prior count output signal for the prior pair, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, machine-generating a factor signal specifying not over the value represented by the count output signal of the prior pair increased by one, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby a factor field is provided for right-shift compressed keys.
Claim 44
Dependent Claim
40 words
A compressed key generation method as defined in claim 17, including the steps of: machine-sensing the second key of said next pair for an end-of-index indication, and generating an end-of-index signal in response to the machine-sensing step detecting said indication.
Claim 45
Dependent Claim
62 words
A compressed key generation method as defined in claim 42, including the steps of: machine-transferring a null code signal to a current compressed key recording area to represent an end-of-index compressed key, and machine-recording in the current compressed key area a point address associated with the first key of said next pair for retrieving the data item represented by said first key.
Claim 46
Dependent Claim
86 words
Compressed key generation means using machine-readable keys in a source index representing different items of information comprising: means for accessing in a sorted sequence each key and its next key to obtain a pair of keys, means for sensing a highest-order unequal byte position, in said pair of keys, said position having unequal bytes in the pair, means for generating a code representing said position, and means for registering said code as a component of a compressed key representing one of the keys in said pair.
Claim 47
Dependent Claim
86 words
Compressed key generation means using machine-readable keys in a source index representing different items of information comprising: means for accessing in a sorted sequence each key and its next key to obtain a pair of keys, means for sensing a highest-order unequal byte position, in said pair of keys, said position having unequal bytes in the pair, means for generating a code representing said position, and means for registering said code as a component of a compressed key representing one of the keys in said pair.
Claim 48
Dependent Claim
51 words
Compressed key generation means as defined in claim 44 further including: means for counting the number of bytes from said position to the highest-order byte position in said pair to obtain said generating means, and means for registering the output of the counting means as said code within said compressed key.
Claim 49
Dependent Claim
48 words
Compressed key generation means as defined in claim 44 further comprising: means for demarcing bytes of one of the keys in sad pair located from said position through the highest-order byte position, whereby key bytes for the compressed key are selectable from bytes defined by said demarcing means.
Claim 50
Dependent Claim
24 words
Compressed key generation means as defined in claim 46 further comprising means for recording any selected key bytes from said key in said pair.
Claim 51
Dependent Claim
63 words
Compressed key generation means as defined in claim 46 further including: means for inhibiting the selection of bytes having a lower-order than said position in the next key of said pair as key bytes for the compressed key, whereby compressed key bytes are selectable from remaining bytes in said next key, and said bytes demarced by said inhibiting means are search noise bytes.
Claim 52
Dependent Claim
43 words
Compressed key generation means as defined in claim 46 in which each key has an associated address for retrieving its represented item of information, further comprising: means for recording with said compressed key the address associated with the next key in said pair.
Claim 53
Dependent Claim
55 words
Compressed key generation means as defined in claim 46 in which said pair is the first pair of keys in the sorted sequence, further including means for transferring all bytes in said next key between said position and the highest-order byte position to form key bytes within the first compressed key in a compressed index.
Claim 54
Dependent Claim
30 words
Compressed key generation means as defined in claim 50 further including means for transferring with the first compressed key a pointer associated with the first key in the source index.
Claim 55
Dependent Claim
37 words
Compressed key generation means as defined in claim 44 further including means for storing the code of said generating means at least until after the generating means outputs a next code for the next pair of keys.
Claim 56
Dependent Claim
54 words
Compressed key generation means as defined in claim 44 applied to two sequential pairs of key, further including means for comparing the codes for the two sequential pairs of keys and outputting a comparison signal, and means for generating a compressed key from the next pair of keys in relation to said comparison signal.
Claim 57
Dependent Claim
59 words
Compressed key generation means as defined in claim 53, including means for detecting said comparison signal and signalling that the code for a second pair of the two sequential pairs of keys is greater than the code for the first pair of keys, and means for generating a compressed key from a keY in the second pair of keys.
Claim 58
Dependent Claim
29 words
Compressed key generation means as defined in claim 54, in which said means for generating includes means for selecting key bytes from the second key of said second pair.
Claim 59
Dependent Claim
56 words
Compressed key generation means as defined in claim 53 including means for detecting said comparison signal and signalling that the code for a second pair of the two sequential pairs is equal to or less than the code for the first pair, and means for generating a compressed key from a key in the second pair.
Claim 60
Dependent Claim
35 words
Compressed key generation means as defined in claim 56 in which said means for generating includes means for selecting not more than one key byte from the second key of said second pair of keys.
Claim 61
Dependent Claim
76 words
Compressed key generation means as defined in claim 46 comprising means for selecting said bytes demarced by said demarcing means from a first key in said pair of keys, means for changing the lowest-order byte of said bytes selected by said selecting means to its next byte in a collating sequence being used, said lowest-order byte being a changed byte, and recording the bytes selected by said means for selecting as modified by said changing means.
Claim 62
Dependent Claim
109 words
Compressed key generation means as defined in claim 58 comprising means for comparing said changed lowest-order byte with the byte in the same location in the next key of the pair, and to handle the situation in which the compared bytes are equal, further including: means for restoring the changed byte to its original form in said first key from which it was selected by said selecting means, means for selecting the adjacent next lower-order byte of said first key, increasing it to its next byte in the collating sequence, and means for recording the last selected byte with the byte in the corresponding byte-position in the next key.
Claim 63
Dependent Claim
109 words
Compressed key generation means using machine-readable keys in a source index comprising: Means for accessing a pair of keys sequentially in the sorted order of the keys in said index, positioning a second key of one pair as a first key of the next pair, means for comparing like-order bytes in a current pair of said keys for equality and inequality from a highest-ordered byte position to at least a highest-order unequal byte position, means for counting the equal bytes of said current pair until said highest-order unequal byte position is sensed, and registering a count signal from said means for counting as a component of a compressed key.
Claim 64
Dependent Claim
109 words
Compressed key generation means using machine-readable keys in a source index comprising: Means for accessing a pair of keys sequentially in the sorted order of the keys in said index, positioning a second key of one pair as a first key of the next pair, means for comparing like-order bytes in a current pair of said keys for equality and inequality from a highest-ordered byte position to at least a highest-order unequal byte position, means for counting the equal bytes of said current pair until said highest-order unequal byte position is sensed, and registering a count signal from said means for counting as a component of a compressed key.
Claim 65
Dependent Claim
36 words
Compressed key generation means as defined in claim 60, further comprising: means for storing the count output signal from said means for counting at least through actuation of the means for counting during the next pair.
Claim 66
Dependent Claim
73 words
Compressed key generation means as defined in claim 61, including: means for changing the status of the next pair and current pair, of keys, to the current pair and prior pair of keys respectively, means for comparing the count output signals for said next pair against the count output signal for said prior pair to generate a shift-type signal, and means for generating a current compressed key in response to said shift-type signal.
Claim 67
Dependent Claim
88 words
Compressed key generation means as defined in claim 62, in which said shift-type signal indicates the count output signal for the current pair is greater than the count output signal for the prior pair, said generating means including: means for copying to a current compressed key recording area those bytes in one of the keys in the current pair from a byte position determined by the count output signal for said prior pair to a lower-order byte position determined by the count output signal for said current pair.
Claim 68
Dependent Claim
91 words
Compressed key generation means as defined in claim 63, in which said generating means includes: means for generating a factor byte-count code from a byte count in the range from the count output signal of said prior pair to one bYte greater than said signal, means for generating a key-byte count code equal to the number of bytes transferred to the compressed key recording area by said means for copying, and means for copying the factor byte-count code and the key-byte count code as fields within the current compressed key area.
Claim 69
Dependent Claim
52 words
Compressed key generation means as defined in claim 63, further including: means for inhibiting the selection in said one of the keys of its bytes having a higher-order than a byte position determined by the count output signal for said prior pair, whereby factor bytes are not included as compressed key bytes.
Claim 70
Dependent Claim
80 words
Compressed key generation means as defined in claim 62, in which said shift-type signal indicates the count output signal for the current pair of keys is less than or equal to the count output signal for the prior pair of keys, said generating means including: means for copying to a current compressed key recording area not more than one byte derived from one of the keys in the current pair at the highest-order unequal byte position for the current pair.
Claim 71
Dependent Claim
97 words
Compressed key generation means as defined in claim 66, in which said generating means includes means for generating a factor byte-count code from a byte count in the range from the count output signal of said prior pair through the count output signal of the current pair increased by one byte, means for generating a key-byte count code equal to the number of bytes transferred to the compressed key recording area by said means for copying, and means for recording the factor byte-count code and the key-byte count code as fields within the current compressed key area.
Claim 72
Dependent Claim
33 words
Compressed key generation means as defined in claim 64 in which said means for copying includes: means for recording both of said codes in a single byte of said current compressed key area.
Claim 73
Dependent Claim
30 words
Compressed key generation means as defined in claim 68, in which means for recording includes: means for recording said single byte at the beginning of said current compressed key area.
Claim 74
Dependent Claim
58 words
Compressed key generation means as defined in claim 68, in which said means for recording includes: means for generating an extender code when the factor byte-count code exceeds an allocated area for said byte-count code in said single byte, and means for recording the factor byte-count code in another predetermined byte location in the current compressed key field.
Claim 75
Dependent Claim
58 words
Compressed key generation means as defined in claim 68, in which said means for recording includes: means for generating an extender code when the key byte-count code exceeds an allocated area for said byte-count code in said single byte, and means for recording the key byte-count code in another predetermined byte location in the current compressed key field.
Claim 76
Dependent Claim
39 words
Compressed key generation means as defined in claim 70, in which said means for recording includes: means for recording the factor byte count code and the key byte-count code in different predetermined bytes in the current compressed key area.
Claim 77
Dependent Claim
33 words
Compressed key generation means as defined in claim 70, in which said means for recording includes: means for recording each of said codes before the key bytes in the current compressed key area.
Claim 78
Dependent Claim
62 words
Compressed key generation means as defined in claim 62, in which said shift-type signal indicates said count output signal for the current pair is equal to the count output signal for the prior pair, said means for generating including: means for copying to a current compressed key recording area a byte from one of said keys at its highest-order unequal byte position.
Claim 79
Dependent Claim
177 words
Compressed key generation means as defined in claim 62, in which said shift-type signal indicates said count output signal for the current pair of keys is equal to the count output signal for the prior pair of keys, including: means for sensing the existence or nonexistence of any key byte for the prioR compressed key obtained by said generating means to provide a prior key-byte existence signal, for controlling the following: means for copying to a current compressed key recording area from one of the keys in a current pair its byte at the highest-order unequal byte position, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, and means for bypassing the means for copying, in response to said prior key-byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby alternation in the existence and nonexistence of key bytes occurs among a succession of compressed keys resulting from a succession of pairs of keys providing equal shift-type signals.
Claim 80
Dependent Claim
59 words
Compressed key generation means as defined in claim 62, in which said shift-type signal indicates the count output signal for said current paid is less than the count output signal for said prior pair, said generating means further including means for inhibiting the copying by said copying means of any key byte to a current compress key recording area.
Claim 81
Dependent Claim
233 words
Compressed key generation means as defined in claim 62, in which said shift-type signal indicates the count output signal for the current pair is greater than the count output signal for the prior pair, said generating means further including means for sensing the existence or nonexistence of any key byte for the prior compress key obtained by said generating means to provide a prior key-byte existence signal, for controlling the following: means for copying to a current compressed key recording area those bytes in one of the keys in a current pair from a byte position specified by the count output signal for said prior pair through a lower-order byte position specified by the count output signal for said prior pair through a lower-order byte position specified by the count output signal for said current pair, in response to said prior key-byte existence single indicating the nonexistence of any key byte in the prior compressed key, means for copying to a current compressed key recording area those bytes in one of the keys in the current pair from a lower-order byte position next to that specified by the count output signal for said prior pair through a lower-order byte position specified by the count output signal for said current pair, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key.
Claim 82
Dependent Claim
65 words
Compressed key generation means as defined in claim 75, in which said shift-type signal indicates the count output signal for said current pair is less than the count output signal for said prior pair, said generating means including: means for generating a null factor signal, means for recording a null code in the current compressed key recording area in response to said null factor signal.
Claim 83
Dependent Claim
44 words
Compressed key generation means as defined in claim 63, including means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 84
Dependent Claim
67 words
Compressed key generation means as defined in claim 63, in which the copying means further includes means for selecting bytes only from the second key in said current pair being operated upon by said copying means, and means for recording a pointer address to information represented by said first key in said pair, whereby the current compressed key recording area receives the output of said copying means.
Claim 85
Dependent Claim
58 words
Compressed key generation means as defined in claim 66, including: means for generating a factor signal indicating not less than the value of said count output signal for the current pair of keys increased by one, and storing said factor signal into the current compressed key area, whereby a minimum factor field is available for left-shift-type compressed keys.
Claim 86
Dependent Claim
48 words
Compressed key generation means as defined in claim 76, including: means for generating a factor signal indicating not over the value of said count output signal for the prior pair of keys increased by one, and means for storing said factor signal into the current compressed key area.
Claim 87
Dependent Claim
143 words
Compressed key generation means as defined in claim 82, in which said means for generating further includes: means for sensing the existence or nonexistence of any key byte for the prior compressed key to provide a prior key-byte existence signal, for controlling the following: means for generating a factor signal specifying not over the value represented by said count output signal for the prior pair, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, means for generating a factor signal specifying not over the value represented by said count output signal for the prior pair increased by one, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby a maximum factor field is available for left-shift-type compressed keys.
Claim 88
Dependent Claim
135 words
Compressed key generation means as defined in claim 79, further including: means for sensing the existence or nonexistence of any key byte for an immediately prior compressed key, to provide a prior key-byte existence signal, for controlling the following: means for generating a factor signal specifying a value of a prior count output signal for the prior pair, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, means for generating a factor signal specifying not over the value represented by the count output signal of the prior pair increased by one, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby a factor field is provided for right-shift compressed keys.
Claim 89
Dependent Claim
39 words
Compressed key generation means as defined in claim 60, including: means for sensing the second key of said next pair for an end-of-index indication, and generating an end-of-index signal in response detecting said indication by said means for sensing.
Claim 90
Dependent Claim
62 words
Compressed key generation means as defined in claim 85, including: means for transferring a null code signal to a current compressed key recording area to represent an end-of-index compressed key, and means for recording in the current compressed key area a pointer address associated with the first key of said next pair for retrieving the date item represented by said first key.
Claim 91
Dependent Claim
68 words
Means for generating compressed keys using machine-readable keys in a source index representing different items of information, comprising means for accessing in a sorted sequence each key and its next key to obtain a pair of keys, in which the next key represents the upper-bound for said first key, means for generating a compressed key representation for said first key from the upper-bound represented by said next key.
Claim 92
Dependent Claim
68 words
Means for generating compressed keys using machine-readable keys in a source index representing different items of information, comprising means for accessing in a sorted sequence each key and its next key to obtain a pair of keys, in which the next key represents the upper-bound for said first key, means for generating a compressed key representation for said first key from the upper-bound represented by said next key.
Claim 93
Dependent Claim
31 words
Means for generating compressed keys as defined in claim 87, further comprising means for recording each compressed key representation in the sequence in which it is generated by said generating means.
Claim 94
Dependent Claim
37 words
Means for generating compressed keys as defined in claim 88, further comprising means for transferring a pointer address associated with said each key, and said means for recording also said pointer address following its compressed key representation.
Claim 95
Dependent Claim
34 words
A compressed key generation method as defined in claim 24, in which said machine-copying step includes the substep of: machine-recording both of said codes in a single byte of said current compressed key area.
Claim 96
Dependent Claim
40 words
A compressed key generation method as defined in claim 28, in which sAid machine-recording substep includes the substep of: machine-recording the factor byte count code and the key byte-count code in different predetermined bytes in the current compressed key area.
Claim 97
Dependent Claim
34 words
A compressed key generation method as defined in claim 28, in which said machine-recording substep includes the substep of: machine-recording each of said codes before the key bytes in the current compressed key area.
Claim 98
Dependent Claim
40 words
A compressed key generation method as defined in claim 23 including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 99
Dependent Claim
40 words
A compressed key generation method as defined in claim 31, including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 100
Dependent Claim
40 words
A compressed key generation method as defined in claim 32, including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 101
Dependent Claim
40 words
A compressed key generation method as defined in claim 33, including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 102
Dependent Claim
40 words
A compressed key generation method as defined in claim 34, including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 103
Dependent Claim
40 words
A compressed key generation method as defined in claim 35 including the further steps of machine-generating a key-byte-count code indicating the number of key bytes for the current compressed key, and machine-recording the key-byte-count code into the current compressed key.
Claim 104
Dependent Claim
68 words
A compressed key generation method as defined in claim 23 in which the generating step includes the substeps of machine-copying bytes only from the second key in said pair from byte locations defined by the respective preceding machine-copying step, and machine-recording a pointer address to information identified by said first key in said pair, whereby the current compressed key recording area receives the output of said machine-copying steps.
Claim 105
Dependent Claim
68 words
A compressed key generation method as defined in claim 31 in which the generating step includes the substeps of machine-copying bytes only from the second key in said pair from byte locations defined by the respective preceding machine-copying step, and machine-recording a pointer address to information identified by said first key in said pair, whereby the current compressed key recording area receives the output of said machine-copying steps.
Claim 106
Dependent Claim
68 words
A compressed key generation method as defined in claim 33 in which the generating step includes the substeps of machine-copying bytes only from the second key in said pair from byte locations defined by the respective preceding machine-copying step, and machine-recording a pointer address to information identified by said first key in said pair, whereby the current compressed key recording area receives the output of said machine-copying steps.
Claim 107
Dependent Claim
68 words
A compressed key generation method as defined in claim 34 in which the generating step includes the substeps of machine-copying bytes only from the second key in said pair from byte locations defined by the respective preceding machine-copying step, and machine-recording a pointer address to information identified by said first key in said pair, whereby the current compressed key recording area receives the ouTput of said machine-copying steps.
Claim 108
Dependent Claim
68 words
A compressed key generation method as defined in claim 35 in which the generating step includes the substeps of machine-copying bytes only from the second key in said pair from byte locations defined by the respective preceding machine-copying step, and machine-recording a pointer address to information identified by said first key in said pair, whereby the current compressed key recording area receives the output of said machine-copying steps.
Claim 109
Dependent Claim
58 words
A compressed key generation method as defined in claim 33, including the additional step: machine-generating a factor signal indicating not less than the value of said count output signal for the current pair increased by one, and storing said factor signal into the current compressed key area, whereby a minimum factor field is available for left-shift-type compressed keys.
Claim 110
Dependent Claim
133 words
A compressed key generation method as defined in claim 36, including the additional steps of; machine-sensing the existence or nonexistence of any key byte for the prior compressed key, to provide a prior key-byte existence signal, for controlling the following substeps: machine-generating a factor signal specifying the value of the prior count output signal for the prior pair, in response to said prior key-byte existence signal indicating the nonexistence of any key byte in the prior compressed key, machine-generating a factor signal specifying not over the value represented by the count output signal of the prior pair increased by one, in response to said prior key byte existence signal indicating the existence of at least one key byte in the prior compressed key, whereby a factor field is provided for right-shift compressed keys.
Claim 111
Dependent Claim
33 words
Compressed key generation means as defined in claim 67 in which said means for copying includes: means for recording both of said codes in a single byte of said current compressed key area.
Claim 112
Dependent Claim
39 words
Compressed key generation means as defined in claim 71, in which said means for recording includes: means for recording the factor byte count code and the key byte-count code in different predetermined bytes in the current compressed key area.
Claim 113
Dependent Claim
33 words
Compressed key generation means as defined in claim 71, in which said means for recording includes: means for recording each of said codes before the key bytes in the current compressed key area.
Claim 114
Dependent Claim
44 words
Compressed key generation means as defined in claim 66, including means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 115
Dependent Claim
44 words
Compressed key generation means as defined in claim 74, including means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 116
Dependent Claim
44 words
Compressed key generation means as defined in claim 75, including means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 117
Dependent Claim
44 words
Compressed key generation means as defined in claim 76, including means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 118
Dependent Claim
44 words
Compressed key generation means as defined in claim 77, including means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 119
Dependent Claim
44 words
Compressed key generation means as defined in claim 78, inclUding means for generating a key-byte-count code indicating the number of key bytes copied by said copying means for the current compressed key, and means for recording the key-byte-count code into the current compressed key.
Claim 120
Dependent Claim
67 words
Compressed key generation means as defined in claim 66, in which the copying means further includes means for selecting bytes only from the second key in said current pair being operated upon by said copying means, and means for recording a pointer address to information represented by said first key in said pair, whereby the current compressed key recording area receives the output of said copying means.
Claim 121
Dependent Claim
63 words
Compressed key generation means as defined in claim 74, in which the copying means further includes means for selecting bytes only from the second key in said current pair being operated upon by said copying means, and means for recording a pointer address to information represented by said pair, whereby the current compressed key recording area receives the output of said copying means.
Claim 122
Dependent Claim
67 words
Compressed key generation means as defined in claim 76, in which the copying means further includes means for selecting bytes only from the second key in said current pair being operated upon by said copying means, and means for recording a pointer address to information represented by said first key in said pair, whereby the current compressed key recording area receives the output of said copying means.
Claim 123
Dependent Claim
67 words
Compressed key generation means as defined in claim 77, in which the copying means further includes means for selecting bytes only from the second key in said current pair being operated upon by said copying means, and means for recording a pointer address to information represented by said first key in said pair, whereby the current compressed key recording area receives the output of said copying means.
Claim 124
Dependent Claim
67 words
Compressed key generation means as defined in claim 78, in which the copying means further includes means for selecting bytes only from the second key in said current pair being operated upon by said copying means, and means for recording a pointer address to information represented by said first key in said pair, whereby the current compressed key recording area receives the output of said copying means.
Claim 125
Dependent Claim
58 words
Compressed key generation means as defined in claim 76, including: means for generating a factor signal indicating not less than the value of said count output signal for the current pair of keys increased by one, and storing said factor signal into the current compressed key area, whereby a minimum factor field if available for left-shift-type compressed keys.
References Cited (Backward Citations)
US3275989A
Cited
US3185823A
Cited
US3185824A
Cited
US3225333A
Cited
US3223982A
Cited
US3237170A
Cited
US3289169A
Cited
US3278907A
Cited
US3490690A
Cited
US3413611A
Cited
US3422403A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-07-12 | 1975-01-11 | 1975-07-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-07-12 | 1979-01-11 | 1979-07-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-07-12 | 1983-01-11 | 1983-07-13 | $7700.00 | Window Closed / Lapsed |