Remplacement de chaine, Aparte

[fatal_error]

Hello,

suite à http://www.maths-forum.com/remplacement-une-chaine-145734.php, mais un peu plus intéressant.

Comment écririez-vous en C++, une classe string, dont la particularité est que si plusieurs occurrences sont trouvées dans une string, alors il suffit de remplacer une seule fois pour que chacune des occurrences soit remplacée.

ex:

Code: Tout sélectionner

my::string monString = "aba";
monString=monString.replace("a","toto");

//implem de my::string::replace
my::string my::string::replace(const my::string& s, const my::string& r)const{
  size_t index= find(s);
  ?? occurrence = extract(index);
  occurrence = r;
  ??
  return replacedString;
}
//end implem


std::cout<<monString<<std::endl;
//affiche totobtoto

[Dlzlogic]

Personnellement, je crois que j'écrirais ma fonction en C, en utilisant strstr et les pointeurs.
Peut-être que je ferais une liste chainée si la chaine risque d'être longue, par exemple, s'il n'y a pas de CRLF.

[ampholyte]

Bonjour,

Petite idée : File + table de hash (avec liste chainée pour la gestion des intersections).

Explication :

Supposons la chaîne : "toto ne mange pas une pomme mais il mange deux pommes"

Supposons que la chaîne à remplacer est "mange", voici le schéma.

On cherche "mange" à l'aide d'un strstr et on ajoute dans la table de hash "toto ne mange ". On ajoute l'index dans une file.

On rajoute dans la table de hash "mange" et on ajoute l'index dans la file.

On cherche "mange" ...., on ajoute " pas une pomme mais il " dans la table et on ajoute l'index dans la file.

On ajoute le reste dans la table de hash et on rajoute l'index dans la file.

Récapitulons ce qu'on obtient :

- Une table de hash contenant la décomposition de notre phrase
- Une file contenant l'ordre des index à appeler pour reconstituer notre phrase.

On remplace "mange" dans notre table de hash par le mot à remplacer

Il suffit ensuite de concatener les index en defilant notre file et on obtient le résultat

J'avoue que ça à l'air un peu tiré par les cheveux, mais c'est la seule idée qui me vient à l'esprit à cette heure :D. Mais cela à le mérite de ne modifier qu'une seule fois la chaine "mange"

[Dlzlogic]

Bonsoir Ampholyte,
Oui, à mon avis c'est tout à fait cela.
On fait une liste chainée de pointeurs de tous les bouts de phrase qui commencent après le mot à remplacer, en plus depuis le début, et qui se termine par un \0 juste avant le mot à remplacer.
pour la restitution il suffit de lister la liste chainée en rajoutant à chaque fois le mot de remplacement.
En fait, je ne suis pas sûr qu'il faille utiliser une table de hachage. A mon avis, une liste chainée suffit.
L'intérêt d'une liste chainée est qu'il n'y a pas besoin d'index, d'autant que la chaine est strictement séquentielle.
On ne modifie pas la chaine à remplacer, on la supprime, et on sait qu'au résultat final, il faudra concaténer le chaine de remplacement.
La seule difficulté, à mon avis est l'espace mémoire nécessaire. Éventuellement la solution serait de commencer par la fin.
Mais à cette heure-ci :dodo:

[ampholyte]

Bonsoir Ampholyte,
Oui, à mon avis c'est tout à fait cela.
On fait une liste chainée de pointeurs de tous les bouts de phrase qui commencent après le mot à remplacer, en plus depuis le début, et qui se termine par un \0 juste avant le mot à remplacer.
pour la restitution il suffit de lister la liste chainée en rajoutant à chaque fois le mot de remplacement.
En fait, je ne suis pas sûr qu'il faille utiliser une table de hachage. A mon avis, une liste chainée suffit.
L'intérêt d'une liste chainée est qu'il n'y a pas besoin d'index, d'autant que la chaine est strictement séquentielle.
On ne modifie pas la chaine à remplacer, on la supprime, et on sait qu'au résultat final, il faudra concaténer le chaine de remplacement.
La seule difficulté, à mon avis est l'espace mémoire nécessaire. Éventuellement la solution serait de commencer par la fin.
Mais à cette heure-ci :dodo:

En effet, j'ai proposé une table de hash afin que l'on ne change qu'une seule fois le mot à remplacer.

Supposons que l'on ait N fois le motif à remplacer.

Liste chainée : on va devoir modifier N fois le motif lors de la reconstruction

Table de hash : Il suffira de modifier qu'une seule fois le motif directement dans le tableau avant de defiler le contenu de la file.

Si on reprend l'énoncé de fatal_error :

dont la particularité est que si plusieurs occurrences sont trouvées dans une string, alors il suffit de remplacer une seule fois pour que chacune des occurrences soit remplacée.

D'où ma proposition, sinon une simple liste chainée (comme tu le proposes) suffit. On pourrait même le faire directement en parcourant le tableau.

[joel76]

On pourrait même le faire directement en parcourant le tableau.

