Page 1 sur 1
[R] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 11:44
par PandiPanda
Bonjour,
Je poste ici pour vous demandé une
petite Grande aide sur la création d'une fonction et non d'un script
Que fera la fonction?
Je voudrai que la fonction recherche dans un String des groupes de lettre qui revienne le maximum de fois et la remplace par un caractere qu'on a prélablement entré en paramètre ^.^
Paramètre de la fonction ?
Func _Afaire($String,$MaxCarac,$OccurMin,$CaracReplace)
@Param:
- > $String: le String à modifié
> $MaxCarac: le nombre de caractere maximal (pour la recherche des groupes de lettre)
> $OccurMin: le nombre minimal d'occurance voulue, pour faire le remplacement
> $CaracReplace: le caractere de remplacement
@Return:
- > $array[0]="String modifié"
> $array[1]="le caractere de remplacement"
> $array[2]="le groupes de mot qui on subit un remplacement"
Exemple de la fonction:
► Afficher le texteExemple1
$String=Pandi-Pandi-Pandi-Panda-Panda-Pandi-Panda-Pandi-Panda
Si ma fonction est comme ceci => _Afaire($String,3,5,".") => elle renverrai un array comme ceci =>
$array[0]=.di-.di-.da-.da-.di-.da-.di-.da
$array[1]="."
$array[2]="Pan"
Si ma fonction est comme ceci => _Afaire($String,5,3,".") => elle renverrai un array comme ceci =>
$array[0]=.-.-.-Panda-Panda-.-Panda-.-Panda
$array[1]="."
$array[2]="Pandi"
► Afficher le texteExemple2
$String=0x66667E47A89B474547E8586666A74846666A87E848C5695D4156A6666
Si ma fonction est comme ceci => _Afaire($String,4,3,".") => elle renverrai un array comme ceci =>
$array[0]=0x.7E47A89B474547E858.A7484.A87E848C5695D4156A.
$array[1]="."
$array[2]="6666"
Si ma fonction est comme ceci => _Afaire($String,4,54845,".") elle renverrai un array comme ceci =>
$array[0]=0x66667E47A89B474547E8586666A74846666A87E848C5695D4156A6666
$array[1]="."
$array[2]=""
Merci pour l'aide a venir, je ne demande pas forcemment une fonction toute faite, même du francais ca m'irai très bien ...
Simplement savoir par ou commencer? la recherche de groupe de lettre récurante le maximum de fois? et comment?
C'est plus un problème d'algorithme que de language en lui même ...
Re: [..] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 16:08
par ZDS
Bonjour,
Je pense pouvoir t'aider là dessus.
Tout d'abord séparer les taches dans l'algo :
- $MaxCaracActuel initialisé à $MaxCarac
- (POINT1)
- Si $MaxCaracActuel = 0, on laisse tomber, on retourne le résultat basique (genre la seconde partie de ton exemple 2) <= C'est la condition d'arrêt de la partie récursive
- Chercher les groupes de lettres de taille $MaxCaracActuel revenant au moins $OccurMin fois.
- Si on a trouvé au moins un résultat, choisir le bloc ayant le plus d'occurrences (je pense, non?)
- Si on a trouvé aucun résultat, reprendre au (POINT1) en choisissant $MaxCaracActuel = $MaxCaracActuel - 1
- Remplacer avec une regexp tous les blocs par le symbole demandé StringRegExpReplace ( $String, $bloc, $CaracReplace) <= Le problème se pose si le bloc trouvé contient des caractères pouvant être considérés comme spéciaux par une regexp. Il faudra peut être faire une fonction à la mano pour ça.
Je te laisse regarder ça, je m'y mettrai un peu plus assidument plus tard, là je suis au boulot.
A bientôt!
EDIT @Jchd: Je ne pense pas non, car je pars de $MaxCaracActuel initialisé à $MaxCarac et y va en décrémentant la longueur, et quand je dis "groupes de lettres de taille $MaxCaracActuel", il s'agit d'une taille exacte. Sinon, tu as raison pour la complexité, O(n3) au minimum, surtout si on teste longueur 5, puis 4, puis 3, etc... (normalement pas plus, mais c'est déjà énorme).
RE-EDIT : En lisant ta modif, Pandi-Panda, je vois que ça risque d'être plus compliqué que l'algo proposé. On en reparle ce soir si tu veux.
Re: [..] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 16:14
par jchd
Ta spec me semble boîteuse telle qu'elle est.
Dans ton premier exemple, le max length est de 3, ce qui signifie en clair des sous-chaînes de longuer 1, 2 ou 3.
Dans ce sens, la fonction trouverait 'a' comme groupe le plus fréquent.
Soit tu nous caches quelque chose, soit ta spec demande plus de précisions.
BTW, n'espère pas un algo foudroyant, ça va être du O(N³) qui va prendre son temps.
Re: [..] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 16:25
par PandiPanda
Hmmm je me suis peut être mal exprimé ...
En fait, oui elle sous entend bel et bien pour l'exemple n°1 une longueur de 1,2,3
cependant je voudrai reduire au maximum le nombre de caractere, donc même si le "a" revien le plus souvent, dans l'exemple ci;
> 9 fois => donc un gain de 9 lettre -9 (pour les point) = 0 lettres !
> le "Pan" revien certe seulement 5 fois, mais elle permet un gain de 3*5 lettre = 15 lettre -5 (pour les points) = 10 lettres !
> le "an" revien 9 fois, un gain de ((9*2) -9) = 9 lettres !
donc on voit que le "pan" est le meilleur choix
je sais pas trop si je suis clair?
Je sais très bien que ce script risquerai de prendre largement son temps, pour cette raison que j'appel à des experts comme vous pour diminuez au maximum ce temps ^.^
Re: [..] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 16:58
par ZDS
Cadeau pondu en 10 minutes, pas sûr qu'il ne plante pas sur des trucs tarabiscotés, mais ça devrait déjà pas mal te dépanner.
► Afficher le texte_aFaire0($str, $strLength, $minOccurence)
Code : Tout sélectionner
Func _aFaire0($str, $strLength, $minOccurence)
Local $pattern = ""
; On fabrique un bloc à capturer, de longueur $strLength
$pattern &= "(.{"&$strLength&"})"
; A partir du second bloc
For $i = 2 To $minOccurence
; On vérifie si le bloc capturé (reférence arrière : "\1") revient après une suite indéfinie de caractères ".*"
$pattern &= ".*" & "\1"
Next
Local $resultat = StringRegExp($str,$pattern,1)
If @error Then Return ""
Return $resultat[0]
EndFunc
Local $str = "Pandi-Pandi-Pandi-Panda-Panda-Pandi-Panda-Pandi-Panda"
Local $strLength=3, $minOccurence=5
ConsoleWrite("RESULTAT [size:"&$strLength&", occ:"&$minOccurence&"] : '"&_aFaire0($str, $strLength, $minOccurence)&"'"&@CRLF)
Local $strLength=4, $minOccurence=5
ConsoleWrite("RESULTAT [size:"&$strLength&", occ:"&$minOccurence&"] : '"&_aFaire0($str, $strLength, $minOccurence)&"'"&@CRLF)
Local $strLength=5, $minOccurence=5
ConsoleWrite("RESULTAT [size:"&$strLength&", occ:"&$minOccurence&"] : '"&_aFaire0($str, $strLength, $minOccurence)&"'"&@CRLF)
Local $strLength=6, $minOccurence=5
ConsoleWrite("RESULTAT [size:"&$strLength&", occ:"&$minOccurence&"] : '"&_aFaire0($str, $strLength, $minOccurence)&"'"&@CRLF)
Local $strLength=7, $minOccurence=5
ConsoleWrite("RESULTAT [size:"&$strLength&", occ:"&$minOccurence&"] : '"&_aFaire0($str, $strLength, $minOccurence)&"'"&@CRLF)
A plus tard !
EDIT @jchd: C'est clair que si c'est pour réinventer la compression d'info c'est pas super utile, mais bon puisque ça n'a pas l'air d'un truc illégal comme un bot ou une bombe nucléaire à domicile, il demande, je propose ^^
RE-EDIT: Ah, mea culpa, désolé de pas avoir saisi le propos directement
Re: [..] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 17:39
par jchd
En résumé, ça revient donc à une compression ton machin, limitée à l'entité apportant le plus de gain.
Il faudrait adapter soit un Huffman soit un ZLW en en limitant la globalité.
EDIT @ zds
Quand je parlais de la spec, c'est celle du OP, fallait pas le prendre mal. J'ai dû m'absenter pendant que je composais le message, du coup le tien s'est intercallé.
Je ne dis pas que c'est "gris". Je pense que ZLW adapté devrait marcher de façon satisfaisante. Voir
cette page
Re: [..] Fonction de remplacement, Algorithme tordu?
Posté : mer. 31 août 2011 18:56
par PandiPanda
Oui Merci bien à vous 2 ^.^
Je vais bel et bien utilisé l'algorithme de ZLW qui à l'air de me convenir et je garde le script de ZDS sous le coude
Merciiiiiiii je met en résolu !