Calculer le nombre maximum d'exécutions possibles pour une chaîne de longueur donnée.

Question

Il y a quelques semaines, Lembik a posé la question suivante :

Une période p d'une chaîne de caractères w est un nombre entier positif quelconque p tal que w[i]=w[i+p] chaque fois que les deux côtés de cette équation sont définis. Soit per(w) dénote la taille de la plus petite période de w . Nous disons qu'une chaîne w est périodique si per(w) <= |w|/2 .

Ainsi, de manière informelle, une chaîne périodique est simplement une chaîne constituée d'une autre chaîne répétée au moins une fois. La seule complication est qu'à la fin de la chaîne, nous n'avons pas besoin d'une copie complète de la chaîne répétée, du moment qu'elle est répétée dans son intégralité au moins une fois.

Par exemple, considérons la chaîne de caractères x = abcab . per(abcab) = 3 comme x[1] = x[1+3] = a , x[2]=x[2+3] = b et il n'y a pas de période plus courte. La chaîne abcab n'est donc pas périodique. Cependant, la chaîne ababa est périodique comme per(ababa) = 2 .

D'autres exemples, abcabca , ababababa y abcabcabc sont également périodiques.

Pour ceux qui aiment les regex, celle-ci détecte si une chaîne est périodique ou non :

\b(\w*)(\w+\1)\2+\b

La tâche consiste à trouver tous les maximum des sous-chaînes périodiques dans une chaîne plus longue. On les appelle parfois exécute dans la littérature.

Une sous-chaîne w[i,j] de w est une sous-chaîne périodique maximale (run) si elle est périodique et si aucune des deux conditions suivantes n'est remplie w[i-1] = w[i-1+p] ni w[j+1] = w[j+1-p] . De manière informelle, la "série" ne peut pas être contenue dans une "série" plus grande ayant la même période.

Étant donné que deux séries peuvent représenter la même chaîne de caractères apparaissant à des endroits différents de la chaîne globale, nous représenterons les séries par des intervalles. Voici la définition ci-dessus répétée en termes d'intervalles.

Une suite (ou une sous-chaîne périodique maximale) dans une chaîne de caractères. T est un intervalle [i...j] con j>=i de telle sorte que

• T[i...j] est un mot périodique de période p = per(T[i...j])
• Il est maximal. Formellement, ni T[i-1] = T[i-1+p] ni T[j+1] = T[j+1-p] . De manière informelle, la série ne peut pas être contenue dans une série plus large avec la même période.

Désignez par RUNS(T) l'ensemble des passages de la chaîne T .

Exemples de courses

• Les quatre sous-chaînes périodiques maximales (runs) de la chaîne de caractères T = atattatt sont T[4,5] = tt , T[7,8] = tt , T[1,4] = atat , T[2,8] = tattatt .

• La chaîne T = aabaabaaaacaacac contient les 7 sous-ensembles périodiques maximaux suivants (runs) : T[1,2] = aa , T[4,5] = aa , T[7,10] = aaaa , T[12,13] = aa , T[13,16] = acac , T[1,8] = aabaabaa , T[9,15] = aacaaca .

• La chaîne T = atatbatatb contient les trois parcours suivants. Ils sont : T[1, 4] = atat , T[6, 9] = atat et T[1, 10] = atatbatatb .

Ici, j'utilise l'indexation 1.

L'objectif

Écrivez le code de sorte que, pour chaque entier n commençant à 2, vous produisiez les plus grands nombres de passages contenus dans toute chaîne binaire de longueur n .

Exemple d'optima

Dans la suite : n, optimum number of runs, example string .

2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100

Existe-t-il un moyen plus rapide de trouver le nombre optimal de cycles pour des valeurs croissantes de n qu'une approche naïve en temps O(n^2 2^n) ?

Answer 1

Un algorithme générationnel pour trouver toutes les solutions

L'idée

Dans chaque chaîne, le dernier caractère ne peut contribuer qu'à un nombre limité de passages.

Un dernier 0 ne peut qu'ajouter une course à

10 + 0 => 100

puisque dans

00 + 0 => 000

c'est seulement une répétition. Et s'il ajoute cette course minimale, la prochaine course minimale possible à ajouter est

110010 + 0 => 1100100

note encore

010010 + 0 => 0100100

n'est pas une course supplémentaire, c'est une répétition. Les prochains ajouts possibles sont

111001001100100
1111001001100100111001001100100
...

Les chiffres peuvent varier, mais les longueurs minimales sont les suivantes

3, 7, 15, 31

qui est

4^1 - 1, 4^2 - 1, ..., 4^n - 1

