Algorithme, factorisation de séquences/combinaisons

je déterre ce fil sur lequel je suis tombé en cherchant sur internet.
Je cherche moi aussi à factoriser un ensemble de chaines de caractères en un regex. Dans mon cas, j'ai quelques centaines de séquences de 4 chiffres dont beaucoup se suivent.

J'ai trouvé un algo tout fait en python ici, à base de Trie justement : http://blog.jancewicz.net/2010/12/op...s-regular.html

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class PrefixTree(object):
    '''
    Prefix tree for generating optimal regular expressions.
    '''
    def __init__(self):
        self.children = {}
        self.terminal = False
 
    def add(self, word):
        if not word:
            self.terminal = True
            return
        firstLetter, rest = word[0], word[1:]
        if firstLetter not in self.children:
            self.children[firstLetter] = PrefixTree()
        self.children[firstLetter].add(rest)
 
    def toRegex(self):
        children = self._getRegexOfChildren()
        if not self.terminal:
            assert self.children
        if self.terminal:
            if children:
                return '(%s)?' % children
            else:
                return ''
        elif len(self.children) > 1:
            return '(%s)' % children
        else:
            return children
 
    def _getRegexOfChildren(self):
        childkeys = sorted(self.children.keys())
        return '|'.join(k + self.children[k].toRegex()
                        for k in childkeys)
 
pt = PrefixTree()
pt.add('0123')
pt.add('0124')
pt.add('0125')
pt.add('0126')
pt.add('1125')
pt.add('1126')
print (pt.toRegex())
 
pt2 = PrefixTree()
pt2.add('3210')
pt2.add('4210')
pt2.add('5210')
pt2.add('6210')
pt2.add('5211')
pt2.add('6211')
print (pt2.toRegex())

donne :

Code:

1
2
(012(3|4|5|6)|112(5|6))
(3210|4210|521(0|1)|621(0|1))

Cet essai montre que le résultat n'est pas optimal. C'est quand même une piste...

j'ai de mon côté écrit une méthode un peu "bourrin" en matlab qui consislte simplement à trier les chaines de caractère puis à les factoriser par la gauche. J'aimerais bien réussir ensuit à re-factoriser le résultat par la droite mais je n'ai pas trop de temps à consacrer donc je cherche du déjà fait. Je suis étonné du peu de codes que j'ai trouvé sur l'Internet. Les expressions régulières sont d'un usage tellement fréquent que c'est étonnant qu'il y ait si peu d'automates pour les fabriquer.

Bref, voilà mon code Matalb :

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
26
27
function R = factorize(N)
% N un vecteur ligne de nombres < 9999 dont on veut factoriser l'écriture en 4 caractères
M = reshape(sprintf('%04d', sort(N)), 4, numel(N)).' ;
while all(M(:,1)=='0')
    M = M(:,2:end) ;
end
R = fact(M) ;
end
 
function R = fact(M) % le moteur, récursif, sur un tableau de n lignes et 4 caractères
A = unique(M(:,1)) ;
if size(M,2)>1
    C = {} ;
    for c = A'
        M1 = M(M(:,1)==c,2:end) ;
        fm = fact(M1) ;
        C{end+1} = fm ;
    end
    R = '(' ;
    for k=1:numel(A)-1
        R = [R, A(k), C{k}, ')|('] ;
    end
    R = [R, A(end), C{end}, ')'] ;
else
    R=['[', A', ']'] ;
end
end