algo : trouver le nombre le 'pattern' le plus frequent

[gruik]

le problème est assez simple finalement, et trouve de nombreuses applications, on peut citer par exemple la methode babbage-kasiski permettant de déterminer la longueur de la clé en cryptanalyse

la question est plus généraliste encore, disons qu'on a une liste d'items [a,a,a,a,b,c,d,a,a,d,a,b,d,d,c,b,a,d,c,a,c,d,d,b,a,a,b,b,a,d,a,a,b,c,d,d,c,a,b,c,d], on pourrait aussi bien voir ça comme un texte/une suite de mots ou une suite de lettres, peu importe

le propos est de trouver la suite d'items la plus longue qui revient le plus fréquemment, comprenez qu'entre "a,a" qui fait 2 items de long et revient 6 fois, on préfèrera donner la priorité au pattern "a,b,c,d" qui fait 4 éléments de long et revient seulement 4 fois

la question est simple, est-ce vous avez des idées de comment je pourrais implémenter ça, si possible de manière relativement efficace ?

[InstinctHack]

Fonctionnel

Code PHP :

function test($array)
{
    $b=explode(',',$array);
    $number=0;
    $search=$b[0];
    $return=array();
    foreach($b as $key=>$value)
    {
        if($value==$search)
        {
            $number++;
        }
        else
        {
            $return[]=$number;
            $number=1;
            $search=$value;
        }
    }
    $return[]=$number;

    arsort($return);

    foreach($return as $key=>$value)
    {
        return $value;
    }
}
echo test('b,v,d,d,g,g,g,g,g,g,g,g,o'); 


EDIT j'ai du mal en ce moment.... là je trouve la longueur du pattern de longueur 1 le long....
Faudrais juste générer les différents pattern possible, et rechercher le nomber d'occurence de chacun.
Je continuerais avec plaisir demain

[gruik]

ton code si je comprends bien retourne la longueur de la plus grande suite d'un meme item (genre pour "g,g,g,g,g,g,g,g" il retournera 8)
(donc pas bon, c'est pas ça l'objectif )

[lesk8vaincra]

Pour proposer un algo faudrait que tu nous dises déja quelle est la règle "générale" pour décider qu'une plus longue suite est préférable.

longueur 4 * 4 est préférable a 6 *2 , mais est ce que 4 * 2 l'est aussi?

En dehors de ca, ca me parait pas bien compliqué, tu fais une boucle qui parcoure ta chaine (ou ton fichier, ou...) et qui compte le nombre d'occurence d'une séquence (a l'aide, par exemple, d'une HashMap<String, int> en java?).

Sinon, a mon sens:

- une boucle de 2 a chaine.length()/2 pour établir la "longueur" des séquences a comparer. A la première itération, on chercher les séquences de longueur 2, puis de longueur 3,...
- une boucle qui "avance" dans la chaine

[b0fh]

Oui en effet, il faut donner un ordre meilleur que "la plus longue chaine", parce que sinon il suffit de prendre la chaîne entière, elle n'apparait qu'une fois mais c'est la plus longue.

Est-ce que (longueur de la sous-chaine) * (occurrences - 1) te parait une bonne métrique ?

Il faut aussi définir si la chaine répétée peut se chevaucher. Si oui, aller jusqu'a longueur/2 n'est pas suffisant; par exemple avec "ababab" la meilleure sous-chaine est probablement"abab"

Est-ce qu'une heuristique serait acceptable ? si oui, l'algorithme de Lempel-Ziv donnera peut-être de bons résultats.

Est-ce que la chaine en entrée a des propriétés statistiques particulières ? si chaque caractère est distribué indépendamment, on peut probablement prédire la longueur approximative de la meilleure chaine ?

Sinon, les solutions proposées sont en O(N^2), ce qui n'est pas "raisonnablement efficace" à mon sens. Je crois qu'une technique légèrement plus efficace serait de faire un tri externe des suffixes du tableau, puis de chercher dans ce tableau la meilleure séquence.

Je fais une implémentation en haskell tout a l'heure

[gruik]

longueur 4 * 4 est préférable a 6 *2 , mais est ce que 4 * 2 l'est aussi?

nop, 6*2 est préférable aux deux autres justement
la longueur est le premier discriminant (donc ca revient à chercher le motif répété au moins une fois le plus long possible), et ensuite seulement le nombre d'occurences est discriminant

En dehors de ca, ca me parait pas bien compliqué, tu fais une boucle qui parcoure ta chaine (ou ton fichier, ou...) et qui compte le nombre d'occurence d'une séquence

oui c'est tout le propos, mais l'approche naïve là dessus ça peut à mon avis rapidement s’avérer couteux, tout dépend la longueur de liste initiale (son nombre d'items, ou de lettre si on parle d'un texte), sachant que la "profondeur de recherche" ira d'un pattern de longueur len(liste_initiale)/2 comme tu le fais remarquer à un pattern de longueur 1 item

