UNIVERSITE DE LA MEDITERRANEE
MASTER INFORMATIQUE 1ère année
Faculté des Sciences de Luminy
Année 2004--2005
Département d'Informatique
M02: Complexité
 
Michel VAN CANEGHEM ( Michel.Van.Caneghem@lidil.univ-mrs.fr)
MAISON TURING COMPLEXITE BIO I BIO II ARO VIDEO


Nouvelles
- Le devoir 1 est à rendre le 29 Novembre 2004

- Le devoir 2 est à rendre le 10 Décembre 2004


Université de
la Méditerranée
Faculté
des Sciences
de Luminy
Département
d'Informatique
Laboratoire
d'Informatique
Fondamentale
Ce document a été traduit de LATEX par HEVEA.

Le devoir 1 : Etude minutieuse du hachage

Table des matières

A rendre pour le Lundi 22 Novembre 2004

1  Présentation

Description de l'objectif du devoir

Les techniques de hachage (hash-code) permettent de consulter un dictionnaire en temps constant O(1), alors que les techniques à base d'arbre nécessitent en moyenne O(logn) opérations si la taille du dictionnaire est de n mots. Nous allons essayer de comprendre pourquoi en corrigeant les fautes d'orthographe d'un texte de Proust : Du côté de chez Swann (ou plutôt en vérifiant que notre dictionnaire contient bien tous les mots qu'il faut!!).

Ce programme s'écrit très simplement en utilisant la classe "HashMap" de Java. Le voici :

spellcheck 
public class spellcheck {
    public static void main(String args[]) throws IOException {
        HashMap dict = new HashMap();
        String word;
        try {
            BufferedReader in = new BufferedReader(new FileReader("francais.mots"));
            while ((word = in.readLine()) != null) {
                dict.put(word, new Integer(1));
            }
            in.close();
        } catch (IOException e) {
            System.err.println(e);
            return;
        }

        try {
            BufferedReader in = new BufferedReader(new FileReader("proust.txt"));
            PrintWriter out = new PrintWriter(new FileWriter("erreurs.txt"));
            while ((word = in.readLine()) != null) {
                if (!dict.containsKey(word) && !dict.containsKey(word.toLowerCase())) {
                    out.println(word);
                }
            }
        } catch (IOException e) {
            System.err.println(e);
            return;
        }
    }
}


ATTENTION Ce programme n'est qu'un exemple. Vous ne pouvez pas l'utiliser tel quel pour faire des mesures. Il vous faut donc tout réécrire [remarque : cela ne fait qu'au plus 30 lignes !!] : L'allocation de la table de hascode et les deux procédures qui consultent un dictionnaire et qui introduisent un nouveau mot dans le dictionnaire. Cela bien sûr pour chacune des méthodes proposées. Vous avez le choix du langage. Personnelement je programme tout en Java, car ce langage est infiniment supérieur à C. Mais il faut de tout pour faire un monde.

2  Le matériel

Essentiellement je vous donne un dictionnaire du français et le texte de Proust. J'espère que ces deux documents n'ont pas de droits de diffusions.

Le dictionnaire : Il a été extrait du dictionnaire du français-GUTemberg 1.0 que l'on trouve sur Linux. En fait j'ai un peu modifié ce dictionnaire en vous construisant la liste des mots de ce dictionnaire. Il y a tous les verbes conjugés ainsi que les pluriels et féminins et quelques noms propres. C'est cette liste que vous devez utiliser pour le devoir. Il y a 342538 entrées dans ce dictionnaire pour une taille de 3,6 Moctets. Voici également ce dictionnaire en format compressé(francais.mots.gz) [819.2 Ko].

Le texte : Il s'agit des premiers chapitre d'un texte que j'aime bien de Marcel Proust -- A la Recherche du Temps Perdu - Du Côté de chez Swann -- Combray. Ce texte est ici : longtempsJeMeSuisCouche.txt. Pour vous faciliter la tache, j'ai enlevé la ponctuation et les apostrophes. Le texte sur lequel vous devez travailler est ici : proust.txt : il y a 79019 mots pour une taille de 419 Ko. Ce texte est extrait du site du Projet Gutenberg (10000 livres en ligne) : http://www.ibiblio.org/gutenberg/, on peut extraire de ce catalogue les livres en français. Il est également intéressant de consulter le site de l'ABU la Bibliothèque universelle : http://abu.cnam.fr/. Il y a 288 textes.

3  Ce qu'il y a à faire