Au début de la chaîne, il n'y a pas besoin d'un caractère différent, donc

maxaddlast = 4^n - 2

donne le nombre maximum de séries qui peuvent être ajoutées en ajoutant le dernier caractère.

L'algorithme

• Pendant que la recherche de la longueur n est effectuée, toutes les variantes sont enregistrées avec un nombre d'exécutions dans [maxNumberOfRuns - maxaddlast(n+1), maxNumberOfRuns].
• Pour trouver une solution avec maxNumberOfRuns pour n+1, il suffit d'étendre toutes les variantes enregistrées avec 0 et 1 et de les vérifier.

La graine

Le problème restant est de dimensionner la pile pour collecter toutes les variantes qui sont nécessaires pour les futures semences.

Comme il n'y a pas assez de données pour deviner une formule valide, un algorithme adaptatif est choisi :

1. La taille initiale de la pile pour n est devinée à partir de n - 1.
2. Pour chaque solution, les tailles de pile utilisées sont vérifiées pour s'assurer qu'il y a toujours de la place par 1 dans la pile.
3. Si la pile a été entièrement utilisée à un certain n, la taille de la pile est augmentée et le calcul est redémarré à n.

Le résultat

length 104 with 91 runs

est atteint dans les 600 secondes. Ensuite, la mémoire est épuisée avec les paramètres par défaut. Utilisez -Xmx16G ou plus. Pour des nombres plus importants, le code doit être modifié pour maintenir la graine sur le disque, et non en mémoire.

Et c'est beaucoup plus rapide que la méthode de la force brute.

** The Code **

Et voici mon exemple de code en Java :

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

import de.bb.util.Pair;

/**
 * A search algorithm to find all runs for increasing lengths of strings of 0s
 * and 1s.
 * 
 * This algorithm uses a seed to generate the candidates for the next search.
 * The seed contains the solutions for rho(n), rho(n) - 1, ..., minstart(n).
 * Since the seed size is unknown, it starts with a minimal seed: minstart(n) =
 * rho(n) - 1; After the solutions are calculated the all seeds are checked. If
 * a seed with minstart(n) was used, that minstart(n) gets decremented and the
 * search is restarted at position n + 1. This guarantees that the seed is
 * always large enough.
 * 
 * Optional TODO: Since the seed can occupy large amounts of memory, the seed is
 * maintained on disk.
 * 
 * @author Stefan "Bebbo" Franke (c) 2016
 */
public class MaxNumberOfRunsAdaptive {
    private static long start;

    private ArrayList<Pair<byte[], ArrayList<Integer>>> seed = new ArrayList<>();
    private int max;
    private ArrayList<ArrayList<Pair<byte[], ArrayList<Integer>>>> nextSeedStack;

    private ArrayList<Integer> maxs = new ArrayList<>();
    private ArrayList<Integer> diffs = new ArrayList<>();
    private ArrayList<Integer> totals = new ArrayList<>();
    private int total;

    private byte[] buffer;

    public static void main(String[] args) {
        int limit = 9999;
        if (args.length == 1) {
            try {
                limit = Integer.parseInt(args[0]);
            } catch (Exception e) {
            }
        }
        start = System.currentTimeMillis();
        new MaxNumberOfRunsAdaptive().run(limit);
        long took = (System.currentTimeMillis() - start) / 100;
        System.out.println("took " + (took / 10.) + "s");
    }

    /**
     * Find a string with the max number of runs for all lengths from 2 to
     * limit;
     * 
     * @param limit
     *            the limit to stop calculation.
     */
    private void run(int limit) {
        maxs.add(0);
        maxs.add(0);
        diffs.add(0);
        diffs.add(1);
        totals.add(0);
        totals.add(0);

        ArrayList<Integer> n0 = new ArrayList<Integer>();
        n0.add(0);
        seed.add(Pair.makePair(new byte[] { '0' }, n0));
        saveSeed(2);

        for (int i = 2; i <= limit;) {
            int restart = compose(i);
            if (restart < i) {
                System.out.println("*** restarting at: " + restart + " ***");
                i = restart;
                loadSeed(i);
                total = totals.get(i - 1);
            } else {
                saveSeed(i + 1);
                ++i;
            }
        }
    }

