B. W. Watson and G. Zwaan. A taxonomy of keyword pattern matching algorithms. In H. A. Wijshoff, editor, Proceedings Computing Science in the Netherlands 93, pages 25--39, SION, Stichting Mathematish Centrum, 1993.  @ NUS  Home/Search   Document Details and Download   Summary   Related Articles   Check

....scans the text from left to right) This agreement is not accidentally, our approach arose during the research project A Taxonomy of Scanner Algorithms . The intention of this project is to clarify the relationship between solutions to the scanning problem by giving a generic derivation, see [19]. Acknowledgements Much of the material presented above arose from the imperative approach of the scannerclub of Eindhoven University in which Bruce Watson and Gerard Zwaan were very active. I am grateful to Jaap van der Woude for his support on the transformational side of the material. The ....

B.W.Watson and G.Zwaan. A taxonomy of keyword pattern matching algorithms. Computing Science Note 92/27, Eindhoven University of Technology. The Netherlands,

....of the algorithms and their descriptions that tend to be rather involved and verbal it is hard to get a good overview and to make a sound comparison between algorithms. In order to fulfill these needs a taxonomy of keyword pattern matching algorithms was presented by Watson and Zwaan in [WZ92, WZ93]. Here, we focus our attention on a part of that taxonomy containing a family of multiple keyword pattern matching algorithms that have a matching time that may be sublinear in the length of the input string (taking the number of symbol comparisons as a measure of matching time) Amongst others, ....

....in a uniform way. This includes formal derivations of the precomputation algorithms for the Boyer Moore algorithm, the Commentz Walter algorithm and the algorithm presented by Fan and Su not yet found in the literature. The taxonomy given here differs from the corresponding part of the taxonomy in [WZ92, WZ93] in that we here present the correct multiple keyword generalization of the Boyer Moore algorithm 1 Introduction rt 2.4 2.5 3.1 x3.8 x3.1 [FS93, FS94] okw ssd nlau olau opt bmcw x3.2 x3.3 x3.4 x3.5 x3.4 x3.6 x3.7 [BM77] nla cw bm cw bm [CW79a, CW79b] p s 2.1 2.2 [KMP77, AC75] Figure ....

[Article contains additional citation context not shown here]

Bruce W. Watson and Gerard Zwaan. A taxonomy of keyword pattern matching algorithms. In H.A. Wijshoff, editor, Proceedings Computing Science in the Netherlands 93, pages 25--39. SION, Stichting Mathematisch Centrum, November 1993.

....of the algorithms and their descriptions that tend to be rather involved and verbal it is hard to get a good overview and to make a sound comparison between algorithms. In order to fulfill these needs a taxonomy of keyword pattern matching algorithms was presented by Watson and Zwaan in [WZ92, WZ93]. Here, we focus our attention on a part of that taxonomy containing a family of multiple keyword pattern matching algorithms that have a matching time that may be sublinear in the length of the input string (taking the number of symbol comparisons as a measure of matching time) Amongst others, ....

....in a uniform way. This includes formal derivations of the precomputation algorithms for the Boyer Moore algorithm, the Commentz Walter algorithm and the algorithm presented by Fan and Su not yet found in the literature. The taxonomy given here differs from the corresponding part of the taxonomy in [WZ92, WZ93] in that we here present the correct multiple keyword generalization of the Boyer Moore algorithm 1 Introduction rt 2.4 2.5 3.1 x3.8 x3.1 [FS93, FS94] okw ssd nlau olau opt bmcw x3.2 x3.3 x3.4 x3.5 x3.4 x3.6 x3.7 [BM77] nla cw bm cw bm [CW79a, CW79b] p s 2.1 2.2 [KMP77, AC75] Figure ....

[Article contains additional citation context not shown here]

Bruce W. Watson and Gerard Zwaan. A taxonomy of keyword pattern matching algorithms. Computing Science Notes 92/27, Eindhoven University of Technology, Eindhoven, the Netherlands, December 1992. The report is available at URL ftp://ftp.win.tue.nl/pub/techreports/pi/pattm/taxonomy/1st.edition/pattm.ps.gz.

....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 variety of workstation hardware) was measured on two types of input: English text and genetic sequences. The input data, which ....

....time involved in pattern matching usually far outweighs the time involved in precomputation, the performance of the precomputation algorithms is not discussed in this paper. The problem, and algorithms solving it, are discussed in detail in the taxonomy of pattern matching algorithms appearing in [WZ92]. The taxonomy concentrates on the systematic derivation (with correctness arguments) of several pattern matching algorithms and their associated precomputation algorithms. Given the algorithm derivations appearing in the taxonomy, the C versions of the algorithms were easily developed. The ....

[Article contains additional citation context not shown here]

Watson, B.W. and G. Zwaan. "A taxonomy of keyword pattern matching algorithms, " Computing Science Note 92/27, Eindhoven University of Technology, The Netherlands, 1992.

No context found.

B. W. Watson and G. Zwaan. A taxonomy of keyword pattern matching algorithms. In H. A. Wijshoff, editor, Proceedings Computing Science in the Netherlands 93, pages 25--39, SION, Stichting Mathematish Centrum, 1993.

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.