Pattern Matching

Gonzalo Navarro

Journal of Applied Statistics, 2004, vol. 31, issue 8, 925-949

Abstract: An important subtask of the pattern discovery process is pattern matching, where the pattern sought is already known and we want to determine how often and where it occurs in a sequence. In this paper we review the most practical techniques to find patterns of different kinds. We show how regular expressions can be searched for with general techniques, and how simpler patterns can be dealt with more simply and efficiently. We consider exact as well as approximate pattern matching. Also we cover both sequential searching, where the sequence cannot be preprocessed, and indexed searching, where we have a data structure built over the sequence to speed up the search.

Keywords: Regular expressions; automata; back tracking; suffix trees and arrays; approximate string matching; bit parallelism (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.tandfonline.com/doi/abs/10.1080/0266476042000270527 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:japsta:v:31:y:2004:i:8:p:925-949

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/CJAS20

DOI: 10.1080/0266476042000270527

Access Statistics for this article

Journal of Applied Statistics is currently edited by Robert Aykroyd

More articles in Journal of Applied Statistics from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().