Patent US5594435A successfully refreshed from Google Patents.
US5594435A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Permutation-based data compression
Assignee: USA TALKS COM Inc A CORP OF NEVADA
•
Filing: 1995-09-13
•
Granted: 1997-01-14
•
Expires: 2015-09-13
Abstract
Abstract A lossless compression method and system is provided, wherein an index to a dictionary or table of entries is generated by producing, for a message consisting of a set of finite symbols in a particular order, an assigned order value, where the number of bits to represent the order value plus the number of bits to identify duplicate symbols of the message is smaller than the number of bits contained in the message itself. A complete message can be communicated as an index to a dictionary by communicating a position (inherently communicating the identity) and a count of repetitions of related to that position from which the original position and order can be recovered and the message can be reconstructed. Since the message itself is an index to a dictionary of finite size, any intelligence which can be extracted from an arrangement of symbols found in the dictionary can be reconstructed. Computation of positions can be done recursively. This invention is based on a principle where there is a nontrivial group wherein the number of bits needed to represent the order of a closed set of symbols plus the count of the number of occurrences of each symbol is less than the number of bits needed to represent the symbols.
Inventors
- 👤 John F. Remillard
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 15:51
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3091
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
203 words
In a data processing system having a data input means, a data output means, processing means and storage means, said processing system for operation on a non-empty closed set of symbols, a method for compressing data comprising the steps of: receiving a bounded message via said data input means to said storage means, said bounded message consisting of a number of distinct symbol types; examining said bounded message with said processing means; thereupon selecting with said processing means a symbol set for describing said bounded message, said symbol set consisting of a closed set of unique symbols, each symbol being of multiple bit length, for use in representing said bounded message to a dictionary; counting with said processing means numbers of occurrences of each said symbol found in said bounded message to obtain symbol counts; thereafter determining with said processing means a unique permutation position of said bounded message with respect to all possible permutations of said symbols found in said bounded message; and communicating said symbol counts with reference to said symbols found in said bounded message and said unique permutation position via said data output means as compressed information for use in the dictionary in order to reconstruct the bounded message.
Claim 2
Dependent Claim
203 words
In a data processing system having a data input means, a data output means, processing means and storage means, said processing system for operation on a non-empty closed set of symbols, a method for compressing data comprising the steps of: receiving a bounded message via said data input means to said storage means, said bounded message consisting of a number of distinct symbol types; examining said bounded message with said processing means; thereupon selecting with said processing means a symbol set for describing said bounded message, said symbol set consisting of a closed set of unique symbols, each symbol being of multiple bit length, for use in representing said bounded message to a dictionary; counting with said processing means numbers of occurrences of each said symbol found in said bounded message to obtain symbol counts; thereafter determining with said processing means a unique permutation position of said bounded message with respect to all possible permutations of said symbols found in said bounded message; and communicating said symbol counts with reference to said symbols found in said bounded message and said unique permutation position via said data output means as compressed information for use in the dictionary in order to reconstruct the bounded message.
Claim 3
Dependent Claim
31 words
The method according to claim 1 wherein the number of distinct symbol types is two (i.e., k=2) to produce a binary-valued symbol set comprising data bits of values 1 and 0.
Claim 4
Dependent Claim
52 words
The method according to claim 1 further including, after said counting step, processing said message such that the number of distinct symbol types is equal to the total number of different symbols used in said message and the distinct symbol types are used once and only once in said message (i.e., k=n).
Claim 5
Dependent Claim
181 words
A data processing system, having a data input means and a data output means, for compressing a message built of a non-empty closed set of symbols, said system comprising: means for receiving a bounded message via said data input means, said bounded message consisting of a number of distinct symbol types describable with an alphabet, said alphabet consisting of a closed set of unique symbols, each symbol being of multiple length, said alphabet for use in representing said bounded message to a dictionary; means coupled to said receiving means for identifying numbers of occurrences of each said symbol found in said bounded message to obtain symbol counts; means for mapping said bounded message to a unique permutation position of said bounded message with respect to all possible permutations of said symbols found in said bounded message; and means coupled to said mapping means for communicating said symbol counts with reference to said symbols found in said bounded message and said unique permutation position via said data output means as compressed information for use in the dictionary to reconstruct the bounded message.
Claim 6
Dependent Claim
181 words
A data processing system, having a data input means and a data output means, for compressing a message built of a non-empty closed set of symbols, said system comprising: means for receiving a bounded message via said data input means, said bounded message consisting of a number of distinct symbol types describable with an alphabet, said alphabet consisting of a closed set of unique symbols, each symbol being of multiple length, said alphabet for use in representing said bounded message to a dictionary; means coupled to said receiving means for identifying numbers of occurrences of each said symbol found in said bounded message to obtain symbol counts; means for mapping said bounded message to a unique permutation position of said bounded message with respect to all possible permutations of said symbols found in said bounded message; and means coupled to said mapping means for communicating said symbol counts with reference to said symbols found in said bounded message and said unique permutation position via said data output means as compressed information for use in the dictionary to reconstruct the bounded message.
Claim 7
Dependent Claim
33 words
The system according to claim 4 wherein the number of distinct symbol types is preset to two (i.e., k=2) to produce a binary-valued symbol set comprising data bits of values 1 and 0.
Claim 8
Dependent Claim
56 words
The method according to claim 4 further including means coupled to said numbers identifying means for processing said message such that the number of distinct symbol types is equal to the total number of different symbols used in said message and the distinct symbol types are used once and only once in said message (i.e., k=n).
References Cited (Backward Citations)
US4545032A
Cited
US5486826A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-14 | 2000-07-15 | 2001-01-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-14 | 2004-07-15 | 2005-01-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-14 | 2008-07-15 | 2009-01-14 | $7700.00 | Window Closed / Lapsed |