Index permuté pas aligné

**ptyxs** · 14/05/2009, 15h05

J'essaie de faire un petit programme créant un index permuté (sur cette notion, voir http://en.wikipedia.org/wiki/Key_Word_in_Context). Il s'agit en fait de l'exercice 05-1, p. 99 du livre Accelerated C++ de Koenig et Moo (http://www.acceleratedcpp.com/).

Un index permuté peut ressembler à ceci (tiré du lien Wikipédia) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
                 KWIC is an      acronym for Key Word In Context, ... 	page 1
                   ...  the most common format for conctordance lines. 	page 1
... the most common format for 	  concordance lines. 	                page 1

Le programme suit les recommandations données par Koenig et Moo, que je traduis ainsi :

1. Lire chaque ligne des données à traiter et pour chaque ligne lue créer un ensemble de permutations circulaires de cette ligne. Les permutations successives placent l'un après l'autre chaque mot de la ligne de données en première position en expédiant le mot qui le précédait à la fin de la ligne.
Par exemple :
The quick brown fox
quick brown fox The
brown fox The quick
fox The quick brown
2. Trier les permutations ainsi obtenues.
3. 'Dépermutez' les permutations et affichez l'ensemble de l'index, ce qui suppose de trouver le séparateur, de 'remettre la ligne à l'endroit', et de l'afficher avec un formatage approprié.

Le programme est testé avec un petit fichier de données de deux lignes :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Le vierge, le vivace et le bel aujourd'hui
Va-t-il nous déchirer avec un coup d'aile ivre

Mon problème est que dans la sortie du petit programme provisoire que j'ai tenté, les mots-clé (entourés d'un astérisque) ne sont pas alignés, certains sont dans une position n et d'autres dans une position n-1, sans que je comprenne pourquoi :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
*************AFFICHAGE DE L'INDEX*****************
                                                            *Le* vierge, le vivace et le bel aujourd'hui 
                                                            *Va-t-il* nous déchirer avec un coup d'aile ivre 
                             Le vierge, le vivace et le bel *aujourd'hui* 
                                     Va-t-il nous déchirer *avec* un coup d'aile ivre 
                                 Le vierge, le vivace et le *bel* aujourd'hui 
                             Va-t-il nous déchirer avec un *coup* d'aile ivre 
                        Va-t-il nous déchirer avec un coup *d'aile* ivre 
                                               Va-t-il nous *déchirer* avec un coup d'aile ivre 
                                       Le vierge, le vivace *et* le bel aujourd'hui 
                 Va-t-il nous déchirer avec un coup d'aile *ivre* 
                                    Le vierge, le vivace et *le* bel aujourd'hui 
                                                 Le vierge, *le* vivace et le bel aujourd'hui 
                                                    Va-t-il *nous* déchirer avec un coup d'aile ivre 
                                Va-t-il nous déchirer avec *un* coup d'aile ivre 
                                                         Le *vierge,* le vivace et le bel aujourd'hui 
                                              Le vierge, le *vivace* et le bel aujourd'hui

