Order preserving data translation

Details Order preserving data translation Order preserving data translation

1994-06-10

1996-12-17

Gaffin, Jeffrey A.

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

341 67, 341106, 341 50, 3644623, H03M 730

Patent

active

055857930

ABSTRACT:
In a computer system, input strings to be translated are composed of characters selected from a first alphabet. According to a predetermined criterion, a list of sub-strings is selected from the input strings to form entries in a dictionary. The entries of the dictionary are arranged according to a collating order of the first alphabet. An interval including the sub-strings of the input strings is partitioned into an all-inclusive and disjoint set of ranges. The sub-strings of the interval are arranged according to the collating order of the first alphabet, and each sub-strings of a particular range has a common prefix, the common prefix selected from the list of sub-strings. A unique encoding is assigned to each common prefix, the corresponding set of unique encodings composed of characters selected from a second alphabet. The input strings are parsed, one at the time, into a plurality of tokens, each token corresponding to a sub-string selected from the dictionary. In an output string, there is placed for each token, a corresponding one of the set of unique encodings.

REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 4677550 (1987-06-01), Ferguson
patent: 5270712 (1993-12-01), Iyer et al.
patent: 5325091 (1994-06-01), Kaplan et al.
patent: 5394143 (1995-02-01), Murray et al.
patent: 5406279 (1995-04-01), Anderson et al.
patent: 5410671 (1995-04-01), Elgamal et al.
patent: 5525982 (1996-06-01), Cheng et al.
Knuth, D., "The Art Of Computer Programming", Second Edition, vol. 1, Fundamental Algorithms, pp. 402-404.
Knuth, D., "The Art Of Computer Programming", vol. 3, Sorting and Searching, pp. 439-445.
Blasgen, M., et al, "An Encoding Method For Multifield Sorting and Indexing", Association for Computing Machinery, Inc., Dec. 1976.
Held, G., "Data Compression", Chapters 2 and 3, 3rd Edition.
Bayer, R., et al, "Prefix B-Trees", ACM Transactions On Database Systems, vol. 2, No. 1, Mar. 1977.
Zandi, A., et al, "Sort Order Preserving Data Compression for Extended Alphabets", Data Compression Conference, 1993 IEEE, pp. 330-339.
Ziv, J., et al, "Compression of Individual Sequences Via Variable-Rate Coding", IEEE Transactions on Information Theory vol. IT-24, No. 5, Sep. 1978, pp. 530-536.
Ziv, J., et al, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions On Information Theory, vol., IT-23, No. 3, May 1977, pp. 337-343.

Affiliated with

Also associated with

Rating

Order preserving data translation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Order preserving data translation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Order preserving data translation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1994590