La distance d'édition (ou Levenshtein) entre deux chaînes est le nombre minimal d'insertions, de suppressions et de substitutions de caractère unique nécessaires pour transformer une chaîne en l'autre. Si les deux chaînes ont chacune une longueur n, il est bien connu que cela peut se faire en temps O (n ^ 2) par programmation dynamique. Le code Python suivant effectue ce calcul pour deux chaînes s1et s2.

def edit_distance(s1, s2):
    l1 = len(s1)
    l2 = len(s2)

    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
      matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
      for sz in range(0,l1):
        if s1[sz] == s2[zz]:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
        else:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
    return matrix[l2][l1]

Dans cette tâche, vous devez vous rapprocher le plus possible du calcul de la distance de montage, mais avec une restriction de mémoire sévère. Votre code est autorisé à définir un tableau contenant 1 000 entiers 32 bits et ce doit être le seul stockage temporaire que vous utilisez dans votre calcul. Toutes les variables et structures de données doivent être contenues dans ce tableau. En particulier, vous ne pourriez pas implémenter l'algorithme ci-dessus comme pour les chaînes de longueur 1000 car il vous faudrait stocker au moins 1 000 000 de numéros. Lorsque votre langue n'a pas naturellement des entiers 32 bits (par exemple Python), vous devez simplement vous assurer de ne jamais stocker un nombre supérieur à 2 ^ 32-1 dans le tableau.

Vous pouvez lire les données en utilisant n'importe quelle bibliothèque standard de votre choix sans vous soucier des restrictions de mémoire dans cette partie. Afin de rendre la compétition équitable pour la partie principale de votre code, vous ne pouvez utiliser que des opérations fonctionnellement équivalentes à celles du langage de programmation C et ne pouvez utiliser aucune bibliothèque externe.

Pour être plus clair, la mémoire pour stocker les données d'entrée ou utilisées par l'interpréteur de votre langue, JVM, etc. ne compte pas dans votre limite et vous ne pouvez rien écrire sur le disque. Vous devez supposer que les données d'entrée sont en lecture seule lorsqu'elles sont en mémoire, vous ne pouvez donc pas les réutiliser pour gagner plus d'espace de travail.

Que dois-je mettre en œuvre?

Votre code doit être lu dans un fichier au format suivant. Il aura trois lignes. La première ligne est la vraie distance d'édition. La seconde est la chaîne 1 et la troisième est la chaîne 2. Je vais la tester avec les exemples de données à https://bpaste.net/show/6905001d52e8 où les chaînes ont une longueur de 10 000 mais elles ne devraient pas être spécialisées pour ces données. Il doit produire la plus petite distance d'édition qu'il puisse trouver entre les deux chaînes.

Vous devrez également prouver que votre distance d'édition provient en fait d'un ensemble valide de modifications. Votre code doit avoir un commutateur qui le transforme en un mode qui peut utiliser plus de mémoire (autant que vous le souhaitez) et génère les opérations d'édition qui donnent votre distance d'édition.

But

Votre score sera le (optimal edit distance/divided by the edit distance you find) * 100. Pour commencer, notez que vous pouvez obtenir un score en comptant simplement le nombre de discordances entre les deux chaînes.

Vous pouvez utiliser n'importe quelle langue de votre choix, librement disponible et facile à installer sous Linux.

Jeu décisif

Dans le cas d'un bris d'égalité, je vais exécuter votre code sur ma machine Linux et le code le plus rapide l'emporte.

C ++, score 92,35

Algorithme d'estimation: l'algorithme trouve le premier endroit où les deux chaînes diffèrent, puis essaie toutes les permutations d'opération N possibles (insérer, supprimer, remplacer - les caractères qui correspondent sont ignorés sans consommer d'opération). Il note chaque ensemble d'opérations possible en fonction de la distance à laquelle cet ensemble d'opérations correspond avec succès aux deux chaînes, ainsi que du degré de convergence des longueurs de chaîne. Après avoir déterminé l'ensemble des N opérations ayant le score le plus élevé, la première opération de l'ensemble est appliquée, la non-concordance suivante est trouvée et le processus se répète jusqu'à ce que la fin de la chaîne soit atteinte.

