时间戳

首页 > 解决方案 > 在列表列表中查找前 N 个最频繁的数字序列

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

问题描述

假设我有以下列表：

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位置(ori=M+1 position, ori=M+2 position, ...,i=L position) then we count the subsequence of lengthMwhere目标`在子序列的最后位置

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

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) 将被返回，因为第三个存在平局。

这是超级简化的，但实际上，我的实际列表

  1. 由数十亿个正整数列表组成（1 到 10,000 之间）
  2. 每个列表可以短至 1 个元素或长达 500 个元素
  3. NM可以小到 1 也可以大到100

我的问题是：

  1. 是否有一个有效的数据结构允许快速查询假设N并且M总是小于 100？
  2. N是否有有效的算法或相关研究领域可以对和的各种组合进行这种分析M？

标签： pythonalgorithmlistnumpygraph

解决方案

这是一个基于广义后缀树结构的想法。您的列表列表可以视为字符串列表，其中字母表由整数组成（因此，您提供的信息中大约有 10k 个字符）。
广义后缀树的构造是在字符串长度的线性时间内完成的，所以这不应该是一个问题，因为无论如何，你必须在某个时候浏览你的列表。

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

然后，您还希望有一个查找表，从(i, d)（i您要查找的整数在哪里，目标，并且d是树中的深度，M）到标有 ' 的后缀链接的节点集letter' i（您的字母表不是由字符组成，而是由整数组成），位于 depth d。可以通过遍历您的后缀链接（BFS 或 DFS）来构建此查找表。您甚至可以只存储对应于最高计数器值的节点。

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

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

对于后缀树的实现，我建议您只阅读原始论文，直到您对有关此事的那些（像这样或那样，sc*-h*b 可以是您的朋友）有深刻而真实的理解，而不是它的在线“解释”，充斥着近似值和错误（即使这篇文章也可以帮助获得第一个想法，但如果您的目标是实现正确的版本，则会在某些时候误导您）。

推荐阅读