确定出现最多的前'm'个k页序列

Question

确定出现最多的前'm'个k页序列

3

一个网站有多个网页，有很多用户访问该网站。假设 -

user 1 has access pattern : x->y->z->a->b->c->d->e->f    
user 2 has access pattern : z->a->b->c->d
user 3 has access pattern : y->z->a->b->c->d
user 4 has access pattern : a->b->c->d

还有很多用户的列表，这些用户是有限且编号的。现在的问题是我们需要确定出现次数最多的前m个k页序列。对于上面的示例，结果将为：(k=3，m=3) a->b->c ，b->c->d，z->a->b。

我无法真正找到一个具体的解决方案。无论使用什么数据结构，都必须遍历所有节点和列表。也许我可以创建一个哈希表，其中键类似于“abc”，而值是其出现的次数。但是在哈希表中找到“m”最常出现的总是很麻烦。

- discoverAnkit

抱歉我的无知，但是k=3和m=3是什么意思？我看到a->b->c出现了4次。 - GMazzacua

m=3，k=3 => 3个最常出现的3页序列。 - discoverAnkit

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Degustaf · Answer 1

我会像你描述的那样，使用 k 元组作为哈希表的键来解决这个问题。

然后，提取前 m 个元素可以通过迭代每个哈希键，并对当前前 m 个元素和当前元素执行冒泡排序来完成。这将具有时间复杂度 O(m*N)，其中 N 是哈希表中键的数量。

- Adam Stelmaszczyk · Answer 2

设p[i]为用户i的模式。对于每个模式i：
对于p[i]中长度为k的每个子字符串s：
如果s在hashmap中，则hashmap[s]++，否则将s放入hashmap。
令k为hashmap中键的数量。按照它们的值按降序排序键。返回排序后的前m个键。

O(klogk)时间复杂度。

- kraskevich · Answer 3

如果哈希是可行的：
- 将它们全部放入哈希映射表中（将一个序列映射到其出现次数的数字）。
- 如何在哈希映射表中找到前 m 个元素？有几种方法：
  1. 将它们全部放入数组中并进行排序。时间复杂度为 O(n log n)，其中 n 是映射表中条目的数量。
  2. 遍历哈希映射表中的条目，并维护一个具有前 m 个元素的优先队列。时间复杂度为 O(n log m)。
  3. 将它们全部放入数组中，并使用快速选择算法选择第 m 个元素。选择所有不大于它的元素。时间复杂度为 O(n) 或 O(n + m * log m)，如果我们需要按排序顺序获取前 m 个条目。
如果哈希不可行，则可以使用后缀数据结构（数组、树、自动机）来计算每个序列的出现次数，然后像第一种方法一样选择最好的前 m 个元素。