Le programme essaie toutes les valeurs de N de 1 à 10 et sélectionne le niveau qui a donné les meilleurs résultats. N = 10 est généralement le meilleur maintenant que la méthode de notation prend en compte la longueur de la chaîne. Des valeurs plus élevées de N seraient probablement encore meilleures, mais prennent exponentiellement plus de temps.

Utilisation de la mémoire: Le programme étant purement itératif, il nécessite très peu de mémoire. Seules 19 variables sont utilisées pour suivre l'état du programme. Celles-ci sont définies par #defines pour agir comme des variables globales.

Utilisation: Le programme est utilisé de la même manière que feersum: le premier paramètre est supposé être le fichier, et tout paramètre supplémentaire indique que les modifications doivent être affichées. Le programme imprime toujours la distance de montage estimée et le score.

Sortie de vérification: sortie de vérification formatée sur trois lignes:

11011111100101100111100110100 110 0 0000   0 01101
R I          IR     R        D   D D    DDD D     D
01 1111110010 0001110001101000110101000011101011010

La ligne du haut est la chaîne cible, le milieu est les opérations et le bas est la chaîne en cours d'édition. Les espaces dans la ligne d'opération indiquent que les caractères correspondent. 'R' indique que la chaîne d'édition a son caractère à cette position remplacé par le caractère de la chaîne cible. 'I' indique que la chaîne d'édition a le caractère de la chaîne cible inséré à cette position. 'D' indique que la chaîne d'édition a son caractère à cette position supprimé. Les chaînes d'édition et cible ont des espaces insérés lorsque l'autre a un caractère inséré ou supprimé afin qu'ils s'alignent.

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <fstream>

int memory[1000];
#define first (*(const char **)&memory[0])
#define second (*(const char **)&memory[1])
#define block_ia memory[2]
#define block_ib memory[3]
#define block_n memory[4]
#define block_op memory[5]
#define block_o memory[6]
#define block_x memory[7]
#define n memory[8]
#define opmax memory[9]
#define best_op memory[10]
#define best_score memory[11]
#define score memory[12]
#define best_counter memory[13]
#define la memory[14]
#define lb memory[15]
#define best memory[16]
#define bestn memory[17]
#define total memory[18]

// verification variables
char printline1[0xffff]={};
char *p1=printline1;
char printline2[0xffff]={};
char *p2=printline2;
char printline3[0xffff]={};
char *p3=printline3;


// determine how many characters match after a set of operations
int block(){
    block_ia=0;
    block_ib=0;
    for ( block_x=0;block_x<block_n;block_x++){
        block_o = block_op%3;
        block_op /= 3;
        if ( block_o == 0 ){ // replace
            block_ia++;
            block_ib++;
        } else if ( block_o == 1 ){ // delete
            block_ib++;
        } else { // insert
            if ( first[block_ia] ){ 
                block_ia++;
            }
        }
        while ( first[block_ia] && first[block_ia]==second[block_ib] ){ // find next mismatch
            block_ia++;
            block_ib++;
        }
        if ( first[block_ia]==0 ){
            return block_x;
        }
    }
    return block_n;
}

// find the highest-scoring set of N operations for the current string position
void bestblock(){
    best_op=0;
    best_score=0;
    la = strlen(first);
    lb = strlen(second);
    block_n = n;
    for(best_counter=0;best_counter<opmax;best_counter++){
        block_op=best_counter;
        score = n-block();
        score += block_ia-abs((la-block_ia)-(lb-block_ib));
        if ( score > best_score ){
            best_score = score;
            best_op = best_counter;
        }
    }
}

// prepare edit confirmation record
void printedit(const char * a, const char * b, int o){
    o%=3;
    if ( o == 0 ){ // replace
        *p1 = *a;
        if ( *b ){
            *p2 = 'R';
            *p3 = *b;
            b++;
        } else {
            *p2 = 'I';
            *p3 = ' ';
        }
        a++;
    } else if ( o == 1 ){ // delete
        *p1 = ' ';
        *p2 = 'D';
        *p3 = *b;
        b++;
    } else { // insert
        *p1 = *a;
        *p2 = 'I';
        *p3 = ' ';
        a++;
    }
    p1++;
    p2++;
    p3++;
    while ( *a && *a==*b ){
        *p1 = *a;
        *p2 = ' ';
        *p3 = *b;
        p1++;
        p2++;
        p3++;
        a++;
        b++;
    }
}


