[R] Arbres et feuilles

[PandiPanda]

Sinon ceci?
avec cette udf

► Afficher le texte

Code : Tout sélectionner

#cs ----------------------------------------------------------------------------

 AutoIt Version : 3.3.12.0
 Auteur:         Pandi_Panda

 Fonction du Script :
    Modèle de Script AutoIt.

#ce ----------------------------------------------------------------------------
#include "AutoitObject.au3"

_AutoItObject_StartUp()

; creation d'un arbre
Local $arbre  = _new_Arbre(1)
ConsoleWrite($arbre.getRacine.getVal&@CRLF)

; ajout de 2 feuille a la racine
$arbre.getRacine.add(2)
$arbre.getRacine.add(3)
; parcours des feuilles crée
Local $arr = $arbre.getRacine.getFeuille
For $i = 0 To UBound($arr)-1
    ConsoleWrite(@TAB&$arr[$i].getVal&@CRLF)
    If $i == UBound($arr)-1 Then $arr[$i].add(4)
Next
; pour la feuille n°2 dans mon cas, je crée une autre feuille dont la valeur est 4
$arr = $arr[UBound($arr)-1].getFeuille
For $i = 0 To UBound($arr)-1
    ConsoleWrite(@TAB&@TAB&$arr[$i].getVal&@CRLF)
Next
_AutoItObject_ShutDown()

Func _new_Arbre($valRacine = "")
    Local $oClassObj = _AutoItObject_Class()
    Local $racine = _new_feuille($valRacine)
    $oClassObj.AddProperty("racine", $ELSCOPE_PRIVATE, $racine)
    $oClassObj.AddMethod("getRacine", "public_arbre_get_racine")
    Return $oClassObj.Object
EndFunc

Func _new_feuille($valFeuille)
    Local $oClassObj = _AutoItObject_Class()
    $oClassObj.AddProperty("val", $ELSCOPE_PRIVATE, $valFeuille)
    $oClassObj.AddProperty("feuille", $ELSCOPE_PRIVATE,"")
    $oClassObj.AddMethod("getVal", "public_feuille_get_val")
    $oClassObj.AddMethod("setVal", "public_feuille_set_val")
    $oClassObj.AddMethod("getFeuille", "public_feuille_get_feuille")
    $oClassObj.AddMethod("add", "public_feuille_add_feuille")
    Return $oClassObj.Object
EndFunc

; arbre
Func public_arbre_get_racine($self)
    Return $self.racine
EndFunc

; feuille
Func public_feuille_get_val($self)
    Return $self.val
EndFunc

Func public_feuille_set_val($self,$val)
    _AutoItObject_AddProperty($self,"val",$ELSCOPE_PRIVATE, $val)
    Return ""
EndFunc

Func public_feuille_get_feuille($self)
    Return $self.feuille
EndFunc

Func public_feuille_add_feuille($self,$val)
    Local $tmp = $self.feuille
    Local $res
    If Not IsArray($tmp) Then
        Local $t[1] = [_new_feuille($val)]
        $res = $t
    Else
        ReDim $tmp[UBound($tmp)+1]
        $tmp[UBound($tmp)-1] = _new_feuille($val)
        $res = $tmp
    EndIf
    _AutoItObject_AddProperty($self,"feuille",$ELSCOPE_PRIVATE,$res)
    return ""
EndFunc

resultat:

► Afficher le texte

Code : Tout sélectionner

1
    2
    3
        4

[sozary]

Ah....... Je vais tester les deux méthodes pour savoir laquelle me parrait la plus facile à utiliser!!
Merci pour tout!

[mikell]

Donc un codage de Huffman serait inenvisageable avec Autoit?

J'ai pas dit ça
Je voulais juste dire qu'une solution Autoit risque fort d'être lourdasse

En se basant strictement sur l'exemple proposé dans la page du site dont tu as tiré la belle image du post n°1
http://walid.nabhan.pagesperso-orange.f ... fman5.html
le script ci-dessous à base d'array 2D est une possibilité

► Afficher le texte

Code : Tout sélectionner

; http://walid.nabhan.pagesperso-orange.fr/developpement/pages/hffalgo/huffman5.html

