Ftyjtk

Apologies if this question is a repeat of available questions. Haven't found one that's quite what I am looking for.

I am interested in detecting patterns in strings/arrays such as ABCABCABCABC where this could equally well be encoded by integers. My application is such that I am working with streaming sensors where each letter in the aforementioned sequence would be one sensor (e.g. A is a sensor). Because of sensor failure and whatnot, my sequences are not always quite periodic/repeating. They can come out like this e.g. BCABCABCAB or ABCBCBCA because of various failures.

My application is made harder because a priori I do not know how many sensors there are in my dataset so I require an algorithm to infer that number from the sequence (like those given above). Alas, the algorithm should yield ABC for all the given examples, as this is the longest and most common pattern.

One idea I had was simply to something like:

import numpy as np

from collections import Counter



# ABCABCABCABC encoded with integers 

A = np.array(

  [[ 1 ,2, 3],

   [ 1 ,2, 3],

   [ 1 ,2, 3],

   [ 1 ,2, 3]])



c = Counter(map(tuple, A)).most_common()[0]



# ((1,2,3), 4)

But this seems rather inefficient as I would have to reshape the array multiple times (and a potentially lot of times, since my sequences are very long and, recall, I do not know a priori that the length of my repeating sequence is 3), and then run Counter each time to assess the regularity of an appearing (or not) pattern.

Other ideas including using the Knuth–Morris–Pratt algorithm along with n-grams or some combination thereof. Alternatively calculating the suffix tree.

Is there a better way?

EDIT

More details:

• Size of data: sequences of length between 1000 and 1000000 ish (though the upper bound is quite unlikely)


• Sub-sequences cannot have repeated entries, they have to be unique. I.e. a sub-sequence cannot be ABB. The reason is quite simple; ultimately I am interested in the temporal evolution of each individual sensor.