Example
\(
\def\sa#1{\tt{#1}}
\)
$$\sa{5}\;\sa{2}\;\sa{9}\;\sa{4}\;\sa{3}\ \approx\ \sa{6}\;\sa{1}\;\sa{7}\;\sa{5}\;\sa{2},$$
which shows in particular their central value is the largest in both words.
For example, the word $\sa{5}\;\sa{2}\;\sa{9}\;\sa{4}\;\sa{3}$ appears
equivalently at position $1$ on
$$\sa{4}\;\underline{\sa{6}\;\sa{1}\;\sa{7}\;\sa{5}\;\sa{2}}\;\sa{9}
\;\sa{8}\;\sa{3}$$
but nowhere else.
For instance, it does not appear at position $4$ because $5\lt8$,
while in the pattern the corresponding values satisfy $5\gt 4$.
|
Problem 31: Order-Preserving Patterns
|
|
Searching time series or list of values for patterns representing specific
fluctuations of the values requires a redefinition of the notion of pattern.
The question is to deal with the recognition of peaks, breakdowns, double-dip
recessions or more features on expenses, rates or the like.
In the problem we consider words drawn from a linear-sortable alphabet
$\Sigma$ of integers.
Two words $u$ and $v$ of the same length over $\Sigma$ are said to be
order-equivalent written $u \approx v$, if
$$u[i] \lt u[j]\Longleftrightarrow v[i] \lt v[j]$$
for all pairs of positions $i,j$ on the words.
The order-preserving pattern-matching problem
is naturally defined as follows: given a pattern $x\in\Sigma^*$ and a text
$y\in\Sigma^*$, check if $x$ is order-equivalent to some factor of $y$.
For simplicity we assume that letters in each considered word are
pairwise distinct (words are permutations of their set of letters).
Design a linear-time algorithm for the order-preserving pattern-matching.
Design a notion of border table adequate to the problem.
References
S. Cho, J. C. Na, K. Park, and J. S. Sim. A fast algorithm for orderpreserving
pattern matching. Inf. Process. Lett., 115(2):397-402, 2015.
M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, A. Langiu,
S. P. Pissis, J. Radoszewski, W. Rytter, and T. Walen. Order-preserving
indexing. Theor. Comput. Sci., 638:122-135, 2016.
P. Gawrychowski and P. Uznanski. Order-preserving pattern matching
with k mismatches. In A. S. Kulikov, S. O. Kuznetsov, and P. A.
Pevzner, editors, Combinatorial Pattern Matching - 25th Annual Symposium,
CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings,
volume 8486 of Lecture Notes in Computer Science, pages 130-139.
Springer, 2014.
M. M. Hasan, A. S. M. S. Islam, M. S. Rahman, and M. S. Rahman. Order
preserving pattern matching revisited. Pattern Recognition Letters,
55:15-21, 2015.
J. Kim, P. Eades, R. Fleischer, S. Hong, C. S. Iliopoulos, K. Park, S. J.
Puglisi, and T. Tokuyama. Order-preserving matching. Theor. Comput.
Sci., 525:68-79, 2014.
M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, and T. Walen.
A linear time algorithm for consecutive permutation pattern matching.
Inf. Process. Lett., 113(12):430-433, 2013.
