Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 7 sur 7
  1. #1
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    227
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2002
    Messages : 227
    Points : 92
    Points
    92

    Par défaut Détecter des patterns

    Bonjour,

    Imaginons cette suite de chiffre:

    4 67 23 88 34 90 23 88 65 3 9 23 88 77 12 3 99 00 11 23 99 00 34 78 56 99 00 34 12

    J'aurais voulu savoir si quelqu'un a déjà écrit un algorithme capable de détecter des, on va dire redondances, dans une suite de chiffres ?

    En gros un algo qui me dit, sans même connaitre les chiffres recherchées, dans cette suite j'ai trouvé trois, heu je sais pas comment l'exprimer, genre voila j'ai trouvé un 23 88 - 99 00 imbriqué dans un autre 23 88 - 99 00 imbriqué dans un autre 23 88 - 99 00 (je sais pas si je me fais bien comprendre c'est un peu spécial comme truc )

    Pouvez-vous m'aider, si du moins vous comprenez ce que je recherche

    Merci par avance !

  2. #2
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    Détecter les "imbrications" sans savoir qu'on cherche des imbrications, ca va être assez compliqué.Dans ton exemple, on pourrait aussi dire qu'on a trois "23 88", suivi de trois "99 00".

    1ère étape, à mon avis, c'est de repérer les séquences de 2 valeurs qui se répètent. Construire une matrice de co-occurrence est un bon moyen.

    2nde étape, remplacer les séquences de 2 valeurs qu'on a trouvé par une seule valeur "spéciale", et recommencer l'étape 1. Ca permet ainsi de trouver des séquences de 3 valeurs qui se répètent.

    etc.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Futur Membre du Club
    Homme Profil pro
    Inscrit en
    août 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : août 2011
    Messages : 17
    Points : 19
    Points
    19

    Par défaut

    Il existe des algorithmes efficaces qui permettent trouver les plus grandes séquences qui se répètent au moins R fois dans la suite. En O(N log N) si ta suite a N chiffres.

    Après ça dépend ce que tu recherches, les plus grandes séquences qui se répètent, les séquences qui se répètent le plus souvent etc...

  4. #4
    Futur Membre du Club
    Inscrit en
    janvier 2008
    Messages
    34
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 34
    Points : 18
    Points
    18

    Par défaut

    Bonjour,

    Moi ça m'intéresse comment s'appelle un tel algorithme ?
    (Dans mon cas chaque chiffre renvoie à une ligne de code distincte et j'ai besoin de repérer des patterns dans un gros code)
    dans le même ordre d'idée, existe-t-il des algorithmes permettant de détecter des patterns similaires mais pas exacts ?

    Gorz

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro Jean-Marc Blanc
    Comme retraité, des masses
    Inscrit en
    avril 2007
    Messages
    2 947
    Détails du profil
    Informations personnelles :
    Nom : Homme Jean-Marc Blanc
    Âge : 73
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : avril 2007
    Messages : 2 947
    Points : 4 531
    Points
    4 531

    Par défaut

    Pour clarifier le problème, juste une question: est-ce que ce sont des chiffres ou des nombres?
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  6. #6
    Membre émérite
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    487
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 487
    Points : 878
    Points
    878

    Par défaut

    Un algo naïf qui ressemble aux algos des graphes et enveloppes diverses

    tab = [1, 34, 10, 2, 34, 5, 34, 10, 2, 6]

    tab_tmp = [] // Mais on peut sûrement faire l'algo sur place avec l'intervalle qui grandit

    Initialisation: On prend le premier élément et on le met dans tab_tmp: [1]

    Et pour chaque élément de tab en commençant par le deuxième.

    *) On prend 34
    Recherche de 34 dans tab_tmp -> Non présent on ne fait rien
    On le met dans tab_tmp: [1, 34]

    *) On prend 10
    Recherche de 10 dans tab_tmp -> Non présent on ne fait rien
    On le met dans tab_tmp: [1, 34, 10]

    *) On prend 2
    Recherche de 2 dans tab_tmp -> Non présent on ne fait rien
    On le met dans tab_tmp: [1, 34, 10, 2]

    *) On prend 34
    Recherche de 34 dans tab_tmp: Trouvé indice 2

    Tant que que les éléments suivants sont égaux
    Suivant de 34 dans tab -> 5
    Suivant de 34 dans tab_tmp -> 10

    Pas égaux: On a trouvé une redondance. À voir si on le considère comme un pattern de 1

    On le met dans tab_tmp: [1, 34, 10, 2, 34]

    *) On prend 5
    Recherche de 5 dans tab_tmp -> Non présent on ne fait rien
    On le met dans tab_tmp: [1, 34, 10, 2, 34, 5]

    *) On prend 34
    Recherche de 34 dans tab_tmp: Trouvé indice 2 et indice 5

    Suivant de 34 dans tab -> 10
    Suivant de 34 dans tab_tmp indice 2 -> 10
    Suivant de 34 dans tab_tmp indice 5 -> 5

    34 dans tab_tmp indice 5 est éliminé, mais pas 34 dans tab_tmp indice 2: on a trouvé un pattern de 2

    On continue
    Suivant de 34, 10 dans tab -> 2
    Suivant de 34, 10 dans tab_tmp indice 2 -> 2

    Il sont égaux, on continue: on a trouvé un pattern de 3

    On continue
    Suivant de 34, 10, 2 dans tab -> 6
    Suivant de 34, 10, 2 dans tab_tmp indice 2 -> 34

    Pas égaux: On a trouvé un pattern de 3 [34, 10, 2]

    On les met dans tab_tmp: [1, 34, 10, 2, 34, 5, 34, 10, 2]

    *) On recommence à partir de 6
    ....

    À vue de nez, c'est un algo en au plus(n!)
    Mais on peut sûrement l'optimiser avec des tableaux associatifs pour la recherche.
    D'ailleurs, il faudra sûrement sauvegarder les patterns et leur nombre quelque part.

    Il n'y a aucune gestion des patterns suffixes/ préfixes, style
    [10, 34, 10, 6, 10, 6, 10, 34, 10, 6, 10, 34]

    Et pour finir, c'est un algo de base, parce qu'en parcourant après ta liste des patterns trouvés, on peut trouver
    1. Le plus grand pattern
    2. Le plus court pattern
    3. La plus grande longueur de pattern
    4. La plus petite longueur de pattern
    5. Le nombre de patterns
    6. Les patterns similaires mais pas exacts
    7. ...

    Et en fonction de que ce qui est recherché on pourra sûrement modifier cet algo de base pour en faire un algo sur place

    Édit: Un deuxième algo naïf
    tab = [1, 34, 10, 2, 34, 5, 34, 10, 2, 6]
    On recherche toutes les redondances
    34: indices 2, 5, 7
    10: indices 3, 8
    2: indices 4, 9

    Et là cela se corse
    Il faut trouver toutes les redondances qui se suivent et qui apparaissent plusieurs fois
    Il faut générer tous les couples [peut-être qu'au fur à mesure on pourra supprimer des nombres/ redondances/ couples] et regarder les indices:
    34, 10, 2, [34, 10], [34, 2], [10, 34], [10, 2], [2, 34], [2, 10], [34, 10, 2], [34, 2, 10], [10, 34, 2], [10, 2, 34], [2, 10, 34], [2, 34, 10]

    Trouver -> [34, 10, 2] -> indices 2, 3, 4 et 7, 8, 9

    Question: comme pour le premier algo. Si un nombre se trouve dans un pattern, peut-il faire parti d'un deuxième pattern?

  7. #7
    Membre chevronné
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mars 2009
    Messages
    424
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : mars 2009
    Messages : 424
    Points : 695
    Points
    695

    Par défaut

    Bonjour,

    Une solution "brute force" ressemble je pense à ceci :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    function findPatterns(s){
        // pour chaque caractère
        for ( var i = 0; i < s.length; i++ ){
            // on recherche un pattern dans la suite de la chaîne
            for ( var j = i+1; j < s.length; j++ ){
                
                // on calcul la taille du pattern
                var count = 0 ;
                for ( var k = 0; k < s.length - j; k++ ){
                    // chiffre différent?
                    if ( s[i+k] != s[j+k] )
                        break;
                    
                    count++ ;
                }
                
                // on tient un pattern de taille significative?
                if ( count >= 4 ){
                   // on exploite s.substring(i,i+count) et s.substring(j,j+count)
                   // ...
                }
            }
        }
    }

    PS :
    - Le code ci-dessus ne prend pas en compte les espaces.
    - Il trouve 1239900, puis 239900, puis 39900, puis 9900 (il faudrait incrémenter de "count" la boule sur "i" quand on trouve un pattern pour l'éviter)
    - Désolé pour JavaScript, j'ai testé avec JSFiddle ici : http://jsfiddle.net/w2vV5/.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •