4

我有以下要求来实现，这对我来说是一个“难题”：
我有网络服务器和各种用户（经过身份验证和登录）访问网站的各个区域（即关注和浏览各种链接）。这些操作（或称为浏览）正在记录到日志文件中。
因此，这些文件捕获用户访问服务器的日期和访问的各种链接，即 URL。
记录的简化格式（出于解释目的）可以如下所示：
Timestamp User-Name URL-1
因此，给出我们可以拥有的日志的简化示例（假设有效日期）： 

Date-1 John    URL-1  
Date-1 Nick    URL-1  
Date-1 John    URL-2  
Date-1 George  URL-1  
Date-1 George  URL-2
Date-1 Eve     URL-2  
Date-1 Nick    URL-2  
Date-1 John    URL-3
Date-1 George  URL-3  
Date-1 John    URL-5  
Date-1 Nick    URL-3  
Date-1 Bill    URL-2  
Date-1 George  URL-5
Date-1 Nick    URL-5      
Date-1 Eve     URL-3                
Date-1 Eve     URL-5

等等，并且可能有成百上千的条目
当我说URL-1我的意思是网站的有效 URL 时，所以URL-1在 John 和 Eve 中真的意味着他们都访问了同一个链接。在此示例URL-2,URL-3,URL-5中是最大常见访问 URL 序列。

问题：我有兴趣使用此信息并找到所有用户在日志文件和/或特定日期时间覆盖的整个日期时间范围内访问的最频繁访问的 URL 序列。
我有一些关于如何去做的初步想法。例如，我的第一个想法是存储所有内容HashMaps并包含每个外观的计数器，然后遍历映射条目以找到最大值，但在我看来，它在空间和运行时都有巨大的开销。
此外，我对此思考得越多，它似乎就越可能有一个“标准”解决方案，例如字符串模式匹配一​​个将遵循的解决方案KMP algorithm。
然后我想如果我可以使用例如后缀树，但我只知道实现一个 trie 并且我相信它的空间复杂度O(N^2). 我知道有压缩版本，但我认为它们太复杂了，如果有更好/标准的解决方案来解决这个问题，我不想浪费时间。

非常感谢任何建议/意见。

4

2 回答 2

3

好吧，你说，任何建议/意见都非常感谢。. 因此，让我建议您简要遵循以下算法：

  1. 过滤所需日期范围的日志文件，为每个用户并行收集一些List.

  2. 在第 1 步之后。您有一组大序列。在此步骤中，此问题相当于在字符串列表中查找最常见的子字符串的任务。这是已经解决的问题。

UPD：之后考虑每个都URL像"char"一些"string".

于 2013-01-11T18:56:36.993 回答
0

很抱歉，但我认为使用日志文件中的数据不可能实现这一点。

我看到的问题是您正在寻找最常用的 URL序列。在您的问题中，您只有 userId 而不是会话指示器，这意味着您无法可靠地找出他们在单个会话期间所做的事情。当你试图找出他们所走的路径时，你可能会混合不同的会话。

假设您有一个 sessionId，您可以创建每个会话的路径并在其上运行一些（仍然未知的）程序以找到最常用的“弧”。

于 2013-01-11T19:17:07.570 回答