A fast algorithm for order-preserving pattern matching

•We present a new method of deciding the order-isomorphism between two strings.•We show that the bad character rule can be applied to the OPPM problem.•We present a space-efficient algorithm computing the shift table for text search.•We present a linear-time algorithm for an integer alphabet in the...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2015-02, Vol.115 (2), p.397-402
Main Authors: Cho, Sukhyeun, Na, Joong Chae, Park, Kunsoo, Sim, Jeong Seop
Format: Article
Language:English
Subjects:
Algorithms
Analysis of algorithms
Data processing
Horspool algorithm
KMP algorithm
Matching
Mathematical problems
Order-isomorphism
Order-preserving pattern matching
Running
Searching
Strings
Studies
Tables
Texts
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We present a new method of deciding the order-isomorphism between two strings.•We show that the bad character rule can be applied to the OPPM problem.•We present a space-efficient algorithm computing the shift table for text search.•We present a linear-time algorithm for an integer alphabet in the worst case. Given a text T and a pattern P, the order-preserving pattern matching (OPPM) problem is to find all substrings in T which have the same relative orders as P. The OPPM has been studied in the fields of finding some patterns affected by relative orders, not by their absolute values. In this paper, we present a method of deciding the order-isomorphism between two strings even when there are same characters. Then, we show that the bad character rule of the Horspool algorithm for generic pattern matching problems can be applied to the OPPM problem and we present a space-efficient algorithm for computing shift tables for text search. Finally, we combine our bad character rule with the KMP-based algorithm to improve the worst-case running time. We give experimental results to show that our algorithm is about 2 to 6 times faster than the KMP-based algorithm in reasonable cases.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2014.10.018