如何找到的与用户ID和PAGEID大的日志文件访问最频繁的3 - 网页序列 [英] How to find the most frequently visited 3-webpage sequence from a large log file with userID and pageID

问题描述

由于网页访问的日志文件：

Given a log file of webpage visited as:

Userid  PageID
A          1
A          2
A          3
B          2
B          3
C          1
B          4
A          4

查找的页ID最频繁的访问顺序：

Find the most frequent visit sequence of page-ID:

 for A : 1-2-3, 2-3-4
 for B : 2-3-4

所以，2-3-4是最常见的。

so, 2-3-4 is the most frequent.

我的想法：

1. 把文件的每个项目为 MAP1＆LT;关键：USER_ID，列表和LT; PAGEID＆GT; ＆GT;
2. 当则为list.size（）== 3 ，创建一个新的结构 three_hits 持有三PAGEID。
3. 在把它放进 MAP2＆LT;结构three_hits，整型计数和GT;
4. 然后，发现MAP2与最大计数器值的项目。

1. Put each item of the file into map1<key:user_id, list<pageID> >.
2. When list.size() == 3, create a new struct three_hits to hold the three pageID.
3. Put it in into map2<struct three_hits, int counter>.
4. Then, find the item in map2 with largest counter value.

声明：

 struct three_hits
 {
     int f_page;
     int s_page;
     int t_page;  
 };
 map<string, list<int> > map_hit;
 map<struct three_hits, int> map_t_hits;

扫描记录：

for each( record: r in log)
{
    if(map_hit.count(r.userid) >0) 
    {
        map_hit[r.uid].second.push_back(r.pageID);

        if(map_hit[r.uid].second.size() ==3)
        {

            list<int> tmp=map_hit[r.uid].second;

            t_hits(tmp[0],tmp[1],tmp[2]);

            // O(n lg n)
            if( map_t_hits.count(t_hits) >0)
                map_t_hits[t_hits]++;
            else
                map_t_hits[t_hits]=1;
        }
        else
        { 
            list<int> tmp(r.pageID);

            map_hit[r.uid]=tmp;
        }
    }
    // O(n)

迭代 map_t_hits 一旦找到它的关键（ t_hits ）与最高值。

Iterate map_t_hits once to locate its key (t_hits) with highest value.

的时间的为O（n 的LG的 N）的和空间的 O（N）的一个映射。

The time O(n lg n) and space O(n) for a maps.

没有更好的办法？

推荐答案

您可以考虑用排序合并这样做。先用一个稳定的排序由用户ID把所有序列的给定用户一起，保持原来的顺序。然后排序所有3-网页的序列，并最终计数等于序列的线路。这也是为O（n log n）的。它可能需要更多的时间在实践中，但可能需要较少的店，如果使用内部存储器中运行，并且可以与各种外部存储器中运行，如果你有太多的数据在任何一个时间，以适应在商店。无论它实际上任何好转取决于您的特定情况的细节。

You might consider doing this with sort-merge. First use a stable sort by user id to put all of the sequences for a given user together, keeping the original order. Then sort all the 3-web page sequences, and finally count runs of equal sequences. This is also O(n log n). It probably takes a bit more time in practice, but might take less store if run using internal memory, and can be run with sorts in external memory, if you have too much data to fit in store at any one time. Whether it's actually any better depends on the details of your particular situation.

这篇关于如何找到的与用户ID和PAGEID大的日志文件访问最频繁的3 - 网页序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！