dimanche 1 juin 2014

TD 3



Pour "finir" de se familiariser avec la notion de pointeur, nous allons nous attaquer à un problème difficile : la reconstruction de documents détruits...

Cela nous permettra de voir les limitations de l'utilisation des tableau, avant de voir (la semaine prochaine) d'autres structures...


Préambule important : vous devez maintenant toujours tester votre programme avec valgrind! Si vous détectez une erreur, vos devez d'abord corriger l'erreur avant d'essayer d'aller plus loin dans le TD.

Le document que nous allons "détruire", puis tenter de reconstruire est le fichier "betty.txt". Pour le "détruire" nous allons simplement mélanger les lignes de ce document. (Un vrai destructeur de document mélangerait les colonnes, mais cela ne change pas grand chose à la problématique).
  • Tout d'abord, avant de reconstruite, il faut détruire... Vous allez donc, à partir du dernier programme fait en TD, faire un programme qui :
    • charge le fichier "betty.txt" en mémoire (déjà fait)
    • mélange aléatoirement les lignes (via un astucieux échange de pointeurs)
    • affiche le tableau ainsi mélangé (déjà fait)
      • ./shredder < betty.txt > doc_detruit.txt 
      • Ensuite, vous utilisez votre programme comme ceci, pour créer un fichier contenant le fichier détruit : 
         
    • Comme vu en cours, vous allez maintenant essayer d'écrire un nouveau programme qui
      • met le document détruit en mémoire (déjà fait)
      • ensuite vous écrivez une fonction qui permet de calculer la similarité entre 2 lignes de texte.
      • vous appliquez cette fonction de manière à calculer la "continuité" de l'ensemble document. C'est à dire calculer et additionner les mesure de similarité de toutes les lignes 2 à 2.
      • Vérifiez que votre mesure de similarité est cohérente. Pour cela calculez la mesure de similarité sur betty et sur le document détruit. Normalement la mesure doit être forte sur betty et plus faible sur le document détruit.
    • Vous pouvez maintenant commencer à implémenter un algorithme d'optimisation de ce score de similarité
      1. mesurez le score de continuité du document
      2. permutez (au hasard) deux lignes du document
      3. mesurer la continuité de cette nouvelle configuration
      4. Si la mesure est meilleure que la situation précédente, on affiche le nouveau score et le document (pour voir le résultat). On met aussi à jour la nouvelle valeur de continuité du document.
      5. Si la mesure est moins bonne, on refait la permutation (pour revenir à la situation précédente).
      6. Recommencer à l'étape 2...
      Il est à noter que cet algorithme a pas mal de défauts, en particulier celui de ne pas avoir de critère d'arrêt!
    Cela devrait être faisable en une séance.
    Si vous avez réussi tout cela, vous pouvez employer la deuxième séance pour commencer un nouveau programme de reconstruction qui implémente l'algorithme "glouton" présenté en cours. Vous devriez alors obtenir un algorithme qui est à la fois plus rapide (et surtout un algorithme qui se termine!), et qui donne de meilleurs résultats.
    Challenge "juste pour le fun" (il n'y a rien d'autre à gagner que ma considération ;) ) : essayez de retrouver ce qui est "caché" dans le document détruit attaché à cet article (voir le fichier "secret.txt").
    La fin de la solution "gloutonne" est laissé en travail personnel.

    Annexe(s):