如果这个问题是可用问题的重复,我们深表歉意。还没有找到我正在寻找的东西。
我对检测字符串/数组中的模式很感兴趣,例如 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
。原因很简单;最终,我对每个传感器的时间演化感兴趣。
最佳答案
好的,我想到了这个,请尝试打破它。
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)
关于python - 在可能不规则的字符串/数组中查找最常见重复模式的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53371043/