Trouver dans un texte les séquences répétées

Version imprimable

12/03/2009, 19h05
Amybond

Trouver dans un texte les séquences répétées

Bonjour,
Je souhaite répertorier toutes les séquences répétées (de longueurs variables) dans un texte donné. Comment dois-je m'y prendre ?

Merci d'avance
13/03/2009, 07h50
Cbenlfun

Moi à ta place je ferais un tableau de chaines de caractère avec std::vector et std::string.

Je lui affecterais mes séquences une par une en effectuant des test pour détecter les doublons.

Le programme pourrait écrire les informations sur les séquences répétées dans un fichier texte avec std::fstream.

Il pourrais aussi faire une copie du fichier d'origine sans les doublons ou même, afficher les parties redondantes et demander à l'utilisateur quoi faire avec.

Sa dépend de ton but.

J'espère t'avoir été utile.
13/03/2009, 10h34
Cheps

Tu cherches des occurences de mots (séparés par des espaces) ou des séquences quelconques? Dans le premier cas c'est assez trivial avec une simple itération sur le texte, par contre le second cas peut s'avérer plus délicat.
13/03/2009, 11h33
r0d

Dans tous les cas, la solution la plus simple consiste à utiliser la classe std::string et sa fonction membre find().
13/03/2009, 12h47
Amybond

Merci pour vos réponses

Je souhaite créer un décrypteur du chiffre de Vigenère.
Donc ce sont des séquences quelconques. http://www.apprendre-en-ligne.net/cr...decodevig.html

Concrètement, comme le faire avec std::string. Car elle peut être aléatoire et de longueur elle aussi aléatoire.

Merci d'avance

Je ne comprends pas le décrypteur de Vigène, mais voici un exemple d'utilisation de la fonctino membre find de la classe string:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
 
int main()
{
	std::string str = "ceci est une chaine de caractere de test";
	size_t pos = str.find( "de" ); // on trouve la premiere occurrence de "de"
	while ( pos != std::string::npos ) // tant que l'on a pas atteint la fin de la chaine de test
	{
		std::cout << "pos = " << pos << std::endl; // on affiche la position du "de" trouvé
		pos = str.find( "de", pos+1 ); // on cherche la prochaine occurrence de "de" à partir de la dernière occurrence trouvée
	}
 
	// end
	std::cout << std::endl << "fini" << std::endl;
	std::cin.get();
	return 0;
}

Ce petit programme va donner comme résultat:

Citation:

pos = 20
pos = 33

fini

J'espère que ça pourra t'aider.

13/03/2009, 14h45
Cheps

Si j'ai bien compris le problème, il n'a pas une chaîne donnée à chercher, mais il doit chercher toutes les séquences se répétant dans le code. Par exemple: fgjdsiugfjiughufdTOTOnvjkxnvjkxcTOTOvnmxklvnmx, il veut trouver "TOTO".

Evidemment on pourrait imaginer un algorithme trivial "brute force", mais si tu as des textes relativement longs ce sera très mauvais en performances. Tu devrais peut-être poser la question dans la section algorithmes.
13/03/2009, 17h24
Amybond

Merci pour l'exemple mais je ne sais pas du tout quel mot je dois chercher ... c'est ça le problème.
Et par brute force cela s'avère très long ...

Je vais poster sur le forum Algorithmes ;)

Je vous tiens au courant
13/03/2009, 19h36
SKZ81

Jette un coup d'oeil du côté de l'algo de ZIP, je sais plus le nom exact.

PS : aucune garantie qu'il te trouve un résultat exact, et ton pb est NP complexe, donc à par le brute force, je te conseille comme alternative l'ordinateur quantique.

A bon entendeur...
13/03/2009, 20h53
Amybond

Tu parles de l'algorithme de compression ZIP ?
13/03/2009, 21h03
coyotte507

Salut, c'est sûr que le brute force n'est pas la meilleure solution, mais il s'exécute seulement en O(n²), ce qui n'est pas si mauvais que ça!

Sinon, il y a une autre solution, qui pourrait se rapprocher de certains algorithmes de tris, et qui utilise ... des arbres?

Tu crées une racine tout d'abord, puis 26 nœuds (chaque nœud correspond à un caractère différent)

