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

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