Coded data generation or conversion – Digital code to digital code converters – To or from bit count codes
Patent
1993-06-30
1995-02-28
Williams, Howard L.
Coded data generation or conversion
Digital code to digital code converters
To or from bit count codes
341 50, 364DIG2, 3649623, 3649622, 395425, H03M 746
Patent
active
053941438
ABSTRACT:
The invention is a compression method which provides the advantages of run-length compression while preserving the natural collating order of the data. The method of the invention replaces sequential repetitions of a target pattern beyond a threshold value followed by a single number which encodes both the repetition count and the collating relationship between the target pattern and the pattern which follows it in the uncollated sequence. In the preferred embodiment of the invention, the code is preceded by at least one repetition of the pattern. In the preferred embodiment of the invention, the numerical code is set as the difference between the run count and the threshold count if the following pattern is less than the target pattern, or if there is no following pattern. If the following pattern is greater than the compression sequence, the code is set as a predetermined number, preferably the maximum binary value of the sequence length, minus the difference between the run count and the threshold count.
REFERENCES:
patent: 4677550 (1987-06-01), Ferguson
patent: 4843389 (1989-06-01), Lisle et al.
patent: 4945475 (1990-07-01), Bruffey et al.
patent: 5001477 (1991-03-01), Hicks et al.
patent: 5270712 (1993-12-01), Iyer et al.
Hicks, Compressing Sort Keys While Maintaining Sort Sequence, IBM Technical Disclosure Bulletin vol. 26 No. 1, Jun. 1983, pp. 388-391.
Rudolf Bayer & Karl Unterauer "Prefix B-Trees," ACM Transactions on Database Systems, vol. 2, No. 1, Mar. 1977.
M. Blasgen, R. Casey, & K. Eswaran "An Encoding Method for Multi-Field Sorting and Indexing," IBM Research Laboratory, San Jose, California, RJ 1753 (25561), Mar. 30, 1976.
Donald E. Knuth "Hu-Tucker" encoding in, Art of Computer Programming, vol. 3, p. 444 in Addison-Wesley 1973 edition.
Gilbert Held "Data Compression," Chapts. 2, 3, 3rd Edition.
Antoshenkov Gennady
Murray James C.
Digital Equipment Corporation
Williams Howard L.
Young Barry N.
LandOfFree
Run-length compression of index keys does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Run-length compression of index keys, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Run-length compression of index keys will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-851055