RegExRésolu

Question

Bonjour,


Après maintes recherches tuto et autres je n'ai pas trouvé ce que je souhaite, du fait je vous demande de l'aide :


J'aimerais connaitre la syntaxe du pattern d'une RegEx qui m'indiquerait par exemple si le mot REQUIN ou QUESTIONNERAS peut être formé avec les lettres suivantes ANORENHQUTDEIVS.


J'ai essayé :
oRegExp.Pattern = "[R?E?Q?U'I?N?]"    (et autres essais)
Set oTrouve = oRegExp.Execute("ANOREHQNUTDEIVS")
Print oTrouve.Count
J'obtiens 8 et il faudrait que j'ai 6 


avec Print oRegExp.Test("ANOREHQNUTDEIVS") j'ai Vrai mais également avec [R?E?Z?U'I?N?], ce qui ne convient pas.


Vous l'avez deviné il s'agit de trouver tous les mots pouvant être formés à partir d'un nombre donné de lettres aléatoires.
Je dispose d'un dico (378912 mots de 3 à 15 lettres) et compare chaque lettre du mot avec les lettres tirées au hazard. Pour accélérer je vérifie si la 1ère lettre aléatoire est présente dans le mot du dico, si oui on teste ce mot.


Pour un ensemble de 15 lettres (ANOREHQNUTDEIVS) j'obtiens 5804 anagrammes en ± 11 sec sous l'IDE et ± 6 sec en compilé. Mais avec une RegEx cela irait peut-etre plus vite ?.


Merci d'avance pour votre attention.


Amicalemnt de Cheyenne.

PCPT · Accepted Answer

re,

Est-ce à dire, qu'avec cette requête,  si j'importe le mot 'ASTHENIQUE'  trié en 'AEEHINQSTU' il sera trouvé par rapport à  ADEEHINNOQRSTUV ? 

pas exactement...
ce que je dis c'est que, requête ou tableau peu importe, au final on va travailler avec un tableau.
tu as donc "une liste" de tous tes mots de 7 lettres par exemple.

ma proposition est "au lieu de boucler sur tes 50000 items" et faire des like sur ton "mot aléatoire", si ta liste est triée et ton mot aussi, tu peux déjà récupérer une plus petite liste, commençant par la première lettre du mot à trouver, par exemple.

par contre effectivement le problème qui va se poser sera de chercher dans
les 7 et les 3 et les 15. tu seras obligé de boucler jusqu'à
13 fois sur ta première dimension mais en plus de réorganiser ta chaine avec toutes les combinaisons possible ^^

ouai si le regex le fait c'est dommage de passer à côté 

en même temps çà m'étonnerait qu'il n'y ait pas déjà ce genre de sources..., as-tu jeté un oeil?

Le problème avec mon tableau c'est qu'il est
dimensionné sur le plus grand nombre de mots soit 59526 pour les 10
lettres, alors qu'il n'y a que 2441 mots de 4 lettres et seulement 589
mots de 3 lettres. Il y a peut-être là une astuce ?
en effet çà le fait pas du tout çà ^^
passe par un TYPE

Option Explicit

Private Type tWords
    Valeurs() As String
End Type
Dim MyWords(3 To 15) As tWords

Private Sub Form_Load()
'   init 
tableau(x)
    ReDim MyWords(3).Valeurs(1 To 589)
    ReDim MyWords(4).Valeurs(1 To 2441)
    '.....
    ReDim MyWords(15).Valeurs(1 To 59256)
End Sub

Private Sub Form_QueryUnload(Cancel As Integer, UnloadMode As Integer)
'   destruction
    Dim i%
    For i = UBound(MyWords) To LBound(MyWords) Step -1
        Erase MyWords(i).Valeurs
    Next i
    Erase MyWords
End Sub

déjà çà, çà devrait te faire gagner de précieuses secondes ;)
j'y pense, regarde aussi dans les sources aux niveau des regex, ou même sur http://logiciel.codes-sources.com, possible qu'il y ait des outils pour construire ta chaîne de recherche ;)

bon courage 

