java - sheet - tree data structure

La secuencia máxima de URL con acceso más frecuente

Question

Tengo el siguiente requisito de implementación que me plantea un "acertijo":
Tengo un servidor web y varios usuarios (autenticados y con sesión iniciada) visitan varias áreas del sitio web (es decir, siguen y navegan varios enlaces). Estas acciones (o lo llaman exploración) se registran en archivos de registro.
Entonces, estos archivos capturan la fecha en que un usuario visitó el servidor y los diversos enlaces, es decir, URL, a los que accedió.
Un formato simplificado de los registros (con fines de explicación) puede ser el siguiente:
Timestamp User-Name URL-1
Entonces, para dar un ejemplo simplificado de los registros que podríamos tener (asuma fechas válidas para esto):

Date-1 John    URL-1  
Date-1 Nick    URL-1  
Date-1 John    URL-2  
Date-1 George  URL-1  
Date-1 George  URL-2
Date-1 Eve     URL-2  
Date-1 Nick    URL-2  
Date-1 John    URL-3
Date-1 George  URL-3  
Date-1 John    URL-5  
Date-1 Nick    URL-3  
Date-1 Bill    URL-2  
Date-1 George  URL-5
Date-1 Nick    URL-5      
Date-1 Eve     URL-3                
Date-1 Eve     URL-5   

etc. y puede haber cientos / miles de entradas
Cuando digo URL-1 me refiero a una URL válida para el sitio y, por lo tanto, URL-1 en John y Eve realmente significa que ambos visitaron el mismo enlace. En este ejemplo, URL-2,URL-3,URL-5 es la secuencia de URL de acceso común máxima.

Problema: estoy interesado en utilizar esta información y encontrar la secuencia de URL accedida con más frecuencia a la que acceden todos los usuarios, tanto en el rango completo de fecha y hora cubierto por los archivos de registro como en una fecha y hora específica.
Tengo algunas primeras ideas sobre cómo ir para esto. Por ejemplo, mi primer pensamiento fue almacenar todo en HashMaps e incluir contadores para cada aspecto y luego recorrer las entradas del mapa para encontrar el máximo, pero me parece que tiene una gran sobrecarga tanto en el espacio como en el tiempo de ejecución.
Además, cuanto más pienso en esto, cuanto más parece que podría tener una solución "estándar" como, por ejemplo, para la coincidencia de patrones de cadenas, uno seguiría el KMP algorithm .
Entonces pensé que si podía usar, por ejemplo, árboles de sufijo, pero solo sé cómo implementar un trie y la complejidad del espacio para esto sería, creo, O(N^2) . Sé que hay versiones comprimidas, pero creo que son demasiado complejas y no quisiera perder tiempo en caso de que haya una solución mejor / estándar para este problema.

Cualquier sugerencia / entrada es muy apreciada.

Answer 1

Bueno, dijiste que cualquier sugerencia / aporte es muy apreciada. . Así que déjame sugerirte que sigas brevemente el algoritmo:

1. Filtre el archivo de registro para el intervalo de fechas necesario, recogiendo secuencias de URL para cada usuario paralelo en alguna List .

2. Después del paso 1. tienes un conjunto de grandes secuencias. En este paso, este problema es equivalente a la tarea de encontrar la subcadena más común en la lista de cadenas . Esto ya está resuelto problema.

UPD: Después de eso, considere cada URL como un "char" en alguna "string" .

Answer 2

Lo siento, pero no creo que sea posible lograrlo con los datos que tiene en sus archivos de registro.

El problema que veo es que estás buscando la secuencia de URL más utilizada. En su pregunta, solo tiene el ID de usuario y no un indicador de sesión, lo que significa que no puede averiguar de manera confiable lo que han estado haciendo durante una sola sesión. Puede que estés mezclando diferentes sesiones cuando trates de descubrir cuál era el camino que estaban tomando.

Supongamos que tiene una sesión. Podría crear una ruta para cada sesión y ejecutar algún programa (aún desconocido) para encontrar los ''arcos'' más utilizados.