Method and apparatus for automatically recognizing repeated shapes for data compaction
AssigneeInternational Business Machines Corporation
InventorsVirginia M. Chung, James E. Stuart
Life of this patent
Estimating the term…
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.
Claims19
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.
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.
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.
Dependencies are inferred from the claim text.