en fait en y réfléchissant là je me dit qu'il y a surement à préciser également la question des patterns identiques "superposés", le cas où l'on a par exemple "a,b,c,d,a,b,c,d,a,b", le pattern le plus long serait donc "a,b,c,d,a,b", avec les deux derniers items "a,b" qui sont également le début du second pattern identique
on a qu'à dire que ce point-ci est libre, comprendre qu'avec ou sans superposition je suis de toutes façons preneur, sachant que sans superposition ça s'optimise forcément plus vite du coup

( édith: le temps que je poste je n'avais pas lu ton message b0fh )

Est-ce qu'une heuristique serait acceptable ? si oui, l'algorithme de Lempel-Ziv donnera peut-être de bons résultats.

posons que non, je jetterais quand même un oeil à Lempel-Ziv histoire de pas mourir idiot

Est-ce que la chaine en entrée a des propriétés statistiques particulières ?

là encore on va partir du principe que non, mais je garde l'idée dans un coin

Je crois qu'une technique légèrement plus efficace serait de faire un tri externe des suffixes du tableau, puis de chercher dans ce tableau la meilleure séquence.

je t'avoues tu me colles là, qu'est-ce que tu appelles "tri externe" et "suffixes" ? ^^

[lesk8vaincra]

Bon jviens de me lancer dans un ptit code, testé mais pas forcémment parfaitement fonctionnel ou même optimisé, je ne veut absolument pas prétendre qu'il te conviendra mais ca pourrait te fournir d'éventuelles pistes:

Code :

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication2;

import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
*
* @author LSV
*/
public class JavaApplication2 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        HashMap<String, Integer> occurences = new HashMap<String, Integer>();

        String chaine = "aaaaaaaaaaaaaaaaaaaaaaabbbcccddddeeee";
        for (int i = 2; i < (chaine.length() / 2); i++) {
            // i indique la longueur de la séquence cherchée
            for(int j=0;(j+i)<chaine.length();j++){
                String sousChaine = chaine.substring(j, j+i);
                occurences.put(sousChaine, stringOccur(chaine, sousChaine));              
            }
        }
        
        int maxOccurs = 0;
        String chaineFrequente = "";
        for (Map.Entry<String, Integer> entry : occurences.entrySet()) {
            System.out.println("Nombre d'occurence de la chaine '"+entry.getKey()+"': "+entry.getValue());
            if(entry.getValue()>maxOccurs){
                maxOccurs = entry.getValue();
                chaineFrequente = entry.getKey();
            }
        }
        
        System.out.println("La chaine la plus fréquente est: '"+chaineFrequente+"' et elle apparait "+maxOccurs+" fois.");
    }

    /**
     * Renvoie le nombre d'occurrences de la sous-chaine de caractères spécifiée
     * dans la chaine de caractères spécifiée
     *
     * @param text chaine de caractères initiale
     * @param string sous-chaine de caractères dont le nombre d'occurrences doit
     * etre compté
     * @return le nombre d'occurrences du pattern spécifié dans la chaine de
     * caractères spécifiée
     */
    public static final int stringOccur(String text, String string) {
        return regexOccur(text, Pattern.quote(string));
    }

    /**
     * Renvoie le nombre d'occurrences du pattern spécifié dans la chaine de
     * caractères spécifiée
     *
     * @param text chaine de caractères initiale
     * @param regex expression régulière dont le nombre d'occurrences doit etre
     * compté
     * @return le nombre d'occurrences du pattern spécifié dans la chaine de
     * caractères spécifiée
     */
    public static final int regexOccur(String text, String regex) {
        Matcher matcher = Pattern.compile(regex).matcher(text);
        int occur = 0;
        while (matcher.find()) {
            occur++;
        }
        return occur;
    }
}

Les fonctions regexOccur et StringOccur ont été trouvées la:
http://www.developpez.net/forums/d183810...ce-string/

A toi d'implémenter la méthode pour déterminer quelle est la meilleure sous-chaine a choisir en fonction de sa longueur et de sa fréquence.

[b0fh]

Alors dans ton exemple premier, la plus longue chaine serait plutôt "aabcd" qui se répète deux fois.

Si tu considères que c'est correct, une implémentation O(n log n) en Haskell:

Code :

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative
import Data.List
import Data.Ord

commonPrefix = ((map fst . takeWhile (uncurry (==))) .) . zip
commons = (zipWith commonPrefix <*> tail) . sort . tails
best = maximumBy (comparing length) . commons

-- best "aaaabcdaadabddcbadcacddbaabbadaabcddcabcd" = "aabcd"

Explications: "tails" crée la liste de tous les suffixes (çad les n derniers caractères, pour n de 1 à la longueur de la chaine). En Haskell prendre la queue d'une liste ne cause pas de réallocation, en C tu pourrais faire pareil en remplissant simplement un tableau de pointeurs vers chaque début possible de la string.

Ce tableau est ensuite trié (tri externe veut dire qu'on trie des pointeurs vers des blogs de données potentiellement beaucoup plus gros, et qu'on évite le cout du déplacement ou du fetch complet desdonnées.)