Si on suppose la chaîne modifiable, pourquoi ne pas mettre un code "impossible" (-1 par exemple) pour remplacer les caractères du mot à modifier, au moment de la création du texte final, à la première rencontre de -1 on recopie le remplaçant et on ignore les -1 suivants.
L'avantage est que lorsqu'on parcourt la chaine initiale, on peut compter le nombre d'occurences du mot à remplacer et ensuite calculer facilement la taille de la nouvelle chaîne.

Pour la recherche, j'utiliserais une sorte d'automate, avec plusieurs états.
Etat 0 : je suis en train de lire un mot lambda, je reste dans cet état tant que je n'ai pas trouve de séparateur. Si je trouve un séparateur, je passe dans l'état 1.
Etat 1 : je viens de trouver un séparateur. Si le caractère courant est le début du mot à remplacer je mémorise ma position et je passe dans l'état 2, sinon je retombe dans l'état 0.
Etat 2 : si je trouve la deuxième lettre du mot, je passe dans l'état 3 sinon je retmobe à l'état 0
etc...
Etat n : si je trouve la dernière lettre du mot à remplacer, je passe à l'état -1, sinon je retombe à l'état 0.
Etat - 1 : je lis un séparateur, donc j'ai trouvé le mot à remplacer, je mets des - 1 aux bons endroits, et je retourne dans l'état 1.

La recherche débute dans l'état 1.

[ampholyte]

Si on suppose la chaîne modifiable, pourquoi ne pas mettre un code "impossible" (-1 par exemple) pour remplacer les caractères du mot à modifier, au moment de la création du texte final, à la première rencontre de -1 on recopie le remplaçant et on ignore les -1 suivants.
L'avantage est que lorsqu'on parcourt la chaine initiale, on peut compter le nombre d'occurences du mot à remplacer et ensuite calculer facilement la taille de la nouvelle chaîne.

Modifier la taille d'une nouvelle chaine n'est pas très compliquée, il est très largement possible de créer sa fonction my_strcat qui contient un petit realloc. En c++ avec un string c'est encore plus simple.

Le but ici n'est pas tant de trouver un moyen de calculer la taille de la nouvelle chaine mais plutôt de ne remplacer qu'une seule fois le motif et non de le remplacer N fois (N étant le nombre d'expression à remplacer dans une chaine). Avec ton système on remplacera chaque -1 par le motif.

(Sauf si je n'ai pas bien compris la question de fatal_error)

[joel76]

Je voulais justement éviter les realloc successifs. En C++, avec la classe string, il ne faut pas se faire d'illusions, les realloc sont invisibles mais existent.

[ampholyte]

Je voulais justement éviter les realloc successifs. En C++, avec la classe string, il ne faut pas se faire d'illusions, les realloc sont invisibles mais existent.

Tout à fait =). Par contre plus simplement tu peux boucler sur la fonction strstr tant que le retour n'est pas NULL. Cela t'évitera de devoir modifier la chaine une première fois pour insérer des -1. (surtout que si la sous-chaine est une lettre tu devras quand même faire des realloc pour mettre tes -1).

[Dlzlogic]

Bonjour,
A mon avis, il y a 3 cas à considérer.
1- le mot à remplacer et le mot de remplacement ont le même nombre de caractères, alors le remplacement peut se faire au fur et à mesure de la lecture de la chaine.
2- suivant que le mot de remplacement est plus long ou pas du mot à remplacer, on commence par la fin ou par le début.
Mais il est vrai que tout dépend des hypothèses, et l'expression "remplacer une seule fois" me laisse un peu perplexe.

[ampholyte]

Mais il est vrai que tout dépend des hypothèses, et l'expression "remplacer une seule fois" me laisse un peu perplexe.

Je suis d'accord avec toi, d'où ma solution un peu particulière :zen:

Si fatal_error pouvait préciser un peu sur le sujet =).

[joel76]

Je pense que ça s'applique au replace du C++ qui remplace toutes les occurences du mot dans une phrase en une seule instruction, les remplacements sont une fois de plus cachés mais ils existent bien.

(surtout que si la sous-chaine est une lettre tu devras quand même faire des realloc pour mettre tes -1)

Non, je mets des -1 sur le mot qui doit être remplacé, la chaine complète est relue au moment de la création du résultat.

[Valentin03]

Non, je mets des -1 sur le mot qui doit être remplacé, la chaine complète est relue au moment de la création du résultat.

Que se passe t-il dans le cas d'une chaîne alphanumérique comportant des "-1°C" ?

[joel76]

pour -1 c'est un texte de 2 caractères, le caractère - (code ASCII 45) et le caractère 1 (code ASCII 49).
Effectivement si dans le texte il y a un caractère codé -1 cela peut poser des problèmes, c'est pour cela que j'ai parlé de "code impossible".

[fatal_error]

hello,

on peut noter deux manières d'envisager le remplacement:
optimiser la mémoire
optimiser la vitesse

De prime abord, on peut envisager la trivialité

Code: Tout sélectionner

size_t index;
size_t oldIndex = 0;
std::string replacedString;
while(index=find(pattern)!=-1){
  //concatenate not matching string until index
  replacedString += substr(oldIndex,index);
  replacedString += substitue;//the string we want instead
  oldIndex = index;
}

