Automaton-based sublinear keyword pattern matching

L.G.W.A. Cleophas, B.W. Watson, G. Zwaan

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
2 Downloads (Pure)


We show how automaton-based sublinear keyword pattern matching (skpm) algorithms appearing in the literature can be seen as different instantiations of a general automaton-based skpm algorithm skeleton. Such algorithms use finite automata (FA) for efficient computation of string membership in a certain language. The algorithms were formally derived as part of a new skpm algorithm taxonomy, based on an earlier suffix-based skpm algorithm taxonomy [1]. Such a taxonomy is based on deriving the algorithms from a common starting point by successively adding algorithm and problem details and has a number of advantages. It provides correctness arguments, clarifies the working of the algorithms and their interrelationships, helps in implementing the algorithms, and may lead to new algorithms being discovered by finding gaps in the taxonomy. We show how to arrive at the general algorithm skeleton and derive some instantiations, leading to well-known factor- and factor oracle-based algorithms. In doing so, we show the shift functions used for them can be (strengthenings of) shift functions used for suffix-based algorithms. This also results in a number of previously undescribed factor-based skpm algorithm variants, whose performance remains to be investigated.
Original languageEnglish
Title of host publicationString Processing and Information Retrieval (Proceedings 11th International Conference, SPIRE 2004, Padova, Italy, October 5-8, 2004)
EditorsA. Apostolico, M. Melucci
Place of PublicationBerlin
ISBN (Print)3-540-23210-9
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Automaton-based sublinear keyword pattern matching'. Together they form a unique fingerprint.

Cite this