ps : merci du merci 
<hr size="2" width="100%" />Prenez un instant pour répondre à [infomsg_SONDAGE-POP3-POUR-CS_769706.aspx ce sondage] svp

PCPT · Answer

salut,

désolé niveau regex..., pas trop mon truc ^^

par contre j'ai bien une idée :)

ne teste pas ANOREHQNUTDEIVS sur toute ta base (ou sur un tableau de tout le contenu), teste ADEEHINNOQRSTUV sur un retour en tableau d'une requête LIKE 'A*' ORDER BY ASC

si tes mots sont triés et que tu compares ton "mot aléatoire" lui aussi trié, tu auras beaucoup moins de comparaisons à faire

voici comment trier un mot (attention : 2 liens indispensables)
Function SortString(ByVal sString As String) As String
    If LenB(sString) Then
        Dim saTmp() As String, i As Long, j As Long, sBuffer As String
        saTmp = StringToCharArray(sString, True) 'http://www.codyx.org/snippet_convertir-chaine-tableau-chaine-tenant-compte-retours-chariot_634.aspx#1896
        Call Tri(saTmp, True) 'http://www.codyx.org/snippet_trier-donnees-tableau-liste-as-string_278.aspx#892
        SortString = Join(saTmp, vbNullString)
        Erase saTmp
    End If
End Function

j'espère que çà pourra t'aider
++ 
<hr size="2" width="100%" />Prenez un instant pour répondre à [infomsg_SONDAGE-POP3-POUR-CS_769706.aspx ce sondage] svp

cs_cheyenne · Answer

Bonjour PCPT,

Merci pour ta réponse, mais...

Je n'ai pas de BdD, les mots sont dans 15 fichiers texte (de 3 à 15 lettres).
Les mots sont tous par ligne de 50 en ordre alphabétique. 
Au départ j'ai un tableau de vide DICO(3 to 15,59256) et j'y case les mots par Split de la ligne lue sur l'espace qui sépare les mots. Le dico est donc en mémoire, cela prend moins de 3 secondes à charger et la recherche est ainsi plus rapide à chaque fois.
Si je demande 9 lettres au hazard je scrute leDICO(9,1...). 
nLettres est issu d'un tableau nbre(15) qui représente le nombre de mots par longeurs (3...15) 
For i=1 to nLettres
   mot= DICO(,9,i)
   ....traitement
next
Si je demande tout, je scrute de x lettres à 3.

C'est pour cela qu'une Regexp m'aurait bien aidé, quoique ma façon de procéder est assez rapide. Voici le code :

txt = txtLETTRES.Text   
'  les lettres aléatoires
Lettres = Len(txt)

  '  mémo des lettres du TextBox
For i = 1 To nLettres   lettre(0, i) Mid$(txt, i, 1): lettre(1, i) lettre(0, j)
Next
      
For nL = nLettres To 3 Step -1   info False: lblINFO "Recherche les mots de " & nL & " lettres"
   For i = 1 To nMOTS(nL) '   589 à 59526 selont le nombre de lettres      mot DICO(nL, i):  n 0
          
      '  si la 1ère lettre du TextBox existe dans le mot
      If InStr(txt, Left$(mot, 1)) Then
      
      '  reset des lettres mémorisée du TextBox             For j 1 To nLettres: lettre(1, j) lettre(0, j):Next 
      For j = 1 To nL            
'  1...15 lettres
         letr = Mid$(mot, j, 1)  '  compare chaque lettre du mot
         For k = 1 To nLettres   '  avec chaque lettre du TextBox            If letr Like lettre(1, k) Then n n + 1: lettre(1, k) "-                ": Exit For  
' lettre trouvée, on la remplace et
                                 on sort de la boucle
           Next k
        Next j




        If n >= nL Then     


'  si n = nombre de lettres du TextBox
        


' si pas déja indiqué on ajoute un commentaire dans la liste        If info False Then info True: lstMOTS.AddItem "   " & nL & " lettres"
        nbre(nL) = nbre(nL) + 1 '


 compteur des mots trouvés de x lettres
        lstMOTS.AddItem mot  ' on met le mot trové dans la liste
      End If
    End If
  Next i
  If nbre(nL) > 0 Then grdNOMBRE.TextMatrix(nL - 2, 1) = nbre(nL) & " Next nL


       
