python - 在列表列表中查找前 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 中位置(或i=M+1位置，或i=M+2位置，...，i=L位置) 然后我们统计长度为M的子序列，其中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
]

当然，我们想要的是频率最高的 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 的各种组合执行此类分析的有效算法或相关研究领域？

Answer 1

这是一个基于 generalized suffix tree 的想法结构体。您的列表列表可以看作是字符串列表，其中字母表将由整数组成(因此字母表中大约有 10k 个字符以及您提供的信息)。
广义后缀树的构造是在线性时间 w.r.t 字符串长度内完成的，因此这应该不是问题，因为在任何情况下，您都必须在某个时候遍历您的列表。

首先，将所有字符串存储在后缀树中。这需要对结构进行 2 次小调整。
您需要记录某个后缀出现的次数，因为您的最终目标是找到符合某些属性的最常见子序列。

然后，您还需要一个来自(i, d) 的查找表(其中i 是您要查找的整数、目标，以及d 是树中的深度，M) 到后缀链接的节点集，这些节点标有“字母”i(你的字母表不是由字符组成，而是由整数组成)，位于 d 深度。可以通过遍历您的后缀链接(BFS 或 DFS)来构建此查找表。您甚至可以只存储对应于最高计数器值的节点。

从那里开始，对于某些查询 (target, M)，您将首先查看查找表，然后在树中找到具有最高计数器值的节点。这将对应于列表列表中最常遇到的“后缀”(或子序列)。

实现非常复杂，因为广义后缀树不是一个简单的结构(根本)，并且正确地实现它并进行修改并不是一件容易的事。但我认为这将允许非常有效的查询时间。

对于后缀树的实现，我建议你只阅读原始论文，直到你对它们有深入而真实的理解(比如 this 或 that ， sc*-h*b 可以是你的 friend )关于这个问题，而不是在线的“解释”，充满了近似和错误(甚至 this post 可以帮助您获得第一个想法，但如果您的目标是实现正确的版本，在某些时候会误导您).