TME 8 - Déterminer les éléments les plus fréquents

Aujourd'hui nous allons extraire les adresses IP les plus fréquentes dans le log d'un serveur web. Les fichiers d'entrée sont ceux utilisé à la dernière séance.

Les arguments

Votre programme prendra deux arguments en ligne de commande. Le nom du fichier log, et une fraction delta. Il affichera ensuite la liste des adresses IP apparaissent au moins une fraction delta fois dans le flux.

Algorithme de Misra-Gries

Implémentez l'algorithme de Misra-Gries donné en cours. Vous devriez avoir le résultat suivant.

$ ./Finfinity.py NASA_access_log_Jul95_ip.log 0.003
17572 10.228.166.74
11591 10.25.119.100
9868  10.54.185.9
7852  10.137.36.142
7573  10.49.150.215
5922  10.18.18.85

S'il vous reste du temps

Implémentez l'algorithme de Bar-Yossef, Jayram, Kumar, Sivakumar et Trevisan présenté en cours, pour le problème d'estimer le nombre d'éléments distincts. En Python3 vous pourriez utiliser le type set et en Java la classe HashSet<Long>.