#Include <Array.au3>

;$string = "Salut à toi, jeune padawan !"
;$string = "anticonstitutionnellement"
$string = @TAB & "Introduction" &@crlf&@crlf & "AutoIt v3 is a freeware BASIC-like scripting language designed for automating the Windows GUI and general scripting. It uses a combination of simulated keystrokes, mouse movement and window/control manipulation in order to automate tasks in a way not possible or reliable with other languages (e.g. VBScript and SendKeys). AutoIt is also very small, self-contained and will run on all versions of Windows out-of-the-box with no annoying runtimes required!"

;$hTimer = TimerInit()

Global $array = _Occurences($string)
; _ArrayDisplay($array)

$ubound = UBound($array)
Global $lettres[$ubound][2]
For $i = 0 to $ubound - 1
   $lettres[$i][0] = $array[$i][1]
Next

While $ubound > 1
  _Bin($array, $lettres)
  $sum = $array[0][0] + $array[1][0]
  $chars = $array[0][1] & $array[1][1]
  For $i = 0 to $ubound - 1
     If $sum <= $array[$i][0] Then 
        _Insert($array, $i, $sum, $chars)
        Exitloop
     ElseIf $sum > _ArrayMax($array, 1) Then
        _Insert($array, $ubound, $sum, $chars)
        Exitloop
     EndIf
  Next
  $ubound -= 1
;  _ArrayDisplay($array, "$ubound")
;  _ArrayDisplay($lettres, "lettres " & $ubound)
Wend

_ArraySort($lettres, 0, 0, 0, 1)
;_ArrayDisplay($lettres)

$encoded = ""
For $i = 1 To StringLen($string)
    For $j = 0 To UBound($lettres) - 1
        If StringMid($string, $i, 1) == $lettres[$j][0] Then
            $encoded &= $lettres[$j][1]
            ExitLoop
        EndIf
    Next
Next
;msgbox(0,"encode", $encoded)

;============================
; décodage

$decoded = _Decode($encoded, $lettres)
;msgbox(0,"decode", TimerDiff($hTimer))
msgbox(0,"decode", $decoded)


;################################################

Func _Bin(ByRef $array, ByRef $lettres)
  For $k = 0 to UBound($lettres)-1
     If StringInStr($array[0][1], $lettres[$k][0], 1) Then $lettres[$k][1] = "0" & $lettres[$k][1]
     If StringInStr($array[1][1], $lettres[$k][0], 1) Then $lettres[$k][1] = "1" & $lettres[$k][1]
  Next
EndFunc

Func _Insert(ByRef $array, $pos, $var1, $var2)
   Local $a = UBound($array)
; insère
   Redim $array[$a+1][2]
   For $d = $a to $pos step -1
       $array[$d][0] = $array[$d-1][0]
       $array[$d][1] = $array[$d-1][1]
   Next
   $array[$pos][0] = $var1
   $array[$pos][1] = $var2
; ajuste
   For $d = 2 to $a
      $array[$d-2][0] = $array[$d][0]
      $array[$d-2][1] = $array[$d][1]
   Next
   Redim $array[$a-1][2]
EndFunc

Func _Decode($coded, $tabref)
 Local $output = "", $len
 While $coded <> ""
   For $i = 0 to UBound($tabref)-1
      $len = StringLen($tabref[$i][1])
      If StringLeft($coded, $len) = $tabref[$i][1] Then  
          $output &= $tabref[$i][0] 
          $coded = StringTrimLeft($coded, $len)
          Exitloop
      EndIf
   Next
 Wend
 Return $output
EndFunc
      
Func _Occurences($txt)
  Local $res[StringLen($txt)][2], $n = 1, $a, $e = 0
  While 1
       $e += 1
       $a = StringSplit($txt, "")
       For $i = 1 to $a[0]
          $txt = StringReplace($txt, $a[$i], $a[$i], 0, 1)
          If @extended = $e Then
              $res[$n-1][1] = $a[$i]
              $res[$n-1][0] = $e
              $txt = StringReplace($txt, $a[$i], "", 0, 1)
              If $txt = "" Then ExitLoop 2
              $n += 1
          EndIf
      Next
  Wend
  Redim $res[$n][2]
  Return $res
