4
$\begingroup$

This is more of a "what technology/library would you use for this?" question than anything else.

I have categorical time series data, and need to match cases in these time series to known patterns. For example, State A, followed by State B within six months, followed by multiple periods of State A, followed by an optional period of State B, followed by State C.

It's quite hard to interrogate e.g. an SQL database or pandas dataframe for sequences of rows that match a pattern like this. How you'd do this "in theory" is build a pattern-matching finite state machine, but I didn't know a relevant library for one. Then I realised I've been using pattern-matching finite state machines for years in the form of regular expressions.

So, what I've been doing is converting my time series to strings, defining my pattern as a regex, and matching them that way. It works extraordinarily well. In spite of this, it feels hacky. Surely there should be some proper way to do this.

Is there? What technology/data structure/library would let me define finite automata for time series and match them based on that definition?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Not sure about the technology - but maybe the concept of the SAX transformation will be useful. $\endgroup$
    – yoav_aaa
    Commented Oct 29, 2018 at 11:52
  • $\begingroup$ What you are describing sounds like a convolution filter to me, in which case you could use np.convolve. $\endgroup$
    – S van Balen
    Commented Aug 9, 2019 at 15:03

1 Answer 1

Reset to default
1
$\begingroup$

If you need optional parts in the pattern then regular expressions were specifically built for those kind of problems. You could probably speed up regular expressions by using loops in Cython, but the time spent programming it is not really worth it.

If your pattern is fixed then there are faster ways to do pattern matching. OpenCV uses Descrete Fourier Transformation to match a template. It is very fast and is available for Python and C++. It is optimized to work with 2D images, and can also work with 32 bit floats. How DFT works

Documentation for template matching in OpenCV

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.