Bonne soirée,@+

Cheyenne

PCPT · Answer

beh pour le moment je laisse la main, au cas où un regexeur saurait t'apporter satisfaction ^^

sinon relance-moi et je verrai comment optimiser un peu...
dans quel cas si tu peux héberger quelques fichiers, les 3 5 et 14 par exemple

++
<hr size="2" width="100%" />Prenez un instant pour répondre à [infomsg_SONDAGE-POP3-POUR-CS_769706.aspx ce sondage] svp

cs_cheyenne · Answer

Re,

Tu me dis :
ne teste pas ANOREHQNUTDEIVS sur toute ta base (ou sur un tableau de tout le contenu), teste ADEEHINNOQRSTUV sur un retour en tableau d'une requête LIKE 'A*' ORDER BY ASC
si tes mots sont triés et que tu compares ton "mot aléatoire" lui aussi trié, tu auras beaucoup moins de comparaisons à faire

Est-ce à dire, qu'avec cette requête,  si j'importe le mot 'ASTHENIQUE'  trié en 'AEEHINQSTU' il sera trouvé par rapport à  ADEEHINNOQRSTUV ? 

Oui, mais j'ai mis le tableau en mémoire pour éviter les accès disque, donc pas de requête de ce type  ! à moins qu'une RegExp correspondante existe (HI HI HI )... Like ne le fait pas, il me semble.

Le problème avec mon tableau c'est qu'il est dimensionné sur le plus grand nombre de mots soit 59526 pour les 10 lettres, alors qu'il n'y a que 2441 mots de 4 lettres et seulement 589 mots de 3 lettres. Il y a peut-être là une astuce ?

Le but de la manip est de faire une vérification pour le Scrabble®  ou pour les 'Chifftres et lettres' et accessoirement de faire des recherches d'anagrammes.

Bonne soirée, @+

PS. J'avais demandé, il y a quelque temps, de l'aide sur les User Controls, je suis arrivé à mes fins grâce à tes conseils avisés. MERCI.

PCPT · Answer

et voilà qui tombe peut-être à pic :
http://www.vbfrance.com/tutoriaux/EXPRESSIONS-RATIONNELLES-REGULIERES_520.aspx

Renfield · Answer

en fait, c'est le contraire.

ton pattern doit être :

^[ANORENHUTQDEIVS]+$

et tu testes pour chaque mot... ou une liste de mots, si tu veux (activer Global, Multiline et IgnoreCase)

en gros, on cherche un mot de 1 à n lettres
qui n'est composé que de ces lettres là...

mis au point grace a mon outil de RegExp :   
http://www.vbfrance.com/codes/REGEXP-WORKSHOP_17331.aspx

Renfield
Admin CodeS-SourceS- MVP Visual Basic

Renfield · Answer

Private Sub
Form_Load()
   MsgBox AreWordsCoumpoundOf("ANORENHQUTDEIVS", "Requin", "belligérant", "Questionneras")
End Sub<hr />
Private Function AreWordsCoumpoundOf(ByRef vsLetters As String, ParamArray vxzWords() As Variant) As String
Dim oRegExp As RegExp
Dim i As Long
Dim nCount As Long
   Set oRegExp = New RegExp
   oRegExp.Global = True
   oRegExp.IgnoreCase = True
   oRegExp.Pattern = "^[" & vsLetters & "]+$"
   
   nCount = UBound(vxzWords) + 1
   If nCount Then
       AreWordsCoumpoundOf = Space$(nCount)
       For i = 0 To nCount - 1
           Mid$(AreWordsCoumpoundOf, i + 1, 1) = Abs(oRegExp.Test(vxzWords(i)))
       Next i
   End If
End Function ,

----

By Renfield





renverras  101

Renfield
Admin CodeS-SourceS- MVP Visual Basic

Renfield · Answer

posté là:

http://www.codyx.org/snippet_tester-si-ou-plusieurs-mot-peut-etre-compose_636.aspx

cs_cheyenne · Answer

Bonjour,


