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

Question

如果这个问题是可用问题的重复，我们深表歉意。还没有找到我正在寻找的东西。

我对检测字符串/数组中的模式很感兴趣，例如 ABCABCABCABC，它同样可以用整数编码。我的应用程序是这样的，我正在使用流式传感器，其中上述序列中的每个字母都是一个传感器(例如 A 是一个传感器)。由于传感器故障等原因，我的序列并不总是周期性/重复的。他们可以像这样出来，例如BCABCABCAB 或 ABCBCBCA 因为各种失败。

我的应用程序变得更加困难，因为我先验地不知道我的数据集中有多少传感器，所以我需要一种算法从序列中推断出该数字(如上面给出的那些)。唉，该算法应该为所有给定的示例生成 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)

但这似乎效率很低，因为我必须多次 reshape 数组(并且可能需要很多次，因为我的序列很长，回想一下，我事先不知道我的重复序列的长度是3)，然后每次运行Counter来评估出现(或不出现)模式的规律性。

其他想法包括使用 Knuth-Morris-Pratt 算法以及 n-gram 或它们的某种组合。或者计算后缀树。

有没有更好的办法？

编辑

更多详情:

• 数据大小:长度在 1000 到 1000000 ish 之间的序列(尽管上限不太可能)
• 子序列不能有重复条目，它们必须是唯一的。 IE。子序列不能是 ABB。原因很简单；最终，我对每个传感器的时间演化感兴趣。

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)