在潜在不规则字符串/数组中查找最常见重复模式的算法

Question

如果此问题重复了可用问题，则表示歉意。还没有找到一个正是我要找的。

我感兴趣的是检测字符串/数组中的模式，例如abcabc，在这些字符串/数组中，这些模式同样可以用整数编码。我的应用程序是这样的，我正在使用流式传感器，其中上述序列中的每个字母都是一个传感器（例如，A是一个传感器）。由于传感器故障等原因，我的序列并不总是非常定期/重复。由于各种故障，它们可能会像这样出现，例如bcabcabca或abcbca。

我的应用程序变得更加困难，因为我事先不知道我的数据集中有多少个传感器，所以我需要一个算法来从序列中推断出那个数字（就像上面给出的那样）。唉，对于所有给定的示例，算法应该产生ABC，因为这是最长和最常见的模式。

我的一个想法是简单地说：

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)

但这似乎效率很低，因为我必须多次（而且可能多次，因为我的序列很长，回想起来，我事先不知道重复序列的长度是3），然后每次运行计数器，以评估出现（或不出现）模式的规律性。

其他想法包括使用Knuth–Morris–Pratt算法以及n-grams或其组合。或者计算后缀树。

有更好的办法吗？

编辑

更多详情：

• 数据大小：长度在1000到1000000 ish之间的序列（尽管上限不太可能）

Answer 1

好的，所以我想出了这个，请尝试打破它。

from nltk import ngrams
from iteration_utilities import all_monotone

def find_longest_monotonic_increasing_ngram(seq):
    # Store stats
    gram_stats = {}
    # Find longest common subsequence / n-gram
    M = []
    for m in range(1,int(0.2*len(seq))):
        gram = Counter(ngrams(seq, m)).most_common()[0]
        # Check if gram is monotonically increasing (i.e. is it sorted)
        if all_monotone(gram[0],strict=True,decreasing=False):
            gram_stats[m] = gram
            M.append(m)

    return max([gram_stats[m][0] for m in M], key=len)

MWE：

A = np.tile([1,2,3], 30)
# Mess up
A = np.insert(A,0,[1,2]) # One missing sensor at t = start
A = np.append(A,1) # two missing sensors at t = final
A[50] = 2 # Missed sensor reading at t=50 
# Run
find_longest_monotonic_increasing_ngram(A)
>>> (1, 2, 3)