int main(int argc, char * argv[]){

    if ( argc < 2 ){
        printf("No file name specified\n");
        return 0;
    }

    std::ifstream file(argv[1]);
    std::string line0,line1,line2;
    std::getline(file,line0);
    std::getline(file,line1);
    std::getline(file,line2);

    // begin estimating Levenshtein distance
    best = 0;
    bestn = 0;
    for ( n=1;n<=10;n++){ // n is the number of operations that can be in a test set
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            first++;
            second++;
        }
        total=0;
        while ( *first && *second ){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            total ++;
            first += block_ia;
            second += block_ib;
        }
        // when one string is exhausted, all following ops must be insert or delete
        while(*second){
            total++;
            second++;
        }
        while(*first){
            total++;
            first++;
        }
        if ( !best || total < best ){
            best = total;
            bestn = n;
        }
    }
    // done estimating Levenshtein distance

    // dump info to prove the edit distance actually comes from a valid set of edits
    if ( argc >= 3 ){
        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        n = bestn;
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            *p1 = *first;
            *p2 = ' ';
            *p3 = *second;
            p1++;
            p2++;
            p3++;
            first++;
            second++;
        }
        while ( *first && *second){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            printedit(first,second,best_op);
            first += block_ia;
            second += block_ib;
        }
        while(*second){
            *p1=' ';
            *p2='D';
            *p3=*second;
            p1++;
            p2++;
            p3++;
            second++;
        }
        while(*first){
            *p1=*first;
            *p2='I';
            *p3=' ';
            p1++;
            p2++;
            p3++;
            first++;
        }

        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        int ins=0;
        int del=0;
        int rep=0;
        while ( *p1 ){
            int a;
            for ( a=0;a<79&&p1[a];a++)
                printf("%c",p1[a]);
            printf("\n");
            p1+=a;
            for ( a=0;a<79&&p2[a];a++){
                ins += ( p2[a] == 'I' );
                del += ( p2[a] == 'D' );
                rep += ( p2[a] == 'R' );
                printf("%c",p2[a]);
            }
            printf("\n");
            p2+=a;
            for ( a=0;a<79&&p3[a];a++)
                printf("%c",p3[a]);
            printf("\n\n");
            p3+=a;
        }
        printf("Best N=%d\n",bestn);
        printf("Inserted = %d, Deleted = %d, Replaced=%d, Total = %d\nLength(line1)=%d, Length(Line2)+ins-del=%d\n",ins,del,rep,ins+del+rep,line1.length(),line2.length()+ins-del);
    }

    printf("%d, Score = %0.2f\n",best,2886*100.0/best);
    system("pause");
    return 0;
}

C ++ 75.0

Le programme est conçu pour fonctionner avec des chaînes de texte arbitraires. Ils peuvent être de longueurs différentes tant qu'aucun des deux ne dépasse 13824 caractères. Il utilise 1 897 entiers 16 bits, ce qui équivaut à 949 entiers 32 bits. Au début, je l'écrivais en C, mais j'ai réalisé qu'il n'y avait pas de fonction pour lire une ligne.

Le premier argument de ligne de commande doit être un nom de fichier. S'il existe un deuxième argument, un résumé des modifications est imprimé. La première ligne du fichier est ignorée tandis que les deuxième et troisième sont les chaînes.

L'algorithme est une version doublement bloquée de l'algorithme habituel. Il effectue essentiellement le même nombre d'opérations, mais est bien sûr beaucoup moins précis, car si une sous-séquence commune est divisée sur le bord d'un bloc, une grande partie des économies potentielles sont perdues.

#include <cstring>
#include <inttypes.h>
#include <iostream>
#include <fstream>

#define M 24
#define MAXLEN (M*M*M)
#define SETMIN(V, X) if( (X) < (V) ) { (V) = (X); }
#define MIN(X, Y) ( (X) < (Y) ? (X) : (Y) )