Ton plus long préfixe répété sera donc forcément sur deux lignes contigues. On considère chaque couple de ligne contigues (le zipWith <*> tails) en y appliquant commonPrefix (qui cherche le plus long préfixe commun possible).

On prend les préfixes résultants, on les trie par longueur, et on prend le plus long.

Si tu veux un critère arbitraire sur la longueur et le nombre de répétitions, tu pourrais placer tous ces préfixes dans un Patricia Tree puis parcourir l'arbre en calculant une métrique quelconque sur chaque noeud.

[gruik]

ok la logique ne m'a pas tout de suite sauté aux yeux et je vais me fendre d'une petite explication au cas où d'autres seraient à la fois intéressés et dans le gaz niveau compréhension

prenons la chaine "abracadabra" (oui je sais c'est pas terriblement original, c'est ni plus ni moins le même exemple que sur wikipedia)
cette chaine compte donc 11 suffixes :

Code :

1    abracadabra
2     bracadabra
3      racadabra
4       acadabra
5        cadabra
6         adabra
7          dabra
8           abra
9            bra
10            ra
11             a

l'idée ça va être de comparer ces suffixes deux à deux pour trouver leur plus long préfixe commun
de fait si on compare par exemple les suffixes "dabra" et "bra", ils ne commencent déjà pas par la même lettre, donc ça nous emmènera pas loin
on va donc, avant de les comparer, trier les suffixes (par ordre alphanumérique croissant), du coup on se retrouve avec :

Code :

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

partant de là - et c'est effectivement plus clair en le voyant - on est sûr que le plus long préfixe commun sera trouvé entre deux suffixes adjacents, puisque grâce au tri ceux qui se ressemblent sont déjà les uns à coté des autres, voyez l'idée ?

reste à appliquer une recherche du plus long préfixe commun entre deux suffixes adjacents n et n+1, de ('a','abra') jusqu'à ('ra','racadabra')

là, pour chaque couple de suffixe on va tout simplement matcher chaque lettre une à une en bouclant jusqu'à la fin du mot le plus court, pour à la fin retourner le plus long préfixe commun des deux suffixes
on se retrouve alors avec une liste de préfixes comme celle là :

Code :

'a'
'abra'
'a'
'a'
''   // ici ('adabra', 'bra') forcement rien ne correspond
'bra'
''   // pareil pour ('bracadabra', 'cadabra')
''   // ('cadabra', 'dabra')
''   // et ('dabra', 'ra')
'ra'

reste juste à prendre le plus long and voila, la plus longue sous-chaine répétée dans "abracadabra" c'est bien "abra"

une implémentation simple (comprenez "qui vautre toute la ram en quelques seconde si la chaine est trop grande mais est suffisamment didactique et fera bien le job pour analyser quelques milliers de caractères") en python :

Code PYTHON :


def lcp (s1, s2):
    '''find the longest common prefix'''
    n = min(len(s1),len(s2))
    for i in xrange(n):
        if s1[i] != s2[i]:
            return s1[:i]
    return s1[:n]

def lrs (chaine):
    '''find the longest repeated substring'''
    suffix = [chaine[i:] for i in xrange(len(chaine))] # huhu..
    suffix.sort()
    prefix = [lcp(suffix[i],suffix[i+1]) for i in xrange(len(suffix)-1)]
    return max(prefix, key=len)

 

Code PYTHON :


>>> import lcs
>>> lcs.lrs('aaaabcdaadabddcbadcacddbaabbadaabcddcabcd')
'aabcd'
 

reste la question de l'efficacité, comme disait b0fh en stockant des pointeurs pour créer son tableau de suffixes plutôt qu'en créant à chaque fois une copie en mémoire on évite d'exploser la ram, ce que semble permettre automatiquement Haskell mais en python le slicing chaine[x:y] occasionne obligatoirement une copie (que ce soit une chaine ou une liste d'ailleurs), affaire à suivre donc...


EDIT: finalement en remplacant le slice chaine[i:] par buffer(chaine,i,None) on a bien ce qu'on veut sans le cout mémoire :

Code DIFF :


def lrs (chaine):
    '''find the longest repeated substring'''
-   suffix = [chaine[i:] for i in xrange(len(chaine))] # huhu..
+   suffix = [buffer(chaine,i) for i in xrange(len(chaine))]
+   print 'chaine   : %d octets' % len(chaine)
+   print 'suffix[] : %d octets' % sys.getsizeof(suffix)
    suffix.sort()
 

Code PYTHON :


>>> import string, lcs
>>> s = ''.join([i for i in open('fichier2Mo','r').read() if i in string.ascii_letters+' '])
>>> lcs.lrs(s)
chaine   : 1209527 octets
suffix[] : 9784704 octets  # machine 64bits
(...)
 

Code LIST :

 

[Dobry]

Merci Gruik, en effet, les algos LCS sont très interessants et c'est un exemple qui s'y porte à merveille
Je sais pas pourquoi mais je bloque toujours avec ces algos (C++) je vais regarder ton code voir si finalement je bloquais pas sur quelque chose d'assez simple !