Journal Articles

download

Performance of hardcoded finite automata

Ernest Ketcha Ngassam, Derrick G. Kourie, and Bruce W. Watson 2006/04 - Journal Article

Software: Practice & Experience, 36(5):525-538, John Wiley & Sons, April 2006.

(show/hide) Abstract

We study the performance of a hardcoded algorithm for recognizing strings of a finite automaton's language and compare it with the use of the more conventional table-driven algorithm. In both cases, performance depends on the finite automaton's dimensions such as alphabet size and the number of states. However, the respective processing mechanisms that influence the performance, in particular cache memory usage, depend on the details of the processor's underlying architecture. In the hardcoded case, the automaton's dimensions determine the size of the code which is, in turn, the primary determinant of the way in which cache memory is used. In the table-driven case, cache memory usage is primarily determined by the way in which portions of the transition table are stored in it. Using statistical regression analysis, we provide multivariate equations to model the observed time efficiency of both methods. The equations obtained are cross-compared and conclusions are drawn.

download

A framework for the dynamic implementation of finite automata for perfomance enhancement

Ernest Ketcha Ngassam, Bruce W. Watson, and Derrick G. Kourie 2005/12 - Journal Article

International Journal of Foundations of Computer Science, 16(6):1193-1206, World Scientific, December 2005.

(show/hide) Abstract

The aim of this work is to provide a model for the dynamic implementation of finite automata for enhanced performance. Investigations have shown that hardcoded finite automata outperforms the traditional table-driven implementation up to some threshold. Moreover, the kind of string being recognized plays a major role in the overall processing speed of the string recognizer. Various experiments are depicted to show when the advantages of using hardcoding as basis for implementing finite automata (instead of using the classical table-driven approach) become manifest. The model, a dynamic algorithm that combines both hardcoding and table-driven is introduced.

download

TAxonomy-BAsed Software COnstruction of SPARE Time: A Case Study

Loek Cleophas and Bruce W. Watson 2005/02 - Journal Article

IEE Proceedings Software, 152(1):29-37, IEE, February 2005.

(show/hide) Abstract

In this paper, we 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. We discuss the aims of TABASCO and of taxonomy construction and taxonomy-based toolkit design in particular. We 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 non-commercial use.

download

SPARE Parts: a C++ toolkit for string pattern recognition

Bruce W. Watson and Loek Cleophas 2004/06 - Journal Article

Software: Practice & Experience, 34(7):697-710, John Wiley & Sons, June 2004.

(show/hide) Abstract

In this paper, we consider the design and implementation of SPARE Parts, a C++ toolkit for pattern matching. SPARE Parts (in particular, the 2003 version presented in this article) is the second generation string pattern matching toolkit by the authors. The toolkit, the first generic program for keyword pattern matching, contains implementations of the well-known Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick and Commentz-Walter algorithms (and their variants).

download

Reducing memory requirements in reachability-based finite automata operations

Bruce W. Watson 2004/03 - Journal Article

Software: Practice & Experience, 34(3):239-248, John Wiley & Sons, March 2004.

(show/hide) Abstract