Le vrai sujet du devoir
  1. Etude de la fonction de hachage : Utiliser la fonction de hachage de java ou celle décrite dans le cours ou une autre!! et vous allez compter la répartition des conflits en fonction de la taille de la mémoire que vous avez choisie. Vous utiliserez le dictionnaire du français fourni précédemment. Vous comparerez ces résultats aux calculs théoriques que l'on à fait dans le cours. Peut-on affirmer que la répartition des clés est aléatoire? Est-ce important?
  2. Mesure des performances en utilisant les listes chainées pour résoudre les conflits : Vous allez mesurer le temps ainsi que le nombre de comparaisons nécessaires pour vérifier si les mots du texte de Proust appartiennent bien au dictionnaire. Vous compterez séparément le nombre de comparaisons nécessaires suivant que le mot appartient ou non au dictionnaire. Est-ce que les résultats ressemblent à ce que l'on avait calculé en cours de manière théorique?
  3. Mesures des performances en utilisant le "linear probing" : mêmes commentaires qu'a la question précédente.
  4. Mesures des performances en utilisant le "double hashing" : mêmes commentaires qu'a la question précédente.
  5. Concluez, en indiquant quel est selon vous la meilleure méthode? Une analyse de la mémoire utilisée serait importante pour cette conclusion.
  6. Que pensez-vous des mots du texte de Proust qui n'étaient pas dans le dictionnaire? Comment pourrait-on faire quand un mot n'est pas dans le dictionnaire pour suggérer une orthographe?
Votre document ne devrait pas dépasser une dizaine de pages. Les deux ou trois premières pages seront consacrés à décrire la méthode et les résultats théoriques. Puis on devrait trouver des tableaux de mesures qui permettront de justifier les conclusions.

Si il y a quelque chose qui vous semble obscur, n'hésitez pas à m'envoyer un mail.

4  Quelques uns de mes résultats

Remplissage des boites

Il s'agit de voir comment les clé se répartissent dans les différentes entréees de la table. On a N = 342538. J'ai choisit M = 600000. On a donc alpha = 0.57. Voici les résultats expérimentaux et théoriques :
nb elem dans la boite nb de boites mesurée nb de boite théorique
0 338982 339011
1 193485 193540
2 55447 55246
3 10400 10513
4 1492 1500
5 175 171
6 17 16
7 2 1

On s'aperçoit d'une très bonne concordance entre les résultats théoriques et les résultats pratiques

Linear Probing

J'ai fait varier la table de hash-code de M=400 000 à M=1 200 000 cases. En utilisant toujours le même dictionnaire du français. Voici mes résultats (mais on aurait pu aussi regarder comment se répartissent les clusters,...):

Linear Probing 
N = 342538, nbMots = 79019, inDico = 77784, outDico = 1235, nbEchecs = 4756
---------------------------------------------------------------------------
 M      alpha   nbCmpD  lgIns   lgSu    lgSuT   lgEc    lgEcT   nbCmpT  tDico   tSpell
400     0.856    1422   4.151   4.684   3.972   26.761  24.613  491618  870      186
500     0.685    462    1.351   2.35    2.087   4.188   5.539   202704  795      145
600     0.571    275    0.804   1.834   1.666   2.24    3.217   153287  718      126
700     0.489    196    0.573   1.594   1.478   1.323   2.415   130296  926      112
800     0.428    152    0.446   1.33    1.374   0.945   2.028   107937  729      102
900     0.381    125    0.366   1.326   1.308   1.109   1.805   108411  902       94
1000    0.343    104    0.305   1.259   1.261   0.595   1.658   100729  668      151
1100    0.311    90     0.263   1.247   1.226   0.867   1.553   101141  875      140
1200    0.285    79     0.232   1.2     1.199   0.453   1.478   95482   781      132


Voici le mode d'emploi : Je vous donne cela à titre d'exemple, vous pouvez mesurer d'autres choses et bien sûr trouver des valeurs très différentes des miennes!!

Double Hashing

J'ai refait exactement la même expérience avec la méthode du double hashing.

Double Hashing 
N = 342538, nbMots = 79019, inDico = 77784, outDico = 1235, nbEchecs = 4756
---------------------------------------------------------------------------
 M      alpha   nbCmpD  lgIns   lgSu    lgSuT   lgEc    lgEcT   nbCmpT  tDico   tSpell
400     0.856   438     1.28    2.329   2.264   8.238   6.944   220311  1091    127
500     0.685   236     0.689   1.766   1.686   2.177   3.175   147722  822     100
600     0.571   164     0.481   1.537   1.482   1.574   2.331   127064  1009    100
700     0.489   127     0.373   1.356   1.373   1.083   1.957   110607  766     112
800     0.428   105     0.307   1.244   1.305   0.816   1.748   100682  848     138
900     0.381   89      0.26    1.203   1.259   0.712   1.616   96994   768     101
1000    0.343   76      0.224   1.207   1.225   0.569   1.522   96583   857     138
1100    0.311   67      0.198   1.183   1.198   0.525   1.451   94527   761     108
1200    0.285   60      0.177   1.144   1.177   0.397   1.399   90903   865     101


C'est la même légende que pour l'expérience précédente.

Un petit test en Java

j'ai utilisé la bibliothèque de java pour comparer la classe "HashMap" avec la classe "TreeMap". Voici les résultats :

Classe HashMap de Java
Mémoire utilisée = 36142936octets
Temps de construction = 4232ms, Temps de consultation = 122ms

Classe TreeMap de Java
Mémoire utilisée = 36785840octets
Temps de construction = 3768ms, Temps de consultation = 309ms

A vous de jouer maintenant............




Lundi 22 novembre 2004
©2004 Michel Van Caneghem