博客中最常见的 3 页序列

给定一个由字段“用户”“页面 url”组成的网络日志。我们必须找出用户最常使用的 3 页序列。

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

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

1. 创建一个哈希表“user_visits”，将用户 ID 映射到您观察到的他们访问的最后两个页面
2. 创建一个哈希表“visit_count”，将页面三元组映射到频率计数
3. For each entry (user, URL) in the log:
   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)