EndFunc
 

Edit après remarque pertinente de jguinch

[Faco]

Hello,
Sin on a le droit de donner du code , moi aussi j'ai testé de le faire : (c'est bourrin et pas très très bien structuré mais ça fait le travail ^^)

► Afficher le texte

Code : Tout sélectionner

#include <array.au3>
Global $string = "abcdbcdcddkjhgfdsrtyuioiuytddfghjknbvcfghuyyfiysgoidiodbo",$tableau

$tableau = _poid($string)
$tableau = _doTree($tableau)
$titi = _recupCodeHuffman($tableau[UBound($tableau)-1][0])
 _display($titi)
ConsoleWrite($titi & @CRLF)

Func _poid($stg)
    Local $char,$nbCharDiff = 0,$tempoSTG = $stg,$charDO=""
    For $i=1 To StringLen($stg)
        $char = StringLeft($tempoSTG,1)
        If Not StringInStr($charDO,$char,1) Then
            $charDO &= $char
            $nbCharDiff += 1
        EndIf
        $tempoSTG = StringTrimLeft($tempoSTG, 1)
    Next
    ConsoleWrite($charDO & "-" & $nbCharDiff &@CRLF)
    Dim $tab[$nbCharDiff][2]
    For $i=1 To $nbCharDiff
        $char = StringLeft($charDO,1)
        $boucle = 1
        While $boucle >0
            $boucle +=1
            If StringInStr($stg,$char,1,$boucle) == 0 Then
                $tab[$i-1][0]=$char
                $tab[$i-1][1]=$boucle-1
                $boucle = 0
            EndIf
        WEnd
        $charDO = StringTrimLeft($charDO, 1)
    Next
    Return $tab
EndFunc

Func _doTree($tab)
    For $i=0 To UBound($tab)-2
        _ArraySort($tab,0,$i,0,1)
        Dim $temp[1][2]
        $temp[0][0]=$tab[$i][0]
        $temp[0][1]=$tab[$i+1][0]
        $tab[$i+1][0]=$temp
        $tab[$i+1][1]=$tab[$i][1] + $tab[$i+1][1]
    Next
    Return $tab
EndFunc

Func _recupCodeHuffman($tab,$tt = "")
    local $temp = ""
    If IsArray($tab) Then
        $temp = _recupCodeHuffman($tab[0][0],$tt & "0") & ";" & _recupCodeHuffman($tab[0][1],$tt & "1")
    Else
        $temp = $tt & "|" & $tab
    EndIf
    Return $temp
EndFunc

Func _display($string)
    Local $temp1 = StringSplit($string,";"),$titi
    Dim $final[$temp1[0]][2]
    For $i=1 To $temp1[0]
        $titi = StringSplit($temp1[$i],"|")
        $final[$i-1][0]=$titi[2]
        $final[$i-1][1]=$titi[1]
    Next
    _ArrayDisplay($final)
EndFunc
 

[mikell]

Le mécanisme de la fonction récursive est sympa
Le problème c'est qu'avec ton code les caractères ";" et "|" sont interdits dans l'input string sous peine de fatal error (comme n'importe quel autre caractère utilisé comme séparateur pourrait l'être d'ailleurs)
C'est à cause de cette limitation que je me suis rabattu sur la formule 'rustique' de l'array évolutive

[jguinch]

@Mikell : tu devrais revoir la partie encodage, en utilisant le même mécanisme que pour le décodage, car dans l'état, si la phrase contient des 0 et des 1, ça fout le bronx (Par exemple "Les 101 dalmatiens").
Tu peux mettre ça à la place (à faire à ta sauce...) :

► Afficher le texte

Code : Tout sélectionner

$encoded = ""
For $i = 1 To StringLen($string)
    For $j = 0 To UBound($lettres) - 1
        If StringMid($string, $i, 1) = $lettres[$j][0] Then
            $encoded &= $lettres[$j][1]
            ExitLoop
        EndIf
    Next
;~    $encoded = StringReplace($encoded, $lettres[$i][0], $lettres[$i][1])

Next
;~ msgbox(0,"encode", $encoded)

