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(log
n) 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
-
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?
- 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?
- Mesures des performances en utilisant le "linear probing" : mêmes commentaires qu'a la question
précédente.
- Mesures des performances en utilisant le "double hashing" : mêmes commentaires qu'a la question
précédente.
- Concluez, en indiquant quel est selon vous la meilleure méthode? Une analyse de la mémoire utilisée
serait importante pour cette conclusion.
- 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
| |