diff --git a/docs/report/bib-rapport.bib b/docs/report/bib-rapport.bib new file mode 100644 index 0000000..097410a --- /dev/null +++ b/docs/report/bib-rapport.bib @@ -0,0 +1,10 @@ +@incollection{zhang2015, +title = {Character-level Convolutional Networks for Text Classification}, +author = {Zhang, Xiang and Zhao, Junbo and LeCun, Yann}, +booktitle = {Advances in Neural Information Processing Systems 28}, +editor = {C. Cortes and N. D. Lawrence and D. D. Lee and M. Sugiyama and R. Garnett}, +pages = {649--657}, +year = {2015}, +publisher = {Curran Associates, Inc.}, +url = {http://papers.nips.cc/paper/5782-character-level-convolutional-networks-for-text-classification.pdf} +} \ No newline at end of file diff --git a/docs/report/rapport.pdf b/docs/report/rapport.pdf new file mode 100644 index 0000000..809f4b7 Binary files /dev/null and b/docs/report/rapport.pdf differ diff --git a/docs/report/rapport.tex b/docs/report/rapport.tex new file mode 100644 index 0000000..5b8b9b0 --- /dev/null +++ b/docs/report/rapport.tex @@ -0,0 +1,103 @@ +\documentclass[a4paper,12pt]{article} +\usepackage[french]{babel} +\usepackage[parfill]{parskip} +\usepackage{graphicx} +\usepackage{amssymb} +\usepackage{amsmath} +\usepackage{amsthm} +\usepackage{xunicode} +\usepackage[T1]{fontenc} +%\usepackage{times} + +\title{Détection de langage de programmation à grande échelle} +\author{Yuan YIN} +\date{} + +\begin{document} +\maketitle + \begin{abstract} + (à compléter) + \end{abstract} + +\section{Introduction} + +La détection de langage de programmation est un problème qui consiste à identifier en quel langage un morceau de code source est écrit. Le code source est désigné par une représentation séquentielle textuelle d'un artéfact du logiciel, qui est souvent sous forme de chaînes de caractères ou, dans un sens plus général, chaînes de bytes. Plus précisément, il s'agit de introduire un modèle qui peut prendre en entrée une chaîne de bytes et puis prédire le langage utilisé. + +Celle-ci peut être utilisée dans de nombreux contextes. Voici quelques scénarios de son application : Dans les EDI, la détection automatique de langage leur permet de réaliser les fonctionnalités telles que la coloration syntaxique, l'auto-complétion du code, \emph{etc}. Dans les archives comme GitHub, ces techniques facilite l'automatisation de l'indexation des dépôts. Ces techniques sont aussi pratiquées dans les projets + +Dans le cadre du TRE, la recherche se déroule dans le contexte de l'archive \emph{Software Heritage} de l'Inria, dans lequel sont stockés plus de 4 milliards fichiers provenant de plus de 80 millions projets. La structure de données de \emph{Software Heritage}, conçue pour éviter la duplication, ne contient que des artéfacts, c'est-à-dire des fichiers sous forme de métadonnée. Chaque artéfact dispose d'un seul identifiant généré depuis soi-même, il est donc impossible de récupérer le nom d'un fichier. C'est la raison pour laquelle, au lieu d'observer l'extension de fichier, nous ne pouvons qu'analyser son contenu pour identifier le langage d'un artéfact. + +Ce travail est composé de deux étapes : 1) étudier les différentes méthodes existantes du domaine en rédigeant une review technique des articles scientifiques, 2) évaluer ces méthodes à grande échelle et adapter à un sous-ensemble de l'archive. + +Ce rapport est organisé de la manière suivante. La Section 2 traite des approches existantes théoriques et pratiques. Dans la Section 3, les méthodes testées dans les expérimentations sont respectivement présentées. Les principaux résultats issus des expérimentations sont présentés et analysés dans la Section 4. La Section 5 donne une vision d'extension possible quand nous devons adapter les méthodes aux besoins réels rencontrés dans l'archive \emph{Software Heritage}. + +\section{État de l'art} + +Vu que la détection de langage de programmation peut être considérée comme un sous-problème de la classification de textes, les approches relatives sont soit des applications des algorithmes bien conçus pour le traitement automatique du langage naturel, soit des outils regroupant de différentes heuristiques. + +Les heuristiques primitives sont largement pratiquées dans les logiciels libres tels que \textsf{Ohcount} et \textsf{SLOCCount}. Afin de distinguer un langage des autres, les développeurs cherchent des motifs spécifiques caractérisant le langage. Ces heuristiques sont souvent purement empiriques, par exemple, un fichier commence par \texttt{\#include} est vraisemblablement écrit en C. Malgré la compréhensibilité des sens de motifs, les approches qui dependent des expressions régulières restent sous-performantes et inefficaces. + +À part les heuristiques, les approches de l'apprentissage supervisé, notamment celles qui sont étudiées dans le domaine du traitement automatique du langage naturel, s'appliquent au problème et donnent des résultats. + +\section{Méthodes} + +\subsection{Jeu de données} + +Etant donné qu'aucun jeu de données de tel genre n'est publiquement disponible de la part des auteurs des articles précédents, nous avons besoin d'en construire un nouveau nous permettant de disposer d'un ensemble de fichiers avec les étiquettes d'identité indiquant le langage utilisé. Comme GitHub est l'un des services de gestion de développement de logiciels les plus populaires, nous pouvons récupérer un nombre considérable de fichiers pour chaque langage pris en compte. + +\subsubsection{Supposition sur la vérité au sol} + +\textsf{Linguist}, logiciel développé par l'équipe GitHub, est capable de reconnaître plus de 400 langages de programmation, de représentation de données et de balisage pour les fichiers contenus dans un dépôt Git. + +\subsubsection{Langages} + +\subsubsection{Récupération de données} + +Pour ce faire, + +\subsection{Méthode de référence : classification en comparant les fréquences de n-grams} + +\subsection{Classification avec le model de langage n-grams} + +\subsection{Modèle bayésien naïf multinominal} + +\subsection{Réseau neuronal convolutif au niveau de tokens} + +\subsection{Réseau neuronal convolutif au niveau de bytes} + +\section{Résultats expérimentaux} + +\subsection{Evaluation des modeles} + +\subsubsection{Impact de nombre de classes} + +\subsubsection{Confusion d'inter-classes} + +\subsection{Benchmark} + +\section{Défis à grande échelle} + +\subsection{Déployabilité des approches dans les systèmes distribués} + +\subsection{Découverte de nouvelles classes} + +\subsubsection{Regroupement hiérarchique agglomératif} + +\subsection{Apprentissage incrémental (partie optionelle)} + +\section{Conclusion} + +\bibliography{bib-rapport} +\bibliographystyle{plain} + +%Rapport +% +%Il doit faire de 15 à 30 pages et, dans la mesure du possible, doit être en grande part lisible par des non-spécialistes. Son plan peut être par exemple : +%présentation du domaine de recherche (le jury n'est pas constitué seulement de spécialistes du domaine, tenez-en compte !) ; +%énoncé et motivation du sujet ; +%résultats existants s'y rapportant (état de l'art, commentaire d'article, ...) ; +%vos résultats personnels (clairement identifiés comme tels). +%Le rapport devra être assorti d'un résumé d'une page compréhensible par quiconque. + +\tableofcontents +\end{document} \ No newline at end of file diff --git a/docs/report/report-en.tex b/docs/report/report-en.tex new file mode 100644 index 0000000..c853899 --- /dev/null +++ b/docs/report/report-en.tex @@ -0,0 +1,110 @@ +\documentclass[a4paper,12pt]{article} +\usepackage[english]{babel} +\usepackage[parfill]{parskip} +\usepackage{graphicx} +\usepackage{amssymb} +\usepackage{amsmath} +\usepackage{amsthm} +\usepackage{xunicode} +\usepackage[T1]{fontenc} +%\usepackage{times} + +\title{Large-scale Programming Language Detection} +\author{Yuan YIN} +\date{} + +\begin{document} +\maketitle + \begin{abstract} + (to be completed) + \end{abstract} + +\section{Introduction} + +Programming Language Detection is a problem of identifying which programming language is a piece of source code written in. We here define the piece of source code as a textual sequential representation of an artefact, which is normally in the form of character sequence or, more generally, byte sequence. More precisely, the objective is to build a model which could predict the language of a given byte sequence. + +The formal definition of the problem as follows: on the input, given an byte sequence $d$ and the number of languages $n$, +\[l_d = \underset{l_i\in \{l_1, ..., l_n\}}{\arg \max}\ m(d, l_i),\] +where $l_d$ is a language, model $m$ calculates a value indicating the likelihood of a document written in language $l_i$ and the most likely one is chosen as the language of the document. + +In general, Programming Language Detection could be utilised in different situations, here are several example applications: language composition of software project in version control systems. For example, GitHub team is developing the project Linguist to return which languages are the project written in; code searching in plain text, in order to track the popularity of a language; language detection helps also IDEs to choose the language whose support functionalities, like syntax highlighting, are implemented. + +We dive into this problem in the context of \emph{Software Heritage}. \emph{Software Heritage}, initiated by Inria, is an archive in which 4 billions source code files from 80 millions projects are stored. + +The reason why the language detection is requested by \emph{Software Heritage} is that the language of a file could not be found in its filename extension. In \emph{Software Heritage}, every source code file is a blob which contains raw content of the file, that means a sequence of bytes without any extra information, such as filename (including filename extension), metadata, \emph{etc}. Since each blob could be represented by an intrinsic identifier generated from the blob itself, the duplication of files is avoided. For this reason, all existing tools depending on filenames fail in our context, and the methods for recognising the language from a sequence of bytes is strongly demanded. + +In this report, we introduce briefly the state-of-the-art methods in Section 2. In Section 3, the procedure of making a feasible data set is related. In Section 4, we explain the methods that we took in account. + + +\section{State of the art} + +The existing approaches could be divided into two groups: practical methods and machine learning methods. + +Practical methods are mostly based on several empirical or external information, basic ideas are presented as follows: +\begin{itemize} + \item Judging from filename extension. The problem from this straightforward method is that some extensions are related to different languages, \emph{e.g.} \texttt{.m} refers to Objective-C and MATLAB, \texttt{.pl} points to Python and Prolog. + \item Grammar-based approches. +\end{itemize} + +\section{Data set} + +Etant donné qu'aucun jeu de données de tel genre n'est publiquement disponible de la part des auteurs des articles précédents, nous avons besoin d'en construire un nouveau nous permettant de disposer d'un ensemble de fichiers avec les étiquettes d'identité indiquant le langage utilisé. Comme GitHub est l'un des services de gestion de développement de logiciels les plus populaires, nous pouvons récupérer un nombre considérable de fichiers pour chaque langage pris en compte. + +\subsection{Supposition sur la vérité au sol} + +\textsf{Linguist}, logiciel développé par l'équipe GitHub, est capable de reconnaître plus de 400 langages de programmation, de représentation de données et de balisage pour les fichiers contenus dans un dépôt Git. + +\subsection{Langages} + +\subsection{Récupération de données} + +Pour ce faire, + +\section{} + +\subsection{Méthode de référence : classification en comparant les fréquences de n-grams} + +\subsection{Classification avec le model de langage n-grams} + +\subsection{Modèle bayésien naïf multinominal} + +\subsection{Réseau neuronal convolutif au niveau de tokens} + +\subsection{Réseau neuronal convolutif au niveau de bytes} + +\section{Résultats expérimentaux} + +\subsection{Evaluation des modeles} + +\subsubsection{Impact de nombre de classes} + +\subsubsection{Confusion d'inter-classes} + +\subsection{Benchmark} + +\section{Défis à grande échelle} + +\subsection{Déployabilité des approches dans les systèmes distribués} + +\subsection{Découverte de nouvelles classes} + +\subsubsection{Regroupement hiérarchique agglomératif} + +\subsection{Apprentissage incrémental (partie optionelle)} + +\section{Conclusion} + +\bibliography{bib-rapport} +\bibliographystyle{plain} + +%Rapport +% +%Il doit faire de 15 à 30 pages et, dans la mesure du possible, doit être en grande part lisible par des non-spécialistes. Son plan peut être par exemple : +%présentation du domaine de recherche (le jury n'est pas constitué seulement de spécialistes du domaine, tenez-en compte !) ; +%énoncé et motivation du sujet ; +%résultats existants s'y rapportant (état de l'art, commentaire d'article, ...) ; +%vos résultats personnels (clairement identifiés comme tels). +%Le rapport devra être assorti d'un résumé d'une page compréhensible par quiconque. + +\tableofcontents +\end{document} \ No newline at end of file diff --git a/scripts/comparison.pdf b/scripts/comparison.pdf index 4077531..78e90a6 100644 Binary files a/scripts/comparison.pdf and b/scripts/comparison.pdf differ diff --git a/scripts/comparison_less.pdf b/scripts/comparison_less.pdf new file mode 100644 index 0000000..e46bacf Binary files /dev/null and b/scripts/comparison_less.pdf differ