Sinon, j'ai fait aussi un code, en partant sur une petite base SQLite (je voulais le poster ça ce week-end, mais ma box a cramé, snif) :

► Afficher le texte

Code : Tout sélectionner

#Include <Array.au3> ; juste pour _ArrayDisplay
#include <SQLite.au3>
#include <SQLite.dll.au3>


AutoItSetOption("MustDeclareVars", 1)

Local $sContent = "Salut à toi, jeune padawan !"

Local $aResult, $iRows, $iColumns
Local $iRval, $iRow, $sEncode, $sDecode



_SQLite_Startup()
_SQLite_Open()


; Etape 1 : Création de la liste de tous les caractères et leur nombre d'occurences
Local $aOcc = _Occurences($sContent)
_ArrayDisplay($aOcc)

; Etape 2 : Création des noeuds
While 1
    $iRval = _SQLite_GetTable2d(-1, "SELECT rowid, Counts FROM tree WHERE ParentID = 0 ORDER BY Counts ASC, rowid DESC", $aResult, $iRows, $iColumns)
    If $iRows = 1 Then ExitLoop
    
    _SQLite_Exec ( -1, "INSERT INTO tree (Counts, ParentID) VALUES (" & $aResult[1][1] + $aResult[2][1] & ", 0);")
    _SQLite_Exec ( -1, "UPDATE tree SET ParentID = " & _SQLite_LastInsertRowID() & ", Weight = 0 WHERE rowid = " & $aResult[1][0] & ";")
    _SQLite_Exec ( -1, "UPDATE tree SET ParentID = " & _SQLite_LastInsertRowID() & ", Weight = 1 WHERE rowid = " & $aResult[2][0] & ";")
WEnd


; Etape 3 : Création de la clé pour chaque caractère (en remontant du caractère à la racine)
For $i = 1 To $aOcc[0][0]
    $iRow = $i
    $aOcc[$i][1] = ""

    While 1
        _SQLite_GetTable2d ( -1, "SELECT ParentID, Weight FROM tree WHERE rowid = " & $iRow & ";", $aResult, $iRows, $iColumns)
        If $aResult[1][0] = 0 Then ExitLoop

        $aOcc[$i][1] = $aResult[1][1] & $aOcc[$i][1]
        $iRow = $aResult[1][0]
    WEnd
Next
_SQLite_Close()
_ArrayDisplay($aOcc)


; Etape 4 : Encodage - Remplacement des caractères par leur clé correspondante
For $i = 1 To StringLen($sContent)
    For $j = 1 To $aOcc[0][0]
        If $aOcc[$j][0] == StringMid( $sContent, $i, 1) Then 
            $sEncode &= $aOcc[$j][1]
            ExitLoop
        EndIF
    Next
Next
MsgBox(0, "Encode", $sEncode)


; Etape 5 : Decodage - Remplacement des clés par chaque caractère correspondant
Local $len = StringLen($sEncode)
For $i = 1 To $len
    For $j = 1 To $aOcc[0][0]
        $sEncode = StringRegExpReplace($sEncode, "^" & $aOcc[$j][1], "")
        If @extended Then
            $len = StringLen($sEncode)
            $sDecode &= $aOcc[$j][0]
            ExitLoop
        EndIf
    Next
Next

MsgBox(0, "Decode", $sDecode)



Func _Occurences($sText)
    Local $aLetters[1][2] = [[ 0 ]], $sLetter, $iCount

    If Not _SQLite_Exec(-1, "CREATE TABLE tree (Counts INT, ParentID INT, Weight INT);") = $SQLITE_OK Then Exit MsgBox(16, "SQLite Error", _SQLite_ErrMsg())

    While $sText <> ""
        $sLetter = StringLeft($sText, 1)
        $sText = StringReplace($sText, $sLetter, "", 0, 1)
        $iCount = @Extended

        Redim $aLetters[ UBound($aLetters) + 1][2]

        $aLetters[ UBound($aLetters) - 1][0] = $sLetter
        $aLetters[ UBound($aLetters) - 1][1] = $iCount

        _SQLite_Exec(-1, "INSERT INTO tree (Counts, ParentID) VALUES (" & $iCount & ", 0);")
    WEnd
    $aLetters[0][0] = UBound($aLetters) - 1

    Return $aLetters