Par exemple le nœud 0 correspond au caractère A,..., le nœud 25 au caractère Z.

Dans chaque nœud tu mets une liste chainée qui répertorie les différentes positions du caractère correspondant au nœud dans le texte.

Tu supprimes les nœuds qui ont moins de deux éléments dans leur liste, car il n'y aura pas de répétitions...

Ensuite, tu pars d'un nœud qu'on va appeler Noeud X et à ce noeud tu en associes 26 autres, qui correspondent encore aux caractères A,B,...,Z.

Le noeud X contient un répertoire de positions correspondant à la même lettre, pour chaque position tu regarde la lettre d'après et stocke sa position dans le noeud de X correspondant.

Tu supprimes tous les nœuds de X contenant moins de deux positions.

Ainsi, pour le moment, tous les nœuds de X correspondent à des séquences de deux lettres qui se répètent.

Si tu répètes la démarche pour un nœud de X, tu auras des séquences de trois lettres. Répète-là encore une fois, si tu veux, et tu auras des séquences de 4 lettres. Je crois qu'il n'y a pas besoin d'aller plus loin que quatre lettres.

Une fois que tu est arrivé à une fin d'arborescence (plus de nœuds ou alors un nœud qui correspond à des séquences de quatre lettres), tu stockes les séquences trouvées, reviens en arrière et supprimes le nœud sur lequel tu as travaillé (pour libérer de l'espace mémoire), et regarde le nœud suivant.

Voilà pour le principe.

Cet algorithme a une complexité en O(n).

Note que j'ai utilisé le terme d'arbre, mais que tu peux vraiment implanter ça différemment (d'ailleurs moi j'utiliserais 4 tableaux contenant chacun 26 listes chainées)

Mais ne t'inquiètes pas, si tu trouves mon explication trop peu claire ou trop compliquée, le brute force reste toujours une option envisageable!
13/03/2009, 21h50
Amybond

Mais ça ne correspond pas à bruteforce ? Car on crée toutes les possibilités entre a et zzzz (exactement comme bruteforce)

Non, pas vraiment.

Le bruteforce consiste à, pour chaque position dans le texte, regarder si la séquence à cette position est aussi présente plus tard dans le texte.
Code:

1 2 3 4 5 6 7 8 9 10 11 //regarder les séquences de trois lettres //L'algorithme du brute force, dans l'esprit for(int i = 0; i < texte.length()-5; i++) { for(int j = i+3; j < texte.length()-2;j++) { if (texte.substr(i, 3) == texte.substr(j,3) { //séquence repérée!! } } }
Par exemple, dans le texte:

Citation:

Mignonne, allons voir si la rose

Avant qu'on arrive au passage "all", on aura déjà comparé "all" à "Mig", "ign", "gno", "non", "onn", "nne", "ne,", "e, ".
Puis on quand on arrive à "all" on le compare à toute la suite...

Procéder ainsi demande un temps proportionnel au carré de la longueur du texte. (O(n²))

La différence, avec l'algorithme de mon post d'avant, c'est que je ne compare jamais deux chaines entre elles, en fait c'est comme si je les triais en groupes...

Cette méthode permet d'avoir un temps linéaire, proportionnel à la longueur du texte. (O(n))

Et je ne crée pas toutes les possibilités: je supprime les noeuds inutiles, c'est à dire les séquences qui ne sont présentes qu'une fois ou pas présentes dans le texte -- et ce faisant il y a plein de possibilités que je n'explore pas.

Par exemple, dans mon exemple d'avant, aucune séquence de deux lettres ou plus envisagée ne commencera par 'u', 'j', 'z', 'k', 'q', 'x', 'y', 't', 'p', 'c', 'w', ...

14/03/2009, 11h13
Amybond

Mais donc il teste uniquement les chaines de 3 caractères ?
14/03/2009, 15h40
coyotte507

Le bruteforce que je t'ai montré c'était pour le chaines de 3 caractères, Mais tu peux faire comme tu veux.

De toute façon, dès que tu as trois caractères qui sont identiques, c'est bon, non?

Sinon tu peux le modifier pour faire 4 caractères, ou plus, comme tu veux.
14/03/2009, 23h58
Amybond

Je vais essayer de le faire sans passer par bruteforce.
Par exemple en utilisant les indices de coïncidences.