网络日志中最频繁的3页序列

Question

给定一个Web日志，其中包含“用户”“页面网址”字段。我们必须找出用户需要的最频繁的3页序列。

有时间戳记。并且不能保证单个用户访问将被顺序记录，就像user1 Page1 user2 Pagex user1 Page2 User10 Pagex user1 Page 3一样，其User1的页面顺序为page1-> page2-> page 3

Answer 1

假设您的日志按时间戳顺序存储，这里有一个算法可以满足您的需要：

1. 创建一个哈希表“user_visits”，将用户 ID 映射到您观察到的他们访问的最后两个页面
2. 创建一个哈希表“visit_count”，将页面三元组映射到频率计数
3. 对于日志中的每个条目（用户、URL）：
   1. 如果 user_visits 中存在具有两个条目的“user”，则将 Visit_count 中与 URL 3 元组相对应的条目加一
   2. 将“URL”附加到 user_visits 中的相关条目，如有必要，删除最旧的条目。
4. 按值对访问计数哈希表进行排序。这是最流行的 URL 序列列表。

这是 Python 中的一个实现，假设您的字段是用空格分隔的：

fh = open('log.txt', 'r')
user_visits = {}
visit_counts = {}
for row in fh:
  user, url = row.split(' ')
  prev_visits = user_visits.get(user, ())
  if len(prev_vists) == 2:
    visit_tuple = prev_vists + (url,)
    visit_counts[visit_tuple] = visit_counts.get(visit_tuple, 0) + 1
  user_visits[user] = (prev_vists[1], url)
popular_sequences = sorted(visit_counts, key=lambda x:x[1], reverse=True)

Answer 2

又快又脏：

• 构建每个用户的 url/时间戳列表
• 按时间戳对每个列表进行排序
• 迭代每个列表
  • 对于每 3 个 URL 序列，创建或增加一个计数器
• 查找 URL 序列计数列表中的最高计数

foreach(entry in parsedLog)
{
    users[entry.user].urls.add(entry.time, entry.url)
}

foreach(user in users)
{
    user.urls.sort()
    for(i = 0; i < user.urls.length - 2; i++)
    {
        key = createKey(user.urls[i], user.urls[i+1], user.urls[i+2]
        sequenceCounts.incrementOrCreate(key);
    }
}

sequenceCounts.sortDesc()
largestCountKey = sequenceCounts[0]
topUrlSequence = parseKey(largestCountkey)