char A[MAXLEN+1], B[MAXLEN+1];
uint16_t d0[M+1][M+1], d1[M+1][M+1], d2[M+1][M+1];

int main(int argc, char**argv)
{

    if(argc < 2)
        return 1;

    std::ifstream fi(argv[1]);

    std::string Astr, Bstr;
    for(int i = 3; i--;)
        getline(fi, i?Bstr:Astr);
    if(!fi.good()) {
        printf("Error reading file");
        return 5;
    }
    if(Astr.length() > MAXLEN || Bstr.length() > MAXLEN) {
        printf("String too long");
        return 7;
    }

    strcpy(A, Astr.c_str());
    strcpy(B, Bstr.c_str());

    uint16_t lA = Astr.length(), lB = Bstr.length();
    if(!lA || !lB) {
        printf("%d\n", lA|lB);
        return 0;
    }
    uint16_t nbA2, nbB2, bA2, bB2, nbA1, nbB1, bA1, bB1, nbA0, nbB0, bA0, bB0; //block, number of blocks
    uint16_t iA2, iB2, iA1, iB1, jA2, jB2, jA1, jB1; //start, end indices of block

    nbA2 = MIN(M, lA);
    nbB2 = MIN(M, lB);
    for(bA2 = 0; bA2 <= nbA2; bA2++) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        for(bB2 = 0; bB2 <= nbB2; bB2++) {
            if(!(bA2|bB2)) {
                d2[0][0] = 0;
                continue;
            }
            iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
            d2[bA2][bB2] = ~0;
            if(bB2)
                SETMIN(d2[bA2][bB2], d2[bA2][bB2-1] + (jB2-iB2));
            if(bA2)
                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2] + (jA2-iA2));

            if(bA2 && bB2) {
                nbA1 = MIN(M, jA2-iA2);
                nbB1 = MIN(M, jB2-iB2);
                for(bA1 = 0; bA1 <= nbA1; bA1++) {
                    iA1 = iA2 + (jA2-iA2) * (bA1-1)/nbA1, jA1 = iA2 + (jA2-iA2) * bA1/nbA1;
                    for(bB1 = 0; bB1 <= nbB1; bB1++) {
                        if(!(bA1|bB1)) {
                            d1[0][0] = 0;
                            continue;
                        }
                        iB1 = iB2 + (jB2-iB2) * (bB1-1)/nbB1, jB1 = iB2 + (jB2-iB2) * bB1/nbB1;
                        d1[bA1][bB1] = ~0;
                        if(bB1)
                            SETMIN(d1[bA1][bB1], d1[bA1][bB1-1] + (jB1-iB1));
                        if(bA1)
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1] + (jA1-iA1));

                        if(bA1 && bB1) {
                            nbA0 = jA1-iA1;
                            nbB0 = jB1-iB1;
                            for(bA0 = 0; bA0 <= nbA0; bA0++) {
                                for(bB0 = 0; bB0 <= nbB0; bB0++) {
                                    if(!(bA0|bB0)) {
                                        d0[0][0] = 0;
                                        continue;
                                    }
                                    d0[bA0][bB0] = ~0;
                                    if(bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0][bB0-1] + 1);
                                    if(bA0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0] + 1);
                                    if(bA0 && bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0-1] + (A[iA1 + nbA0 - 1] != B[iB1 + nbB0 - 1]));
                                }
                            }
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1-1] + d0[nbA0][nbB0]);
                        }
                    }
                }

                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2-1] + d1[nbA1][nbB1]);
            }
        }
    }
    printf("%d\n", d2[nbA2][nbB2]);

    if(argc == 2)
        return 0;

    int changecost, total = 0;
    for(bA2 = nbA2, bB2 = nbB2; bA2||bB2; ) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
        if(bB2 && d2[bA2][bB2-1] + (jB2-iB2) == d2[bA2][bB2]) {
            total += changecost = (jB2-iB2);
            char tmp = B[jB2];
            B[jB2] = 0;
            printf("%d %d deleted {%s}\n", changecost, total, B + iB2);
            B[jB2] = tmp;
            --bB2;
        } else if(bA2 && d2[bA2-1][bB2] + (jA2-iA2) == d2[bA2][bB2]) {
            total += changecost = (jA2-iA2);
            char tmp = B[jA2];
            A[jA2] = 0;
            printf("%d %d inserted {%s}\n", changecost, total, A + iA2);
            A[jA2] = tmp;
            --bA2;
        } else {
            total += changecost = d2[bA2][bB2] - d2[bA2-1][bB2-1];
            char tmpa = A[jA2], tmpb = B[jB2];
            B[jB2] = A[jA2] = 0;
            printf("%d %d changed {%s} to {%s}\n", changecost, total, B + iB2, A + iA2);
            A[jA2] = tmpa, B[jB2] = tmpb;
            --bA2, --bB2;
        }
    }


    return 0;
}

