Taxonomy-based software construction of SPARE Time: a case study

The authors consider the design and implementation of SPARE Time as an example of taxonomy-based software construction (TABASCO). SPARE Time is a C++ toolkit for keyword pattern matching. It differs from other toolkits in that it is based on a taxonomy of keyword pattern matching algorithms. They discuss the aims of TABASCO and of taxonomy construction and taxonomy-based toolkit design in particular. They show how the taxonomy structure induces the architecture and design of SPARE Time. The taxonomy-oriented derivation also makes the toolkit easier to understand and use. The toolkit - like the taxonomy - contains the well known Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick and Commentz-Walter algorithms, as well as variants thereof, including more recent algorithms such as Backward Oracle Matching. It is freely available for noncommercial use.