    /**
     * Load the seed for the length from disk.
     * 
     * @param length
     */
    private void loadSeed(int length) {
        try {
            seed.clear();
            final FileReader fr = new FileReader("seed-" + length + ".txt");
            final BufferedReader br = new BufferedReader(fr);
            for (String line = br.readLine(); line != null; line = br.readLine()) {
                final int space = line.indexOf(' ');
                final byte[] b = line.substring(0, space).getBytes();
                final String sends = line.substring(space + 2, line.length() - 1);
                final ArrayList<Integer> ends = new ArrayList<>();
                for (final String s : sends.split(",")) {
                    ends.add(Integer.parseInt(s.trim()));
                }
                seed.add(Pair.makePair(b, ends));
            }
            fr.close();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Save the seed for the given length to the disk.
     * 
     * @param length
     *            the length
     */
    private void saveSeed(int length) {
        try {
            final FileWriter fos = new FileWriter("seed-" + length + ".txt");
            for (final Pair<byte[], ArrayList<Integer>> p : seed) {
                fos.write(new String(p.getFirst()) + " " + p.getSecond().toString() + "\n");
            }
            fos.close();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Compose new strings from all available bases. Also collect the candidates
     * for the next base.
     */
    private int compose(int length) {
        max = 0;

        int nextStackSize;
        if (diffs.size() > length)
            nextStackSize = diffs.get(length) + 1;
        else
            nextStackSize = diffs.get(length - 1) - 1;
        if (nextStackSize < 2)
            nextStackSize = 2;

        // setup collector for next bases
        nextSeedStack = new ArrayList<>();
        for (int i = 0; i < nextStackSize; ++i) {
            nextSeedStack.add(new ArrayList<Pair<byte[], ArrayList<Integer>>>());
        }

        buffer = new byte[length];
        // extend the bases
        for (Pair<byte[], ArrayList<Integer>> e : seed) {
            final byte[] s = e.getFirst();
            System.arraycopy(s, 0, buffer, 0, length - 1);
            if (s.length < 3 || s[s.length - 1] == '1' || s[s.length - 2] == '1' || s[s.length - 3] == '1') {
                buffer[length - 1] = '0';
                test(length, e.getSecond());
            }
            if (s.length < 3 || s[s.length - 1] == '0' || s[s.length - 2] == '0' || s[s.length - 3] == '0') {
                buffer[length - 1] = '1';
                test(length, e.getSecond());
            }
        }
        long took = (System.currentTimeMillis() - start) / 100;

        final ArrayList<String> solutions = new ArrayList<String>();
        for (Pair<byte[], ArrayList<Integer>> p : nextSeedStack.get(nextSeedStack.size() - 1)) {
            solutions.add(new String(p.getFirst()));
        }
        total += solutions.size();
        if (totals.size() <= length)
            totals.add(0);
        totals.set(length, total);

        if (maxs.size() <= length) {
            maxs.add(0);
        }
        maxs.set(length, max);

        System.out.println(length + " " + max + " " + (took / 10.) + " " + total + " " + solutions);

        seed.clear();
        // setup base for next level
        for (ArrayList<Pair<byte[], ArrayList<Integer>>> t : nextSeedStack) {
            seed.addAll(t);
        }

        if (diffs.size() <= length) {
            diffs.add(1);
        }
        int restart = length;
        // check for restart
        for (final String b : solutions) {
            for (int i = 2; i < b.length(); ++i) {
                int diff = maxs.get(i) - countRuns(b.substring(0, i));
                if (diff >= diffs.get(i)) {
                    if (i < restart)
                        restart = i;
                    diffs.set(i, diff + 1);
                }
            }
        }
        System.out.println(diffs);

        return restart;
    }

    /**
     * Test the current buffer and at it to the next seed stack,
     * 
     * @param l
     *            the current length
     * @param endRuns
     *            the end runs to store
     */
    void test(final int l, final ArrayList<Integer> endRuns) {
        final ArrayList<Integer> r = incrementalCountRuns(l, endRuns);
        final int n = r.get(r.size() - 1);

        // shift the nextBaseStack
        while (max < n) {
            nextSeedStack.remove(0);
            nextSeedStack.add(new ArrayList<Pair<byte[], ArrayList<Integer>>>());
            ++max;
        }

        // add to set in stack, if in stack
        final int index = nextSeedStack.size() - 1 - max + n;
        if (index >= 0)
            nextSeedStack.get(index).add(Pair.makePair(buffer.clone(), r));
    }

    /**
     * Find incremental the runs incremental.
     * 
     * @param l
     *            the lengths
     * @param endRuns
     *            the runs of length-1 ending at length -1
     * @return a new array containing the end runs plus the length
     */
    private ArrayList<Integer> incrementalCountRuns(final int l, final ArrayList<Integer> endRuns) {
        final ArrayList<Integer> res = new ArrayList<Integer>();
        int sz = endRuns.size();
        // last end run dummy - contains the run count
        int n = endRuns.get(--sz);
        int pos = 0;

        for (int i = l - 2; i >= 0; i -= 2) {
            int p = (l - i) / 2;
            // found something ?
            if (equals(buffer, i, buffer, i + p, p)) {
                while (i > 0 && buffer[i - 1] == buffer[i - 1 + p]) {
                    --i;
                }
                int lasti = -1;

                while (pos < sz) {
                    lasti = endRuns.get(pos);
                    if (lasti <= i)
                        break;
                    lasti = -1;
                    ++pos;
                }
                if (lasti != i)
                    ++n;

                res.add(i);
            }
        }

        res.add(n);
        return res;

    }

    /**
     * Compares one segment of a byte array with a segment of a 2nd byte array.
     * 
     * @param a
     *            first byte array
     * @param aOff
     *            offset into first byte array
     * @param b
     *            second byte array
     * @param bOff
     *            offset into second byte array
     * @param len
     *            length of the compared segments
     * @return true if the segments are equal, otherwise false
     */
    public final static boolean equals(byte a[], int aOff, byte b[], int bOff, int len) {
        if (a == null || b == null)
            return a == b;
        while (len-- > 0)
            if (a[aOff + len] != b[bOff + len])
                return false;
        return true;
    }

    /**
     * Simple slow stupid method to count the runs in a String.
     * 
     * @param s
     *            the string
     * @return the count of runs.
     */
    static int countRuns(String s) {
        int n = 0;
        int l = s.length();
        for (int i = 0; i < l - 1; ++i) {
            for (int k = i + 1; k < l; ++k) {
                int p = 0;
                while (i + p < k && k + p < l) {
                    if (s.charAt(i + p) != s.charAt(k + p))
                        break;
                    ++p;
                }
                if (i + p == k) {
                    int jj = k + p - 1;
                    if (i > 0 && s.charAt(i - 1) == s.charAt(i - 1 + p)) {
                        continue;
                    }
                    while (jj + 1 < l && s.charAt(jj + 1) == s.charAt(jj + 1 - p)) {
                        ++jj;
                        ++k;
                    }
                    ++n;
                }
            }
        }
        return n;
    }
}

Answer 2

Réponse partielle. L'idée est de s'inspirer de l'algorithme de recherche de chaînes de Boyer-Moore, en le modifiant de manière à ce que la chaîne à faire correspondre provienne de la chaîne source.

Considérons le problème pour une chaîne de longueur n recherche de pistes d'époque k , donde 2k < n . S'il existe un algorithme en temps polynomial pour ce problème, alors il en existe un pour le problème général. Il suffit d'exécuter un tel algorithme une fois pour chaque 2 <= k <= n/2 . Si le problème spécifique se déroule dans O(p(n)) donde p a un degré d alors le problème général s'exécutera avec un polynôme de degré d+1 . Il suffit donc d'examiner le problème spécifique.

Soit la chaîne d'entrée T[0 ... n-1] . La clé ici est de réaliser que si T[i] != T[i+k] , alors la paire d'indices (i, i+k) crée une obstruction à l'existence d'une course. Lorsque nous voyons une obstruction, nous pouvons subdiviser le problème en deux problèmes sur des chaînes d'entrée plus courtes : T[0 ... i+k-1] y T[i+1 ... n-1] . Si l'une de ces chaînes est trop courte, alors l'algorithme n'émet rien et se termine ; c'est de cette façon que la récursion se termine lorsqu'il n'y a pas d'exécution. Cherchez maintenant les obstructions a i+1 , i+2 , ..., jusqu'à i+k-1 . S'il en existe, clivage. D'autre part, s'il existe une séquence [i ... i+k-1] sans obstruction, alors on a un parcours de longueur 2k . Si nous trouvons un run, nous le prolongeons au maximum (c'est facile), puis nous découpons le problème en trois morceaux : le préfixe, le run et le suffixe. Nous émettons le run et nous avons maintenant deux problèmes, le préfixe et le suffixe, chacun plus court. Pour exécuter cette opération de manière récursive, choisissez un problème initial i avec valeur (n+k)/2 .

La raison pour laquelle il s'agit d'une réponse partielle est que je laisse de côté l'analyse selon laquelle il s'agit d'un algorithme en temps polynomial. La raison pour laquelle la preuve n'est pas triviale est que, lorsque vous avez une obstruction, les longueurs i+k y n-i-1 s'ajoutent n+k-1 qui est plus grand que n Il est donc concevable que la longueur totale des entrées d'une pile de récurrence puisse croître de manière exponentielle. D'autres arguments seraient nécessaires pour montrer que cela ne se produit pas réellement.