> PCPT
Ben oui, effectivement, que n'y ai-je pas pensé plus tôt... 
Passer par un type ! je teste et te dis si je gagne du temps par rapport à
mon tableau à 2 dimensions.
Non,  je ne réorganise pas ma chaine. Dèjà si la première lettre de celle-ci n'existe pas dans le mot je passe au mot suivant, gain de temps.
Si la première lettre est présente dans le mot alors je teste chacune de ses lettres avec  avec celles de la chaine en remplacant chaque lettre trouvée par un "-" de façon à ce quelle ne soit pas recomptée. Si le nombre de lettres trouvées est égal à la longueur du mot, c'est OK, j'inscris le mot dans la liste.
J'avais auparavant consulté l'excellent tutorial de CACOPHRENE que tu m'indiques. Mais n'en avais, sans doute pas, tiré toutes les leçons !


> Renfield
J'avais essayé avec ton REGEXP-WORKSHOP, très pratique, mais n'étant pas parvenu à mes fins j'ai finalement demandé de l'aide.
Merci, pour la définition du Pattern et du snippet.


Je vois tout cela ultérieurement et je vous tiens au courant en validant ou non vos réponses.




Merci pour votre aide
 et bonne journée.


Bien cordialement de Cheyenne

cs_cheyenne · Answer

>


Renfield

 C'est OK, 


MERCI
Je colle ce code de test, si cela peut aider quelqu'un...




Extraction de mots valides à partir d'un chaîne de lettres aléatoires




Ne pas oublier de mettre la référence Microsoft VBScript Regular Expression 5.5




Private Sub Form_Activate()
   Dim i        As Integer
   Dim mot(8)   As String
   Dim oRegExp  As RegExp
   Dim oMatch   As Match
   Dim oMatches As MatchCollection
      With Me: .FontName "Courier New": .FontSize 10: End With
   
   mot(1) = "ESTIVAL"
   mot(2) = "REVENDIQUER"
   mot(3) = "PCPT"
   mot(4) = "ANODISER"
   mot(5) = "RENFIELD"
   mot(6) = "HURON"
   mot(7) = "ANESTHESIE"
   mot(8) = "PROGRAMMEUR"
   
   Set oRegExp = New RegExp
   oRegExp.Pattern = "^[ANORENHUTQDEIVS]+$"
 
   Print: Print "ANORENHUTQDEIVS": Print
  
   For i = 1 To 8
      Print mot(i);
      Set oMatches = oRegExp.Execute(mot(i))
      If oMatches.Count = 1 Then
         Set oMatch = oMatches(0)
         If oMatch.Length = Len(mot(i)) Then Print Tab(15); "OUI"
         Set oMatch = Nothing
      Else
         Print Tab(15); "NON"
      End If
   Next

   Set oRegExp = Nothing
   Set oMatches = Nothing
End Sub

Renfield · Answer

tu peux te contenter de :

   For i = 1 To 8
      Print mot(i);
      If oRegExp.Test(mot(i)) Then
            Print Tab(15); "OUI"
      Else
            Print Tab(15); "NON"
      End If
   Next i

du fait que je demande commence par et finit par, dans le pattern (^ et $)

cs_cheyenne · Answer

> Renfield

Oui effectivement, c'est plus concis.
Je débute avec les RegExp et je n'avais pas pensé à utiliser oRegExp.Test
Merci pour l'optimisation.

> PCPT
J'ai mis en application ce que tu me préconises, l'utilisation d'un Type.
Ce n'est pas significatif au niveau de l'exécution, mais par contre, je divise par 12 l'occupation mémoire du tableau et la feuille se décharge beaucoup  plus rapidement.

Je valide donc vos réponses qui m'ont bien aidé. Merci encore à vous deux.

Bonne semaine,

Cheyenne

cs_cheyenne · Answer

Au secours Renfield,

Si je teste ADONNNNNNN " ou EEEE  avec le pattern  "^[ANORENHUTQDEIVS]+$" la réponse est OUI. Alors que les lettres ne sont pas toutes contenues dans le pattern.

