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) :
Le programme suit les recommandations données par Koenig et Moo, que je traduis ainsi :
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 est testé avec un petit fichier de données de deux lignes :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é.
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 :
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
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); }
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; }
Partager