Technical Reports

download
Classification for Selected Spell Checkers and Correctors
Hsuan Lorraine Liang, Bruce W. Watson & Derrick G. Kourie 2008/03 - Technical Report
Technical Report TR-UNISA-2008-01, School of Computing, University of South Africa, March 2008.
(show/hide) Abstract
The aim of this work is to provide a better understanding of the spell checking and correcting tasks. An empirical investigation of various spell checking/correcting packages provides a comparison and suggests a classification of these packages in terms of their functionalities, implementation strategies, and performance.

download
Proceedings of the Eindhoven FASTAR Days 2004
Loek Cleophas & Bruce W. Watson (editors) 2004/12 - Technical Report
Computer Science Technical Report 04-40, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, December 2004.

download
A new taxonomy of sublinear keyword pattern matching algorithms
Loek Cleophas, Bruce W. Watson & Gerard Zwaan 2004/03 - Technical Report
Computer Science Technical Report 04-07, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, March 2004.
(show/hide) Abstract
This paper presents a new taxonomy of sublinear (multiple) keyword pattern matching algorithms. Based on an earlier taxonomy by Watson and Zwaan [WZ96, WZ95], this new taxonomy includes not only suffix-based algorithms related to the Boyer-Moore, Commentz-Walter and Fan-Su algorithms, but factor- and factor oracle-based algorithms such as Backward DAWG Matching and Backward Oracle Matching as well. In particular, we show how suffix-based (Commentz-Walter like), factor- and factor oracle-based sublinear keyword pattern matching algorithms can all be seen as instantiations of a general sublinear algorithm skeleton. In addition, we show all shift functions defined for the suffix-based algorithms to be in principle reusable for factor- and factor oracle-based algorithms. The taxonomy is based on deriving the algorithms from a common starting point by adding algorithm and problem details, in order to arrive at efficient or well-known algorithms. Such a presentation provides correctness arguments for the algorithms as well as clarity on how the algorithms are related to one another. In addition, it is helpful in the construction of a toolkit of the algorithms. [WZ95] B. W. Watson and G. Zwaan. A taxonomy of sublinear multiple keyword pattern matching algorithms. Computing Science Report 95/13, Department of Computing Science, Eindhoven University of Technology, 1995. [WZ96] B. W. Watson and G. Zwaan. A taxonomy of sublinear multiple keyword pattern matching algorithms. Science of Computer Programming, 27(2):85-118, 1996.

download
Constructing Factor Oracles
Loek Cleophas, Gerard Zwaan, and Bruce W. Watson 2004/01 - Technical Report
Computer Science Technical Report 04-01, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, January 2004.
(show/hide) Abstract
A factor oracle is a data structure for weak factor recognition. It is an automaton built on a string p of length m that is acyclic, recognizes at least all factors of p, has m+1 states which are all final, and has m to 2m-1 transitions. In this paper, we give two alternative algorithms for its construction and prove the constructed automata to be equivalent to the automata constructed by the algorithms in [1]. Although these new O(m^2) algorithms are practically inefficient compared to the O(m) algorithm given in [1], they give more insight into factor oracles. Our first algorithm constructs a factor oracle based on the suffixes of p in a way that is more intuitive. Some of the crucial properties of factor oracles, which in [1] need several lemmas to be proven, are immediately obvious. Another important property however becomes less obvious. A second algorithm gives a clear insight in the relationship between the trie or dawg recognizing the factors of p and the factor oracle recognizing a superset thereof. We conjecture that an O(m) version of this trie-based algorithm exists. [1] Cyril Allauzen, Maxime Crochemore, and Mathieu Raffinot. Efficient Experimental String Matching by Weak Factor Recognition. In Proceedings of the 12th conference on Combinatorial Pattern Matching, volume 2089 of LNCS, pages 51-72, 2001.

download
On Hardcoding Finite State Automata Processing
E. Ketcha Ngassam, Bruce W. Watson, and Derrick G. Kourie 2003/10 - Technical Report
Computer Science Technical Report 03-10, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, October 2003.
(show/hide) Abstract
In this paper, we present various experiments in hardcoding the transition table of a finite state machine directly into string-recognizing code. Measurements are provided to show the time efficiency gains by various hardcoded versions over the traditional table-driven approach.


