A pattern matching problem
Developing software involves solving an indefinite number of small pattern matching problems. Recently I had to find a simple way to match a specific pattern of heartbeats in a parsed ECG signal.
The problem can be reduced to this: Return the number of occurrences of a pattern, say
[4,5,6], in a longer sequence, such as
I’m sure this problem has been solved a millions times over in computing history. But, besides regular expressions (which deals with text strings), I didn’t find a straightforward solution in Python’s standard library.
Looking for a solution, I came across Stack Overflow (SO) where someone else, having the same problem, posted it as a question. The accepted answer outlined an algorithm, but didn’t provide any code.
Therefore, I came up with my own solution, which I posted on SO, and repeat here (Python code):
import itertools def pattern_match(pattern, sequence): """Count the number of times that pattern occurs in the sequence. """ pattern = tuple(pattern) k = len(pattern) # create k iterators for the sequence i = itertools.tee(sequence, k) # advance the iterators for j in range(k): for _ in range(j): next(i[j]) count = 0 for q in zip(*i): if pattern == q: count += 1 return count
Here is a Gist solving the example problem above, which was posed in the SO question.
If you are curious, the answer is 4.