Index permuté pas aligné

Version imprimable

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:

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 :

Citation:

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:

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:

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:

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:

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;
}

Citation:

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:

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

14/05/2009, 15h20
ptyxs

Ah oui en effet ! Merci.

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:

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:

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:

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

15/05/2009, 07h13
ptyxs
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:

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:

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...
15/05/2009, 08h49
Goten

T'as inclus <locale> ?
15/05/2009, 08h55
ptyxs

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 ?
15/05/2009, 09h06
Goten

En fait j'avais mal lu, j'ai vu que tu arrivais pas à compiler.
15/05/2009, 10h11
ptyxs

Je n'ai rencontré aucun problème à la compilation.
15/05/2009, 11h17
JolyLoic

Ok, ça veut donc dire que ton éditeur travaille en UTF-8, où un caractère é est représenté par 2 caractères, et que ton compilateur ne comprend pas ce langage là, ou pas bien, du moins tel que tu l'invoques.

Ne travaillant pas sous Linux avec gcc, je n'ai pas d'expérience sur ce problème. Un rapide google m'a retourné : http://mail.nl.linux.org/linux-utf8/.../msg00009.html

Peut-être en jouant là dessus et sur l'encoding de ton fichier peux tu avoir des résultats, mais ça me semble aller à contre courant de ce que j'ai compris de la mode Linux qui voudrait qu'UTF-8 soit le standard pour tout.
15/05/2009, 12h29
ptyxs

Unicode c'est une 'mode Linux', ça alors , j'en apprends des choses !!

En fait quelque part dans son bouquin The C++ Programming Language, Stroustrup dit si je me souviens bien que les string peuvent traiter sans problème Unicode, mais sans donner de détails...

D'une manière générale une bonne doc ou un bon bouquin sur le traitements en C++ des caractères, autres qu'ASCII strict, qu'on trouve dans les orthographes des langues humaines, ça m'intéresserait bien.
15/05/2009, 12h37
Médinoc

Ce n'est pas Unicode qui est la mode Linux, c'est plus "UTF-8 sans BOM partout".
15/05/2009, 13h08
ptyxs
J'avais pensé qu'utiliser wstring pourrait peut-être aider. Et en effet, ceci :
Code:

1 2 3 4 5 6 7 8 9 10 11 #include <iostream> #include <string> using namespace std; int main() { wstring s = L"clé"; wcout << s.size() << endl; }
me donne correctement en sortie....
3
!!
Je vais voir ça...
15/05/2009, 13h36
Médinoc

Mais là, ce n'est pas de l'UTF-8, mais une chaîne de caractères "larges". Généralement de l'UCS-4 (ou UTF-32) sous Linux, et de l'UTF-16 sous Windows.
15/05/2009, 15h02
ptyxs

Le fil suivant semble intéressant pour convertir de l'UTF-8 en caractères larges :

http://www.cplusplus.com/forum/beginner/7233/

Mais je le répète une bonne doc accessible faisant le point sur ces problèmes semble dramatiquement faire défaut. C'est un peu étrange que des points si cruciaux pour le traitement des langues humaines (autres que l'anglais) soient si difficiles à clarifier...
15/05/2009, 15h53
Médinoc
Il faut dire que ce ne sont pas des problèmes faciles à résoudre non-plus:
- Problème d'unicode avec UTF-8
- Impossibilité d'utiliser les fonctions texte de stdio.h pour écrire un fichier en caractères larges de manière standard
- Manque de fonctions à la fois standard et sûres pour convertir entre caractères minces et larges (les seuls noms de locale standard sont "" et "C")
- Problème des consoles sous Windows (dû à la compatibilité DOS), résolu en .Net mais pas en Win32
Etc.
15/05/2009, 15h56
ptyxs

Sur le BOM, je trouve ceci dans Wikipédia, qui semble indiquer que l'absence de BOM dans les systèmes de type Unix n'est pas purement un effet de mode...

Citation:

Beaucoup de logiciels Windows (incluant Windows Notepad) en ajoutent un aux fichiers UTF-8. Cependant, sur des systèmes de type Unix (qui utilisent beaucoup les fichiers textes pour la configuration) cette pratique n'est pas recommandée, car cela peut interférer avec le traitement adéquat de codes importants tels que le sha-bang au début d'un script interprété[3]. Il peut également interférer avec le source pour les langages de programmation qui ne le reconnaissent pas. Par exemple, gcc reporte des stray characters au début du fichier source, et en PHP, si l'output buffering est désactivé, cela a pour effet subtil de faire que la page commence immédiatement à être envoyée au navigateur, et d'empêcher les custom headers d'être spécifiés par le script PHP. La représentation UTF-8 du BOM est la séquence d'octets EF BB BF, qui apparaît en codage ISO-8859-1 comme "ï»¿" dans les éditeurs de textes et navigateurs mal préparés pour traiter l'UTF-8. Ils peuvent également échouer à appliquer la première règle d'une feuille CSS[4].

J'ajoute que dans la page en anglais de Wikipédia il est indiqué que le comité de normalisation Unicode admet le BOM mais ne le recommande pas pour l'UTF-8 :

Citation:

While UTF-8 does not have byte order issues, a BOM encoded in UTF-8 may nonetheless be encountered. A UTF-8 BOM is explicitly allowed by the Unicode standard[1], but is not recommended[2], as it only identifies a file as UTF-8 and does not state anything about byte order.

(Trad : Bien qu'en UTF-8 il n'y ait pas de problème d'ordre des octets, il peut arriver tout de même de rencontrer un BOM encodé en UTF-8. Un BOM UTF-8 est explicitement accepté par le standard Unicode, mais il n'est pas recommandé, étant donné qu'il ne sert qu'à identifier un fichier comme étant en UTF-8 et ne dit rien de l'ordre des octets.)
15/05/2009, 15h59
Médinoc

Disons que la BOM n'est pas nécessaire si tout est déjà UTF-8, mais comme ça n'est pas le cas (surtout sous Windows)...

Pour ses extensions de la CRT, Microsoft a trouvé le truc: La BOM est traitée de manière transparente par les fonctions d'accès aux fichiers, le programme utilisateur ne voit donc pas de stray characters...
15/05/2009, 16h04
ptyxs

Bon, finalement je ne suis pas parvenu à résoudre vraiment le problème, mais au moins à comprendre sa nature, ce qui est rassurant...
Merci à tous.