Определите верхнюю 'm' наиболее часто встречающуюся k-страницу-последовательность

Question

На веб-сайте есть несколько веб-страниц, и есть много пользователей, которые обращаются к веб-сайту. Assume--

user 1 has access pattern : x->y->z->a->b->c->d->e->f  
user 2 has access pattern : z->a->b->c->d 
user 3 has access pattern : y->z->a->b->c->d 
user 4 has access pattern : a->b->c->d 

и список продолжается для много много пользователей, которые конечны и пронумерованы. Теперь вопрос в том, что мы должны определить вершину m наиболее часто встречающейся k-страничной последовательности. Для приведенного выше примера результатом будет: (k = 3, m = 3) a-> b-> c, b-> c-> d, z-> a-> b.

Я не мог найти конкретного решения здесь. Независимо от того, какие структуры данных я использую, я должен пройти через все узлы и списки. Может быть, я могу создать хеш-таблицу, где ключ - это что-то вроде «abc», а значение - это количество раз. Но тогда найти «m», наиболее часто встречающееся в хеш-таблице, всегда было бы болью.

Answer 1

Я бы применил эту проблему так же, как вы описали, используя ключи k в качестве ключей для вашей хеш-таблицы.

Затем для извлечения верхних m элементов можно выполнить путем итерации через каждый хеш-ключ и выполнения сортировки пузырьков на текущем верхнем m элементах и ​​вашем текущем элементе. Это будет иметь временную сложность O(m*N), где N - это количество ключей в вашей хеш-таблице.

Answer 2

1. Да p[i] be a pattern of user i. Для каждого шаблона i:
2. Для каждой подстроки s длины k в p[i]:
3. если (s в hashmap) hashmap[s]++ еще поставил s в hashmap.
4. Позвольте k быть числом ключей в hashmap. Сортируйте ключи в порядке убывания по их значениям. Возврат m первые ключи после сортировки.

O(klogk) временная сложность.

Answer 3

1. Если хеширования выполнима:

   • поместить их всех в хэш-карту (которая отображает последовательность ряда ее появлений).

   • Как найти Top m элементов на карте хэша? Существует несколько способов:

     1. Поместите их все в массив и отсортируйте. Сложность времени - O(n log n), где n - количество записей на карте.

     2. Итерацию над записями хеш-карты и поддержание очереди приоритетов с верхними m элементами, видимыми до сих пор. Сложность времени - O(n log m).

     3. Поместите их все в массив и выберите m-й элемент, используя алгоритм quickselect. Выберите все, что не больше.Сложность времени - O(n) или O(n + m * log m), если нам нужно получить топ m записей в отсортированном порядке.

2. Если хеширования не представляется возможным, вы можете использовать структуру суффикса данных (массив, дерево, автомат) для подсчета числа вхождений каждой последовательности, а затем выбрать лучший m так же, как в 1.