New applications of finite automata, such as computational linguistics and asynchronous circuit simulation, can require automata of millions or even billions of states. All known construction methods (in particular, the most effective reachability-based ones that save memory, such as the subset construction, and simultaneously minimizing constructions, such as Brzozowski's) have intermediate memory usage much larger than the final automaton, thereby restricting the maximum size of the automata which can be built. In this paper, I present a reachability-based optimization which can be used in most of these construction algorithms to reduce the intermediate memory requirements. The optimization is presented in conjunction with an easily understood (and implemented) canonical automaton construction algorithm.

download

A new algorithm for the construction of minimal acyclic DFAs

Bruce W. Watson 2003/08 - Journal Article

Science of Computer Programming, 48(2-3):81-97, Elsevier Science, August/September 2003.

(show/hide) Abstract

We present a semi-incremental algorithm for constructing minimal acyclic deterministic finite automata. Such automata are useful for storing sets of words for spell-checking, among other applications. The algorithm is semi-incremental because it maintains the automaton in nearly minimal condition and requires a final minimization step after the last word has been added (during construction). The algorithm derivation proceeds formally (with correctness arguments) from two separate algorithms, one for minimization and one for adding words to acyclic automata. The algorithms are derived in such a way as to be combinable, yielding a semi-incremental one. In practice, the algorithm is both easy to implement and displays good running time performance.

download

A Boyer-Moore-style algorithm for regular expression pattern matching

Bruce W. Watson and Richard E. Watson 2003/08 - Journal Article

Science of Computer Programming, 48(2-3):99-117, Elsevier Science, August/September 2003.

(show/hide) Abstract

This paper presents a Boyer-Moore-type algorithm for regular expression pattern matching, answering an open problem posed by Aho in 1980 (Pattern Matching in Strings, Academic Press, New York, 1980, p. 342). The new algorithm handles patterns specified by regular expressions-a generalization of the Boyer-Moore and Commentz-Walter algorithms. 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. In certain cases, the Boyer-Moore (respectively Commentz-Walter) algorithm has greatly outperformed the Knuth-Morris-Pratt (respectively Aho-Corasick) algorithm (as discussed by Watson in his Ph.D. Thesis, Eindhoven University of Technology, September 1995, and in: N. Ziviani, R. Baeza-Yates, K. Guimaraes (Eds.), Proc. Third South American Workshop on String Processing, International Informatics Series, vol. 4, Carleton University Press, Recife, Brazil, 1996, pp. 280-294). In testing, the algorithm presented in this paper also frequently outperforms the regular expression generalization of the Aho-Corasick algorithm.

A new family of string pattern matching algorithms

Bruce W. Watson and Richard E. Watson 2003/07 - Journal Article

South African Computer Journal, 30:34-41, Computer Society of South Africa and South African Institute of Computer Scientists, July 2003

(show/hide) Abstract

Even though the field of pattern matching has been well studied, there are still many interesting algorithms to be discovered. In this paper, we present a new family of single keyword pattern matching algorithms. We begin by deriving a common ancestor algorithm, which navely solves the problem. Through a series of correctness preserving predicate strengthenings, and implementation choices, we derive efficient variants of this algorithm. This paper also presents one of the first algorithms which could be used to do a minimal number of match attempts within the input string (by maintaining as much information as possible from each match attempt).

A new family and structure for Commentz-Walter-style multiple-keyword pattern matching algorithms

Bruce W. Watson 2003/07 - Journal Article

South African Computer Journal, 30:29-33, Computer Society of South Africa and South African Institute of Computer Scientists, July 2003

(show/hide) Abstract

In this paper, I present a new family of Commentz-Walter-style multiple-keyword string pattern matching algorithms. The algorithms share a common algorithmic skeleton, which is significantly optimized when compared to the original Commentz- Walter skeleton and subsequently derived improvements. The new skeleton is derived via correctness-preserving stepwise algorithmic improvements, in the Eindhoven style of programming.

download

A new regular grammar pattern matching algorithm

Bruce W. Watson 2003/04 - Journal Article

Theoretical Computer Science, 299(1-3):509-521, Elsevier Science, April 2003.

(show/hide) Abstract

This paper presents a Boyer Moore type algorithm for regular grammar pattern matching, answering a variant of an open problem posed by Aho (Pattern Matching in Strings, Academic Press, New York, 1980, p. 342). The new algorithm handles patterns specified by regular (left linear) grammars - a generalization of the Boyer Moore (single keyword) and Commentz-Walter (multiple keyword) algorithms. Like the Boyer Moore and Commentz-Walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. The precomputation functions are derived, and it is shown that they can be obtained from Commentz-Walter's d1 and d2 shift functions. In most cases, the Boyer Moore (respectively, Commentz-Walter) algorithm has greatly outperformed the Knuth-Morris-Pratt (respectively, Aho-Corasick) algorithm. In practice, an earlier version of the algorithm presented in this paper also frequently outperforms the regular grammar generalization of the Aho-Corasick algorithm.

download

An Efficient Incremental DFA Minimization Algorithm

Bruce W. Watson and Jan Daciuk 2003/03 - Journal Article

Journal of Natural Language Engineering, 9(1):49-64, Cambridge University Press, March 2003.

(show/hide) Abstract

In this paper, we present a new Deterministic Finite Automata (DFA) minimization algorithm. The algorithm is incremental - it may be halted at any time, yielding a partially-minimized automaton. All of the other (known) minimization algorithms have intermediate results which are not useable for partial minimization. Since the first algorithm is easily understood but inefficient, we consider three practical and effective optimizations. The first two optimizations do not affect the asymptotic worst-case running time - though they perform well on a large class of automata. The third optimization yields an quadratic-time algorithm which is competitive with the previously known ones.

Directly constructing minimal DFAs: combining two algorithms by Brzozowski

Bruce W. Watson 2002/12 - Journal Article

South African Computer Journal, 29:17-23, Computer Society of South Africa and South African Institute of Computer Scientists, December 2002

(show/hide) Abstract

In this paper, we combine (and refine) two of Brzozowski's algorithms - yielding a single algorithm which constructs aminimal deterministic finite automaton (DFA) from a regular expression.

download

A Fast and Simple Algorithm for Constructing Minimal Acyclic Deterministic Finite Automata

Bruce W. Watson 2002/02 - Journal Article

Journal of Universal Computer Science, 8(2), Know-Center, Springer, Joanneum Research and IICM, Graz University of Technology, February 2002

(show/hide) Abstract

In this paper, we present a fast and simple algorithm for constructing a minimal acyclic deterministic finite automaton from a denite set of words. Such automata are useful in a wide variety of applications, including computer virus detection, computational linguistics and computational genetics. There are several known algorithms that solve the same problem, though most of the alternative algorithms are considerably more difficult to present, understand and implement than the one given here. Preliminary benchmarking indicates that the algorithm presented here is competitive with the other known algorithms.

A taxonomy of algorithms for constructing minimal acyclic deterministic finite automata

Bruce W. Watson 2001/08 - Journal Article

South African Computer Journal, 27:12-17, Computer Society of South Africa and South African Institute of Computer Scientists, August 2001

(show/hide) Abstract

In this paper, we present a taxonomy of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs). Such automata represent finite languages and are therefore useful in applications such as storing words for spell-checking, computer and biological virus searching, text indexing and XML tag lookup. In such applications, the automata can grow extremely large (with more than 10^6 states) and are difficult to store without compression or minimization. The taxonomization method arrives at all of the known algorithms, and some which are likely new ones (though proper attribution is not always possible, since the algorithms are usually of commercial value and some secrecy frequently surrounds the identities of the original authors).

Incremental Construction of Minimal Acyclic Finite-State Automata

Jan Daciuk, Stoyan Mihov, Bruce W. Watson, and Richard E. Watson 2000/04 - Journal Article

Computational Linguistics, 26(1):3-16, MIT Press, April 2000

(show/hide) Abstract

In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings. Traditional methods consist of two phases: the first to construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering of the input strings. Our method is fast and significantly lowers memory requirements in comparison to other methods.

Implementing and using finite automata toolkits

Bruce W. Watson 1996/12 - Journal Article

Journal of Natural Language Engineering, 2(4):295-302, Cambridge University Press, December 1996.

download

A taxonomy of sublinear multiple keyword pattern matching algorithms

Bruce W. Watson and Gerard Zwaan 1996/09 - Journal Article

Science of Computer Programming, 27(2):85-118, Elsevier Science, September 1996.