US5371499A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression using hashing
Assignee: Intersecting Concepts Inc
•
Filing: 1992-10-23
•
Granted: 1994-12-06
•
Expires: 2012-10-23
Abstract
Abstract Compressing a sequence of characters drawn from an alphabet uses string substitution with no a priori information. An input data block is processed into an output data block comprised of variable length incompressible data sections and variable length compressed token sections. Multiple hash tables are used based on different subblock sizes for string matching, and this improves the compression ratio and rate of compression. The plurality of uses of the multiple hash tables allows for selection of an appropriate compression data rate and/or compression factor in relation to the input data. Using multiple hashing tables with a recoverable hashing method further improves compression ratio and compression rate. Each incompressible data section contains means to distinguish it from compressed token sections.
Inventors
- 👤 Mark D. Graybill
- 👤 Donald R. Harris
- 👤 Dean K. Gibson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 08:55
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; G; G06; G06T; G06T9/00; G06T9/005; H03M7/3086
Claims Analysis
Total Claims: 111
Claim 1
Independent Claim
172 words
A method of compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, and (d) if a hash match occurs in at least one hash table, outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data.
Claim 2
Independent Claim
172 words
A method of compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, and (d) if a hash match occurs in at least one hash table, outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data.
Claim 3
Dependent Claim
50 words
A method as claimed in claim 1 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 4
Dependent Claim
39 words
A method as claimed in claim 1 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 5
Dependent Claim
57 words
A method as claimed in claim 1 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 6
Dependent Claim
35 words
A method as claimed in claim 1 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 7
Independent Claim
197 words
A method of compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) determining at least part of a hash key for one of the hash tables from the hash key of another of the hash tables.
Claim 8
Independent Claim
197 words
A method of compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) determining at least part of a hash key for one of the hash tables from the hash key of another of the hash tables.
Claim 9
Dependent Claim
60 words
A method as claimed in claim 6 wherein the hashed keys for a first hash table are determined on a first data subblock size and wherein a second hash table contains keys obtained from the second subblock size, and wherein the hash keys for the first subblock size are obtained at least in part from the second hash table keys.
Claim 10
Dependent Claim
50 words
A method as claimed in claim 6 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 11
Dependent Claim
39 words
A method as claimed in claim 6 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 12
Dependent Claim
57 words
A method as claimed in claim 6 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 13
Dependent Claim
35 words
A method as claimed in claim 6 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 14
Independent Claim
221 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) if a hash match occurs in at least one hash table, outputting the subsequent occurrence of the string as compressed data, such that when a hash match occurs in a table related to a larger subblock size and a hash match occurs in a table related to a smaller subblock size, the hash match in the hash table of the larger subblock size is selected for the compressed data output.
Claim 15
Independent Claim
221 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) if a hash match occurs in at least one hash table, outputting the subsequent occurrence of the string as compressed data, such that when a hash match occurs in a table related to a larger subblock size and a hash match occurs in a table related to a smaller subblock size, the hash match in the hash table of the larger subblock size is selected for the compressed data output.
Claim 16
Dependent Claim
50 words
A method as claimed in claim 12 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 17
Dependent Claim
39 words
A method as claimed in claim 12 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 18
Dependent Claim
57 words
A method as claimed in claim 12 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 19
Dependent Claim
35 words
A method as claimed in claim 12 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 20
Independent Claim
210 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) if a hash match occurs in a hash table, outputting the subsequent occurrence of the string as compressed data, such that where a hash match occurs for more than one hash table, determining the longer match length of the string of input data for each respective hash table, and outputting the longer match length as the compressed data output.
Claim 21
Independent Claim
210 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) if a hash match occurs in a hash table, outputting the subsequent occurrence of the string as compressed data, such that where a hash match occurs for more than one hash table, determining the longer match length of the string of input data for each respective hash table, and outputting the longer match length as the compressed data output.
Claim 22
Independent Claim
242 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, (e) if a hash match occurs in a hash table, outputting the subsequent occurrence of the string as compressed data, such that where a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, the hash match of the larger subblock size is selected as the compressed data output, and (f) wherein the hash keys for the larger subblock size are computed using at least part of the value of hash keys from the smaller subblock size.
Claim 23
Independent Claim
242 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, (e) if a hash match occurs in a hash table, outputting the subsequent occurrence of the string as compressed data, such that where a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, the hash match of the larger subblock size is selected as the compressed data output, and (f) wherein the hash keys for the larger subblock size are computed using at least part of the value of hash keys from the smaller subblock size.
Claim 24
Independent Claim
247 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, (e) wherein when a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, selecting the hash match of the larger subblock size as the compressed data output, and (f) if a hash match occurs in a hash table, outputting the subsequent occurrence of the string as compressed data, such that when a larger subblock size does not match on a minimum match length, selecting the smaller subblock size hash value if such smaller subblock value matches for its respective minimum length.
Claim 25
Independent Claim
247 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, (e) wherein when a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, selecting the hash match of the larger subblock size as the compressed data output, and (f) if a hash match occurs in a hash table, outputting the subsequent occurrence of the string as compressed data, such that when a larger subblock size does not match on a minimum match length, selecting the smaller subblock size hash value if such smaller subblock value matches for its respective minimum length.
Claim 26
Dependent Claim
50 words
A method as claimed in claim 17 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 27
Dependent Claim
39 words
A method as claimed in claim 17 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 28
Dependent Claim
57 words
A method as claimed in claim 17 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 29
Dependent Claim
35 words
A method as claimed in claim 17 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 30
Dependent Claim
50 words
A method as claimed in claim 18 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 31
Dependent Claim
39 words
A method as claimed in claim 18 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 32
Dependent Claim
57 words
A method as claimed in claim 18 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 33
Dependent Claim
35 words
A method as claimed in claim 18 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 34
Dependent Claim
50 words
A method as claimed in claim 19 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 35
Dependent Claim
39 words
A method as claimed in claim 19 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 36
Dependent Claim
57 words
A method as claimed in claim 19 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 37
Dependent Claim
35 words
A method as claimed in claim 19 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 38
Independent Claim
199 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, compressing and outputting the subsequent occurrence of the string in accordance with the hash match, and if a hash miss occurs, outputting such data as uncompressed data, and (e) when a hash miss occurs in the hash tables, hashing is effected for at least one of the hash tables by employing a hash key from the hash miss whereby a reduced number of operations is required for hashing.
Claim 39
Independent Claim
199 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, compressing and outputting the subsequent occurrence of the string in accordance with the hash match, and if a hash miss occurs, outputting such data as uncompressed data, and (e) when a hash miss occurs in the hash tables, hashing is effected for at least one of the hash tables by employing a hash key from the hash miss whereby a reduced number of operations is required for hashing.
Claim 40
Dependent Claim
39 words
A method as claimed in claim 32 wherein a value of the hash key from the hashing for one hash table is transferred at least in part into a value of the hash key for the second hash table.
Claim 41
Dependent Claim
32 words
A method as claimed in claim 32 wherein a value of hash key from the hash miss is used for obtaining a value of the hashing key from the same hash table.
Claim 42
Dependent Claim
50 words
A method as claimed in claim 32 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 43
Dependent Claim
39 words
A method as claimed in claim 32 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 44
Dependent Claim
57 words
A method as claimed in claim 32 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 45
Dependent Claim
35 words
A method as claimed in claim 32 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 46
Dependent Claim
50 words
A method as claimed in claim 33 wherein the hashed information in relation to the input data is stored in at east one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 47
Dependent Claim
39 words
A method as claimed in claim 33 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 48
Dependent Claim
57 words
A method as claimed in claim 33 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 49
Dependent Claim
35 words
A method as claimed in claim 33 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 50
Dependent Claim
45 words
A method as claimed in claim 32 wherein when a hash miss occurs, the hash key of the hash miss is used in the subsequent hashing by the step of at least one computation being a simple shift, or a computation being an exclusive OR.
Claim 51
Independent Claim
231 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) if a hash match occurs outputting the subsequent occurrence of the string as compressed data, such that when a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, selectively applying the hash match from either the larger subblock size, thereby to obtain a higher compression rate or applying the longest match of both the hash matches thereby to obtain a high compression ratio.
Claim 52
Independent Claim
231 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match for each of the subblocks does not occur in any hash table, outputting at least the first character of an input subblock as uncompressed data, and (e) if a hash match occurs outputting the subsequent occurrence of the string as compressed data, such that when a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, selectively applying the hash match from either the larger subblock size, thereby to obtain a higher compression rate or applying the longest match of both the hash matches thereby to obtain a high compression ratio.
Claim 53
Dependent Claim
50 words
A method as claimed in claim 44 wherein the hashed information in relation to the input data is stored in at least one of the hash tables and is selectively only a source pointer to prior hashed subblocks or the source pointer representative of the hashed subblocks and additional data.
Claim 54
Dependent Claim
39 words
A method as claimed in claim 44 wherein selectively either one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks, or a source pointer to prior hashed subblocks and additional data.
Claim 55
Dependent Claim
57 words
A method as claimed in claim 44 wherein the hashed information in the hash entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed information being directed by a hash key to the hash table entry containing information representative of prior hashed subblocks.
Claim 56
Dependent Claim
35 words
A method as claimed in claim 44 wherein hashing is effected on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 57
Independent Claim
170 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining a hash table for a data subblock size, the hash table having hash keys, (b) hashing a string of input characters of the input data for the data subblock size and entering the hash information into hash table entries addressed by hash keys, (c) hashing, for the subblock size, subsequent strings of data and searching for a match of prior strings related to the hashed information addressed by the hash keys in the hash table, (d) if a hash match occurs, compressing and outputting the subsequent occurrence of the string as compressed data, and if a hash miss occurs, outputting at least the first character of the subblock as uncompressed data, and (e) when a hash miss occurs in the hash table, hashing is effected for a next key for the hash table by employing the key from the hash miss whereby a reduced number of operations is required for hashing.
Claim 58
Independent Claim
170 words
A method of compressing a stream of input data into a compressed string of output data comprising: (a) maintaining a hash table for a data subblock size, the hash table having hash keys, (b) hashing a string of input characters of the input data for the data subblock size and entering the hash information into hash table entries addressed by hash keys, (c) hashing, for the subblock size, subsequent strings of data and searching for a match of prior strings related to the hashed information addressed by the hash keys in the hash table, (d) if a hash match occurs, compressing and outputting the subsequent occurrence of the string as compressed data, and if a hash miss occurs, outputting at least the first character of the subblock as uncompressed data, and (e) when a hash miss occurs in the hash table, hashing is effected for a next key for the hash table by employing the key from the hash miss whereby a reduced number of operations is required for hashing.
Claim 59
Dependent Claim
38 words
A method as claimed in claim 49 including maintaining multiple hash tables, each for a different subblock size and applying the key from a hash miss of each respective table to the next key of a hash table.
Claim 60
Dependent Claim
181 words
Apparatus for compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and means for using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, and (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data.
Claim 61
Dependent Claim
181 words
Apparatus for compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and means for using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, and (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data.
Claim 62
Dependent Claim
36 words
Apparatus as claimed in claim 51 including means in the hash table for storing selectively only a source pointer to prior hashed subblocks or the source pointer representative of the prior hashed subblocks and additional information.
Claim 63
Dependent Claim
39 words
Apparatus as claimed in claim 51 including means whereby selectively one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks or a source pointer to prior hashed subblocks and additional data.
Claim 64
Dependent Claim
52 words
Apparatus as claimed in claim 51 including means whereby hashed information in the hash entries in the hash tables are selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed data being directed by a key to the hash table entry containing information representative of prior hashed subblocks.
Claim 65
Dependent Claim
35 words
Apparatus as claimed in claim 51 including means for effecting hashing on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 66
Dependent Claim
208 words
Apparatus for compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and means for using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) means for determining at least part of hash key for one of the hash tables from the hash key of the second of the hash tables.
Claim 67
Dependent Claim
208 words
Apparatus for compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and means for using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) means for determining at least part of hash key for one of the hash tables from the hash key of the second of the hash tables.
Claim 68
Dependent Claim
58 words
Apparatus as claimed in claim 56 including means wherein the hash key for a first hash table is determined on a first data subblock size relative to hash keys for a second hash table, and means for obtaining the hashed keys for the first subblock size at least in part from data from the second hash table keys.
Claim 69
Dependent Claim
205 words
Apparatus for compressing a steam of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and means for using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) means, when a hatch match occurs for different tables, for selecting a larger subblock size for the compressed data output of step (d).
Claim 70
Dependent Claim
205 words
Apparatus for compressing a steam of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and means for using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) means, when a hatch match occurs for different tables, for selecting a larger subblock size for the compressed data output of step (d).
Claim 71
Dependent Claim
36 words
Apparatus as claimed in claim 58 including means in the hash table for storing selectively only a source pointer to prior hashed subblocks or the source pointer representative of the prior hashed subblocks and additional information.
Claim 72
Dependent Claim
39 words
Apparatus as claimed in claim 58 including means whereby selectively one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks or a source pointer to prior hashed subblocks and additional data.
Claim 73
Dependent Claim
35 words
Apparatus as claimed in claim 58 including means for effecting hashing on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 74
Dependent Claim
228 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) wherein where a hash match occurs for more than one of the hash tables, means for determining the longer match length of the string of input data for each respective hash table, and means for outputting the longer match length as the compressed data output of step (d).
Claim 75
Dependent Claim
228 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) wherein where a hash match occurs for more than one of the hash tables, means for determining the longer match length of the string of input data for each respective hash table, and means for outputting the longer match length as the compressed data output of step (d).
Claim 76
Dependent Claim
267 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, (e) wherein where a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, means for selecting the hash match of the larger subblock size for the compressed data output of step (d), and (f) wherein when the one subblock size is larger than the second subblock size, means for computing hash keys for the larger subblock size, using at least part of the value of hash keys from the smaller subblock size.
Claim 77
Dependent Claim
267 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, (e) wherein where a hash match occurs in a table related to a larger subblock size relative to a hash match in a table related to a smaller subblock size, means for selecting the hash match of the larger subblock size for the compressed data output of step (d), and (f) wherein when the one subblock size is larger than the second subblock size, means for computing hash keys for the larger subblock size, using at least part of the value of hash keys from the smaller subblock size.
Claim 78
Dependent Claim
209 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) wherein when a larger subblock size does not match on a minimum match length, means for selecting the smaller subblock size hash match if such smaller subblock value matches.
Claim 79
Dependent Claim
209 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) wherein when a larger subblock size does not match on a minimum match length, means for selecting the smaller subblock size hash match if such smaller subblock value matches.
Claim 80
Dependent Claim
36 words
Apparatus as claimed in claim 62 including means in the hash table for storing selectively only a source pointer to prior hashed subblocks or the source pointer representative of the prior hashed subblocks and additional information.
Claim 81
Dependent Claim
39 words
Apparatus as claimed in claim 62 including means whereby selectively one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks or a source pointer to prior hashed subblocks and additional data.
Claim 82
Dependent Claim
52 words
Apparatus as claimed in claim 62 including means whereby hashed information in the hash entries in the hash tables are selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed data being directed by a key to the hash table entry containing information representative of prior hashed subblocks.
Claim 83
Dependent Claim
35 words
Apparatus as claimed in claim 62 including means for effecting hashing on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 84
Dependent Claim
36 words
Apparatus as claimed in claim 63 including means in the hash table for storing selectively only a source pointer to prior hashed subblocks or the source pointer representative of the prior hashed subblocks and additional information.
Claim 85
Dependent Claim
39 words
Apparatus as claimed in claim 63 including means whereby selectively one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks or a source pointer to prior hashed subblocks and additional data.
Claim 86
Dependent Claim
52 words
Apparatus as claimed in claim 63 including means whereby hashed information in the hash entries in the hash tables are selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hashed data being directed by a key to the hash table entry containing information representative of prior hashed subblocks.
Claim 87
Dependent Claim
35 words
Apparatus as claimed in claim 63 including means for effecting hashing on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 88
Dependent Claim
224 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) when a hash miss occurs in at least one of the hash tables, means for effecting hashing for an increased subblock size for the hash table, by employing hash keys from the hash miss whereby a reduced number of operations is required for hashing.
Claim 89
Dependent Claim
224 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) when a hash miss occurs in at least one of the hash tables, means for effecting hashing for an increased subblock size for the hash table, by employing hash keys from the hash miss whereby a reduced number of operations is required for hashing.
Claim 90
Dependent Claim
38 words
Apparatus as claimed in claim 73 including means for transferring a value of hash key from the hashing for one hash table at least in part into the value of a hash key for the second hash table.
Claim 91
Dependent Claim
35 words
Apparatus as claimed in claim 73 including means for obtaining a value of a hashing key from the hash miss for use for obtaining the value of the hash key from the same hash table.
Claim 92
Dependent Claim
36 words
Apparatus as claimed in claim 73 including means in the hash table for storing selectively only a source pointer to prior hashed data, or the source pointer representative of the prior hashed data and additional information.
Claim 93
Dependent Claim
38 words
Apparatus as claimed in claim 73 including means whereby selectively one or both of the hash tables contain selectively only a source pointer to prior hashed data, or a source pointer to prior hashed data and additional information.
Claim 94
Dependent Claim
62 words
Apparatus as claimed in claim 73 wherein information stored in entries in the hash tables and wherein the information in the entries in at least one of the hash tables is selectively unconditionally replaced, or conditionally replaced or removed on the occurrence of subsequent hash keys being directed to an entry in the hash table containing information representative of prior hashed data.
Claim 95
Dependent Claim
227 words
Apparatus for compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) wherein, when a hash match occurs in a table related to a larger subblock size relative to a hash match and a table related to a smaller subblock size, means for selectively applying the hash match from either the larger subblock size or the smaller subblock size.
Claim 96
Dependent Claim
227 words
Apparatus for compressing a stream of input data into a compressed stream of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs in at least one hash table, means for outputting the subsequent occurrence of the string as compressed data, and if a hash match for each of the subblocks does not occur in any hash table, means for outputting at least the first character of an input subblock as uncompressed data, and (e) wherein, when a hash match occurs in a table related to a larger subblock size relative to a hash match and a table related to a smaller subblock size, means for selectively applying the hash match from either the larger subblock size or the smaller subblock size.
Claim 97
Dependent Claim
36 words
Apparatus as claimed in claim 79 including means in the hash table for storing selectively only a source pointer to prior hashed subblocks or the source pointer representative of the prior hashed subblocks and additional information.
Claim 98
Dependent Claim
39 words
Apparatus as claimed in claim 79 including means whereby selectively one or multiple of the hash table entries contain selectively only a source pointer to prior hashed subblocks or a source pointer to prior hashed subblocks and additional data.
Claim 99
Dependent Claim
35 words
Apparatus as claimed in claim 79 including means for effecting hashing on a data subblock size of three for a first hash table and a data subblock size of four for a second hash table.
Claim 100
Dependent Claim
43 words
Apparatus as claimed in claim 79 wherein when a hash miss occurs, the key of the hash miss is used in the subsequent hashing by the step of at least one computation being a simple shift, or a computation being an exclusive OR.
Claim 101
Dependent Claim
197 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs, means for compressing and outputting the subsequent occurrence of the string as compressed data, and if a hash miss occurs, means for outputting such data as uncompressed data, and (e) when a hash miss occurs in the hash table, means for effecting hashing for a next key for the hash table, by employing hash keys from the hash miss whereby a reduced number of operations is required for hashing.
Claim 102
Dependent Claim
197 words
Apparatus for compressing a stream of input data into a compressed string of output data comprising: (a) maintaining multiple hash tables, each respectively for a different data subblock size, and each hash table having entries having respective hash keys, (b) means for hashing a string of input characters of the input data for each of the different data subblock sizes to obtain the hash keys, and using these hash keys to address hash table entries containing hash information to facilitate location of string matches, (c) means for hashing, for each of the subblock sizes, subsequent strings of data and searching for a match of prior strings related to the information addressed by hash keys in at least one of the hashing tables, (d) if a hash match occurs, means for compressing and outputting the subsequent occurrence of the string as compressed data, and if a hash miss occurs, means for outputting such data as uncompressed data, and (e) when a hash miss occurs in the hash table, means for effecting hashing for a next key for the hash table, by employing hash keys from the hash miss whereby a reduced number of operations is required for hashing.
Claim 103
Dependent Claim
41 words
Apparatus as claimed in claim 84 including means for maintaining multiple hash tables, each for a different subblock size and means for applying the key from a hash miss of each respective table to the next key of a hash table.
Claim 104
Dependent Claim
103 words
A generator for hashing a stream of input data comprising: (a) interfaces to multiple hash tables designating a different data subblock size for each hash table, (b) means for hashing strings of input characters of the input data for each of the different data subblock sizes to produce hash keys, and means for entering the hash information into hash entries of the hash table addressed by hash keys, (c) means for producing multiple hash keys for each of the subblock sizes, and (d) means for producing a hash key for a first subblock size from a hash key of a second subblock size.
Claim 105
Dependent Claim
103 words
A generator for hashing a stream of input data comprising: (a) interfaces to multiple hash tables designating a different data subblock size for each hash table, (b) means for hashing strings of input characters of the input data for each of the different data subblock sizes to produce hash keys, and means for entering the hash information into hash entries of the hash table addressed by hash keys, (c) means for producing multiple hash keys for each of the subblock sizes, and (d) means for producing a hash key for a first subblock size from a hash key of a second subblock size.
Claim 106
Dependent Claim
38 words
A hash generator as claimed in claim 86 wherein there are two hash tables, and wherein a smaller subblock size is designated for a first hash table and a larger subblock size designated for a second hash table.
Claim 107
Dependent Claim
25 words
A generator as claimed in claim 86 comprising means for producing hash keys for a larger subblock size from hash keys of smaller subblock size.
Claim 108
Dependent Claim
90 words
A generator for hashing a stream of data comprising: (a) interface means to a hash table with a designated input data subblock size for the hash table, and the hash table having hash keys, (b) means for hashing strings of input characters of the input data for each input data subblocks, and means for entering the hashed information into hash entries of the hash table addressed by the hash keys, and (c) means for producing a next hash key from a prior hash key on occurrence of a hash miss.
Claim 109
Dependent Claim
90 words
A generator for hashing a stream of data comprising: (a) interface means to a hash table with a designated input data subblock size for the hash table, and the hash table having hash keys, (b) means for hashing strings of input characters of the input data for each input data subblocks, and means for entering the hashed information into hash entries of the hash table addressed by the hash keys, and (c) means for producing a next hash key from a prior hash key on occurrence of a hash miss.
Claim 110
Dependent Claim
42 words
A generator as claimed in claim 89 wherein there are interface means respectively to multiple hash tables, and wherein a first subblock size is designated for a first hash table and a different subblock size is designated for a second hash table.
Claim 111
Dependent Claim
40 words
A generator as claimed in claim 89 wherein there are at least two different data subblock sizes and including means for providing a hash key for a first subblock size from a prior hash key of a second subblock size.
References Cited (Backward Citations)
US3914586A
Cited
US4021782A
Cited
US3976844A
Cited
US4054951A
Cited
US4087788A
Cited
US4295124A
Cited
US4412306A
Cited
US4464650A
Cited
US4560976A
Cited
GB2152253A
Cited
US4491934A
Cited
US4538240A
Cited
US4677649A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4586027A
Cited
US4588985A
Cited
US4612532A
Cited
US4758899A
Cited
US4701745A
Cited
US4682150A
Cited
US4809350A
Cited
US4730348A
Cited
US4872009A
Cited
US4853696A
Cited
US4876541A
Cited
US4906991A
Cited
US4899147A
Cited
US4961139A
Cited
US5032987A
Cited
US5129074A
Cited
US5010553A
Cited
US5003307A
Cited
US5016009A
Cited
US4979039A
Cited
US4929946A
Cited
US4988998A
Cited
US5049881A
Cited
US5132992A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-12-05 | 1998-06-06 | 1998-12-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-05 | 2002-06-06 | 2002-12-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-05 | 2006-06-06 | 2006-12-06 | $7700.00 | Window Closed / Lapsed |