Travail noté sur le moteur de recherche Lucene

Consignes du travail noté 4

Vous devez rédiger un court rapport (en format « pdf », « Word 97/2000/XP », « RTF », « OpenDocument » ou « texte ») que vous transmettrez, par courriel, à votre personne tutrice. L’objet du courriel doit commencer par « [INF6460][TRAVAIL4] », afin de permettre à la personne tutrice de classer rapidement ses messages. Dans le corps de votre message ainsi que dans votre rapport, vous devez bien indiquer votre nom, votre numéro d’étudiant ainsi que le numéro du travail. Joignez les classes Java dans une archive zip.

Le travail est noté sur 10 points. Il faut prévoir environ 9 heures pour le faire.

Troncature

Pour l’exécution de ce travail, vous devrez veiller à activer la troncature des mots en supposant que tous les textes sont en anglais.

Concepts formels et treillis de Galois

Au sens de « treillis de Galois » et dans notre contexte particulier, un concept formel sera tout simplement un ensemble de mots et un ensemble de documents dans lesquels tous les mots se trouvent dans tous les documents et, inversement, dans lesquels tous les documents contiennent tous les mots. Par exemple, si les textes A, B et C contiennent les mots vapeur et maison, alors les ensembles (vapeur, maison) et (A,B,C) forment un concept formel. Un treillis de Galois (ou de concepts) est construit à partir de tous les concepts trouvés et il constitue une représentation de la concordance entre les documents et les mots.

Par exemple, soit la matrice d’occurrences suivante :

	vapeur	maison
A
B	X
C	X	X
D

Dès lors, le concept regroupant le plus de mots est C x (vapeur,maison). Le concept regroupant le plus de documents, outre $(A,B,C,D)\times \oslash$, est (B,C) x (vapeur).

Références :
– D. Eppstein, Arboricity and bipartite subgraph listing algorithms, Inf. Proc. Lett, vol 51, 1994, p 207-211.
– R. Godin et al., Méthodes de classification conceptuelle basées sur les treillis de Galois et applications,
Revue d’intelligence artificielle, 1995.
– Vicky Choi, Faster Algorithms for Constructing a Concept (Galois) Lattice, arXiv cs.DM/0602069.

Rappel : chronométrer une tâche en Java

Quand on vous demande de calculer le temps d’exécution d’une tâche en Java par votre appareil, vous pouvez utiliser l’exemple de code suivant :

long avant = System.currentTimeMillis();

mafonction();

long apres = System.currentTimeMillis();

System.out.println("Ça a pris "+ (apres-avant)/1000.0+" secondes.");

Évidemment, il faut éviter d’utiliser d’autres applications pendant que votre programme s’exécute !

Parfois, pour obtenir une meilleure estimation du temps , on peut effectuer le travail en boucle et faire la moyenne, comme dans cet exemple :

long avant = System.currenTimeMillis();

for (int k = 0; k < 1000; ++k)

  mafonction();

long apres = System.currenTimeMillis();

System.out.println("Ça a pris "+ (apres-avant)/1000.0+" secondes");

System.out.println("Une moyenne de  "+ (apres-avant)/(1000*1000.0)+" secondes.");

Rappel : lire une liste dans un fichier texte

Si vous avez un fichier en format texte Java, vous pouvez en lire le contenu et le mettre dans un tableau avec le code suivant :

import java.util.*;

import java.io.*;



public class test {

        public static void main(String arg[]) throws IOException {

                BufferedReader sr = new BufferedReader(

                                new FileReader(arg[0]));

                String line;

                Vector<String> lignes = new Vector<String>();

                while ( ( line = sr.readLine()) != null) 

                        lignes.add(line);

                String[] li = lignes.toArray(new String[0]);

                for (int k = 0; k < li.length; ++k)

                        System.out.println(li[k]);

        }

}

Rappel : accès aux dossiers

Étant donné un instance de la classe java.io.File, vous pouvez vérifier s’il s’agit d’un dossier avec la méthode isDirectory(). Dans ce cas, vous pouvez avoir accès aux fichiers qu’il contient avec la méthode listFiles(). Dans le cas où il s’agit d’un fichier, vous pouvez vérifier l’extension d’un fichier avec un appel tel que getName().endsWith(".txt").

La méthode getPath() vous permet d’avoir accès au chemin du fichier, ce qui est utile lors de l’indexation. Par exemple, vous pouvez composer un champ Lucène de cette manière :

new StringField("path", file.getPath(), Field.Store.YES);

Rappel : Lire le contenu d’un fichier

