US5481472A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for automatically recognizing repeated shapes for data compaction
Assignee: International Business Machines Corp
•
Filing: 1993-05-18
•
Granted: 1996-01-02
•
Expires: 2013-05-18
Abstract
Abstract A methodology and apparatus for extracting repeated data from a large body of data for compaction and reproduction by step-and-repeat operations includes extraction of data based on common parameters and a variable parameter. Lists are formed from the extracted data after ordering and repeat displacements are computed. Maximum displacement or delta is also computed and compared based on the range of addresses in the lists and a minimum number of step-and-repeat operations which can be done with a command which represents a compaction of data. A plurality of compressed data coding formats are provided and optimally applied during operation of the invention.
Inventors
- 👤 Virginia M. Chung
- 👤 James E. Stuart
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 15:56
CPC Classifications
H; H01; H01J; H01J37/00; H01J37/30; H01J37/302; H01J37/3023; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398; H01J2237/00; H01J2237/30; H01J2237/304; H01J2237/30405; H01J2237/30416; H01J2237/30422
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
223 words
A method of generating descriptions of step-and-repeat operations for compaction of data having at least an address and at least first, second and third parameters and containing repeated patterns comprising the steps of forming a list of portions of said data having at least one common first parameter, forming an ordered list from said portions of said data in accordance with said second and third parameters of said data, determining displacements between members of said ordered list from values of said third parameter of said data, incrementing an address of a member of said ordered list by at least one said displacement to obtain a further address, detecting if a member of said ordered list has said further address, and if a member of said ordered list has said further address, incrementing a step count and repeating said incrementing step from said further address and said detecting step, and if a member of said ordered list is not found, removing said member of said ordered list which has been incremented by said incrementing step and all members of said ordered list which have been detected by said detecting step from said ordered list and forming a coded description of said members of said ordered list which have been removed by said removing step using at least said second parameter and said step count.
Claim 2
Independent Claim
223 words
A method of generating descriptions of step-and-repeat operations for compaction of data having at least an address and at least first, second and third parameters and containing repeated patterns comprising the steps of forming a list of portions of said data having at least one common first parameter, forming an ordered list from said portions of said data in accordance with said second and third parameters of said data, determining displacements between members of said ordered list from values of said third parameter of said data, incrementing an address of a member of said ordered list by at least one said displacement to obtain a further address, detecting if a member of said ordered list has said further address, and if a member of said ordered list has said further address, incrementing a step count and repeating said incrementing step from said further address and said detecting step, and if a member of said ordered list is not found, removing said member of said ordered list which has been incremented by said incrementing step and all members of said ordered list which have been detected by said detecting step from said ordered list and forming a coded description of said members of said ordered list which have been removed by said removing step using at least said second parameter and said step count.
Claim 3
Dependent Claim
76 words
A method as recited in claim 1, including the further steps of finding a range of addresses in said ordered list, establishing a minimum number of step-and-repeat operations which can be described in less data than data to describe said minimum number of instances of said data, dividing said range by a number which is one less than said minimum number, and ignoring all said displacements which are greater than a result of said dividing step.
Claim 4
Dependent Claim
64 words
A method as recited in claim 1, including the further steps of accumulating instances of equal displacements, and repeating said steps of incrementing and detecting steps only for displacements having a number of instances equal to or greater than a minimum number of step-and-repeat operations which can be described in less data than data to describe said minimum number of instances of said data.
Claim 5
Dependent Claim
54 words
A method as recited in claim 3, wherein said detecting step includes substituting said step count for said minimum number, wherein said method further includes repeating, subsequent to said substituting step, said steps of incrementing and detecting steps only for displacements having a number of instances equal to or greater than said step count.
Claim 6
Independent Claim
235 words
A method of generating descriptions of step-and-repeat operations for compaction of data having at least an address and at least first, second and third parameters and containing repeated patterns comprising the steps of forming a list of portions of said data having at least one common first parameter, forming an ordered list from said portions of said data in accordance with said second and third parameters of said data, forming a truncated list of members of said ordered list having a consistent value of said second parameter of said data, determining displacements between members of said truncated list, incrementing an address of a member of said truncated list by at least one said displacement to obtain a further address, detecting if a member of said truncated list has said further address, and if a member of said truncated list has said further address, incrementing a step count and repeating said incrementing step from said further address and said detecting step, and if a member of said truncated list is not found, removing said member of said truncated list which has been incremented by said incrementing step and all members of said truncated list which have been detected by said detecting step from said truncated list and forming a coded description of said members of said truncated list which have been removed by said removing step using said first and second parameters and said step count.
Claim 7
Independent Claim
235 words
A method of generating descriptions of step-and-repeat operations for compaction of data having at least an address and at least first, second and third parameters and containing repeated patterns comprising the steps of forming a list of portions of said data having at least one common first parameter, forming an ordered list from said portions of said data in accordance with said second and third parameters of said data, forming a truncated list of members of said ordered list having a consistent value of said second parameter of said data, determining displacements between members of said truncated list, incrementing an address of a member of said truncated list by at least one said displacement to obtain a further address, detecting if a member of said truncated list has said further address, and if a member of said truncated list has said further address, incrementing a step count and repeating said incrementing step from said further address and said detecting step, and if a member of said truncated list is not found, removing said member of said truncated list which has been incremented by said incrementing step and all members of said truncated list which have been detected by said detecting step from said truncated list and forming a coded description of said members of said truncated list which have been removed by said removing step using said first and second parameters and said step count.
Claim 8
Dependent Claim
166 words
A method as recited in claim 5, including the further steps of determining displacements between members of said ordered list from values of said third parameter of said data, incrementing an address of a member of said ordered list by at least one said displacement to obtain a further address, detecting if a member of said ordered list has said further address, and if a member of said ordered list has said further address, incrementing a step count and repeating said incrementing step from said further address and said detecting step, and if a member of said ordered list is not found, removing said member of said ordered list which has been incremented by said incrementing step and all members of said ordered list which have been detected by said detecting step from said ordered list and forming a coded description of said members of said truncated list which have been removed by said removing step using at least said second parameter and said step count.
Claim 9
Dependent Claim
76 words
A method as recited in claim 5, including the further steps of finding a range of addresses in said truncated list, establishing a minimum number of step-and-repeat operations which can be described in less data than data to describe said minimum number of instances of said data, dividing said range by a number which is one less than said minimum number, and ignoring all said displacements which are greater than a result of said dividing step.
Claim 10
Dependent Claim
76 words
A method as recited in claim 6, including the further steps of finding a range of addresses in said ordered list, establishing a minimum number of step-and-repeat operations which can be described in less data than data to describe said minimum number of instances of said data, dividing said range by a number which is one less than said minimum number, and ignoring all said displacements which are greater than a result of said dividing step.
Claim 11
Dependent Claim
64 words
A method as recited in claim 5, including the further steps of accumulating instances of equal displacements, and repeating said steps of incrementing and detecting steps only for displacements having a number of instances equal to or greater than a minimum number of step-and-repeat operations which can be described in less data than data to describe said minimum number of instances of said data.
Claim 12
Dependent Claim
54 words
A method as recited in claim 9, wherein said detecting step includes substituting said step count for said minimum number, wherein said method further includes repeating, subsequent to said substituting step, said steps of incrementing and detecting steps only for displacements having a number of instances equal to or greater than said step count.
Claim 13
Dependent Claim
64 words
A method as recited in claim 6, including the further steps of accumulating instances of equal displacements, and repeating said steps of incrementing and detecting steps only for displacements having a number of instances equal to or greater than a minimum number of step-and-repeat operations which can be described in less data than data to describe said minimum number of instances of said data.
Claim 14
Dependent Claim
54 words
A method as recited in claim 11, wherein said detecting step includes substituting said step count for said minimum number, wherein said method further includes repeating, subsequent to said substituting step, said steps of incrementing and detecting steps only for displacements having a number of instances equal to or greater than said step count.
Claim 15
Dependent Claim
36 words
A method as recited in claim 6, wherein said steps of forming coded descriptions of members removed from said ordered list and said truncated list, respectively, include separate steps of forming coded descriptions in different formats.
Claim 16
Independent Claim
94 words
A method of compressing numerical control data comprising the steps of extracting at least one major list of data having identical values of at least one first parameter, extracting at least one minor list from said major list having identical values of a second parameter, determining displacements between members of said minor list, generating a step-and-repeat command descriptive of at least a minimum number of members of said minor list for which said displacements are identical, and removing members of said minor list which are described by said step-and-repeat command from said major list.
Claim 17
Independent Claim
94 words
A method of compressing numerical control data comprising the steps of extracting at least one major list of data having identical values of at least one first parameter, extracting at least one minor list from said major list having identical values of a second parameter, determining displacements between members of said minor list, generating a step-and-repeat command descriptive of at least a minimum number of members of said minor list for which said displacements are identical, and removing members of said minor list which are described by said step-and-repeat command from said major list.
Claim 18
Dependent Claim
82 words
A method as recited in claim 14, including the further, subsequent, steps of determining displacements between members of said major list, and generating a step-and-repeat command descriptive of at least a minimum number of members of said major list for which said displacements are identical, said step-and-repeat command descriptive of at least a minimum number of members of said major list specifying a value of said second parameter for each of said at least minimum number of members of said minor list.
Claim 19
Dependent Claim
47 words
A method as recited in claim 14, including the further step of determining a range of addresses in said minor list, and computing a maximum displacement which is consistent with finding at least said minimum number of members separated by identical displacements within said range of addresses.
Claim 20
Dependent Claim
51 words
A method as recited in claim 14, wherein said step of determining displacements in said minor list includes the further steps of accumulating a number of instances in which a displacement is determined to be identical to a displacement previously determined, and comparing said number of instances to said minimum number.
Claim 21
Dependent Claim
55 words
A method as recited in claim 15, including the further step of determining a range of addresses in at least one of said major list and said minor list, and computing a maximum displacement which is consistent with finding at least said minimum number of members separated by identical displacements within said range of addresses.
Claim 22
Dependent Claim
59 words
A method as recited in claim 15, wherein said step of determining displacements in regard to at least one of said major and minor lists includes the further steps of accumulating a number of instances in which a displacement is determined to be identical to a displacement previously determined, and comparing said number of instances to said minimum number.
References Cited (Backward Citations)
US4291231A
Cited
US4259724A
Cited
US4531191A
Cited
US4538232A
Cited
US4433384A
Cited
JPS5891638A
Cited
JPS59124127A
Cited
US4744047A
Cited
US4843563A
Cited
US4910679A
Cited
US4950910A
Cited
US5086398A
Cited
US5337247A
Cited
US5129201A
Cited
US5428552A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-01 | 1999-07-03 | 2000-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-01 | 2003-07-03 | 2004-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-01 | 2007-07-03 | 2008-01-02 | $7700.00 | Window Closed / Lapsed |