Dans les grandes lignes.

Maintenant, qu'est-ce qu'on voit: on voit qu'on a alloué autant d'espace que de
patterns trouvés.

Du coup, remplacer une seule fois prend du sens, on cherche à ne pas réallouer une
séquence d'octets qui est la même!

Ma question s'orientant plus vers une minimisation de la mémoire allouée.
Mais poussons la réflexion un peu plus loin.

l'utilisateur écrit

Code: Tout sélectionner

my::string s("zzzztotozzzz");
my::string s2=s.replace("o","i"); //s affiche zzzztotozzzz, mais s2 affiche zzzztitizzzz
puis
my::string s3=s2;//s3 affiche zzzztitizzzz
my::string s4=s3.replace("ti","ta");//s4 affiche zzzztatazzzz


On voudrait éviter de rallouer à chaque fois les caractères pour zzzz...., bref les sous chaines non touchées! et tant qu'à faire idem pour les sous-chaines remplacées!
J'ai pas spécialement d'idées derrière en tête, mais c'était plus dans cette voie que je m'étais posé la question hier!

edit: bien sûr on pourrait mapper l'alphabet, mais bon, c'est pas dit d'y etre gagnant

[Dlzlogic]

Bonjour fatal,
Deux réactions me viennent à l'esprit,
1- si on veut optimiser la mémoire et le temps d'exécution, il faut écrire la fonction en C, c'est à dire en utilisant strstr, strcat et les pointeurs.
2- la recherche et le traitement caractère par caractère me parait à exclure.
Mais c'est mon avis.
Il ne faut pas oublier que le C++, c'est d'abord du C.
La fonction "find" est un membre de str::string ?
Pourquoi pas utiliser tout simplement strchr ? ou alors on travaille sur une liste, et non sur une chaine, c'est à dire un tableau de char, j'ai un peu de mal à comprendre.

[ampholyte]

Bonjour,

Je rejoints l'avis de Dlzlogic concernant l'utilisation du C plutôt que du C++.

Si tu cherches à optimiser la mémoire et le temps d'exécution, je te propose d'utiliser les fonctions memmove et memcpy.

1) Supposons le prototype de la fonction

Code: Tout sélectionner

char *search_and_replace(char *buffer, char *search, char *replace);

Avec buffer, la chaine principale, search la chaine à remplacer et replace la chaine remplaçante.

On stockera dans 3 size_t, la taille de chaque chaine à l'aide d'un strlen (par exemple).

2) On compte le nombre de search dans buffer à l'aide de strstr. Supposons que l'on obtient N fois la chaine search

3) On sera alors qu'il y a caractères à remplacer et donc caractères à ajouter.
On procède alors à un realloc (et l'unique realloc de la fonction search_and_replace()) si c'est nécessaire sinon on le fera à la fin (si la taille de search est plus grande que la taille de replace)

4) On revient au début de notre buffer et pour chaque strstr, suivant le cas on effectue un memmove puis un memcpy ou vice et versa.


La complexité de cette algo est donc O(strlen(buffer)) et sa place en mémoire sera le plus petit possible.

[joel76]

Remplace-t-on des mots ou des séquences ? Pour des mots, il faut d'abord les délimiter, donc après avoir trouver un mot, on repart au début du mot pour savoir si c'est le mot recherché, celà fait une lecture de chaînes supplémentaire par rapport à mon automate.
En gros, si ce sont des mots, on a 3 parcours de chaine pour le remplacement, avec mon automate, 2 seulement, ce n'est pas forcément énorme en temps d'exécution mais quand même.

[ampholyte]

On ne parle pas de mots mais de séquences je pense pour que la fonction soit le plus général possible.

Par ailleurs, je ne vois pas pourquoi tu aurais besoin de délimiter tes mots. En plaçant un pointeur sur le premier caractère de ton mot et connaissant la taille tu es parfaitement capable de trouver la fin de ce mot.

[fatal_error]

Hello,

Donc deja, je vais etre un peu sec mais:
preferer le C par rapport au C++ n est absolument pas justifie ici.
Qu il s agisse de gestion memoire ou de gestion de rapidite.

Si vous faites allusion aux char*, rien n empeche de gerer des char* en C++, encore faudrait-il justifier l overhead d un sizeof et le comportement de string.

Maintenant comme vous semblez a tout prix vouloir faire du C, pourquoi pas, mais evitons ces arguments ou alors comparons apres que des solutions comparables aient ete proposees.

Enfin vous ne semblez pas vous preoccupez de l assignation d une telle structure, et de la modification de la premiere chaine...

Code: Tout sélectionner

mystring s("blabla");
mystring s2=s.replace("a","b");
//s2 reutilise la chaine utilisee par s.
s.inplaceReplace("aeff","feeee");
//s2 n est pas impacte par la modification de s


J ai pas dit que c est necessare, mais c est une question a se poser, ce genre de cas (ou la premiere chaine est modifiee) peut il arriver, si oui comment le gerer pour ne pas impacter les chaines qui se basent sur la premiere...