Vous pouvez lire le contenu d’un fichier en Java avec la classe java.io.FileReader. Pour des raisons de performance, on la combine le plus souvent avec la classe BufferedReader de cette manière

Reader r = new BufferedReader(new FileReader(file));

Lucène vous permet d’indexer un fichier à l’aide d’une instance de la classe Reader, comme ceci :

new TextField("contenu",reader);

Énoncé

Question 1 (4 points)

Étant donné l’ensemble des documents sur le cédérom Gutenberg qui vous est fourni, répondez aux questions suivantes.

– Indexez d’abord seulement 10 documents, puis 20, puis 30, puis la totalité des documents ayant l’extension txt sur le cédérom (dans les répertoires etextxx) ; calculez ensuite le temps nécessaire pour l’exécution de chaque étape, puis calculez la taille (sur le disque) de chaque index ainsi que la somme respective de la taille des fichiers. Faites aussi, en boucle, pour chaque index, 100 fois 10 recherches par mots-clés, puis divisez la somme obtenue par 1000 pour obtenir le temps de recherche. Dressez un tableau de cinq colonnes avec les intitulés suivants : nombre de fichiers, taille totale des fichiers, temps d’indexage, taille de l’index, et temps de recherche moyen.
– À partir du tableau de l’exercice précédent, pouvez-vous dire si la performance de Lucene décroît avec la taille de l’index ? Supposons que votre index soit 1000 fois plus important, quel serait, environ, le temps de recherche moyen ?
– À partir de votre tableau, donnez la taille de l’index et le temps nécessaire pour construire l’index si vous devez indexer 8 milliards de documents faisant en moyenne 20 Ko. Est-ce possible d’envisager la chose ? Que feriez-vous si on vous donnait le mandat de la faire ?

Question 2 (4 points)

Pour cette question, utilisez un index de tous les documents dont l’extension est txt sur le cédérom Gutenberg, avec troncature. N’oubliez pas d’utiliser la troncature de la langue anglaise, sinon vos résultats pourraient être erronés !

On suppose que l’utilisateur vous fournit une liste de mots, un par ligne, dans un fichier texte appelé « mots.txt ». Votre application doit trouver les réponses aux questions suivantes lorsqu’on l’exécute en ligne de commande comme ceci : « java MonLucene mots.txt » où le fichier « mots.txt » est dans le répertoire courant.

– Le premier concept à trouver est celui regroupant le plus de documents et ayant au moins un mot dans la liste que votre utilisateur vous fournit. S’il y en a plus d’un, il faut tous les trouver. (Ne donnez que les mots définissant le concept. N’incluez pas la liste des documents.)
– Le second concept à trouver est celui utilisant deux mots dans la liste, et le plus grand nombre de documents. Encore une fois, s’il y en a plus d’un, il faut tous les trouver. Ces concepts donnent des paires de mots qui sont liés parce qu’ils apparaissent fréquemment ensemble dans le même document. (Ne donnez que les ensembles de mots définissant un concept. N’incluez pas la liste des documents.)
– Finalement, le dernier concept à trouver est celui utilisant trois mots apparaissant dans le plus grands nombres de documents. S’il y en a plus d’un, il faut tous les trouver. Ces concepts donnent des triplets de mots qui sont liés parce qu’ils apparaissent fréquemment ensemble dans le même document. (Ne donnez que les ensembles de mots définissant un concept. N’incluez pas la liste des documents.)

Indice. Pour le premier problème, faite une recherche avec chacun des mots. Trouvez ensuite le mot le plus populaire (ou les mots les plus populaires), soit le mot apparaissant dans le plus de documents. Répétez ensuite avec les paires de mots et, finalement, avec les triplets de mots.

Il faut remettre non seulement le code, mais la solution correspondant à la liste de mots suivante :

man

woman

house

home

school

dog

cat

land

country

white

children

example

paper

music

letter

river

book 

town

room

friend

Indice. Si le mot « man » est présent dans 500 documents, alors les mots « man » et « woman » doivent être présents dans au plus 500 documents. Vérifiez bien que vos statistiques ont du sens !

Question 3 (2 points)

– Quelle est la complexité de l’implémentation (faite à la question précédente) selon le nombre de mots spécifiés : est-ce $O(n)$, $O(n^2)$ ou $O(n^3)$ ? Que se passerait-il si l’utilisateur saisissait 1000 mots au lieu de 20 mots ?
– Nous vous avons demandé d’utiliser la troncature. Que se passerait-il si vous répétiez l’expérience sans effectuer la troncature des mots. Expliquez votre point de vue.

Les travaux du cours INF 6460 ne sont pas sous une licence Creative Commons.

Semaine 10