Gestion ficher .txt C++Résolu

Question

Bonjours à vous, je travail actuellement sur un projet de décryptage, et la méthode de cryptanalyse que je suis mener à utilisé est le forçage par dictionnaire, c'est-à-dire que j'ai un texte codé, j'essaye plusieurs solution et je vérifie dans le dictionnaire si les mots trouvés existent. Voilà pour la petit histoire... Maintenant, j'ai mon dictionnaire en .txt et mon code principale de décryptage, pour une recherche normale dans mon dictionnaire, pas de soucis, je lis ligne après ligne mon fichier, je compare avec ce que j'ai trouvé, si ça correspond pas je passe à la ligne suivant et ainsi de suite jusqu'à la fin du fichier texte. Si aucun mot ne correspondait, je test une autre solution, etc... Malheureusement, comme vous pouvez le pensez cette méthode n'est pas très optimisé, dès qu'on a plusieurs solution à vérifier, le temps devient trop grand, c'est pourquoi j'aimerais faire une recherche dichotomique dans mon dictionnaire. Mais pour cela, à vrai dire je ne vous pas comment modifier mon ancien programme pour y arriver... Je suppose qu'il faudrait partir comme ça :
double i(0);
ifstream fichier("dico.txt", ios::in); //ouverture du fichier nommé "dico"
if(fichier)	//si le fichier c'est bien ouvert
    {
        while(getline(fichier, ligne)) //lecture ligne par ligne du fichier 
        {
i++;
}
        i= (int) i/2 ; // milieu de mon dictionnaire
 
Mais par la suite, comment lire la ligne numéro i ?

Merci d'avance, Scorp'

cptpingu · Accepted Answer

La dichotomie n'est pas du tout la méthode la plus rapide :)
Dans ce cas, c'est la table de hachage qui donne les meilleurs résultats.

En C++, tu as l'arbre de recherche (std::map) qui sera déjà pas mal. En C++11 (si tu l'as), c'est la table de hachage (std::unordered_map) qui est la plus rapide (et de très très loin puisque la complexité est de 0(1), contre O(log n) pour la dichotomie et l'arbre, contre O(n) pour la recherche classique).

#include <string>
#include <fstream>
#include 
#include <map>

int main()
{
  std::map<std::string, bool> map;
  std::ifstream fichier("final.txt");
  if (fichier)
  {
     std::string ligne; 
     while(fichier >> ligne) 
       map.insert(std::make_pair(ligne, true));
  }

  // Vérifier si un mot est présent dans le dictionnaire:
  if (map.find("chien") != map.end())
    std::cout << "Présent" << std::endl;
  else
    std::cout << "Non présent" << std::endl;

  return 0;
}

Merci pour tes conseils, par enlevé les "using namespace" tu voulais dire faire comme ça ?

Oui, mais lis le lien, tout simplement :).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

cptpingu · Answer

Bonjour.

Je n'ai pas compris ce que tu cherches à réaliser. Si tu cherches à avoir des mots du dictionnaire aisément atteignable, il te faut les charger entièrement dans une std::map (ou une std::unordered_map si tu as C++11).
Si ton but est de faire une recherche dans un dictionnaire, alors tu les charges dans un std::vector, et tu appliques la dichotomie sur ce conteneur.

Quelques conseils:
- double i(0), peut s'écrire double i = 0; (C'est étrange d'écrire double i(0), bien que pas faux).
- Évite les "using namespace", voir: http://0217021.free.fr/portfolio/axel.berardino/articles/bon-usage-using-namespace
- Pas besoin de std::ios::in dans un std::ifstream, puisque c'est déjà un std::ostream + std::ios::in !

Pense bien à préciser, afin que l'on t'aide au mieux.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

Scorpiange · Answer