A new recursive algorithm for building minimal acyclic deterministic finite automata
Bruce W. Watson 2001/00 - Technical Report
Technical Report, Department of Computer Science, University of Pretoria, South Africa, 2001


A new family of Commentz-Walter-style multiple-keyword pattern matching algorithms
Bruce W. Watson 2001/00 - Technical Report
Technical Report, Department of Computer Science, University of Pretoria, South Africa, 2001


An incremental DFA minimization algorithm
Bruce W. Watson 2001/00 - Technical Report
Technical Report, Department of Computer Science, University of Pretoria, South Africa, 2001


A history of Brzozowski's DFA minimization algorithm
Bruce W. Watson 2001/00 - Technical Report
Technical Report, Department of Computer Science, University of Pretoria, South Africa, 2001

download
A taxonomy of sublinear keyword pattern matching algorithms
Bruce W. Watson and Gerard Zwaan 1995/00 - Technical Report
Computing Science Report 95/13, Department of Computing Science, Eindhoven University of Technology, 1995.
(show/hide) Abstract
This paper presents a taxonomy of sublinear keyword pattern matching algorithms related to the Boyer-Moore algorithm and the Commentz-Walter algorithm. The taxonomy includes, amongst others, the multiple keyword generalization of the single keyword Boyer-Moore algorithm and an algorithm by Fan and Su. The corresponding precomputation algorithms are presented as well. The taxonomy is based on the idea of ordering algorithms according to their essential problem and algorithm details, and deriving all algorithms from a common starting point by successively adding these details in a correctness preserving way. This way of presentation not only provides a complete correctness argument of each algorithm, but also makes very clear what algorithms have in common (the details of their nearest common ancestor) and where they differ (the details added after their nearest common ancestor). Introduction of the notion of safe shift distances proves to be essential in the derivation and classification of the algorithms. Moreover, the paper provides a common derivation for and a uniform presentation of the precomputation algorithms, not yet found in the literature.

download
A Boyer-Moore type algorithm for regular expression pattern matching
Bruce W. Watson and Richard E. Watson 1994/00 - Technical Report
Computing Science Report 94/31, Department of Computing Science, Eindhoven University of Technology, 1994.
(show/hide) Abstract
This paper presents a Boyer-Moore-type algorithm for regular expression pattern matching, answering an open problem posed by A. V. Aho in 1980 [Aho80, p. 342]. The new algorithm handles patterns specified by regular expressions---a generalization of the Boyer-Moore and Commentz-Walter algorithms (which deal with patterns that are single keywords and finite sets of keywords, respectively). Like the Boyer-Moore and Commentz-Walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. The precomputation algorithms are derived, and it is shown that the required shift functions can be precomputed from Commentz-Walter's and shift functions known as d_{1} and d_{2}. In certain cases, the Boyer-Moore (Commentz-Walter) algorithm has greatly outperformed the Knuth-Morris-Pratt (Aho-Corasick) algorithm. In testing, the algorithm presented in this paper also frequently outperforms the regular expression generalization of the Aho-Corasick algorithm. [Aho80] A.V. Aho. Pattern matching in strings. In R.V. Book, ed., Formal Language Theory: Perspectives and Open Problems, pages 325-347, Academic Press, New York, 1980.