EndFunc

 

Bon par contre, on est bien d'accord : c'est super lent avec AutoIt, c'est pas fait pour ça

[mikell]

Merci pour les 101 dalmatiens, erreur d'inattention typique
Mais je suis pas le seul

Code : Tout sélectionner

 If $aOcc[$j][0] [color=#FF0000]==[/color] StringMid( $sContent, $i, 1) Then

[jguinch]

Ah oui, bien joué l'ami...

[Faco]

Le mécanisme de la fonction récursive est sympa
Le problème c'est qu'avec ton code les caractères ";" et "|" sont interdits dans l'input string sous peine de fatal error (comme n'importe quel autre caractère utilisé comme séparateur pourrait l'être d'ailleurs)
C'est à cause de cette limitation que je me suis rabattu sur la formule 'rustique' de l'array évolutive

effectivement, quand j'ai codé ça, ça ma même pas traversé la tête de mettre autre chose que des lettres en entrée.
Mais, c'est facilement contournable, il faut des séparateurs avec 2 caractères ( ";" -> ";/" , "|"->"|!" par exemple).
mon code reste quand même pas top.

tchou !

[sozary]

Merci bien!!
Je ne suis pas chez moi actuellement et ne pourrais pas tester vos codes !
Je reviendrais ce week end et y mettrais mes différentes questions, car après un coup d'oeil, eh bah... j'ai pas trop compris comment vous procédiez pour classer les donner comme dans un arbre !
J'envois ce message grâc à une borne wi-fi de Quick donc j'ai pus accèder pendant quelques minutes au forum !

[jguinch]

Juste une question sozary a quoi va te servir un tel script ? Vu la lenteur...

[mikell]

Surtout avec un code à base de sqlite 300 fois plus lent (environ) qu'un code à base d'array

[jguinch]

@mikell : mon code est lent, c'est un fait... Ce temps de latence est simplement dû au fait que le script va télécharger SQLite.dll systématiquement...
Si tu télécharges la dll et que tu la place dans le même dossier que le script, tu verras qu'il n'y a pas une si grande différence que ça (le tiens est 3 fois plus rapide pour la phrase d'intro AutoIt que tu as utilisé dans ton code...)
Maintenant, avec un fichier de 100 lignes :
- mon script : 9801ms
- ton script : 94409ms

[jchd]

Et si, par curiosité, tu englobes ta boucle de création des noeuds ainsi :

Code : Tout sélectionner

_SQLite_Exec(-1, "begin;")
While 1
    ; ...insertion des noeuds
WEnd
_SQLite_Exec(-1, "commit;")

est-ce que ça impacte le chrono ?

[jguinch]

Comme je ne maîtrise pas tellement du tout le SQL, je n'avais pas pensé à utiliser le begin/commit...
A priori, pas d'amélioration...

[mikell]

C'est vrai, l'array marche mieux jusqu'à une trentaine de lignes à peu près, après c'est l'horreur
Mais de toute façon c'est académique, pour un fichier de 100 lignes on arrive déjà dans la tranche des 10 secondes (20 s pour 200 lignes avec ton code, etc) alors que le premier zippeur venu fait ça en quelques centièmes

[jguinch]

Entièrement d'accord : c'est pas fait pour ça.
D'où ma question sur l'intérêt de la chose

[jchd]

Personnellement je préfère de loin voir des questions posées sur des implémentations d'algorithmes courants, plutôt que sur des PixelSearch et autre MouseClick dont on sait très bien à quoi ils vont servir.

Pour la transaction, ça ne m'étonne pas : avec une base en mémoire on ne court-circuite que peu voire pas de code dans bien des cas.

[sozary]

Ah! Ok! J'ai bien étudié vos codes et est compris dans l'ensemble (je suis même parvenus à faire un petit arbre tout seul !)!

Pour la question, je me suis intéressé à cet algorithme car étudiant la programmation, ma curiosité m'a poussé à me documenter !
L'algorithme de Huffman m'a alors séduit !
Merci encore à tous pour vos réponses!