US5651099A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Use of a genetic algorithm to optimize memory space
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-01-26
•
Granted: 1997-07-22
•
Expires: 2015-01-26
Abstract
Abstract The present invention is accomplished by first initializing a plurality of individuals. A trie is constructed for each individual, where the trie represents the original data. The trie comprises a root node, a plurality of sub-nodes and sub-arrays in a hierarchical arrangement. The individual indicates the number of the sub-nodes, sub-arrays and number of entries in each sub-array. Within a trie, delete any sub-array which contains redundant data and remove any of sub-node which contains redundant data. Apply an overlapping reduction function to the trie. With the trie constructed, determine the size for the trie and associate the size to the individual. Select a mating population based on trie size. Choose and perform at least one operation for the mating population, where the operation is the operations of crossover or mutation. For crossover, create at least one new individual by recombining the "genes" of at least two individual from the mating population. Then, add the new individual to the plurality of individuals. For mutation, mutate an individual by stochastically changing a property of the individual, then place the mutated individual in the plurality of individuals. Iterate for a predefined number of generations. Finally, keep in memory the trie with the smallest size.
Inventors
- 👤 Shane Konsella
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 16:33
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; G; G06; G06N; G06N3/00; G06N3/12; G06N3/126; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
148 words
A method for storing original data in a computer memory, said method comprising the steps of: picking a number of generations; initializing a plurality of individuals; for each individual, determining a size for a trie symbolized by said each individual where said trie represents said original data; selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual's trie size; choosing and performing at least one operation for said mating population, where said operation is the operation of crossover; said operation of crossover comprising creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; iteratively doing said steps of determining, selecting, and choosing and performing for said number of generations times; and keeping in memory the trie having minimum said size.
Claim 2
Independent Claim
148 words
A method for storing original data in a computer memory, said method comprising the steps of: picking a number of generations; initializing a plurality of individuals; for each individual, determining a size for a trie symbolized by said each individual where said trie represents said original data; selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual's trie size; choosing and performing at least one operation for said mating population, where said operation is the operation of crossover; said operation of crossover comprising creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; iteratively doing said steps of determining, selecting, and choosing and performing for said number of generations times; and keeping in memory the trie having minimum said size.
Claim 3
Dependent Claim
74 words
The method as described in claim 1 wherein said step of selecting comprising: defining said mating population as having a plurality of individuals, said number of individuals in said mating population equals the number of individuals in said plurality of individuals; copying individuals from said plurality of individuals to said mating population where probability of being copied is inversely related to said individual's trie size; and deleting all individuals in said plurality of individuals.
Claim 4
Dependent Claim
40 words
The method as described in claim 1 wherein said individual is a binary number with N number of bits set to a first value, said step of crossover occurs by exchanging first value bits between said at least two individuals.
Claim 5
Dependent Claim
18 words
The method as described in claim 1 wherein said step of initializing randomly generates said plurality of individuals.
Claim 6
Dependent Claim
46 words
The method as described in claim 2 wherein said step of choosing and performing further comprising an operation of mutation, if said chosen operation is mutation, mutating said individual by stochastically changing a property of said individual, placing said mutated individual in said plurality of individuals.
Claim 7
Dependent Claim
34 words
The method as described in claim 5 wherein said individual is a binary number with N number of bits set to a first value, said step of changing a property modifies said binary number.
Claim 8
Dependent Claim
79 words
The method as described in claim 1 wherein said step of determining comprising the steps of: creating a root node, a plurality of sub-nodes, and a plurality of sub-arrays in a hierarchical arrangement, said individual indicates a number of said sub-nodes and said sub-arrays, and a number of entries in said sub-array; deleting any of said plurality of sub-arrays which contain redundant data; removing any of said plurality of sub-nodes which contain redundant data; and applying overlapping reduction function.
Claim 9
Dependent Claim
73 words
The method as described in claim 7 wherein each of sub-array having a head and a tail, said step of applying overlapping reduction function comprising the steps of: first finding overlappable entries in said tail for each of said entries in said sub-array; second finding overlappable entries in said head for each of said entries in said sub-array; and matching said overlappable entries in said tail with said overlappable entries in said head.
Claim 10
Dependent Claim
64 words
The method as described in claim 8 wherein said individual is a binary number with N number of bits set to a first value, said step of creating further comprising the step of linking said root with said plurality of sub-nodes and said sub-arrays to form a modified hybrid multiway radix search tree, said root and said plurality of sub-nodes arranged in N levels.
Claim 11
Independent Claim
248 words
A method for storing original data in a minimum amount of computer memory, said method comprising the steps of: picking a number of generations; initializing a plurality of individuals; for each individual: constructing a trie, where said trie represents said original data, said trie comprising a root node, a plurality of sub-nodes, and a plurality of sub-arrays in a hierarchical arrangement, said individual indicates a number of said sub-nodes and said sub-arrays, and a number of entries in said sub-array; deleting any of said plurality of sub-arrays which contain redundant data; removing any of said plurality of sub-nodes which contain redundant data; applying overlapping reduction function to said trie; determining a size for said trie; associating said size to said individual; selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual's trie size; choosing and performing at least one operation for said mating population, where said operation is the operations of crossover or mutation; if said chosen operation is crossover, creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; if said chosen operation is mutation, mutating an individual in said mating population by stochastically changing a property of said individual, placing said mutated individual into said plurality of individuals; iteratively performing steps for said number of generations times; and keeping in said memory the trie having minimum said size.
Claim 12
Independent Claim
248 words
A method for storing original data in a minimum amount of computer memory, said method comprising the steps of: picking a number of generations; initializing a plurality of individuals; for each individual: constructing a trie, where said trie represents said original data, said trie comprising a root node, a plurality of sub-nodes, and a plurality of sub-arrays in a hierarchical arrangement, said individual indicates a number of said sub-nodes and said sub-arrays, and a number of entries in said sub-array; deleting any of said plurality of sub-arrays which contain redundant data; removing any of said plurality of sub-nodes which contain redundant data; applying overlapping reduction function to said trie; determining a size for said trie; associating said size to said individual; selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual's trie size; choosing and performing at least one operation for said mating population, where said operation is the operations of crossover or mutation; if said chosen operation is crossover, creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; if said chosen operation is mutation, mutating an individual in said mating population by stochastically changing a property of said individual, placing said mutated individual into said plurality of individuals; iteratively performing steps for said number of generations times; and keeping in said memory the trie having minimum said size.
Claim 13
Dependent Claim
74 words
The method as described in claim 10 wherein said step of selecting comprising: defining said mating population as having a plurality of individuals, said number of individuals in said mating population equals the number of individuals in said plurality of individuals; copying individuals from said plurality of individuals to said mating population where probability of being copied is inversely related to said individual's trie size: and deleting all individuals in said plurality of individuals.
Claim 14
Dependent Claim
73 words
The method as described in claim 10 wherein each of sub-array having a head and a tail, said step of applying overlapping reduction function comprising the steps of: first finding overlappable entries in said tail for each of said entries in said sub-array; second finding overlappable entries in said head for each of said entries in said sub-array; and matching said overlappable entries in said tail with said overlappable entries in said head.
Claim 15
Dependent Claim
90 words
The method as described in claim 10 wherein said individual is a binary number with N number of bits set to a first value, said step of crossover occurs by exchanging first value bits between said at least two individuals, said step of changing a property modifies said binary number, said step of constructing further comprising the step of linking said root with said plurality of sub-nodes and said sub-arrays to form a modified hybrid multiway radix search tree, said root and said plurality of sub-nodes arranged in N levels.
Claim 16
Dependent Claim
168 words
A computer system that stores an original data comprising: a memory in which a plurality of individuals are stored; a processor coupled to said memory, said processor executes a sequence of instruction; means for determining a size of a trie symbolized by each individual where said trie represents said original data, said means for determining coupled to said processor; means for selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual's trie size; means for choosing and performing an operation for said mating population, where said operation is the operation of crossover, said means for choosing and performing coupled to said processor; means for performing said operation of crossover comprising creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; and means for keeping in memory the trie having minimum said size, said means for keeping coupled to said processor.
Claim 17
Dependent Claim
168 words
A computer system that stores an original data comprising: a memory in which a plurality of individuals are stored; a processor coupled to said memory, said processor executes a sequence of instruction; means for determining a size of a trie symbolized by each individual where said trie represents said original data, said means for determining coupled to said processor; means for selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual's trie size; means for choosing and performing an operation for said mating population, where said operation is the operation of crossover, said means for choosing and performing coupled to said processor; means for performing said operation of crossover comprising creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; and means for keeping in memory the trie having minimum said size, said means for keeping coupled to said processor.
Claim 18
Dependent Claim
80 words
The computer system of claim 14 wherein said means for selecting further comprising: means for defining said mating population as having a plurality of individuals, said number of individuals in said mating population equals the number of individuals in said plurality of individuals; means for copying individuals from said plurality of individuals to said mating population where probability of being copied is inversely related to said individual's trie size; and means for deleting all individuals in said plurality of individuals.
Claim 19
Dependent Claim
51 words
The computer system of claim 14 wherein said means for choosing and performing an operation further comprising an operation of mutation, said computer system further comprising means for performing said operation of mutation comprising stochastically changing a property of said individual, placing said mutated individual back into said plurality of individuals.
Claim 20
Dependent Claim
31 words
The computer system of claim 16 wherein said individual is a binary number with N number of bits set to a first value, said changing a property modifies said binary number.
Claim 21
Dependent Claim
55 words
The computer system of claim 14, said trie comprising: a root node having at least two pointers; and at least two sub-arrays linked to said root node through said at least two pointers in a hierarchical arrangement, said at least two sub-arrays each having a plurality of entries in which said original data is stored.
Claim 22
Dependent Claim
42 words
The computer system of claim 18, said trie further comprising: a plurality of sub-nodes located between said root node and said sub-arrays, said root linked with said plurality of sub-nodes and said sub-arrays to form a modified hybrid multiway radix search tree.
Claim 23
Dependent Claim
61 words
The computer system of claim 19 wherein said means for determining a size further comprising: means for deleting any of said plurality of sub-arrays which contain redundant data; means for removing any of said plurality of sub-nodes which contain redundant data; means for applying overlapping reduction function; and means for counting the amount of said memory necessary to store the trie.
References Cited (Backward Citations)
US4697242A
Cited
US4881178A
Cited
US5058144A
Cited
US4935877A
Cited
US5148513A
Cited
US5343554A
Cited
US5136686A
Cited
US5276868A
Cited
US5151697A
Cited
US5151950A
Cited
DE4110400A1
Cited
US5379036A
Cited
US5226082A
Cited
US5406279A
Cited
US5412384A
Cited
JPH0744520A
Cited
JPH0785270A
Cited
US5528701A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-21 | 2001-01-20 | 2001-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-21 | 2005-01-20 | 2005-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-21 | 2009-01-20 | 2009-07-22 | $7700.00 | Window Closed / Lapsed |