Mot factorisation en temps

Étant donné deux chaînes , nous écrivons pour leur concaténation. Étant donné une chaîne et entier , nous écrivons pour la concaténation de copies de . Maintenant donné une chaîne, nous pouvons utiliser cette notation pour la 'comprimer', c'est-à-dire que peut être écrit comme . Appelons le poids d'une compression le nombre de caractères qui y apparaissent, donc le poids de est deux, et le poids de (une compression d' ) est de trois (séparé$S_1, S_2$$S_1S_2$$S$$k\geq 1$$(S)^k = SS\cdots S$$k$$S$$AABAAB$$((A)^2 B)^2$ ( ( A ) 2 B 2 ) ( A B ) 2 A A B A B A A$((A)^2 B^2)$$(AB)^2 A$$ABABA$$A$ sont comptés séparément).

Considérons maintenant le problème du calcul de la compression "la plus légère" d'une chaîne donnée avec . Après réflexion, il existe une approche de programmation dynamique évidente qui s'exécute en ou selon l'approche exacte.$S$$|S|=n$$O(n^3 \log n)$$O(n^3)$

Cependant, on m'a dit que ce problème peut être résolu en temps , bien que je ne trouve aucune source sur la façon de le faire. Plus précisément, ce problème a été évoqué lors d'un récent concours de programmation (problème K ici , deux dernières pages). Au cours de l'analyse, un algorithme été présenté et, à la fin, la borne pseudo quadratique a été mentionnée ( ici à la marque de quatre minutes). Malheureusement, le présentateur n'a fait référence qu'à «un lemme de combinatoire de mots compliqué», alors maintenant je suis venu ici pour demander la solution :-)$O(n^2 \log n)$$O(n^3 \log n)$

Si je ne vous comprends pas, je pense que la factorisation du coût minimum peut être calculée en temps comme suit.$O(n^2)$

Pour chaque indice i, nous calculerons un ensemble de valeurs pour comme suit. Soit le plus petit entier tel qu'il existe un entier satisfaisantPour ce , soit le plus grand avec cette propriété. Si aucun n'existe, définissez afin que nous sachions qu'il y a zéro pour cet indice.$(p_i^\ell, r_i^\ell)$$\ell=1,2,\ldots$$p_i^1\ge 1$$r\ge 2$

Soit le plus petit entier strictement supérieur à satisfaisant, de même, pour certains . Comme précédemment, prenez pour être le maximum ayant fixé . En général, est le plus petit nombre strictement supérieur à . Si aucun tel n'existe, alors .$p_i^2$$(r_i^1-1)p_i^1$

Notez que pour chaque indice i, nous avons car les valeurs de augmentent géométriquement avec . (si existe, il n'est pas seulement strictement plus grand que mais plus grand que celui d'au moins Ceci établit l'augmentation géométrique. )$L_i=O(\log (i+1))$$p_i^\ell$$\ell$$p_i^{\ell+1}$$(r_i^\ell-1)p_i^\ell$$p_i^\ell/2$

Supposons maintenant que toutes les valeurs nous soient données. Le coût minimum est donné par la récurrence entendu que pour nous définissons . Le tableau peut être rempli en temps .$(p_i^\ell,r_i^\ell)$

$$\mathrm{dp}(i,j) = \min\left\{\mathrm{dp}(i, j-1) + 1, \min_\ell \left(\mathrm{dp}\left(i,j - r_j^\ell p_j^\ell\right) + \mathrm{dp}(j-r_j^\ell p_j^\ell+1,j-p_j^\ell)\right)\right\}$$ $i>j$$\mathrm{dp}(i,j) = +\infty$$O(n^2 + n\sum_j L_j)$

Nous avons déjà observé ci-dessus que en délimitant la somme terme par terme. Mais en fait, si nous regardons la somme entière, nous pouvons prouver quelque chose de plus net.$\sum_j L_j = O(\sum_j \log (j+1)) = \Theta(n\log n)$

Considérons l'arbre de suffixe de l'inverse de (c'est-à-dire l'arbre de préfixe de S). Nous facturerons chaque contribution à la somme à un bord de afin que chaque bord soit facturé au plus une fois. Chargez chaque au bord émanant de et allant vers . Ici est la feuille de l'arbre préfixe correspondant à et nca désigne l'ancêtre commun le plus proche.$T(\overleftarrow{S})$$S$$\sum_i L_i$$T(\overleftarrow{S})$$p_i^j$$\mathrm{nca}(v(i), v(i-p_i^j))$$v(i-p_i^j)$$v(i)$$S[1..i]$

Cela montre que . Les valeurs peuvent être calculées dans le temps par une traversée de l'arbre des suffixes mais je laisserai les détails à une édition ultérieure si quelqu'un est intéressé.$O(\sum_i L_i)=O(n)$$(p_i^j,r_i^j)$$O(n+\sum_i L_i)$

Faites-moi savoir si cela a du sens.

Il y a votre chaîne initiale S de longueur n. Voici le pseudo-code de la méthode.

next_end_bracket = n
for i in [0:n]: # main loop

    break if i >= length(S) # due to compression
    w = (next_end_bracket - i)# width to analyse

    for j in [w/2:0:-1]: # period loop, look for largest period first
        for r in [1:n]: # number of repetition loop
            if i+j*(r+1) > w:
                break r loop

            for k in [0:j-i]:
                # compare term to term and break at first difference
                if S[i+k] != S[i+r*j+k]:
                    break r loop

        if r > 1:
            # compress
            replace S[i:i+j*(r+1)] with ( S[i:i+j] )^r
            # don't forget to record end bracket...
            # and reduce w for the i-run, carrying on the j-loop for eventual smaller periods. 
            w = j-i

J'ai intentionnellement donné peu de détails sur les "crochets d'extrémité" car il faut beaucoup d'étapes pour empiler et désempiler, ce qui rendrait la méthode principale peu claire. L'idée est de tester une éventuelle contraction supplémentaire à l'intérieur de la première. par exemple ABCBCABCBC => (ABCBC) ² => (A (BC) ²) ².

Donc, le point principal est de chercher d'abord les grandes périodes. Notez que S [i] est le ième terme de S qui saute tout "(", ")" ou puissance.

• la boucle i est O (n)
• la boucle j est O (n)
• r + k-boucles est O (log (n)) car il s'arrête à la première différence

C'est globalement O (n²log (n)).