Détecter des patterns

Version imprimable

20/12/2012, 13h54
Mercenary Developer

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 :roll: c'est un peu spécial comme truc )

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

Merci par avance !
20/12/2012, 19h11
pseudocode

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". :D

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.
20/12/2012, 23h44
zamato

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...
11/04/2014, 16h14
Gorzyne

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
11/04/2014, 19h15
FR119492

Pour clarifier le problème, juste une question: est-ce que ce sont des chiffres ou des nombres?
Jean-Marc Blanc
12/04/2014, 01h52
foetus
Un algo naïf qui ressemble aux algos des graphes et enveloppes diverses :mrgreen:

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!) :mrgreen:
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] :mouarf: :mouarf:

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 :mrgreen:

Édit: Un deuxième algo naïf :mrgreen:
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 :whistle:
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? :koi: :koi:

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/.