download
The performance of single-keyword and multiple-keyword patern matching algorithms
Bruce W. Watson 1994/00 - Technical Report
Computing Science Report 94/19, Department of Computing Science, Eindhoven University of Technology, 1994.
(show/hide) Abstract
This paper presents a toolkit of pattern matching algorithms, performance data on the algorithms, and recommendations for the selection of an algorithm (given a particular application). The pattern matching problem is: given a finite non-empty set of keywords and an input string, find all occurrences of any of the keywords in the input string. The pattern matching toolkit (written in the C programming language, and freely available) contains implementations of the Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick, and Commentz-Walter algorithms. The algorithms are implemented directly from the abstract algorithms derived and presented in the taxonomy of Watson and Zwaan [WZ92]. The toolkit provides one of the few known correct implementations of the Commentz-Walter precomputation algorithm. The performance of all of the algorithms (running on a variery of workstation hardware) was measured on two types of input: English text and genetic sequences. The input data, which is the same as that used in the benchmarks of Hume and Sunday [HS91], were chosen to be representative of two of the typical uses of pattern matching algorithms. The differences between natural language text and genetic sequences serve to highlight the strengths and weaknesses of each of the algorithms. Until now, the performance of the multiple-keyword algorithms (Aho-Corasick and Commentz-Walter) had not been extensively measured. The Knuth-Morris-Pratt and Aho-Corasick algorithms performed linearly and consistently (on widely varying keyword sets), as their theoretical running time predicts. The Commentz-Walter algorihtm (and its variants) displayed more interesting behaviour, greatly out-performing even the best Aho-Corasick variant on a large portion of the input data. The recommendations section of this paper details the conditions under which a particular algorithm should be chosen. [HS91] S.C. Hume and D. Sunday. Fast string searching. Software---Practice & Experience, 21(11):1221-1248, John Wiley & Sons, 1991. [WZ92] B. W. Watson and G. Zwaan. A taxonomy of keyword pattern matching algorithms. Computing Science Report 92/27, Department of Computing Science, Eindhoven University of Technology, 1992.

download
The design of the FIRE engine: A C++ toolkit for FInite automata and Regular Expressions
Bruce W. Watson 1994/00 - Technical Report
Computing Science Report 94/22, Department of Computing Science, Eindhoven University of Technology, 1994.
(show/hide) Abstract
This paper describes the design and implementation of version 1.2 of the FIRE engine. The FIRE engine is a C++ class library implementing finite automata and regular expression algorithms. The algorithms implemented in the toolkit are almost all of those presented in the taxonomies of finite automata algorithms [Wat93a, Wat93b]. The reader is assumed to be familiar with the two taxonomies and with advanced C++ programming techniques. The toolkit is implemented largely in an object-oriented style, with finite automata and regular expressions being defined as classes. All of the classes and functions in the toolkit are presented in the same format. For each class (or function) the format includes a short description of its behaviour, details of its implementation, and techniques for improving its performance. [Wat93a] B.W. Watson. A taxonomy of finite automata construction algorithms. Computing Science Report 93/43, Department of Computing Science, Eindhoven University of Technology, 1993. [Wat93b] B.W. Watson. A taxonomy of finite automata minimization algorithms. Computing Science Report 93/44, Department of Computing Science, Eindhoven University of Technology, 1993.

download
An introduction to the FIRE engine: A C++ toolkit for FInite automata and Regular Expressions
Bruce W. Watson 1994/00 - Technical Report
Computing Science Report 94/21, Department of Computing Science, Eindhoven University of Technology, 1994.
(show/hide) Abstract
This paper is an introduction to the programmer's interface of version 1.2 of the FIRE engine. The FIRE engine is a C++ class library implementing finite automata and regular expressions algorithms. The algorithms implemented in the toolkit are almost all of those presented in the taxonomies of finite automata algorithms [Wat93a, Wat93b]. None of the implementation details of the library are discussed---such design and implementation details are given in [Wat94]. The toolkit is unique in providing implementations of all of the known algorithms for constructing finite automata. The implementations, which were developed with efficiency in mind, are intended for use in production quality applications. No shell or graphical user-interface is provided, as the toolkit is intended for integration into applications. The implementations of the algorithms follow directly from the abstract algorithms appearing in [Wat93a, Wat93b]. As such, the toolkit also serves as an educational example of the implementation of abstract algorithms. [Wat93a] B.W. Watson. A taxonomy of finite automata construction algorithms. Computing Science Report 93/43, Department of Computing Science, Eindhoven University of Technology, 1993. [Wat93b] B.W. Watson. A taxonomy of finite automata minimization algorithms. Computing Science Report 93/44, Department of Computing Science, Eindhoven University of Technology, 1993. [Wat94] B.W. Watson. The design and implementation of the FIRE engine: A C++ toolkit for FInite automata and Regular Expressions. Computing Science Report 94/22, Department of Computing Science, Eindhoven University of Technology, 1994.

download
A taxonomy of finite automata minimization algorithms
Bruce W. Watson 1993/00 - Technical Report
Computing Science Report 93/44, Department of Computing Science, Eindhoven University of Technology, 1993.
(show/hide) Abstract
This paper presents a taxonomy of finite automata minimization algorithms. Brzozowski's elegant minimization algorithm differs from all other known minimization algorithms, and is derived separately. All of the remaining algorithms depend upon computing an equivalence relation on states. We define the equivalence relation, the partition that it induces, and its complement. Additionally, some useful properties are derived. It is shown that the equivalence relation is the greatest fixed point of an equation, providing a useful characterization of the required computation. We derive an upperbound on the number of approximation steps required to compute the fixed point. Algorithms computing the equivalence relation (or the partition, or its complement) are derived systematically in the same framework. The algorithms include Hopcroft's, several algorithms from text-books (including Hopcroft and Ullman's [HU79], Wood's [Wood87], and Aho, Sethi, and Ullman's [ASU86]), and several new algorithms or variants of existing algorithms. [ASU86] A.V. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techniques, and Tools, Addison-Wesley Publishing Co., Reading, MA, 1988. [HU79] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., Reading, MA, 1979. [Wood87] D. Wood. Theory of Computation, Harper & Row Publishers, New York, NY, 1987.

download
A taxonomy of finite automata construction algorithms
Bruce W. Watson 1993/00 - Technical Report
Computing Science Report 93/43, Department of Computing Science, Eindhoven University of Technology, 1993.
(show/hide) Abstract
This paper presents a taxonomy of finite automata construction algorithms. Each algorithm is classified into one of two families: those based upon the structure of regular expressions, and those based upon the automata-theoretic work of Myhill and Nerode. Many of the algorithms appearing in the literature are based upon the structure of regular expressions. In this paper, we make this term precise by defining regular expressions as a Sigma-term algebra, and automata constructions as various Sigma-algebras of automata. Each construction algorithm is then presented as the unique natural homomorphism from the Sigma-term algebra of regular expressions to the appropriate Sigma-algebra of automata. The concept of duality is introduced and used to derive more practical construction algorithms. In this way, we succesfully present (and relate) algorithms given by Thompson, Berry and Sethi, McNaughton and Yamada, Glushkov, and Aho, Sethi, and Ullman. Efficient implementations (including those due to Chang and Paige, and Br�ggemann-Klein) are also treated. As a side-effect we derive several new algorithms. A pair of impractical, but theoretically interesting, construction algorithms were presented by Myhill and Nerode. Some encoding techniques are used to make the algorithms practical---giving Brzozowski's algorithm based upon derivatives. DeRemer's algorithm is derived as an encoding of Brzozowski's algorithm. Two new algorithms, related to DeRemer's, are derived. Lastly, this family of algorithms is related to the first family. In addition to classifying the algorithms, we identify (and abstract from) the coding tricks and implementation details present in many of the published algorithms. This paper also presents an introduction to finite automata, Sigma-algebras, and their properties.

download
A taxonomy of keyword pattern matching algorithms
Bruce W. Watson and Gerard Zwaan 1992/00 - Technical Report
Computing Science Report 92/27, Department of Computing Science, Eindhoven University of Technology, 1992.
(show/hide) Abstract
This paper presents a taxonomy of keyword pattern matching algorithms, including the well-known Knuth-Morris-Pratt, Aho-Corasick, Boyer-Moore, and Commentz-Walter algorithms and a number of their variants. The taxonomy is based on the idea of ordering algorithms according to their essential problem and algorithm details, and deriving all algorithms from a common starting point by adding these details in a correctness preserving way. This way of presentation not only provides a complete correctness argument of each algorithm, but also makes very clear what algorithms have in common (the details of their nearest common ancestor) and where they differ (the details added after their nearest common ancestor). Moreover, the paper provides complete derivations of the intricate precomputation algorithms, some of which either can not be found in the literature (Commentz-Walter) or are given in several different versions (Boyer-Moore).