Le programme lit successivement les lignes du fichier de données. Il place les mots de la ligne dans un vecteur de strings (grâce à la fonction split()).
Il crée toutes les permutations circulaires des mots de la ligne (via permu()) et les stocke dans un autre vecteur de string (p).
Quand toutes les lignes ont été traitées ainsi, le programme trie p par ordre alphabétique (chaque string de p commence par un mot-clé, on obtiendra ainsi une suite alphabétique ordonnée selon la position du mot clé dans l'ordre alphabétique).
Ensuite, le programme affiche toutes les permutations en les 'dépermutant' et en affichant (normalement) tous les mots-clé les uns sous les autres à la même position (encadrés par leur contexte dans la ligne lue).

Voici le code du programme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <algorithm>
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include "split.h"
 
using namespace std;
 
const string sep = "$$$!"; // sépare la tête de la queue d'une permutation circulaire
const string::size_type nb_char = 60; // nb de car précédant le mot-clé à l'affichage
 
//--------------------------------------------------------------------------
 
vector<string>  permu(const vector<string>& mots) // renvoie l'ensemble des permutations circulaires de mots
{
  vector<string> result;
 
  for (vector<string>::size_type i = 0; i < mots.size(); ++i) { // boucle des permutations
	string s; //contiendra une permutation
 
	for (vector<string>::size_type j = i ; j < mots.size(); ++j) // début de la permu
	    if(j == i)
	      s += '*'+mots[j]+'*'+' ';
	    else
	      s += mots[j]+' ';
 
 
	s += sep; //fin de la ligne d'origine
 
	for (vector<string>::size_type k = 0; k < i; ++k) //fin de la permu (début de la ligne d'origine)
	    s += mots[k]+' ';
 
	result.push_back(s);
  }
 
  return result;
}
 
//-------------------------------------------------------------------------
 
void affich_permu(vector<string>  p)
{
  for (vector<string>::iterator it = p.begin(); it < p.end(); ++it) {
 
string::iterator itstr = search(it->begin(), it->end(), sep.begin(), sep.end()); // on cherche le séparateur
 
      itstr += sep.size(); // on saute le séparateur
 
 
      if (itstr >= it->end()) { // le séparateur est en fin de ligne
	  string s(it->begin(), it->end()-sep.size());
	  cout << string(nb_char, ' ')  << s  << endl; //on affiche toute la ligne à droite de nb_char espaces
      }
      else {
	string s1(itstr, it->end()); // s1 contient la partie de ligne à droite du séparateur
 
	cout << string(nb_char - s1.size(), ' ') << s1; // on l'affiche à gauche
 
	string s2(it->begin(),it->end()-s1.size()-sep.size()); // s2 contient ce qui est à gauche du séparateur
	//s2 commence par le mot-clé, on l'affiche après s1
	cout << s2 << endl;
      }
 
 
  }
}
 
//-------------------------------------------------------------------------
 
int main()
{
  ifstream ifs("input");
  string s;
  vector<string> p;
 
  while(ifs) {
      getline(ifs, s);
 
      vector<string> v = split(s); // v contient les mots de la string s
 
      vector<string> tmp;
      tmp = permu(v); // tmp contient toutes les permutations cirulaires de v
      // la boucle suivante les ajoute dans le vecteur p
      for (vector<string>::iterator it = tmp.begin(); it < tmp.end(); ++it)
	  p.push_back(*it);
  }
 
  sort(p.begin(),p.end()); // on trie p pour avoir ensuite un index par ordre alphabétique des mots-clé
 
  //boucle provisoire, pour la mise au point, qui affiche toutes les permutations circulaires contenues dans p
  for (int i = 0; i < p.size(); ++i) {
    cout << p[i] << ' ';
 
    cout << endl;
  }
 
  cout << endl;
  cout << "*************AFFICHAGE DE L'INDEX*****************" << endl;
  // affiche l'index permuté
  affich_permu(p);
}

La fonction split(), due à Koenig et Moo se présente ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cctype>
#include <string>
#include <vector>
 
#include "split.h"
 
using std::vector;
using std::string;
 
#ifndef _MSC_VER
using std::isspace;
#endif
 
vector<string> split(const string& s)
{
	vector<string> ret;
	typedef string::size_type string_size;
	string_size i = 0;
 
	// invariant: we have processed characters `['original value of `i', `i)'
	while (i != s.size()) {
		// ignore leading blanks
		// invariant: characters in range `['original `i', current `i)' are all spaces
		while (i != s.size() && isspace(s[i]))
			++i;
 
		// find end of next word
		string_size j = i;
		// invariant: none of the characters in range `['original `j', current `j)' is a space
		while (j != s.size() && !isspace(s[j]))
			++j;
 
		// if we found some nonwhitespace characters
		if (i != j) {
			// copy from `s' starting at `i' and taking `j' `\-' `i' chars
			ret.push_back(s.substr(i, j - i));
			i = j;
		}
 
	}
	return ret;
}

**Médinoc** · 14/05/2009, 15h15

Envoyé par ptyxs

NB Le rouge qui apparaît ici n'a aucune pertinence.

Tu peux te débarrasser du rouge en ajoutant "=X" dans ta balise CODE. Ça donne ceci:

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
*************AFFICHAGE DE L'INDEX*****************
                                                            *Le* vierge, le vivace et le bel aujourd'hui 
                                                            *Va-t-il* nous déchirer avec un coup d'aile ivre 
                             Le vierge, le vivace et le bel *aujourd'hui* 
                                     Va-t-il nous déchirer *avec* un coup d'aile ivre

**ptyxs** · 14/05/2009, 15h20

Ah oui en effet ! Merci.

**JolyLoic** · 15/05/2009, 02h52

J'ai tout de suite remarqué quelque-chose : Les lignes décalées sont celles ayant un accent à afficher en premier...

Et quand j'ai recompilé sur ma machine (visual C++2008), j'ai un assert quand on fait isspace sur... le 'é' !

Du coup, j'ai modifié la fonction split :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
		while (i != s.size() && isspace(static_cast<unsigned char>(s[i])))
			++i;
 
		// find end of next word
		string_size j = i;
		// invariant: none of the characters in range `['original `j', current `j)' is a space
		while (j != s.size() && !isspace(static_cast<unsigned char>(s[j])))
			++j;

Car en effet, dans la tradition C, isspace prend en paramètre non pas un char, mais un int. Et un char négatif se cast en int négatif, ce qui pose problème.

Voulant du code plus propre que ce cast, je suis passé par la fonction C++ de détection d'espace :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
		while (i != s.size() && isspace(s[i], std::locale::locale()))
			++i;
 
		// find end of next word
		string_size j = i;
		// invariant: none of the characters in range `['original `j', current `j)' is a space
		while (j != s.size() && !isspace(s[j], std::locale::locale()))
			++j;

Dans les deux cas, j'ai bien :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
                                                  *Le* vierge, le vivace et le bel aujourd'hui
                                                  *Va-t-il* nous déchirer avec un coup d'aile ivre
                                                  *Va-t-il* nous déchirer avec un coup d'aile ivre
                   Le vierge, le vivace et le bel *aujourd'hui*
                            Va-t-il nous déchirer *avec* un coup d'aile ivre
                            Va-t-il nous déchirer *avec* un coup d'aile ivre
                       Le vierge, le vivace et le *bel* aujourd'hui
                    Va-t-il nous déchirer avec un *coup* d'aile ivre
                    Va-t-il nous déchirer avec un *coup* d'aile ivre
               Va-t-il nous déchirer avec un coup *d'aile* ivre
               Va-t-il nous déchirer avec un coup *d'aile* ivre
                                     Va-t-il nous *déchirer* avec un coup d'aile ivre
                                     Va-t-il nous *déchirer* avec un coup d'aile ivre
                             Le vierge, le vivace *et* le bel aujourd'hui
        Va-t-il nous déchirer avec un coup d'aile *ivre*
        Va-t-il nous déchirer avec un coup d'aile *ivre*
                          Le vierge, le vivace et *le* bel aujourd'hui
                                       Le vierge, *le* vivace et le bel aujourd'hui
                                          Va-t-il *nous* déchirer avec un coup d'aile ivre
                                          Va-t-il *nous* déchirer avec un coup d'aile ivre
                       Va-t-il nous déchirer avec *un* coup d'aile ivre
                       Va-t-il nous déchirer avec *un* coup d'aile ivre
                                               Le *vierge,* le vivace et le bel aujourd'hui
                                    Le vierge, le *vivace* et le bel aujourd'hui

**ptyxs** · 15/05/2009, 07h13

Oh mais c'est bien sûr !!! Je n'avais pas vu cette histoire de 'é', honte à moi ! Je vais essayer tes propositions.
EDIT :
En fait la fonction size() de string compte deux caractères pour un 'é', d'où mon problème.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
  string s("clé");
  cout << s.size() << endl;
 
}

donne en sortie : 4

Dans mon programme, quand on affiche la première de deux string d'une ligne de sortie on démarre donc un caractère trop à gauche quand elle contient un 'é', voir la ligne s:uivante du code (dans la fonction affich_permu()) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cout << string(nb_char - s1.size(), ' ') << s1; // on l'affiche à gauche

s1.size() est en excès d'une unité pour les lignes avec un 'é' dans s1, et, du coup, on affiche un espace de moins que nécessaire devant s1.

Malheureusement, sur mon système (Linux, version Ubuntu 9.04, compilateur g++) aucune de tes deux propositions, qui compilent toutes les deux correctement, ne change le problème en sortie...

**Goten** · 15/05/2009, 08h49

T'as inclus <locale> ?

**ptyxs** · 15/05/2009, 08h55

Oui. J'ai inclus <locale>.
La question - générale - devient : comment faire en sorte (et en particulier dans un environnement Linux/g++) que string.size() ne compte qu'un seul caractère pour un caractère accentué du français ?

Index permuté pas aligné

C++

Vue hybride

Discussions similaires

Partager

Partager