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