Je pense que cela provient du fait que la présence d'une seule de ces lettres soit effective, non ?
Par contre si une des lettres n'est pas présente dans le pattern c'est NON, ce qui est bien.

Il y a-t-il une autre solution ?

Pour PCPT :
Tu détruis le tableau à partir de l'indice le plus haut vers le plus bas, y a t'il une raison particulière ?

@+ Cheyenne

PCPT · Answer

on remplie généralement un tableau de 0 vers X
idem pour une collection
on connecte un DB, puis un RS (vers DB). donc logiquement on ferme le RS avant le DB

pour ces raisons j'ai toujours pris l'habitude de détruire dans ce sens qui me paraît logique, donc l'opposé de l'ordre de création, mais aucune raison littérale non...

cs_cheyenne · Answer

Ok c'est une sorte de LIFO, Hi.

Ben dis-donc, à part Renfield, ça ne se bouscule pas pour les RegExp...

Allez, bonne soirée à toi et encore merci.

PCPT · Answer

LIFO exactement oui, cependant comme je l'ai dit, je fais de cette manière juste parce que mon esprit tordu le voit "logique"...
la logique de l'un n'est pas forcément celle de l'autre ^^

certains diront même que VB gère très bien tout seul son garbage collector et qu'il est inutile de détruire en "partant".
je me suis déjà aperçu que non donc par ce principe...

çà ne se bouscule pas non, remarque c'est normal car très peu utilisé. moi en dernier, preuve en est j'ai répondu pour te proposer "si pas de réponse, on peut voir autrement" ^^

vaste sujet, pas forcément difficile mais il faut en avoir l'utilité "un moment donné" pour s'y plonger.

je te souhaite la participation de différents plongeurs ^^

Renfield · Answer

et voilà.... j'ignore si on peut optimiser davantage, mais ca devrais donner un bon coup de fouet à ton code ^^



Option Explicit

Private Type SafeArray1
    cDims As Integer
    fFeatures As Integer
    cbElements As Long
    cLocks As Long
    pvData As Long
    cElements As Long
    lLbound As Long
End Type

Private Const FADF_AUTO = &H1
Private Const FADF_STATIC = &H2
Private Const FADF_FIXEDSIZE = &H10

Private Declare Function ArrPtr Lib "msvbvm60.dll" Alias "VarPtr" (Ptr() As Any) As Long
Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal Length As Long)

Private Function IsWordCoumpoundOf(ByRef vsWord As String, ByRef vsLetters As String, Optional ByVal vbCanReuseLetters As Boolean = False) As Boolean
Dim xbCount(128) As Integer
Dim xbBuffer() As Byte
Dim tArray As SafeArray1
Dim i As Long
'# Version naïve.... bien trop lente
'    For i = 1 To Len(vsWord)
'        xbCount(Asc(Mid$(vsWord, i, 1))) = xbCount(Asc(Mid$(vsWord, i, 1))) - 1
'    Next i
'    For i = 1 To Len(vsLetters)
'        xbCount(Asc(Mid$(vsLetters, i, 1))) = xbCount(Asc(Mid$(vsLetters, i, 1))) + 1
'    Next i

'# Version intermédiaire... on commence à avoir de bonnes performances
'    xbBuffer = StrConv(vsWord, vbFromUnicode)
'    For i = 0 To UBound(xbBuffer)
'        xbCount(xbBuffer(i)) = xbCount(xbBuffer(i)) - 1
'    Next i
'    xbBuffer = StrConv(vsLetters, vbFromUnicode)
'    For i = 0 To UBound(xbBuffer)
'        xbCount(xbBuffer(i)) = xbCount(xbBuffer(i)) + 1
'    Next i

