Lundi, 7 décembre 2009

Projets

Filed under: — Daniel Lemire @ 2:57

Voici quelques projets au baccalauréat ou à la maîtrise que je suis prêt à superviser. Cette liste n’est pas exhaustive.

Analyse linguistique des langages informatiques

On sait que dans les langues naturelles (anglais, français, etc.), les mots les plus fréquents tendent à être plus courts (le, la, est, a, papa, etc.). Que pouvons-nous dire au sujet des langages informatiques comme le Java ou le C++? Comme ces languages n’évoluent pas de manière naturelles, mais sont inventés en grande partie par quelques individus, nous n’avons aucune raison de penser que les mêmes mécanismes s’appliquent.

Dans le cadre de ce projet vous allez récupérer une grande quantité de code informatique à partir du site code.google.com pour ensuite faire une analyse de la fréquence des termes, noms de fonctions, mots réservés, etc. pour les principaux langages informatiques. Votre but est de valider l’hypothèse selon laquelle les termes les plus fréquents tendent à être plus courts. Vous devrez aussi identifier les exceptions et faire une analyse comparative des langages.

Exécution : vous devrez réaliser un logiciel capable de traiter rapidement un grand nombre de fichiers afin de calculer des statistiques.

Bibliographie sommaire

Miller, G. A. and Newman, E. B. and Friedman, E. A., Length-frequency statistics for written English, Information and control 1 (4), 1958.
Loi de Zipf (wikipédia)

Analyse comparative des sites de commerce électronique et des sites universitaires

On peut penser que les sites web de commerce électroniques, comme amazon.ca ou futureshop.ca, conçoivent leurs sites avec soin afin de maximiser leurs ventes. Les sites universitaires ont d’autres objectifs. Tous les concepteurs de sites web doivent tenir compte des moteurs de recherche. Pouvons-nous quantifier ces différences en analysant la structure, la topologie des sites web?

Dans ce projet, vous allez représenter un site web comme un graphe et en étudier les propriétés topologiques, notamment en calculant les degrés de chaque pages (liens entrants et sortant) ou en calculant l’indicateur PageRank.

Vous cherchez à valider l’hypothèse selon laquelle, à partir d’une simple analyse des liens, on peut déterminer l’intention d’un site de commerce électronique (vendre des produits). En analysant les sites web universitaires, vous allez aussi tenter de valider l’hypothèse selon laquelle ces sites ont une topologie comparable – par opposition aux sites de commerce électronique.

Exécution : vous devrez réaliser un logiciel capable de récupérer des pages web, d’en extraire les hyperliens et de produire des statistiques sur la topologie de ces liens.

Bibliographie sommaire

Daniel Lemire, Algorithme PageRank (notes de cours)
Théorie des graphes (wikipédia)
Optimisation pour les moteurs de recherche (wikipédia)

Index bitmap compressés dans Lucène?

Le moteur de recherche Lucène, dans sa version actuelle, utilise des index bitmap non compressés afin de traiter rapidement les requêtes à la volée. Ceux-ci posent un problème, car ils consomment beaucoup de mémoire quand il y a des centaines de milliers de documents ou davantage.

Dans ce projet, vous allez modifier le code source du moteur de recherche Lucène afin de tester différents types d’index bitmap compressés.

Exécution : vous devrez récupérer, tester et adapter du logiciel Java mettant en oeuvre des index bitmap compressés.

Bibliographie sommaire

Apache Lucene (site web, voir en particulier la classe org.apache.lucene.util.OpenBitSet.java)
Daniel Lemire, javaewah: A compressed alternative to the Java BitSet class (logiciel)
Kamel Aouiche, Daniel Lemire and Owen Kaser, Tri de la table de faits et compression des index bitmaps avec alignement sur les mots, BDA’08, 2008.

Interface HTML 5 pour l’exploration de documents

On veut pouvoir explorer le texte d’une base de documents. Quels sont les mots les plus fréquents? Quelles sont les cooccurrences les plus fréquentes? Est-ce que l’utilisateur peut composer à la volée sa propre application?

Dans ce projet, vous allez créer une application HTML 5.0 avec ECMAScript afin de visualiser les statistiques textuelles d’un document.

Bibliographie sommaire

Dido (MIT)
Owen Kaser and Daniel Lemire, Tag-Cloud Drawing: Algorithms for Cloud Visualization. In proceedings of Tagging and Metadata for Social Information Organization (WWW 2007), 2007.
Données boursières en HTML 5

Analyse de l’universalité de la technique de hashing Pearson

La technique de hashing de Pearson est l’une des techniques les plus rapides et simples pour le hachage de chaînes de caractères de longueur variable. Malheureusement, si on sait qu’elle est quasi-universelle en pratique, personne n’a pas le démontrer avec une analyse théorique.

Bibliographie sommaire

P. K. Pearson, Fast hashing of variable-length text strings, Communications of the ACM, 1990
Daniel Lemire and Owen Kaser, Recursive n-gram hashing is pairwise independent, at best, Computer Speech & Language 24 (4), pages 698-710, 2010.

Mesure de l’influence des utilisateurs de Twitter

Une mesure populaire de l’influence des utilisateurs de Twitter est TunkRank. Il existe cependant plusieurs autres alternatives dont, tout simplement, une mesure du nombre d’utilisateurs suivant les tweets de cet utilisateur.
Est-ce qu’il est fréquent que ces mesures diffèrent vraiment? Basé sur un échantillonnage des utilisateurs, il faut répondre à cette question.

Bibliographie sommaire

Weng, J. and Lim, E.P. and Jiang, J. and He, Q., Twitterrank: finding topic-sensitive influential twitterers, ACM international conference on Web search and data mining, 2010.
Cha, M. and Haddadi, H. and Benevenuto, F. and Gummadi, K.P., Measuring User Influence in Twitter: The Million Follower Fallacy, Proceedings of the 4th International Conference on Weblogs and Social Media, 2010.