Code compaction by evolutionary algorithm

• US 6,260,031 B1
• Filed: 12/21/1998
• Issued: 07/10/2001
• Est. Priority Date: 12/21/1998
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (SoftBank Group Corp.)
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Eshelman, Larry J., Mathias, Keith E., Schaffer, J. David
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Starks, Wilbert L.
• Application Number:
  US09/217,408
• Time in Patent Office: 932 Days
• Field of Search: 706/13, 382/232, 382/243, 375/254
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A code compaction based on macro substitutions is presented wherein the choice of possible macro substitutions is guided by an evolutionary algorithm process. In a preferred embodiment, a random population of sets of macro substitutions are generated and a compaction effectiveness is evaluated for each set. This random population is partitioned into pairs of “parents”, and each pair of parents produce a pair of “offspring”. The effectiveness of the compaction provided by each of the offspring is evaluated, and a “survival of the fittest” algorithm is applied to identify the individuals that have the best compaction effectiveness. These preferred individuals are partitioned into pairs of parents who produce pairs of offspring, and the most compaction-effective individuals are selected to be parents for the next generation. This process continues until subsequent generations show insignificant improvement, and the best individual is selected as the solution.

Claims

1. A compactor for compacting a data set comprising:

an evolutionary algorithm processor that is configured to generate a plurality of offspring chromosomes from a population of parent chromosomes,

a macro suggester, operably coupled to the evolutionary algorithm processor for receiving each offspring chromosome of the plurality of offspring chromosomes, and producing therefrom a set of macros corresponding to said each offspring chromosome, and

a macro pool that is configured to contain a plurality of macro sequences that includes a macro sequence corresponding to each macro of the set of macros corresponding to said each offspring chromosome,

a tiler, operably coupled to the macro suggester and the macro pool, that is configured to provide a compaction of the data set based on the macro pool and the set of macros corresponding to said each offspring chromosome, and

wherein

the evolutionary algorithm processor is further configured to modify the population of parent chromosomes based upon a compaction measure associated with the compaction of the data set corresponding to said each offspring chromosome.

2. The compactor of claim 1, wherein

the evolutionary algorithm processor is configured to generate the plurality of offspring chromosomes from pairings of selected parent chromosomes in the population of parent chromosomes.

3. The compactor of claim 1, wherein the evolutionary algorithm processor is configured to generate the offspring chromosomes via the CHC algorithm.

4. The compactor of claim 1, wherein the tiler is further configured to generate a macro dictionary that includes at least one of the macro sequences corresponding to at least one offspring chromosome.

5. The compactor of claim 1, wherein the evolutionary algorithm processor is further configured to mutate at least one parent chromosome of the population of parent chromosomes.

6. The compactor of claim 1, wherein the macro suggester provides the set of macros based on a marginal worth of said each macro of the set of macros, the marginal worth being based on a compaction effectiveness measure associated with said each macro.

7. A method for compacting a data set comprising the steps of

identifying a plurality of macro sequences within the data set and associating a macro attribute to each macro sequence of the plurality of macro sequences,

generating a plurality of parental chromosomes, each parental chromosome having a corresponding set of macro attributes,

evaluating each said parental chromosome to determine a parent compaction measure associated with each said parental chromosome,

generating a plurality of offspring chromosomes based on the plurality of parental chromosomes via an evolutionary algorithm process, each offspring chromosome of the plurality of offspring chromosomes having a corresponding set of macro attributes,

evaluating each offspring chromosome of the plurality of offspring chromosomes to determine an offspring compaction measure associated with said each offspring chromosome,

identifying a plurality of preferred chromosomes based on the offspring compaction measure associated with said each offspring chromosome, and

generating a compacted data set based on the set of macro attributes corresponding to a selected chromosome of the plurality of preferred chromosomes.

8. The method of claim 7, wherein the step of generating the compacted data set includes the step of

substituting a macro symbol for at least one occurrence of the macro sequence within the data set corresponding to at least one macro attribute of the selected chromosome.

9. The method of claim 7, wherein the step of evaluating each offspring chromosome includes the steps of:

selecting at least one macro attribute from the offspring chromosome,

tiling the at least one macro attribute on the data set to produce an offspring data set,

determining the offspring compaction measure based on a size of the offspring data set.

10. The method of claim 9, wherein the step of selecting the at least one macro attribute from the offspring chromosome is based on a marginal compaction effectiveness of the at least one macro attribute.

11. The method of claim 10, wherein the step of determining the offspring compaction measure is also based on a size of the macro sequence corresponding to the at least one macro attribute.