'# Version finale, optimisée (inclue en plus l'option 'vbCanReuseLetters')
    With tArray
        .cDims = 1
        .cbElements = 1
        .fFeatures = FADF_AUTO Or FADF_STATIC Or FADF_FIXEDSIZE
        
        .cElements = LenB(vsWord)
        .pvData = StrPtr(vsWord)
        CopyMemory ByVal ArrPtr(xbBuffer), VarPtr(tArray), 4
        For i = 0 To UBound(xbBuffer) Step 2
            If vbCanReuseLetters Then
                xbCount(xbBuffer(i)) = -1
            Else
                xbCount(xbBuffer(i)) = xbCount(xbBuffer(i)) - 1
            End If
        Next i
        CopyMemory ByVal ArrPtr(xbBuffer), 0&, 4
        
        .cElements = LenB(vsLetters)
        .pvData = StrPtr(vsLetters)
        CopyMemory ByVal ArrPtr(xbBuffer), VarPtr(tArray), 4
        For i = 0 To UBound(xbBuffer) Step 2
            If vbCanReuseLetters Then
                xbCount(xbBuffer(i)) = 0
            Else
                xbCount(xbBuffer(i)) = xbCount(xbBuffer(i)) + 1
            End If
        Next i
        CopyMemory ByVal ArrPtr(xbBuffer), 0&, 4
    End With
    
    IsWordCoumpoundOf = True
    For i = 0 To UBound(xbCount)
        If xbCount(i) < 0 Then
            IsWordCoumpoundOf = False
            Exit For
        End If
    Next i
End Function

Renfield · Answer

je ne pense pas qu'un Pattern (dynamique) puisse le faire... et surement pas aussi rapidement (les RegExp, c'est lent)

en mettant les mains dans ton code, on pourrais surement l'accelerer un peu, mais ce point précis n'est plus le goulot d'etranglement qu'il fut...

observe le code des versions intermediaires, laissées en commentaire (en fait, j'ai codé la version avec Asc après coup, histoire de comparer ^^)

le but général de l'algo est un tri que l'on appel tri compteur. il va bien quand on a un nombre donné d'elements (ici 128). Chaque case correspond au caractère dont le code ascci est l'indice de la case. (exemple, "A" sera la case 65 ...
on soustrait (on aurait pu ajouter) 1 dans chaque case correspondant a une lettre...
on fait un passage, ensuite, avec les lettres disponibles, mais en ajoutant 1, cette fois, a ces compteurs.

au final, il suffit de scruter le tableau des compteurs de lettres : si une seule case est restée inférieure à 0, notre jeu de lettre ne nous permet pas de composer notre mot.

- le code de base exploite naïvement les instructions VB... Mid$ et Asc
- le code intermédiaire fait la meme chose, en recopiant les chaines dans des tableaux d'octets. Après coup, manipuler le tableau est plus rapide que de jouer avec des Mid$ (qui alloue dynamiquement des chaines, pour bosser)
- l'idée de la version finale est de ne pas réallouer un seul octet pour questionner les lettres dans un tableau de Byte...  on fait juste pointer un tableau de bytes sur chaque chaine de caractères... ainsi, on manipule les mêmes données, et on gagne quelques cycles... pas de recopie.

Renfield · Answer

je relis mon commentaire, je le trouve pas très clair... 

je vais donc rééxpliquer l'algo par l'exemple :

mot testé :  "REGEX"
lettres : "EGPRX"

pour simplifier, on aura que 26 cases dans le compteur

R=> 18ème lettre de l'alphabet  => Compteur[18] = -1
E=> 5ème lettre de l'alphabet  => Compteur[5] = -1
G=> 7ème lettre de l'alphabet  => Compteur[7] = -1
E=> 5ème lettre de l'alphabet  => Compteur[5] = -2
X=> 24ème lettre de l'alphabet  => Compteur[24] = -1

second passage, avec les lettres dispos :

E=> 5ème lettre de l'alphabet  => Compteur[5] = -1  (on ajoute 1)
G=> 7ème lettre de l'alphabet  => Compteur[7] = 0
P=> 16ème lettre de l'alphabet  => Compteur[16] = 1
R=> 18ème lettre de l'alphabet  => Compteur[18] = 0
X=> 24ème lettre de l'alphabet  => Compteur[24] = 0

enfin, on parcours notre tableau compteur....

on trouve Compteur[5] < 0 donc, le mot REGEX ne peux pas être composé à l'aide des lettres E, G, P, R et X

voilà ^^
dsl si tu avais tout bien vu dès le départ, mais bon...

RegEx

25 réponses

Votre réponse

Discussions similaires