Merci de ta réponse, effectivement peut être je n'ai pas très bien précisé le but. Ce que je cherche actuellement, c'est de pouvoir trouver le plus rapidement possible un mot dans le dictionnaire.
Pour cela, la recherche dichotomique, après quelque essaie sur des tableaux de nombres, est la meilleur solution car elle s’exécute plus rapidement car elle fait moins d'étapes.
Sauf que dans un tableau de nombre (classé par ordre croissant) c'est plus facile : je connais sa taille, disons 100, et si je cherche a savoir si un nombre est dans ce tableau, je pars de la case 50, si mon chiffre cherché est plus grand que celui de la case 50, je vais le comparer au chiffre de la case 75, sinon, je le compare à celui de la case 25 et je continue comme ça avec 25 ou 75. Comme ça, je diminue l'intervalle dans lequel mon chiffre peut être jusqu'à le trouver ou pas, auquel cas il n'est pas dans le tableau.
Je cherche à faire la même chose en remplaçant mon tableau par un fichier texte, et mes chiffre par des mots.
Pour ce faire, aucun problème sauf au moment ou je veux atteindre le mot du milieu du dictionnaire. Je pourrais simplement parcourir mon fichier texte jusqu'à atteindre le mot numéro i/2 (i étant le nombre de mots total du dictionnaire) mais je voudrais savoir si il n'y a pas justement une commande pour parvenir à une ligne donné, ou on peut indiqué directement la ligne que l'on veut lire. Un peu comme la fonction getline sauf en rajoutant le numéro de ligne. Vous voyez un peu ce que je veux dire ?

En abrégé je me demandais si il y a une solution pour pas être obligé de faire ça :

#include <string>
#include <fstream>
#include 

int main()
{
    int n =  3; //si par exemple le mots du milieu du dico est à la 3ème ligne
    int i = 0;
 
    std::ifstream fichier("final.txt");
 
    if(fichier)
    {
        std::string ligne; 
        while( i<n && std::getline( fichier, ligne )) 
        {
            i++;
        }
        std::cout<<ligne<<std::endl;
    }
system("pause") ;
    return 0;
}

Merci pour tes conseils, par enlevé les "using namespace" tu voulais dire faire comme ça ?

Scorpiange · Answer

D'accord merci de ta réponse, je vais voir ça !

Scorpiange · Answer

Salut, après recherche sur internet à propos des arbres de recherche j'arrive pas bien à saisir comment ça fonctionne. Est ce que tu pourrais expliquer un peu le principe ? 
Merci encore de ton aide !

cptpingu · Answer

C'est assez compliqué à expliquer.
Tout ce que je peux en dire, c'est qu'au arbre ne sera pas tellement plus rapide qu'un tableau trié avec dichotomie (même complexité). C'est simplement une manière d'ordonner les éléments qui fait que l'on a moins de parcours à réaliser qu'avec un tableau.
En revanche, l'ajout dans une map est plus rapide que d'ajouter un tableau et le trier derrière. Il est aussi plus simple d'utilisation (comme tu peux le voir dans mon exemple).

Je ne peux pas dessiner, je vais essayer de faire un schéma. Soit le tableau [4, 7, 2, 18, 5, 1] l'arbre sera:

         4
        / \
       2   7
      /   / \
     1   5   18

C'est ce qu'on appelle un arbre binaire de recherche. Le noeud de gauche est toujours inférieur au noeud courant, tandis que le noeud de droite est toujours supérieur ou égale au noeud courant.
Pour atteindre le chiffre 1, au lieu de faire 5 étapes pour le tableau non trié que tu avais, tu n'auras que 3 étapes (4, 2, 1).

Je t'invite à regarder des cours sur les abres binaires de recherche si tu veux bien comprendre le principe.
A noter que le std::map fait tout cela pour toi, de manière automatique.

Je rappelle que c'est tout de même bien moins rapide qu'une table hachage qui, quelque soit la taille de ton conteneur, coutera toujours une seul étape.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

Scorpiange · Answer

J'ai compris le principe ! Merci beaucoup :p

Gestion ficher .txt C++

7 réponses

Votre réponse

Discussions similaires