Image analysis – Pattern recognition – Context analysis or word recognition
Reexamination Certificate
1998-11-06
2001-12-25
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Context analysis or word recognition
C714S036000
Reexamination Certificate
active
06333999
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to systems and methods of generating a series of character strings, and in particular to a method and system for systematically generating a series of character strings from the systematic application of a rule set to a template.
2. Description of the Related Art
Frequently, in testing computer software products, the need arises to create many ordered sequences of character strings; each based on a specified theme. Such ordered sequences can be used in a program to test the operation of functional attributes in the software product. The desired sequences are variations of the sequence theme, which are unique in specific, non-random, and non-trivial ways and are produced according to a first-to-last ordering. Manually producing such sequences can be extremely time-consuming.
Manually producing such sequences is a time-consuming and error-prone process. Automated test case generators have been developed which reduce the time to create test case sequences and reduce the chances of error. These automated test case generators include random test case generators and rule-based test case generators.
Random test case generators can be effective, but are limited in usefulness. Random generators do not allow control over the order in which the test cases are generated, nor do they allow control over the specific contents of each test case.
Rule-based test case generators have similar limitations. Many rule-based generators will produce only a specific type of test case (for example, program generators typically do not generate data I/O data records). Other rule-based test case generators can generate test cases only in a specific programming language. Current rule-based generation systems are deficient in one or more of the following ways: template specification (many do not provide for the specification of a template), allowing non-terminal strings to be produced (many do not allow non-terminal strings to be produced where a non-terminal string, if input to the method, would be further transformed), or output strings re-input to the generator (abstraction ability). Abstraction ability is desirable, since it allows for the generation of potentially many templates and rules from a single template and set of rules.
What is needed is a system for efficiently generating a sequence of character stings in a versatile, systematic and predictable way. The present invention satisfies that need.
SUMMARY OF THE INVENTION
To address the requirements described above, the present invention discloses a method, apparatus, article of manufacture, and a memory structure for making multiple consecutive variations of a single character-string template (or pattern) where each variation differs from the previous one in a systematic way. The pattern is not restricted in form or in content, and the variations can include adding, deleting, and modifying lines and strings in the pattern, and making no change. This is implemented by executing production rules on a template.
Production rules specify the substitutions that are to be made in the template. A number of different types of production rules are disclosed, which make complex substitution sequences easy to accomplish.
A template is a set of strings which expresses a theme and into which substitutions are made. It is the pattern which is used in evaluating the output strings. The template simplifies the specification of the production rules, and provides good documentation about the type of result to be produced. Unlike other rule-based generation programs, the template used in the present invention allows the template pattern to be written in any language (including any programming language, even those which have been defined, but not implemented) without restriction.
Another feature of the present invention is that the production rules are executed only once per enumeration (output), and they are executed in a first-to-last sequence (i.e. there is no skipping rules, no random processing, no mandatory continuation of processing until all terminal symbols are produced). Some rule based production systems must continue processing until no rule can be applied (i.e. until all “non-terminal strings” are transformed into “terminal strings”).
Patterns for a variety of applications can be generated with the present invention. For example, when the pattern is a computer program (a level 1 pattern), applying the described method results in the automatic generation of programs which are suitable for compiling by a compiler (level 0 patterns). When applied to an option list for a compiler, the method results in the automatic generation of compiler options. Further, when the pattern is a level n meta-pattern (n>1), applying the described method results in an automatic generation of level n-1 patterns.
In one embodiment, the method herein described begins by defining a template comprising a plurality of template character strings, and defining an ordered series of production rules, each with a comparison field, an operator, and a substitution field defining an initial value and a current value. The current value of each production rule is set to the initial value, and the production rules are applied to the template one at a time in execution order. The result of this application of production rules to the template is then enumerated (output). Finally, the production rules are then iterated (i.e. updated in accordance with the operator and substitution field) and again applied to the template.
In an alternative embodiment, the foregoing method steps are represented by a series of instructions recognizable by a computer. These instructions may be embodied in a storage device, or transmitted over a communications network to a local computer. Another alternative embodiment comprises a means for defining a template with a plurality of character strings, means for defining an ordered series of production rules having the characteristics described above, means for setting the current value of each production rule to the initial value, means for applying each of the production rules in order to the template, and a means for iterating the production rules after each of the production rules have been applied.
The foregoing method, apparatus, article of manufacture and memory structure result in a number of significant improvement over current pattern generators in the following areas:
Productivity: productivity is increased because the present invention allows a few lines written in the enumeration language to produce many lines of output.
Thoroughness: Because it permits the user to more easily generate a large number of enumerations, the present invention encourages the software developer to perform more comprehensive and thorough testing.
Knowledge Organization: The template and rule set used by the present invention is an “encapsulation” of a set of enumerations, where each enumeration in the set is created in deterministic order. Creating this encapsulation requires understanding of the characteristics of the enumerations and the changes that occurs with them.
Abstraction: The disclosed template and rule set can produce strings that are templates and sets of rules (which can then be input into the procedure). This is meaningful when the target set of strings has been encapsulated into a set of templates and rules (set “A”, for example), and then set A is encapsulated into a template and rules.
Systematic coverage: The application of rules to the template results in a deterministic output, so the enumerations are produced in a predictable manner. This also allows the nth enumeration from a set of rules to be enumerated for special treatment or study.
Accuracy: Systematic enumeration avoids the mistakes of by-hand enumeration.
Ease of Maintenance: If modification of the enumerations is required, it can be easily accomplished by re-enumerating a modified template and/or rules, thus saving writing special processing code or performing modifications by hand.
Compact Form: The enumerations can
Azarian Seye D.
Gates & Cooper LLP
International Business Machines - Corporation
Johns Andrew W.
LandOfFree
Systematic enumerating of strings using patterns and rules does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systematic enumerating of strings using patterns and rules, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systematic enumerating of strings using patterns and rules will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2584647