Python, 100

J'ai réussi à calculer la distance d'édition parfaitement dans la limite de mémoire allouée. Malheureusement, cette entrée viole deux règles du défi, dans la lettre sinon dans l'esprit.

Tout d'abord, je n'ai pas réellement stocké mes données dans 1 000 pouces 32 bits. Pour les chaînes de 10000 caractères, mon programme crée deux tableaux de 10000 éléments qui ne contiendront que +1, 0 ou -1. À 1,585 bits par nombre ternaire, il serait possible de regrouper ces 20000 trits en 31700 bits, laissant 300 bits plus que suffisant pour mes 7 entiers 16 bits restants.

Deuxièmement, je n'ai pas implémenté le mode requis pour afficher les modifications. J'ai, en variante, implémenté un mode qui imprime la matrice d'édition complète. Il est absolument possible de calculer le chemin d'édition à partir de cette matrice, mais je n'ai pas le temps pour l'instant de l'implémenter.

#!/usr/bin/env python

import sys

# algorithm originally from
# https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows

print_rows = False
if len(sys.argv) > 2:
    print_rows = True

def LevenshteinDistance(s, t):
    # degenerate cases
    if s == t:
        return 0
    if len(s) == 0:
        return len(t)
    if len(t) == 0:
        return len(s)

    # create two work vectors of integer distance deltas

    # these lists will only ever contain +1, 0, or -1
    # so they COULD be packed into 1.585 bits each
    # 15850 bits per list, 31700 bits total, leaving 300 bits for all the other variables

    # d0 is the previous row
    # initialized to 0111111... which represents 0123456...
    d0 = [1 for i in range(len(t)+1)]
    d0[0] = 0        
    if print_rows:
        row = ""
        for i in range(len(t)+1):
            row += str(i) + ", "
        print row

    # d1 is the row being calculated
    d1 = [0 for i in range(len(t)+1)]

    for i in range(len(s)-1):
        # cummulative values of cells north, west, and northwest of the current cell
        left = i+1
        upleft = i
        up = i+d0[0]
        if print_rows:
            row = str(left) + ", "
        for j in range(len(t)):
            left += d1[j]
            up += d0[j+1]
            upleft += d0[j]
            cost = 0 if (s[i] == t[j]) else 1
            d1[j + 1] = min(left + 1, up + 1, upleft + cost) - left
            if print_rows:
                row += str(left+d1[j+1]) + ", "

        if print_rows:
            print row

        for c in range(len(d0)):
            d0[c] = d1[c]

    return left+d1[j+1]

with open(sys.argv[1]) as f:
    lines = f.readlines()

perfect = lines[0]
string1 = lines[1]
string2 = lines[2]
distance = LevenshteinDistance(string1,string2)
print "edit distance: " + str(distance)
print "score: " + str(int(perfect)*100/distance) + "%"

exemple d'entrée:

2
101100
011010

exemple de sortie détaillée:

0, 1, 2, 3, 4, 5, 6,
1, 1, 1, 2, 3, 4, 5,
2, 1, 2, 2, 2, 3, 4,
3, 2, 1, 2, 3, 2, 3,
4, 3, 2, 1, 2, 3, 3,
5, 4, 3, 2, 1, 2, 3,
6, 5, 4, 3, 2, 2, 2,
edit distance: 2
score: 100%