Наиболее частая 3-страничная последовательность в блоге

Question

Учитывая веб-журнал, который состоит из полей «Пользователь» «URL страницы». Мы должны выяснить наиболее частую 3-страничную последовательность, которую используют пользователи.

Есть отметка времени. и не гарантируется, что однопользовательский доступ будет регистрироваться последовательно, это может быть как user1 Page1 user2 Pagex user1 Page2 User10 Pagex user1 Page 3 ее страница страницы User1s - page1-> page2-> page 3

Answer 1

Предполагая, что ваш журнал хранится в порядке отметок времени, вот алгоритм, который сделает то, что вам нужно:

1. Создайте хеш-таблицу 'user_visits', отображающую идентификатор пользователя на последние две страницы, которые вы наблюдали, чтобы они посетили
2. Создание хеш-таблицы 'visit_count', сопоставляющей 3 кортежа страниц с частотой
3. Для каждой записи (пользователя, URL) в журнале:
   1. Если в user_visits есть «user» с двумя записями, увеличьте запись в visit_count, соответствующую 3-му кортежу URL, на один
   2. Добавьте 'URL' к соответствующей записи в user_visits, удалив самую старую запись при необходимости.
4. Сортировать хеш-таблицу visit_count по значению. Это ваш список самых популярных последовательностей 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)

Answer 3

Вот немного SQL, предполагая, что вы можете поместить свой журнал в таблицу, такую ​​как

CREATE TABLE log (
   ord  int,
   user VARCHAR(50) NOT NULL,
   url  VARCHAR(255) NOT NULL,
   ts   datetime
) ENGINE=InnoDB;

Если данные не отсортированы по пользователю, то (при условии, что столбец ord - это номер строки из файла журнала)

SELECT t.url, t2.url, t3.url, count(*) c
FROM  
      log t INNER JOIN
      log t2 ON t.user = t2.user INNER JOIN
      log t3 ON t2.user = t3.user
WHERE 
      t2.ord IN (SELECT MIN(ord) 
                 FROM log i 
                 WHERE i.user = t.user AND i.ord > t.ord) 
      AND
      t3.ord IN (SELECT MIN(ord) 
                 FROM log i 
                 WHERE i.user = t.user AND i.ord > t2.ord)
GROUP BY t.user, t.url, t2.url, t3.url
ORDER BY c DESC
LIMIT 10;

Это даст 10 лучших путей остановки для пользователя. В качестве альтернативы, если вы можете получить его по заказу пользователя и времени, вы можете легче присоединиться к ряду номеров.

Answer 4

1.Reads user page access urls from file line by line,these urls separated by separator,eg: 
u1,/
u1,main
u1,detail

The separator is comma.
2.Store each page's visit count to map:pageVisitCounts;
3.Sort the visit count map by value in descend order;

public static Map<String, Integer> findThreeMaxPagesPathV1(String file, String separator, int depth) {
    Map<String, Integer> pageVisitCounts = new HashMap<String, Integer>();
    if (file == null || "".equals(file)) {
        return pageVisitCounts;
    }
    try {
        File f = new File(file);
        FileReader fr = new FileReader(f);
        BufferedReader bf = new BufferedReader(fr);

        Map<String, List<String>> userUrls = new HashMap<String, List<String>>();
        String currentLine = "";
        while ((currentLine = bf.readLine()) != null) {
            String[] lineArr = currentLine.split(separator);
            if (lineArr == null || lineArr.length != (depth - 1)) {
                continue;
            }
            String user = lineArr[0];
            String page = lineArr[1];
            List<String> urlLinkedList = null;
            if (userUrls.get(user) == null) {
                urlLinkedList = new LinkedList<String>();
            } else {
                urlLinkedList = userUrls.get(user);
                String pages = "";
                if (urlLinkedList.size() == (depth - 1)) {
                    pages = urlLinkedList.get(0).trim() + separator + urlLinkedList.get(1).trim() + separator + page;
                } else if (urlLinkedList.size() > (depth - 1)) {
                    urlLinkedList.remove(0);
                    pages = urlLinkedList.get(0).trim() + separator + urlLinkedList.get(1).trim() + separator + page;
                }
                if (!"".equals(pages) && null != pages) {
                    Integer count = (pageVisitCounts.get(pages) == null ? 0 : pageVisitCounts.get(pages))  + 1;
                    pageVisitCounts.put(pages, count);
                }
            }
            urlLinkedList.add(page);
            System.out.println("user:" + user + ", urlLinkedList:" + urlLinkedList);
            userUrls.put(user, urlLinkedList);
        }
        bf.close();
        fr.close();
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }
    return pageVisitCounts;
}

public static void main(String[] args) {
    String file = "/home/ieee754/Desktop/test-access.log";
    String separator = ",";
    Map<String, Integer> pageVisitCounts = findThreeMaxPagesPathV1(file, separator, 3);
    System.out.println(pageVisitCounts.size());
    Map<String, Integer>  result = MapUtil.sortByValueDescendOrder(pageVisitCounts);
    System.out.println(result);
}

Answer 5

Эта проблема похожа на

Найти k наиболее часто встречающихся слов из файла

Вот как вы можете ее решить:

• Сгруппируйте каждый триплет (стр. 1, стр. 2, стр. 3) в слово
• Примените упомянутый алгоритм здесь

Answer 6

Исходный код в Mathematica

s= { {user},{page} }  (* load List (log) here *)

sortedListbyUser=s[[Ordering[Transpose[{s[[All, 1]], Range[Length[s]]}]] ]]

Tally[Partition [sortedListbyUser,3,1]]