US4796003A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compaction
Assignee: AT&T Inc
•
Filing: 1984-06-28
•
Granted: 1989-01-03
•
Expires: 2004-06-28
Abstract
Abstract An algorithm or technique for compacting (and expanding) digital data is disclosed in which the data is broken up into words or lexemes. The words are entered into a push-down list as they are received and, if already on the list, a list location identifier is transmitted and the word moved to the top of the list. The last word on the list falls off the list when a new word is entered at the top and thereafter is treated as a new word. The data expander maintains identical lists and substitutes the data word for the list location code when received. Both hardware and software implementations are disclosed.
Inventors
- 👤 Jon L. Bentley
- 👤 Daniel D. K. Sleator
- 👤 Robert E. Tarjan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 14:07
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; G; G11; G11B; G11B20/00; G11B20/00007
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
139 words
A system for compacting a sequence of multicharacter data words, comprising: input means for receiving said sequence of words, means for outputting a compacted sequence of said words, a single fixed length push-down storage means, means for determining in order if each word of the sequence is presently stored in the push-down storage means, means responsive to the determining means for generating a location code corresponding to the present address, if any, of a word in the push-down storage means, means for placing each word of said sequence nearer to the top of said push-down storage means than its present location, if any, in the push-down storage means, and means for substituting for a word in the outputted character sequence a said generated location code, wherein the location code contains less characters on average than the corresponding data word.
Claim 2
Independent Claim
139 words
A system for compacting a sequence of multicharacter data words, comprising: input means for receiving said sequence of words, means for outputting a compacted sequence of said words, a single fixed length push-down storage means, means for determining in order if each word of the sequence is presently stored in the push-down storage means, means responsive to the determining means for generating a location code corresponding to the present address, if any, of a word in the push-down storage means, means for placing each word of said sequence nearer to the top of said push-down storage means than its present location, if any, in the push-down storage means, and means for substituting for a word in the outputted character sequence a said generated location code, wherein the location code contains less characters on average than the corresponding data word.
Claim 3
Dependent Claim
14 words
The system according to claim 1 comprising a digital computer and a computer program.
Claim 4
Dependent Claim
16 words
The system according to claim 1 or 2 wherein said location codes comprise arbitrary prefix codes.
Claim 5
Dependent Claim
16 words
The system according to claim 1 or 2 wherein said location codes comprises fixed length addresses.
Claim 6
Dependent Claim
27 words
The system according to claim 1 wherein said push-down storage means comprises means for placing said each new word at the top of said push-down storage means.
Claim 7
Dependent Claim
39 words
The system of claim 1 wherein the location code generating means further comprises random access storage means for storing the location codes at addresses thereof corresponding to the storage addresses of the corresponding words in the push-down storage means.
Claim 8
Independent Claim
92 words
The method of compacting a stream of digital data bits comprising the steps of partitioning said stream into a plurality of lexemes, storing each lexeme in a first-in, first-out list nearer to the top of said list than its present position, if any, in the list, and for each lexeme already on the list, substituting a location code for the lexeme, wherein the length of the location codes are on average less than the length of the lexemes, or selecting the lexeme itself for lexemes not on said list, for further utilization.
Claim 9
Independent Claim
92 words
The method of compacting a stream of digital data bits comprising the steps of partitioning said stream into a plurality of lexemes, storing each lexeme in a first-in, first-out list nearer to the top of said list than its present position, if any, in the list, and for each lexeme already on the list, substituting a location code for the lexeme, wherein the length of the location codes are on average less than the length of the lexemes, or selecting the lexeme itself for lexemes not on said list, for further utilization.
Claim 10
Dependent Claim
12 words
The method of claim 7 as performed in special purpose circuit hardware.
Claim 11
Dependent Claim
12 words
The method of claim 7 as performed in a programmed digital computer.
Claim 12
Independent Claim
23 words
The method of claims 7, 8 or 9 further comprising the step of establishing variable length arbitrary prefix codes as said location codes.
Claim 13
Independent Claim
18 words
The method of claims 7, 8 or 9 further comprising the step of establishing fixed length location codes.
Claim 14
Dependent Claim
33 words
The method of claim 7 further comprising the steps of moving each lexeme already on said list to the top of said list, and entering new lexemes at the top of said list.
References Cited (Backward Citations)
US3717851A
Cited
US4319225A
Cited
US4121259A
Cited
US4107457A
Cited
US4168513A
Cited
US4446516A
Cited
US4396906A
Cited
US4464650A
Cited
US4447676A
Cited
US4612532A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-01-03 | 1992-07-04 | 1993-01-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-01-03 | 1996-07-04 | 1997-01-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-01-03 | 2000-07-04 | 2001-01-03 | $7700.00 | Window Closed / Lapsed |