algorithm - 在十亿序列列表中查找前 N 个最频繁的数字序列

Question

假设我有以下列表:

x = [[1, 2, 3, 4, 5, 6, 7],  # sequence 1
     [6, 5, 10, 11],  # sequence 2
     [9, 8, 2, 3, 4, 5],  # sequence 3
     [12, 12, 6, 5],  # sequence 4
     [5, 8, 3, 4, 2],  # sequence 5
     [1, 5],  # sequence 6
     [2, 8, 8, 3, 5, 9, 1, 4, 12, 5, 6],  # sequence 7
     [7, 1, 7, 3, 4, 1, 2],  # sequence 8
     [9, 4, 12, 12, 6, 5, 1],  # sequence 9
]

本质上，对于包含目标编号 5 的任何列表(即 target=5 )列表中的任何位置，顶部的 N=2 是什么长度为 M=4 的最常观察到的子序列？

那么，条件是:

1. 如果target列表中不存在，那么我们完全忽略该列表
2. 如果列表长度小于M然后我们完全忽略这个列表
3. 如果列表的长度正好是M但是target不在 Mth 中位置然后我们忽略它(但如果 target 在 Mth 位置我们计算它)
4. 如果列表长度，L , 长于 M和 target在i=M位置(or i=M+1 position, or i=M+2 position, ...,我=L position) then we count the subsequence of length男where target`在子序列的最后位置

因此，使用我们的列表列表示例，我们将计算以下子序列:

subseqs = [[2, 3, 4, 5],  # taken from sequence 1
           [2, 3, 4, 5],  # taken from sequence 3
           [12, 12, 6, 5],  # taken from sequence 4
           [8, 8, 3, 5],  # taken from sequence 7
           [1, 4, 12, 5],  # taken from sequence 7
           [12, 12, 6, 5],  # taken from sequence 9
]

当然我们要的是top N=2按频率的子序列。所以，[2, 3, 4, 5]和 [12, 12, 6, 5]是计数前两个最频繁的序列。如果N=3那么所有子序列 ( subseqs ) 都将被返回，因为第三个并列。

重要

这是 super 简化的，但实际上，我的实际序列列表

1. 由数十亿个正整数列表(1 到 10,000 之间)组成
2. 每个列表可以短至 1 个元素，也可以长至 500 个元素
3. N和 M可以小到 1 也可以大到 100

我的问题是:

1. 假设 N 是否有一种高效的数据结构可以实现快速查询？和 M总是小于 100？
2. 是否有已知算法可以对 N 的各种组合执行此类分析？和 M ？我看过后缀树，但我必须推出自己的自定义版本才能接近我的需要。
3. 对于同一个数据集，我需要重复查询数据集以获取 target 的各种值或不同组合, N , 和 M (其中 target <= 10,000、N <= 100 和 `M <= 100)。我怎样才能有效地做到这一点？

Answer 1

扩展我的评论。这是一个草图，您可以如何使用开箱即用的后缀数组来解决这个问题:

1) 使用停止符号反转并连接您的列表(我在这里使用 0)。

[7, 6, 5, 4, 3, 2, 1, 0, 11, 10, 5, 6, 0, 5, 4, 3, 2, 8, 9, 0, 5, 6, 12, 12, 0, 2, 4, 3, 8, 5, 0, 5, 1, 0, 6, 5, 12, 4, 1, 9, 5, 3, 8, 8, 2, 0, 2, 1, 4, 3, 7, 1, 7, 0, 1, 5, 6, 12, 12, 4, 9]

2) 构建一个 suffix array

[53, 45, 24, 30, 12, 19, 33, 7, 32, 6, 47, 54, 51, 38, 44, 5, 46, 25, 16, 4, 15, 49, 27, 41, 37, 3, 14, 48, 26, 59, 29, 31, 40, 2, 13, 10, 20, 55, 35, 11, 1, 34, 21, 56, 52, 50, 0, 43, 28, 42, 17, 18, 39, 60, 9, 8, 23, 36, 58, 22, 57]

3) 构建 LCP array . LCP 数组会告诉您一个后缀与其在后缀数组中的邻居有多少个相同的数字。但是，遇到停止符号需要停止计数

[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 2, 1, 1, 0, 2, 1, 1, 2, 0, 1, 3, 2, 2, 1, 0, 1, 1, 1, 4, 1, 2, 4, 1, 0, 1, 2, 1, 3, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 2, 1, 2, 0]

4) 当查询出现时 (target = 5, M= 4)，您在后缀数组中搜索目标的第一次出现并扫描相应的 LCP 数组，直到后缀的起始数量发生变化。下面是LCP数组中对应所有以5开头的后缀的部分。

[..., 1, 1, 1, 4, 1, 2, 4, 1, 0, ...]

这告诉您有两个长度为 4 的序列出现了两次。使用索引刷过一些细节，您可以找到序列并将它们还原以获得最终结果。

复杂性

• 建立后缀数组是O(n)，其中n是所有列表中元素的总数和O(n)的空间
• 构建LCP阵列在时间和空间上也是O(n)
• 在后缀中搜索一个目标数，平均时间复杂度为O(log n)
• 扫描相关子序列的成本与目标出现的次数成线性关系。根据您给定的参数，这应该是平均数的 1/10000。

前两个步骤离线进行。查询在技术上是 O(n)(由于第 4 步)但有一个小常数 (0.0001)。